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

}