Минимакс неправильно оценивает ветки в крестиках-ноликах

Я пытаюсь создать идеальную игру в крестики-нолики на C. Я использую 2D-массив для отслеживания доски.

Я сузил проблему до того, как моя функция minimax оценивает каждый потенциальный ход, но у меня возникли проблемы с ее отладкой, потому что ошибка обычно возникает вокруг второго хода, и я не могу отслеживать все потенциальные состояния игры с этого момента.

Компьютер идет первым, и это всегда «X». minimax вызывается из функции computerMove, которая пробует каждый доступный ход, а затем минимизирует их. Он принимает значение, возвращенное для потенциального состояния игры из minimax, в качестве временного счета и сравнивает его с текущим максимальным результатом. Я уверен, что часть программы работает. Проблема заключается в самой функции minimax

Вот важные части моего кода:

int minimax(char board[][3], char maxPlayer) // +10 -> X wins 
{                                            // -10 -> O wins
    char minPlayer;                          //   0 -> draw
    int scores[3][3];
    if (maxPlayer == 'X') minPlayer = 'O';
    else minPlayer = 'X';
    int topScore = 0;

    // initializing scores to ensure a move is selected
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            scores[i][j] = -11;
        }
    }

    // check for terminal state
    if (isWinning(board,'X') || isWinning(board,'O') || 
    !moveAvailable(board)) {
        if (isWinning(board,'X')) return 10;
        else if (isWinning(board,'O')) return -10;
        else return 0;
    }

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[i][j] == 'U') { 
                board[i][j] = maxPlayer;                // try the move
                scores[i][j] = minimax(board,minPlayer);// minimax it
                board[i][j] = 'U';                      // undo the move
            }
        }
    }  

    // if calling minimax for computer, maximize the score
    if (maxPlayer == 'X') {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (scores[i][j] > topScore && scores[i][j] != -11) 
                    topScore = scores[i][j];
            }
        }
    }

    // if calling minimax for human, minimize the score
    else if (maxPlayer == 'O') {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (scores[i][j] < topScore && scores[i][j] != -11) 
                    topScore = scores[i][j];
            }
        }
    }
    return topScore;
}

person Colin Harrison    schedule 09.07.2017    source источник
comment
Лучше всего мне подходит эта строка: if (board[i][j] == 'U') {. Это условие никогда не бывает истинным, я думаю   -  person Vidor Vistrom    schedule 09.07.2017
comment
эта строка: scores[row][column] = -11; // set all to 'O' wins неверна. Согласно другому комментарию к оператору подписи функции, выигрыш «O» равен -10, а не -11.   -  person user3629249    schedule 10.07.2017
comment
Каждая рекурсия начинается с новой, неинициализированной версии scores[][] Вероятно, это неправильно.   -  person user3629249    schedule 10.07.2017
comment
Значения scores всегда равны 0, -11 и +10. Я считаю, что баллы должны суммироваться. т.е. инициализируйте каждый новый scores всеми 0, тогда каждый рекурсивный вызов minimax() должен приводить к увеличению верхнего уровня scores (возможно, на -10) от результата рекурсивных вызовов minimax()   -  person user3629249    schedule 10.07.2017
comment
@VidorVistrom, я думаю, доска изначально содержит всех нас, поэтому он хочет эту проверку.   -  person gdelab    schedule 10.07.2017
comment
@user3629249 user3629249 он использует scores[row][column] = -11; как логическое значение slotAlreadyUsed, а не как оценку, поэтому ему в основном нужно значение, которое никогда не используется для истинной оценки. Он хочет новый счет[][] на каждом шаге, так как счет каждого хода зависит от состояния доски. Оценки не должны увеличиваться по глубине, вам нужны только максимальные или минимальные из них в зависимости от слоя, на котором вы находитесь.   -  person gdelab    schedule 10.07.2017


Ответы (1)


Проблема с инициализацией topScore:

  • Вы должны инициализировать topScore значением 11 или -11, в зависимости от того, кто играет, а не 0, иначе оба игрока будут считать, что всегда могут достичь как минимум ничьей (что не так), начиная с глубины 2.

  • с точки зрения хорошей практики (имхо), я думаю, что последние два цикла должны быть сгруппированы в один, с условием if (maxPlayer == 'X') внутри него, непосредственно перед обновлением topScore. Кроме того, вы должны пропустить все позиции, где board[i][j]!='U', это легче понять, чем искать -11 в баллах (что, впрочем, хорошо).

person gdelab    schedule 10.07.2017