I'm trying to implement a MiniMax algorithm in a Reversi/Othello game, and I'm pretty stuck, since the function I wrote looks perfectly normal, and yet I get some strange moves, and a crash after a few. Here's the function finding an optimum move:
public Field findBestMove(GameBoard gb, int depth, int player)
{
if(depth >= max_depth) return null;
ArrayList <Field> moves = findAllPossibleMoves(gb, player);
Field best_move = null;
/** iterating over all possible moves, to find the best one */
for (int i=0; i<moves.size(); i++)
{
/* board to simulate moves */
GameBoard temp_board = new GameBoard(gb);
Field move = moves.get(i);
game.move(move, temp_board, player);
int opposite_player = player == GameBoard.WHITE ? GameBoard.BLACK : GameBoard.WHITE;
Field best_deep_move = findBestMove (temp_board, depth + 1, opposite_player);
/** if the maximum depth is reached, we have a null, so we evaluate */
if (best_deep_move == null)
{
/** we rate it according to the evaluation table */
move.setRating(evaluate (temp_board, player));
}
else
{
move.setRating(best_deep_move.getRating());
}
if(best_move == null)
{
best_move = move;
}
else
{
if (depth%2==0)
{
/** for us, we look for the maximum */
if (best_move.getRating() < move.getRating()) best_move = move;
}
else
{
/** for the opponent, we look for the minimum */
if (best_move.getRating() > move.getRating()) best_move = move;
}
}
}
return best_move;
}
After each move, the active player is changed. In the onTouchEvent method of the GameView, first the player makes his move, and then the player is changed to the WHITE one, which is the AI, and it makes a move. It should search for the best move in his tree, and then perform ONE move, instead he does several weird moves. I've no idea why, for each branch I create a new copy of a board, so I have no idea why the main game board gets modified.
Any ideas?