MiniMax reversi implementation

Question

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?

Answer 1

If changing a copy of an object affects the original. Then it is a "shallow copy". That means that somewhere in data structure objects are shared. You want a "deep copy".

Show us the code for new GameBoard(gb)

Some optinos: you can implement clone for your Gameboard and all of the objects it contains (and that they contain). Or, implement an undo() function in your game board. As long as you undo every move in your gameboard you can perform moves on it. That would save memory and object creation overhead when doing test moves during evaluation..