Что случилось с моим Tic Tac Toe AI?

Question

Я прочитал учебник о минимаксах и попытался сделать tac tac toe AI. Но код по какой-то причине не работает оптимально, чего я не могу найти. Ai может размещать куски, но это не умный ai. Я ожидал, что это будет непобедимым. Чем выше глубина, тем глубже становится ai. «Игра» - это мой другой класс, в котором находится настоящая игра.

private Game game; 
private Piece[][] board; 
private Piece ai = Piece.CIRCLE; 
private Piece player = Piece.CROSS; 

public AI(Game game) { 
    this.game = game; 
    this.board = game.getBoard(); 

} 

public int[] move() { 
    int[] result = minimax(1, ai); 

    return new int[] {result[1], result[2]}; 
} 

private int[] minimax(int depth, Piece piece) { 
    List<int[]> possibleMoves = generateMoves(); 

    int bestScore = (piece == ai) ? Integer.MIN_VALUE : Integer.MAX_VALUE; 
    int currentScore; 
    int bestRow = -1; 
    int bestCol = -1; 

    if (possibleMoves.isEmpty() || depth == 0) { 
     // Game over or depth reached 
     bestScore = evaluate(); 
    } 
    else { 
     for (int[] move : possibleMoves) { 
      // Try this move for the player 
      board[move[0]][move[1]] = player; 
      if (piece == ai) { // ai is maximizing player 
       currentScore = minimax(depth - 1, player)[0]; 

       if (currentScore > bestScore) { 
        bestScore = currentScore; 
        bestRow = move[0]; 
        bestCol = move[1]; 
       } 
      } 
      else { // player is minimizing player 
       currentScore = minimax(depth - 1, ai)[0]; 

       if (currentScore < bestScore) { 
        bestScore = currentScore; 
        bestRow = move[0]; 
        bestCol = move[1]; 
       } 
      } 

      // Undo move 
      board[move[0]][move[1]] = null; 
     } 
    } 

    return new int[] {bestScore, bestRow, bestCol}; 
} 

private List<int[]> generateMoves() { 
    List<int[]> possibleMoves = new ArrayList<int[]>(); 

    // If game over 
    if (game.getWinner() != null) { 
     return possibleMoves; // return empty list 
    } 

    // Add possible moves to list 
    for (int x = 0; x < 3; x++) { 
     for (int y = 0; y < 3; y++) { 
      if (game.getBoard()[x][y] == null) { 
       possibleMoves.add(new int[] {x, y}); 
      } 
     } 
    } 

    return possibleMoves; 
} 

private int evaluate() {   
    int score = 0; 
    // Evaluate 
    score += evaluateLine(0, 0, 0, 1, 0, 2); // row 0 
    score += evaluateLine(1, 0, 1, 1, 1, 2); // row 1 
    score += evaluateLine(2, 0, 2, 1, 2, 2); // row 2 
    score += evaluateLine(0, 0, 1, 0, 2, 0); // col 0 
    score += evaluateLine(0, 1, 1, 1, 2, 1); // col 0 
    score += evaluateLine(0, 2, 1, 2, 2, 2); // col 0 
    score += evaluateLine(0, 0, 1, 1, 2, 2); // diag 1 
    score += evaluateLine(0, 2, 1, 1, 2, 0); // diag 2 

    return score; 
} 

// Return +100, +10, +1 for 3-, 2-, 1-in-a-line for ai 
// Return -100, -10, -1 for 3-, 2-, 1-in a line for player 
// Else return 0 
private int evaluateLine(int row1, int col1, int row2, int col2, int row3, int col3) { 
    int score = 0; 

    // First cell 
    if (board[row1][col1] == ai) { 
     score = 1; 
    } 
    else if (board[row1][col1] == player) { 
     score = -1; 
    } 

    // Second cell 
    if (board[row2][col2] == ai) { 
     if (score == 1) { // board1 is ai 
      score = 10; 
     } 
     else if (score == -1) { // board1 is player 
      return 0; 
     } 
     else { // board1 is empty 
      score = 1; 
     } 
    } 
    else if (board[row2][col2] == player) { 
     if (score == -1) { // board1 is player 
      score = -10; 
     } 
     else if (score == 1) { // board1 is ai 
      return 0; 
     } 
     else { // board1 is empty 
      score = -1; 
     } 
    } 

    // Third cell 
    if (board[row3][col3] == ai) { 
     if (score > 0) { // board1 and/or board2 is ai 
      score *= 10; 
     } 
     else if (score < 0) { // board1 and/or board2 is player 
      return 0; 
     } 
     else { // board1 and/or board2 is empty 
      score = 1; 
     } 
    } 
    else if (board[row3][col3] == player) { 
     if (score < 0) { // board1 and/or board2 is player 
      score *= 10; 
     } 
     else if (score > 1) { // board1 and/or board2 is ai 
      return 0; 
     } 
     else { // board1 and/or board2 is empty 
      score = -1; 
     } 
    } 

    return score; 
} 

Answer 1

minimax возвращается движение в терминах пары строк/столбцов, а не оценка. Таким образом,

currentScore = minimax(depth - 1, player)[0]; 

не имеет смысла. Это, вероятно, вызывает любое движение к строке 3, чтобы выглядеть лучше, чем любой шаг в строке 1 или грести 2.

minmax потребности передать
назад счет в дополнении к лучшему ходу.

Answer 2

Несколько вещей, которые я заметил:

• Первая строка в цикле, проходящей через возможные ходы говорит board[move[0]][move[1]] = player;. Это должно быть piece вместо player, теперь ваш ИИ думает, что только части человеческого игрока когда-либо оказываются на доске.
• Минимакс должен быть очень легко способен искать полное игровое дерево менее чем за секунду. Поэтому я бы рекомендовал разрешить поиск настолько глубоко, насколько ему нравится, вместо ограничения глубины поиска 1. Это также устранило бы необходимость создания этой эвристической функции оценки; вы бы дали только большой балл за победу, 0 за галстук и очень отрицательный балл за проигрыш. Основная причина, по которой я рекомендую это, - это то, что я подозреваю, что может быть что-то не так с функцией оценки, хотя я не уверен, так как я не проверял ее подробно. Если вы действительно настаиваете на раннем завершении поиска и использовании эвристической функции оценки, вам нужно убедиться, что функция «симметрична». При этом я имею в виду, что оценка платы с точки зрения одного игрока должна всегда результат ровно-1 раз счет той же доски оценивался с точки зрения противника.