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