Othello Alpha-Beta-Beschneidung spielt schlecht Python

Question

Ich versuche derzeit, eine gute KI für Othello zu machen, und habe dies mit dem Minimax -Algorithmus getan. Als ich jedoch versuchte, eine tiefere Suche mit Alpha-Beta-Beschneidung durchzuführen, schien der Algorithmus schrecklich zu spielen. Ich habe es mit anderen Quellen wie Wiki und Berkly.edu überprüft, und ich glaube, ich habe es richtig implementiert, aber ich kann das Problem immer noch nicht finden.

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

Answer 1

Ihr Alpha-Beta-Code ist wahrscheinlich falsch. Seien Sie sich bewusst, was passiert, wenn ein Spieler „die Kurve übergeht“ (dh keine verfügbaren Bewegungen), ich hatte aufgrund dessen einen schwierigen Fehler in meinem Code.

Haben Sie die Rekursion mit den wechselnden Alpha- und Beta -Werten bezeichnet? Meins funktioniert so (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;
}

Der Anruf ist wie:

 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);

Bearbeiten: Falls ein Spieler keine verfügbaren Moves hat, GetAllmoves () gibt einen "Dummy Move" zurück, das das Board überhaupt nicht ändert, sondern nur die Kurve übergeben.

Ich hoffe es hilft!

Answer 2

Ihre Alphabeta -Implementierung sieht für mich gut aus. Da Minimax und Alphabeta bei korrekter Implementierung die gleichen Ergebnisse erzielen, sollten Sie Ihren alten Minimaxcode als Scheck gegen Alphabeta zumindest für bescheidene Suchtiefen verwenden können. Wenn sich ihre Ergebnisse bei der Suche nach demselben Spielbaum unterscheiden, wissen Sie, dass Sie etwas falsch gemacht haben.

Aber höchstwahrscheinlich ist das schlechte Spiel das Ergebnis von etwas in Ihrer "HEUR" -Stechnungsfunktion.