Othello Alpha-Beta Élagage mal jouer python

Question

Je suis en train de faire actuellement une bonne IA pour Othello, et ont fait en utilisant l'algorithme Minimax. Cependant, quand j'ai essayé de faire une recherche plus approfondie en utilisant la taille alpha-bêta, il semblait que l'algorithme jouait terriblement. Je l'ai vérifié avec d'autres sources comme Wiki et Berkely.edu, et je pense que je l'ai mis en œuvre correctement, mais je ne peux toujours pas trouver le problème.

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

Votre code alpha-bêta est probablement faux. Soyez conscient de ce qui se passe quand un joueur « passer le tour » (à savoir n'a pas de mouvements possibles), j'ai eu un bug difficile dans mon code, à cause de cela.

Avez-vous appelé la récursion avec l'alpha et les valeurs bêta commutées? Le mien fonctionne comme ceci (code 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;
}

L'appel est comme:

 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: Dans le cas où un joueur n'a pas disponible, se déplace getAllMoves (retour) un « mouvement factice », qui ne change pas la carte du tout, il suffit de passer le tour.

it helps!

Answer 2

Votre mise en œuvre alphabeta sonore me regarde. Depuis Minimax et alphabeta produisent les mêmes résultats lorsqu'elles sont appliquées correctement, vous devriez être en mesure d'utiliser votre ancien code Minimax comme un chèque contre alphabeta, au moins pour des profondeurs de recherche modestes. Si leurs résultats diffèrent lorsque vous recherchez le même arbre de jeu, alors vous savez que vous avez fait quelque chose de mal.

Mais le plus probable, les pauvres jeu est le résultat de quelque chose dans votre « heur » fonction d'évaluation.