11-用α-β剪枝算法优化极小化极大算法

8.3.3　用α-β剪枝算法优化极小化极大算法

极小化极大算法的效果很好，但目前还没法实现很深的搜索。极小化极大算法有一个小扩展算法，被称为α-β剪枝（alpha-beta pruning）算法，在搜索时能将不会生成更优结果的棋局排除，由此来增加搜索的深度。只要跟踪记录递归调用 minimax() 间的两个值α和β，即可实现神奇的优化效果。α表示搜索树当前找到的最优极大化走法的评分，而β则表示当前找到的对手的最优极小化走法的评分。如果β小于或等于α，则不值得对该搜索分支做进一步搜索，因为已经发现的走法比继续沿着该分支搜索得到的走法都要好或相当。这种启发式算法能显著缩小搜索空间。

代码清单8-20给出的就是刚刚介绍的 alphabeta() 。应该将其放入现有的minimax.py文件中。

代码清单8-20　minimax.py（续）

def alphabeta(board: Board, maximizing: bool, original_player: Piece, max_depth: 
     int = 8, alpha: float = float("-inf"), beta: float = float("inf")) -> float:
    # Base case – terminal position or maximum depth reached
    if board.is_win or board.is_draw or max_depth == 0:
        return board.evaluate(original_player)
    # Recursive case - maximize your gains or minimize the opponent's gains
    if maximizing:
        for move in board.legal_moves:
            result: float = alphabeta(board.move(move), False, original_player, max_
             depth - 1, alpha, beta)
            alpha = max(result, alpha)
            if beta <= alpha:
                break
        return alpha
    else:  # minimizing
        for move in board.legal_moves:
            result = alphabeta(board.move(move), True, original_player, max_depth - 1,
             alpha, beta)
            beta = min(result, beta)
           if beta <= alpha:
               break
        return beta

现在可以做两处很小的改动，以便让上述新函数发挥作用。让 minimax.py 中的 find_ best_move() 不再调用 minimax() ，而是改为调用 alphabeta() ，并将connectfour_ai.py中的搜索深度由 3 改为 5 。有了这些改动，普通的四子棋玩家将无法击败本章的AI了。在我的计算机上， minimax() 的搜索深度为 5 ，四子棋AI每步大约耗时3分钟，而相同深度条件下用 alphabeta() 每步大约耗时30秒，只需要六分之一的时间！这种剪枝优化的效果简直令人难以置信。