Minimax/Alpha-Beta剪枝

What · 是什么

Minimax（极小化极大）是双人零和完全信息博弈的对抗搜索算法：我方（MAX）选择使自己分数最大的走法，对方（MIN）选择使我方分数最小的走法，自底向上回溯求得双方最优策略下我方能保证的分数。Alpha-Beta 剪枝在搜索中维护 α（MAX 玩家可保证的分数下界）与 β（MIN 玩家可保证的上界），当某节点出现 α≥β 时，其剩余分支不可能被双方理性选择，直接剪掉，从而大幅减少搜索量。

Why · 为什么

How · 实现

伪代码

# Negamax 统一形式
score = minimax(state, depth, alpha, beta, is_max)

if 终局/到达深度: return 静态估值
if is_max:  # MAX节点
    for each move:
        alpha = max(alpha, minimax(child, alpha, beta, False))
        if alpha >= beta: break   # 剪枝
    return alpha
else:  # MIN节点
    for each move:
        beta = min(beta, minimax(child, alpha, beta, True))
        if alpha >= beta: break   # 剪枝
    return beta

Python 实现

LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]


def evaluate(state):
    """终局判定: 1=max(X)赢, -1=max输, 0=平; 未终局返回None"""
    for a, b, c in LINES:
        if state[a] == state[b] == state[c] and state[a] != '.':
            return 1 if state[a] == 'X' else -1
    if '.' not in state:
        return 0
    return None


def minimax(state, is_max):
    """Minimax: 井字棋, X=MAX, O=MIN, 返回MAX可保证分数"""
    e = evaluate(state)
    if e is not None:
        return e
    if is_max:
        best = -2
        for i in range(9):
            if state[i] == '.':
                ns = state[:i] + 'X' + state[i+1:]
                best = max(best, minimax(ns, False))
        return best
    else:
        best = 2
        for i in range(9):
            if state[i] == '.':
                ns = state[:i] + 'O' + state[i+1:]
                best = min(best, minimax(ns, True))
        return best


def alpha_beta(state, is_max, alpha, beta):
    """Alpha-Beta剪枝: 与minimax结果一致但剪去无效分支"""
    e = evaluate(state)
    if e is not None:
        return e
    if is_max:
        for i in range(9):
            if state[i] == '.':
                ns = state[:i] + 'X' + state[i+1:]
                alpha = max(alpha, alpha_beta(ns, False, alpha, beta))
                if alpha >= beta:
                    break  # 剪枝
        return alpha
    else:
        for i in range(9):
            if state[i] == '.':
                ns = state[:i] + 'O' + state[i+1:]
                beta = min(beta, alpha_beta(ns, True, alpha, beta))
                if alpha >= beta:
                    break  # 剪枝
        return beta


if __name__ == "__main__":
    # 空棋盘: 完美博弈下先手(X)是平局 -> 分数0
    assert minimax('.' * 9, True) == 0
    assert alpha_beta('.' * 9, True, -2, 2) == 0

    # X在中心, 轮到O: O应打平 -> 0
    s = '.....X...'
    assert minimax(s, False) == 0
    assert alpha_beta(s, False, -2, 2) == 0

    # X差一步连线(第1行XX.), 轮到X: 必胜 -> 1
    s = 'XX......O'
    assert minimax(s, True) == 1
    assert alpha_beta(s, True, -2, 2) == 1

    # O差一步连线(第1行OO.), 轮到O: 必胜(对X为-1) -> -1
    s = 'OO......X'
    assert minimax(s, False) == -1
    assert alpha_beta(s, False, -2, 2) == -1

    # 终局
    assert minimax('XXX......', True) == 1
    assert minimax('OOO......', True) == -1

    # 交叉验证所有中间局面
    def gen_states(depth):
        res = []
        def rec(s, d, turn):
            res.append(s)
            if d == depth:
                return
            for i in range(9):
                if s[i] == '.':
                    rec(s[:i] + turn + s[i+1:], d + 1, 'O' if turn == 'X' else 'X')
        rec('.' * 9, 0, 'X')
        return res

    tested = 0
    for s in gen_states(4):
        if evaluate(s) is not None:
            continue
        mx = s.count('X'); mo = s.count('O')
        if mx < mo or mx > mo + 1:
            continue
        is_max = (mx == mo)
        a = minimax(s, is_max)
        b = alpha_beta(s, is_max, -2, 2)
        assert a == b, (s, a, b)
        tested += 1
    print(f"minimax-alpha-beta all tests passed ({tested} positions cross-validated)")

易错点

• α 与 β 的语义(MAX下界/MIN上界)颠倒会导致错误剪枝
• 剪枝条件 α≥β 时两种节点都成立，α=β 也必须剪
• 根节点返回值应为 α(MAX) 或 β(MIN)，勿混淆
• 深度受限时需静态评估函数截断，返回值需有界(在(α,β)内才有剪枝意义)
• 走法顺序不排序时剪枝效率大幅下降

例题

信源

• OI Wiki✓ https://oi-wiki.org/search/alpha-beta/
• 书籍✓ CPH ch22 (Game theory / minimax 相关)