алгоритм miniMax в Java

Question

В настоящее время меня не устраивает программируемый ИИ. Предполагается, что ИИ набирает лучший результат за каждый ход на доске 3x3 (TicTacToe).

Возможные оценки: -1 (Проигрыш), 0 (T ie) и 1 (Победа).

Сначала вызывается метод makeTurn(), который затем вызывает метод, содержащий алгоритм miniMax.

public void makeTurn(Button[][] currentBoard) {                                                 // Calculating best move using miniMax algorithm
        AIcheck = new Check(currentBoard);
        int bestScore = Integer.MIN_VALUE;
        int[] bestMove = new int[2];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (currentBoard[i][j].getText().equals("")) {
                    currentBoard[i][j].setText("O");
                    int score = calcScore(currentBoard, 0, false);
                    System.out.println(score);
                    currentBoard[i][j].setText("");
                    if (score > bestScore) {
                        bestScore = score;
                        bestMove = new int[]{i, j};

                    }
                }
            }
        }
        Board.getInstance().getField(bestMove[0], bestMove[1]).performClick();
    }

private int calcScore(Button[][] currentBoard, int depth, boolean isMax) {                      // MiniMax Algorithm, calculating score for each branch via recursive execution
        int score;
        if (AIcheck.checkWin()) {
            return (Util.getInstance().getTurnCounter() % 2) == 0 ? 1 : -1;
        } else if (AIcheck.checkTie()) {
            return 0;
        }
        int bestScore = isMax ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (currentBoard[i][j].getText().equals("")) {
                    if (isMax) {
                        currentBoard[i][j].setText("O");
                    } else {
                        currentBoard[i][j].setText("X");
                    }
                    score = calcScore(currentBoard, depth + 1, !isMax);
                    currentBoard[i][j].setText("");
                    bestScore = isMax ? Math.max(bestScore, score) : Math.min(bestScore, score);
                }
            }
        }
        return bestScore;
    }

Я использую isMax, чтобы определить, пришла ли очередь максимайзера или нет, также используя turnCounter % 2, чтобы определить, какой сейчас ход игрока, так как они ходят.

И все же ИИ не мешает моей победе, больше похоже, что он просто переходит от одного поля к другому , вместо выбора оптимального поля. Как мне правильно реализовать алгоритм miniMax? Большое спасибо!

Пример:

[] | [] | []

[] | [] | []

[X] | [] | []

[O] | [] | []

[] | [] | []

[X] | [] | []

[O] | [] | []

[] | [] | []

[X] | [] | [X]

[O] | [O] | []

[] | [] | []

[X] | [] | [X]

[O] | [O] | [X]

[] | [] | []

[X] | [] | [X]

[O] | [O] | [X]

[O] | [] | []

[X] | [] | [X]

[O] | [O] | [X]

[O] | [X] | [] Я выигрываю, также это показывает, что ИИ, похоже, просто занимает следующее место (слева направо справа)

[X] | [] | [X]

Answer 1

Думаю, проблема в том, как определить, кто выиграл в calcScore. Вы используете Util.getInstance().getTurnCounter(), но, похоже, вы не обновляете счетчик в рекурсивных вызовах. Вместо этого вы можете просто использовать depth % 2 или isMax для этого:

if (AIcheck.checkWin()) {
    return isMax ? -1 : 1;
}

Answer 2

Возникла проблема с вашим заданием bestScore . Для каждого пустого поля вы делаете следующее:

int bestScore = isMax ? Integer.MIN_VALUE : Integer.MAX_VALUE;

Если вы рассчитываете его таким образом, вы всегда будете получать одни и те же оценки, что может быть причиной выбора только следующего пустого поля. В минимаксном алгоритме вам нужен способ присвоения разных значений очков для каждого хода, чтобы вы могли найти лучший ход путем сравнения. В шахматной игре или чем-то подобном эти баллы обычно выставляются с помощью эвристики. Поскольку ваша игра намного проще, это должно быть проще. Простым решением может быть присвоение разных очков каждому состоянию доски, и вы можете просто выбрать ходы, которые приводят к этому желаемому состоянию. Вы можете легко это сделать, поскольку количество этих состояний в вашей игре очень ограничено.

Answer 3

Думаю, проблема в этой строке в calcScore()

if (currentBoard[i][j].getText().equals("")) {

Вы подсчитываете счет только в том случае, если доска пуста, но вы всегда устанавливаете его на «0» перед вызовом функции, поэтому блок кода для этого if никогда не будет выполнен.

makeTurn() похоже, но я думаю, вы очищаете доски между ходами? Если нет, вам также необходимо обновить это.

Изменить: в основной функции:

                    currentBoard[i][j].setText("O");
                    int score = calcScore(currentBoard, 0, false);

в calcScore:

// this will always evaluate to false
if (currentBoard[i][j].getText().equals("")) {