Otello potatura alfa-beta gioca male pitone

Question

Attualmente sto cercando di fare una buona intelligenza artificiale per Otello, e lo hanno fatto utilizzando l'algoritmo Minimax. Tuttavia, quando ho provato a fare una ricerca più profonda con alfa-beta potatura, sembrava che l'algoritmo stava giocando terribilmente. Ho controllato con altre fonti come Wiki e Berkely.edu, e credo di aver implementato correttamente, ma non riesco ancora a trovare il problema.

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

Il tuo codice alfa-beta è probabilmente sbagliato. Essere consapevoli di ciò che accade quando un giocatore 'passare il turno' (vale a dire non ci sono mosse disponibili), ho avuto un bug difficile nel mio codice, a causa di questo.

Hai chiamato la ricorsione con l'alfa e beta valori commutati? Il mio funziona come questo (codice Java):

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

La chiamata è come:

 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: Nel caso in cui un giocatore non ha mosse disponibili, getAllMoves () restituiscono una 'mossa fittizia', che non cambia il consiglio a tutti, basta passare il turno.

Speranza che aiuta!

Answer 2

I tuoi sguardi AlphaBeta corretta attuazione a me. Dal momento che Minimax e alphabeta produrre gli stessi risultati quando viene implementato correttamente, si dovrebbe essere in grado di utilizzare il codice di Minimax vecchio come un controllo contro alphabeta, almeno per una profondità di ricerca modesti. Se i loro risultati differiscono quando si cerca lo stesso albero di gioco, poi si sa che hai fatto qualcosa di sbagliato.

Ma molto probabilmente, i poveri gioco è il risultato di qualcosa nel vostro "heur" funzione di valutazione.