I've been working on writing a minimax algorithm for my tictactoe game, but it doesn't seem to be choosing the correct move. It is possible to win against the computer, so I must have something mixed up here. I think the algorithm itself seems fine, so I'm pretty sure the problem is how I'm getting the best move. Does anyone have any suggestions?
minimax method
private int minimax(Board board, boolean maximizingPlayer, char symbol){
//System.out.println(symbol);
Board copyBoard = new Board(board.getCells());
char winner = copyBoard.checkWin();
if(winner!='-' || copyBoard.checkDraw()){
return score(winner);
}
if(maximizingPlayer){
int bestValue = Integer.MIN_VALUE;
for(Board b : simulatePossibleMoves(copyBoard,mySymbol)){
int value = minimax(b,false,switchSymbol(mySymbol));
if(bestValue < value){
bestValue = value;
bestMove = b.getLastMove();
}
}
return bestValue;
}
else{
int bestValue = Integer.MAX_VALUE;
for(Board b: simulatePossibleMoves(copyBoard, switchSymbol(mySymbol))){
int value = minimax(b,true,mySymbol);
if(bestValue > value){
bestValue = value;
bestMove = b.getLastMove();
}
}
return bestValue;
}
}
score method
private int score(char winner){
if(winner == mySymbol)
return 10;
else if(winner == switchSymbol(mySymbol))
return -10;
return 0;
}
EDIT:
Example of a game(Human is X, AI is O)
O top left corner
x Center
O middle left
X Bottom left
O top middle
X Top right (Human win)
EDIT 2:
More code, not sure if the error could be in here or not, might as well include it.
private ArrayList<Integer> getPossibleMoves(Board board){
ArrayList<Integer> moves = new ArrayList<>();
for(int i = 0; i < board.getCells().length; i++)
if(!board.isCellTaken(i))
moves.add(i);
return moves;
}
private ArrayList<Board> simulatePossibleMoves(Board board, char symbol){
ArrayList<Board> possibleBoards = new ArrayList<>();
for(Integer move : getPossibleMoves(board)){
Board temp = new Board(board.getCells());
temp.setCell(move, symbol);
possibleBoards.add(temp);
}
return possibleBoards;
}
private char switchSymbol(char s){
if(s=='X')
return 'O';
return 'X';
}
It turns out I've been trying to use the algorithm incorrectly by choosing the bestvalue inside the minimax method itself. By creating another method that calls the minimax method, I was able to find the best move that way. The following code has worked for me.
public int getMiniMaxMove(Board board){
int score = -1;
int bestMove = -1;
for(int i : getPossibleMoves(board)){
Board copyBoard = new Board(board.getCells());
copyBoard.setCell(i, mySymbol);
int moveScore = minimax(copyBoard,false,mySymbol);
if(moveScore >= score){
score = moveScore;
bestMove = i;
}
}
return bestMove;
}
private int minimax(Board board, boolean maximizingPlayer, char symbol){
Board copyBoard = new Board(board.getCells());
char winner = copyBoard.checkWin();
if(winner!='-' || copyBoard.checkDraw()){
return score(winner);
}
if(maximizingPlayer){
int bestValue = Integer.MIN_VALUE;
for(Board b : simulatePossibleMoves(copyBoard,mySymbol)){
int value = minimax(b,false,switchSymbol(mySymbol));
if(bestValue < value){
bestValue = value;
}
}
return bestValue;
}
else{
int bestValue = Integer.MAX_VALUE;
for(Board b: simulatePossibleMoves(copyBoard, switchSymbol(mySymbol))){
int value = minimax(b,true,mySymbol);
if(bestValue > value){
bestValue = value;
}
}
return bestValue;
}
}