Question

I'm implementing the MiniMax algorithm for AI in a Reversi game, and I'm trying to add Alpha-Beta prunning method. If I get it correctly, the AI should choose exactly the same moves like in standard MiniMax, just in a reduced time, thanks to cutting the branches off. However, the AI plays in a very stupid way, and I tried to examine all the branches, can't find the reason why, though. The implementation without the alpha-beta works fine, for the record. Here's the function:

public Field alphaBeta (GameBoard gb, int depth, boolean player, int alpha, int beta)
{
    /** maximum depth of search reached, we stop */
    if(depth >= max_depth) return null;

    //player = (depth+1)%2 + 1;

    /** getting a list of moves to chose from */
    ArrayList <Field> moves = findAllPossibleMoves(gb, player); 

    Field best_move = null;

    /** iterating over all possible moves, to find the best one */      
    for (int i=moves.size();--i>=0;)
    {
        /** board to simulate moves */
        GameBoard temp_board = new GameBoard(gb);
        /** getting the current move */
        Field move = moves.get(i);      
        /** simulating the move for the current node */
        game.move(move, temp_board, player);
        //Log.i("board", "Depth:"+depth+" Player:"+player+" Move:"+i+" Rating:"+evaluate(temp_board));
        Log.i("board", ""+moves.get(i).getX()+","+moves.get(i).getY());         
        temp_board.printBoard();
        Field best_deep_move = alphaBeta (gb, depth + 1, !player, alpha, beta);

        if(best_deep_move != null)
        {
            move.setRating(best_deep_move.getRating());
        }       

        /** if the maximum depth is reached, we have a null, so we evaluate */
        else 
        {
            move.setRating(evaluate (temp_board, game.getActive_player()));
        }
  if (depth%2==0) // max
        {
            alpha = Math.max(alpha, move.getRating());
        }
        else
        {
            beta = Math.min(beta, move.getRating()); 
        }   


        /** if we are not the deepest possible, we get the rating from the lower node */

        if(best_move == null) 
        {
            best_move = move;           
        }           
        else
        {   
            Log.i("update", "Current move rating:"+move.getRating());
            Log.i("update", "New move rating:"+best_move.getRating());
            if (depth%2==0)
            {
                Log.i("update", "MAX player");
                /** for us, we look for the maximum */
                if (best_move.getRating() < move.getRating()) 
                {
                    best_move = move;   
                    best_move.alpha = alpha;
                }
                if( beta <= alpha)
                {
                    break;
                }

            }
            else
            {
                Log.i("update", "MIN player");
                /** for the opponent, we look for the minimum */
                if (best_move.getRating() > move.getRating()) 
                {
                    best_move = move;   
                    best_move.beta = beta;
                }
                if( beta <= alpha)
                {
                    break;
                }
            }
            Log.i("update", "Updated move rating"+best_move.getRating());
        }
    }


    return best_move;
}

The entire code is pretty vast, so I won't paste it all here. Just ask about some functions/classes you think you should look at, and I paste them right away. I'd appreciate any hints on that.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top