Othello Alpha-Beta Pruning playing badly python

Question

I am currently trying to make a good AI for Othello, and have done so using the Minimax algorithm. However, when I tried to make a deeper search using alpha-beta pruning, it seemed like the algorithm was playing terribly. I checked it with other sources like Wiki and Berkely.edu , and I think I have implemented it correctly, but I still can't find the problem.

def alphabeta(board, player, a, b, lev):
        h = heur(board, player)
        if lev == 0:
                return h, None
        poss = get_legal_moves(board, player)
        if len(poss) == 0:
                return h, None
        move = 0
        for x in poss:
                cpboard = board[:]
                cpboard[x] = player
                bracket(cpboard, player, x)
                a1, q = alphabeta(cpboard, opponent_color(player), a, b, lev-1)
                if player is me:
                        if a1 > a:
                                a, move = a1, x
                else:
                        if a1 < b:
                                b, move = a1, x
                if b <= a:
                        break
        if player is me:
                return a, move
        else:
                return b, move

before you start second guessing your code, are you sure your `heur` function is correct? — inspectorG4dget, Jan 11 '12 at 20:43

Fernando · Accepted Answer · 2012-03-02T17:22:35.993

Your alpha-beta code is probably wrong. Be aware of what happens when a player 'pass the turn' (i.e. has no available moves), i had a tricky bug in my code, due to this.

Did you call the recursion with the alpha and beta values switched? Mine works like this (Java code):

private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth)
{
    float bestResult = -Float.MAX_VALUE;
    OthelloMove garbage = new OthelloMove();

    int state = board.getState();
    int currentPlayer = board.getCurrentPlayer();

    if (state == OthelloBoard.STATE_DRAW)
        return 0.0f;
    if ((state == OthelloBoard.STATE_BLACK_WINS) && (currentPlayer == OthelloBoard.BLACK))                    
        return INFINITY;        
    if ((state == OthelloBoard.STATE_WHITE_WINS) && (currentPlayer == OthelloBoard.WHITE))
        return INFINITY;
    if ((state == OthelloBoard.STATE_BLACK_WINS) && (currentPlayer == OthelloBoard.WHITE))
        return -INFINITY;
    if ((state == OthelloBoard.STATE_WHITE_WINS) && (currentPlayer == OthelloBoard.BLACK))
        return -INFINITY;

    if (depth == maxDepth)
        return OthelloHeuristics.eval(currentPlayer, board);

    ArrayList<OthelloMove> moves = board.getAllMoves(currentPlayer);

    for (OthelloMove mv : moves)
    {            
        board.makeMove(mv);
        alpha = - minimax(board, garbage, -beta, -alpha, depth + 1);
        board.undoMove(mv);

        if (beta <= alpha)
            return alpha;
        if (alpha > bestResult)
        {                
            best.setFlipSquares(mv.getFlipSquares());
            best.setIdx(mv.getIdx());        
            best.setPlayer(mv.getPlayer());
            bestResult = alpha;
        }
    }

     return bestResult;
}

The call is like:

 OthelloMove bestFound = new OthelloMove();
 int maxDepth = 8;
 minimax(board, bestFound, -Float.MAX_VALUE, Float.MAX_VALUE, maxDepth);
//Wait for Thread to finish
 board.makeMove(bestFound);

Edit: In case a player has no available moves, getAllMoves() return a 'dummy move', that doesn't change the board at all, just pass the turn.

Hope it helps!

score 1 · Answer 2 · answered Jan 16 '12 at 08:05

1

Your alphabeta implementation looks sound to me. Since minimax and alphabeta produce the same results when implemented correctly, you should be able to use your old minimax code as a check against alphabeta, at least for modest search depths. If their results differ when searching the same game tree, then you know you've done something wrong.

But most likely, the poor play is the result of something in your "heur" evaluation function.

answered Jan 16 '12 at 08:05

Kyle Jones

5,492
1
21
30

I am sure that my heur function is good, because when I run a minimax search, it plays extremely well. – jcolen19 Jan 21 '12 at 22:08
1

Then the next step is to run your minimax and alphabeta code side-by-side against the same Othello positions, searching to the same depth and see where they differ. Start with a shallow depth and rerun at increased depth until there is a discrepancy. That should allow you to debug the problem. – Kyle Jones Jan 22 '12 at 01:03

Othello Alpha-Beta Pruning playing badly python

2 Answers2