Minimax Algorithm ведет себя неожиданно

Question

Я пытаюсь реализовать алгоритм Minimax для Tic Tac Toe и просто не могу заставить его работать правильно. Я попытался переписать его несколько раз, но он не дает правильного вывода.

Вот код для MinimaxGame.java, который реализует игру-

public class MinimaxGame { 
    public MinimaxResult play(MinimaxBoard board) { 
     ArrayList<Position> possibleMoves = board.getAllPossibleMoves(); 
     MinimaxBoard bestChild = null; 
     int bestScore= Integer.MIN_VALUE; 

     for (Position position : possibleMoves) { 
      MinimaxBoard child = new MinimaxBoard((MinimaxBoard)board.clone(), position, 'O'); 
      int moveScore = max(child); 

      if (moveScore > bestScore) { 
       bestChild = child; 
       bestScore = moveScore; 
      } 
     } 

     MinimaxResult result = new MinimaxResult(bestChild, bestScore); 
     return result; 
    } 

    private int max(MinimaxBoard child) { 
     ArrayList<Position> possibleMoves = child.getAllPossibleMoves(); 
     if (possibleMoves.isEmpty()) { 
      int score = evaluateScore(child); 
      return score; 
     } 

     int bestScore = Integer.MIN_VALUE; 
     for (Position position : possibleMoves) { 
      MinimaxBoard currentChild = new MinimaxBoard((MinimaxBoard)child.clone(), position, 'X'); 
      int moveScore = min(currentChild); 

      if (moveScore > bestScore) { 
       bestScore = moveScore; 
      } 
     } 

     return bestScore; 
    } 

    private int min(MinimaxBoard child) { 
     ArrayList<Position> possibleMoves = child.getAllPossibleMoves(); 
     if (possibleMoves.isEmpty()) { 
      int score = evaluateScore(child); 
      return score; 
     } 

     int bestScore = Integer.MAX_VALUE; 
     for (Position position : possibleMoves) { 
      MinimaxBoard currentChild = new MinimaxBoard((MinimaxBoard)child.clone(), position, 'O'); 
      int moveScore = max(currentChild); 

      if (moveScore < bestScore) { 
       bestScore = moveScore; 
      } 
     } 

     return bestScore; 
    } 

    private boolean hasWon(MinimaxBoard board, char player) { 
     boolean status = false; 
     char [][] boardArray = board.boardArray; 

     // Check rows 
     for (int i = 0; i < 3; i++) { 
      status |= (boardArray[i][0] == player) && (boardArray[i][1] == player) && (boardArray[i][2] == player); 
      if (status) { 
       return true; 
      } 
     } 

     // Check columns 
     for (int i = 0; i < 3; i++) { 
      status |= (boardArray[0][i] == player) && (boardArray[1][i] == player) && (boardArray[2][i] == player); 
      if (status) { 
       return true; 
      } 
     } 

     // Check left diagonal 
     status |= (boardArray[0][0] == player) && (boardArray[1][1] == player) && (boardArray[2][2] == player); 
     if (status) { 
      return true; 
     } 

     // Check right diagonal 
     status |= (boardArray[0][2] == player) && (boardArray[1][1] == player) && (boardArray[2][0] == player); 
     if (status) { 
      return true; 
     } 

     return false; 
    } 


    // The function simply returns a score of +1 if computer wins, -1 if the user wins, 
    // and 0 in case of a draw. 
    private int evaluateScore(MinimaxBoard board) { 
     if (hasWon(board, 'X')) { 
      return -1; 
     } 
     else if (hasWon(board, 'O')) { 
      return 1; 
     } 

     return 0; 
    } 

    // Main method included for debugging purposes 
    public static void main(String args[]) { 
     Board sampleBoard = new Board(); 
     sampleBoard.setState("----X----"); 
     MinimaxBoard minimaxBoard = new MinimaxBoard(sampleBoard); 

     MinimaxGame game = new MinimaxGame(); 
     MinimaxResult result = game.play(minimaxBoard); 

     Board updatedBoard = result.getUpdatedBoard().getBoard(); 
     System.out.println(updatedBoard.getState()); 
    } 
} 

Как видно, я пытаюсь выполнить его с этим начальным string-

"----X----" 

И выход, который я получаю, это-

"OOOOXOOOO" 

Ins чтобы реагировать самым оптимальным ходом, он ведет себя в этом супер странном виде и помещает «О» в каждое пустое место. Я пробовал отлаживать код, но я до сих пор не знаю, что происходит с кодом. Я просто не могу понять, где возникает проблема.

Может ли кто-нибудь помочь мне? Заранее спасибо.

Редактирование-

Вот код для MinimaxBoard.java, в котором я реализован метод клон(), а также. Но все же, выход такой же. Может ли кто-нибудь сказать мне, почему?

public class MinimaxBoard implements Cloneable { 
public char[][] boardArray; 

public MinimaxBoard(Board board) { 
    boardArray = convertBoardTo2D(board.getState()); 
} 

public MinimaxBoard(MinimaxBoard board, Position position, char player) { 
    this.boardArray = board.boardArray; 
    boardArray[position.row][position.coloumn] = player; 
} 

public Board getBoard() { 
    Board board = new Board(); 

    StringBuilder builder = new StringBuilder(); 
    for (int i = 0; i < boardArray.length; i++) { 
     builder.append(String.valueOf(boardArray[i])); 
    } 

    board.setState(builder.toString()); 
    return board; 
} 

public char[][] convertBoardTo2D(String boardString) { 
    char[][] boardArray = new char[3][3]; 
    char[] chars = boardString.toCharArray(); 
    if (chars.length == 9) { 
     for (int i = 0; i < chars.length; i++) { 
     boardArray[i/3][i%3] = chars[i]; 
     } 
    } 

    return boardArray; 
} 

public ArrayList<Position> getAllPossibleMoves() { 
    ArrayList<Position> allMoves = new ArrayList<Position>(); 

    for(int i = 0; i < 3; i++) { 
     for(int j = 0; j < 3; j++) { 
      if(boardArray[i][j] == '-') { 
       allMoves.add(new Position(i, j)); 
      } 
     } 
    } 

    return allMoves; 
} 

@Override 
public Object clone() { 
    try { 
     return (MinimaxBoard)super.clone(); 
    } 
    catch(CloneNotSupportedException e) { 
     return null; 
    } 
} 

} 

Answer 1

Я думаю, вы должны клонировать свою доску. В вашем прецедентного вы установите «0» на все возможные позиции

MinimaxBoard child = new MinimaxBoard(board, position, 'O'); 

вы должны измениться, чтобы

MinimaxBoard child = new MinimaxBoard(board.clone(), position, 'O'); 

и осуществлять клон() метод в классе Board

Пример реализации клона:

@Override 
public Object clone() { 
    try { 
     MinimaxBoard cloned = (MinimaxBoard)super.clone(); 
     cloned.boardArray = (char[][])boardArray.clone(); 
     for(int row=0; row< cloned.boardArray.length;row++) 
      cloned.boardArray[row] = (char[])boardArray[row].clone(); 
     return cloned; 
    } 
    catch(CloneNotSupportedException e) { 
     return null; 
    } 
} 

}