Java 克隆方法未按预期工作（minimax 算法案例）

Question

我正在开发一个 Android 应用程序，一个简单的井字游戏副项目。我正在使用 minimax 算法，每次尝试计算移动时我都需要克隆棋盘。

我面临的问题是，每次我的对象被克隆并且我操纵克隆的属性时，它也会更改原始对象的属性，在本例中是游戏的棋盘。

我不明白为什么它在我的单元测试中运行良好，但在我集成和玩游戏时却不行。

计算机 class 使用 AI(Minimax) class 计算最佳点：

public class ComputerPlayer extends Player {

private String token;
AI AI;

public ComputerPlayer() {
    super();
    AI AI = null;
}

public String getToken() {
    return token;
}

public void setToken(String token) {
    this.token = token;
    this.initializeAI();
}

public void autoToken(String token) {
    if(token.equals("X")) {
        this.setToken("O");
    } else {
        this.setToken("X");
    }
}

public void play(Board board) throws CloneNotSupportedException {
    Board clone = (Board) board.clone();
    int spot = AI.getBestSpot(clone);
    play(board, spot);
}

public void play(Board board, int spot) {
    board.setSpot(spot, token);
}

public void initializeAI() {
    if( token != null ) {
        this.AI = new AI(token);
    }
}

}

采用克隆方法的板 class：

    public Board() {
    this.grid = new String[]{"0", "1", "2", "3", "4", "5", "6", "7", "8"};
    this.winCombinations = new int[][]{{0,1,2}, {3,4,5}, {6,7,8}, {0,3,6}, {1,4,7,}, {2,5,8}, {0,4,8}, {2,4,6}};
}

public String[] getGrid() {
    return grid;
}

public int[][] getWinCombinations() {
    return winCombinations;
}

public String[] getAvailableSpots() {
    ArrayList<String> resultList = new ArrayList<String>();
    for(int i = 0; i < grid.length; i++) {
        if(!grid[i].equals("X") && !grid[i].equals("O")) {
            resultList.add(grid[i]);
        }
    }
    return resultList.toArray(new String[resultList.size()]);
}

public void reset() {
    grid = new String[]{"0", "1", "2", "3", "4", "5", "6", "7", "8"};
}

public void setSpot(int i, String token) {
    grid[i] = token;
}

public void setGrid(String[] grid) {
    this.grid = grid;
}

@Override
public Object clone() {
    Board boardClone = null;
    try {
        boardClone = (Board) super.clone();
    } catch (CloneNotSupportedException e) {
        e.printStackTrace();
    }
    return boardClone;
}
}

AI class:

public class AI {

private String token;
GameState gameState;
private String opponentToken;

public AI(String token) {
    this.token = token;
    this.gameState = new GameState();
    this.opponentToken = null;

    setOpponentToken();
}


public String getToken() {
    return token;
}

public String getOpponentToken() {
    return opponentToken;
}

public void setOpponentToken() {
    if(this.token == "X") {
        opponentToken = "O";
    } else {
        opponentToken = "X";
    }
}

public int getBestSpot(Board board) throws CloneNotSupportedException {
    String[] grid = board.getGrid();
    if( !grid[4].equals("X") && !grid[4].equals("O")) {
        return 4;
    } else {
        return Integer.parseInt((String) this.maximizedSpot(board)[0]);
    }
  }

public Object[] maximizedSpot(Board board) throws CloneNotSupportedException {
    Board boardClone = (Board) board.clone();

    int bestScore = 0;
    String bestSpot = null;
    int score;

    String[] availableSpots = boardClone.getAvailableSpots();

    for(String availableSpot: availableSpots) {
        int spot = Integer.parseInt(availableSpot);
        boardClone.setSpot(spot, this.token);

        if( gameState.finished(boardClone) ) {
            score = this.getScore(boardClone);
        } else {
            Object[] minimizedSpot = this.minimizedSpot(boardClone);
            score = (int) minimizedSpot[1];
        }
        boardClone = (Board) board.clone();

        if( bestScore == 0 || score > bestScore ) {
            bestScore = score;
            bestSpot = availableSpot;
        }
    }
    return new Object[]{bestSpot, bestScore};
  }

public Object[] minimizedSpot(Board board) throws CloneNotSupportedException {
    Board boardClone = (Board) board.clone();

    int bestScore = 0;
    String bestSpot = null;
    int score;

    String[] availableSpots = boardClone.getAvailableSpots();

    for(String availableSpot: availableSpots) {
        int spot = Integer.parseInt(availableSpot);
        boardClone.setSpot(spot, this.opponentToken);

        if ( gameState.finished(boardClone) ) {
            score = this.getScore(boardClone);
        } else {
            Object[] maximizedSpot = this.maximizedSpot(boardClone);
            score = (int) maximizedSpot[1];
        }
        boardClone = (Board) board.clone();

        if (bestScore == 0 || score < bestScore) {
            bestScore = score;
            bestSpot = availableSpot;
        }

    }
    return new Object[]{bestSpot, bestScore};
 }

public int getScore(Board board) {
    if( gameState.finished(board) ) {
        String winnerToken = (gameState.getWinnerToken());
        if( winnerToken == token ) {
            return 1;
        } else if ( winnerToken == opponentToken ) {
            return -1;
        }
    }
    return 0;
}
}

集成测试失败：

@Test
public void testCanUseAI() {
    String[] newGrid = new String[]{"0", "1", "2",
                                    "3", "X", "5",
                                    "6", "7", "8"};
    board.setGrid(newGrid);
    try {
        computerPlayer.play(board);
    } catch (CloneNotSupportedException e) {
        e.printStackTrace();
    }
    String[] result = new String[]{"0", "1", "O",
                                   "3", "X", "5",
                                   "6", "7", "8"};
    System.out.print(board.getGrid()[1]);
    System.out.print(result[1]);
    assertTrue( Arrays.deepEquals(board.getGrid(), result) );
}
}

Answer 1

根据 clone() JavaDoc，您的克隆方法必须手动复制

any mutable objects that comprise the internal "deep structure" of the object being cloned and replacing the references to these objects with references to the copies

这似乎适用于 grid 和 winCombinations

Answer 2

看来你的克隆方法失败了。它不进行实际的克隆。它会引发异常，您应该在控制台上看到它作为堆栈跟踪。

不再推荐克隆方法本身。相反，您应该创建一个将源对象作为参数的构造函数。在此构造函数中，您应该对源对象进行深度复制。以下是如何在您的情况下执行此操作的示例：

public class Board {

    private String[] grid;
    private int[][] winCombinations;

    public Board() {
            this.grid = new String[] { "0", "1", "2", "3", "4", "5", "6", "7", "8" };
            this.winCombinations = new int[][] { { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 0, 3, 6 }, { 1, 4, 7, },
                            { 2, 5, 8 }, { 0, 4, 8 }, { 2, 4, 6 } };
    }

    /**
     * Cloning constructor to make a deep copy of the original source
     * @param sourceBoard Object to be deep copied to a new instance
     */
    public Board(Board sourceBoard) {
            this();
            System.arraycopy(sourceBoard.grid, 0, this.grid, 0, sourceBoard.grid.length);

            for (int i = 0; i < winCombinations.length; i++) {
                    int[] line = winCombinations[i];
                    System.arraycopy(sourceBoard.winCombinations[i], 0, line, 0, line.length);
            }
    }

请记住，您有责任自行复制每个对象。如果您只是复制对对象的引用，两个实例将指向同一个对象，并且数据将像您提到的那样混合。

这是一个使用克隆构造函数的简单示例：

        public static void main(String[] args) {

            Board board = new Board();
            String[] newGrid = new String[] { "0", "1", "2", "3", "X", "5", "6", "7", "8" };
            board.setGrid(newGrid);

            // Instead of using clone methods, create new instance from source object
            Board clone = new Board(board);

            System.out.println(clone.getGrid() == board.getGrid()); // false => deep copy done
    }

我希望这能帮助您推进您的项目。编码愉快！

Java 克隆方法未按预期工作（minimax 算法案例）

Java clone method not working as expected (minimax algorithm case)

java

deep-copy

tic-tac-toe

minimax

android-studio