pythonrecursionminimaxreversi

Othello Alpha-Beta Pruning playing badly python


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

Solution

  • 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!