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

Question

I'm working on an Android app, simple tic-tac-toe side project. I'm using the minimax algorithm and I need to clone the board every time it tries to calculate a move.

The problem I'm facing is that every time my object is cloned and I manipulate the properties of the clone it also changes the properties of the original object, in this case the board for the game.

I don't understand why though as it works well in my unit tests but not when I integrate and play the game.

Computer class using AI(Minimax) class to calculate best spot:

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

}

Board class with clone method:

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

Failing integration test:

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

Possibly related to https://stackoverflow.com/questions/869033/how-do-i-copy-an-object-in-java — Codor, Apr 30 '18 at 14:12
Have you taken a look at making a deepcopy? Not sure if clone just creates a shadow copy with pointers to the original, but creating a deepcopy shouldn't. See: https://stackoverflow.com/questions/64036/how-do-you-make-a-deep-copy-of-an-object-in-java — MartW, Apr 30 '18 at 14:19
Do not use `Cloneable` and `clone()` [since it is broken by desing](https://www.artima.com/intv/bloch13.html). Write a proper [copy constructor](https://stackoverflow.com/questions/29362169/why-do-we-need-copy-constructor-and-when-should-we-use-copy-constructor-in-java) instead. — Turing85, Apr 30 '18 at 14:20

score 1 · Answer 1 · answered Apr 30 '18 at 14:23

1

According to the clone() JavaDoc your clone method must manually copy

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

This seems to apply to grid and winCombinations

answered Apr 30 '18 at 14:23

Jan Larsen

831
6
13

1

[According to Josh Bloch, you should not use `Cloneable` at all.](https://www.artima.com/intv/bloch13.html) – Turing85 Apr 30 '18 at 14:24
I agree, but this seems to be the solution to the posed problem. – Jan Larsen Apr 30 '18 at 14:25

score 1 · Accepted Answer · answered Apr 30 '18 at 14:46

It seems that your clone method fails. It doesn't do the actual cloning. It will raise an exception, which you should see as an stack trace on your console.

The clone method itself is not recommended anymore. Instead you should create an constructor that will have the source object as a parameter. In this constructor you should make a deep copy of source object. Here is an example how to do this in your case:

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

Remember that you are responsible yourself to make copy of each object. If you just copy the reference to object, both instances will point to same object and the data will get mixed like you mentioned.

Here is a simple example using the clone constructor:

        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
    }

I hope this will help you to go forward with your project. Happy coding!

Added the constructor to the board class and replaced the clone() method in computer class with the new copy constructor. App is now working as expected and I can play the game. I'm still using the clone() method in AI class, it seems to work well. I don't know if I should go ahead and refactor using the copy constructor. Thank you! — Huasmc, Apr 30 '18 at 15:04

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

2 Answers2