python beta-Othello修剪得很糟糕

Question

我目前正在尝试为奥赛罗做一个好的人工智能，并且已经使用了极大极小算法。然而，当我试图使用alpha-beta剪枝进行更深入的搜索时，这个算法似乎玩得很糟糕。我查了其他来源，比如Wiki和伯克利.edu，我想我已经正确地执行了它，但是我仍然找不到问题。在

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

你的α-β密码可能是错的。注意当一个球员“传球”（即没有可用的移动）时会发生什么，我的代码中有一个棘手的错误，这就是原因。在

你调用了alpha和beta值切换的递归吗？ 我的工作原理如下（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;
}

通话内容如下：

^{pr2}$

编辑：如果玩家没有可用的移动，getAllMoves（）将返回一个“虚拟移动”，即 根本不换板子，只要过弯就行了。在

希望有帮助！在

Answer 2

你的alphabeta实现在我看来很不错。由于minimax和alphabeta在正确实现时会产生相同的结果，因此您应该能够使用旧的minimax代码来检查alphabeta，至少在适当的搜索深度下是这样。如果他们在搜索同一个游戏树时结果不同，那么你就知道你做错了什么。在

但最有可能的是，你的“heur”评估函数中的某个因素导致的。在