예상치 않게 동작하는 Minimax 알고리즘

Question

Tic Tac Toe의 Minimax 알고리즘을 구현하려고하는데 올바르게 실행되지 않는 것 같습니다. 나는 여러 번 다시 써 보았지만 올바른 결과를 얻지는 못했다. 여기

은 알 수있는 바와 같이

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----" 

그리고 그것을 실행하려고하고있는 game-를 구현 MinimaxGame.java, 코드입니다 내가 얻는 결과물은 다음과 같습니다.

"OOOOXOOOO" 

Ins 가장 최적의 움직임으로 반응하는 데있어,이 이상한 방식으로 행동하고 모든 빈 위치에 'O'를 넣습니다. 코드 디버깅을 시도했지만 코드에 어떤 문제가 있는지 알지 못합니다. 나는 문제가 어디에서 발생하는지 간단히 알 수 없다.

누군가 나를 도울 수 있습니까? 미리 감사드립니다. 여기

편집 -

내가 아니라 클론() 메소드를 구현하는 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

게시자의 게시판을 복제해야한다고 생각합니다. 귀하의 경우는

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

당신이

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

로 변경하고 보드 클래스에서 복제 구현의

예를 클론() 메소드를 구현해야 가능한 모든 위치에서 '0'으로 설정합니다

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

}