05-极小化极大算法

8.2.2　极小化极大算法

若要在双人、零和、全信息的对弈游戏（如井字棋、跳棋或国际象棋）中找到最佳走法，极小化极大策略是一种经典算法。它已经对其他类型的游戏进行了扩展和修改。极小化极大算法通常采用递归函数来实现，这时两个玩家要么是极大化玩家，要么是极小化玩家。

极大化玩家的目标是找到能获得最大收益的走法。但是，极大化玩家必须考虑极小化玩家的走法。在每次试图求出极大化玩家的最大收益后，递归地调用 minimax() 以求得对手的回手，也就是让极大化玩家的收益最小化的走法。这个过程一直来回进行（求最大值、求最小值、求最大值等），直到达到递归函数的基线条件。基线条件为终局（赢或平局）或达到最大搜索深度。

调用 minimax() 将返回极大化玩家的起始位置的评分。就 TTTBoard 类的 evaluate() 方法而言，如果双方的最佳走法将导致极大化玩家获胜，则返回1分。如果最佳走法将导致极大化玩家输棋，则返回−1分。如果最佳走法将导致平局，则返回0分。

这个分数将会在达到基线条件时返回。然后，再沿着达到基线条件的各层递归调用逐级向上返回。对于每次求最大值的递归调用，向上返回的是下一步走法的最佳评分。对于每次求最小值的递归调用，向上返回的是下一步走法的最差评分。这样，决策树就建立起来了。图8-2呈现了这样一棵决策树，有助于厘清还剩最后两步的一局棋向上返回评分的过程。

对于搜索空间太深而无法抵达终局的游戏（例如跳棋和国际象棋）， minimax() 会在到达一定深度后停止。要搜索的棋步数深度有时被称为“层”（ply）。然后启动评分函数，采用启发法对棋局进行评分。游戏对初始玩家越有利，得分就越高。我们在介绍四子棋时将会再回来讨论这个概念，四子棋的搜索空间比井字棋的搜索空间大多了。

代码清单8-8中给出的就是 minimax() 的全部内容。

代码清单8-8　minimax.py

from __future__ import annotations
from board import Piece, Board, Move
# Find the best possible outcome for original player
def minimax(board: Board, maximizing: bool, original_player: Piece, max_depth: int = 8)
    -> 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:
        best_eval: float = float("-inf") # arbitrarily low starting point
       for move in board.legal_moves:
           result: float = minimax(board.move(move), False, original_player, max_depth - 1)
           best_eval = max(result, best_eval)
       return best_eval
    else: # minimizing
       worst_eval: float = float("inf")
       for move in board.legal_moves:
          result = minimax(board.move(move), True, original_player, max_depth - 1)
          worst_eval = min(result, worst_eval) 
       return worst_eval

在每次递归调用过程中，无论当前是极大化玩家还是极小化玩家，或者是对 original_player 的棋局进行评分，都需要跟踪记录棋局。 minimax() 的前几行代码负责处理基线条件：末端节点（赢、输或平局）或到达的最大深度。 minimax() 函数的其余部分是对递归情况的处理。

其中一种递归情况是求最大值，这时需要查找能够生成最高评分的走法。另一种递归情况是求最小值，这时查找的是导致最低评分的走法。这两种情况交替进行，直至抵达终局状态或最大深度（基线条件）。

不幸的是，只是原封不动地用 minimax() 无法找出给定棋局的最佳走法。它只能返回一个分值（一个 float 类型值），而无法给出生成该评分的最佳的第一步该怎么下。

于是我们要创建一个辅助函数 find_best_move() 来为某棋局中每一步合法的走法循环调用 minimax() ，以便找出评分最高的走法。我们可以将 find_best_move() 视作对 minimax() 的第一次求最大值调用，只是带上了初始的棋步而已。具体代码如代码清单8-9所示。

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

# Find the best possible move in the current position 
# looking up to max_depth ahead
def find_best_move(board: Board, max_depth: int = 8) -> Move:
    best_eval: float = float("-inf")
    best_move: Move = Move(-1)
    for move in board.legal_moves:
        result: float = minimax(board.move(move), False, board.turn, max_depth)
        if result > best_eval:
            best_eval = result
            best_move = move
    return best_move

现在万事俱备，我们可以开始搜索任何井字棋局的最佳走法了。