Minimax算法意外行为

Question

我正在尝试为Tic Tac Toe实现Minimax算法，并且似乎无法使其正确运行。我尝试了多次重写，但没有给出正确的输出。

这里是代码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()); 
    } 
} 

很明显，我想这个最初与字符串

"----X----" 

，并执行它这我得到的输出是这个 -

"OOOOXOOOO" 

宏他们以最优化的方式做出回应，以这种超级奇怪的方式表现出来，并在每个空位置放上'O'。 我试过调试代码，但我仍然不知道代码出了什么问题。我根本弄不清楚问题出在哪里。

有人可以帮我吗？提前致谢。

编辑 -

这里是MinimaxBoard.java，其中我已经实现了clone（）方法以及代码。但是，输出是一样的。有人可以告诉我为什么吗？

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'); 

并实现clone（）方法在董事会类的clone实施

例子：

@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; 
    } 
} 

}