零和博弈/Minimax

What · 是什么

零和博弈（zero-sum game）：一名玩家的收益恰为另一名玩家的损失（收益之和为 0）。两类：(1) 序贯零和（轮流行动）：局面 S 的博弈值 V(s)=v(s)（终止），V(s)=max{V(t)}（玩家 1 行动），V(s)=min{V(t)}（玩家 2 行动）——即 Minimax 递推；配合 Alpha-Beta 剪枝、记忆化可加速。(2) 同时零和：收益矩阵 V=(v(a1,a2))，纯策略未必有解（石头剪刀布），需混合策略（概率分布）；von Neumann 极小极大定理断言 max-min=min-max=w，双方最优混合策略的价值唯一，可化为线性规划求解。

Why · 为什么

How · 实现

伪代码

# 序贯零和：树/图中按轮到谁取 max 或 min
# 用节点表示状态，叶为估值；递归记忆化
def minimax(node, maximizing):
  if node 是叶: return 估值(node)
  if maximizing: return max(minimax(c, False) for c in children)
  else:         return min(minimax(c, True)  for c in children)
# Alpha-Beta: 传入 alpha,beta，越界即剪枝
# 同时零和: 线性规划（numpy/scipy）求混合策略

Python 实现

def minimax(node, maximizing=True):
    """序贯零和博弈 Minimax。
    node 为叶子时是数值，否则是后继节点列表。
    返回玩家 1 的最优收益。
    """
    if isinstance(node, (int, float)):
        return node
    vals = [minimax(c, not maximizing) for c in node]
    return max(vals) if maximizing else min(vals)


def minimax_ab(node, maximizing, alpha, beta, node_id="root", memo=None):
    """Minimax + Alpha-Beta 剪枝（带记忆化）。
    memo: dict id -> 已算值，用于有环/重复子结构加速（需保证能终止）。
    """
    if memo is None:
        memo = {}
    if node_id in memo:
        return memo[node_id]
    if isinstance(node, (int, float)):
        return node
    if maximizing:
        best = float("-inf")
        for i, c in enumerate(node):
            val = minimax_ab(c, False, alpha, beta, f"{node_id}.{i}", memo)
            best = max(best, val)
            alpha = max(alpha, best)
            if beta <= alpha:  # 剪枝
                break
    else:
        best = float("inf")
        for i, c in enumerate(node):
            val = minimax_ab(c, True, alpha, beta, f"{node_id}.{i}", memo)
            best = min(best, val)
            beta = min(beta, best)
            if beta <= alpha:  # 剪枝
                break
    memo[node_id] = best
    return best


def solve_matrix_game(matrix):
    """同时零和：求解 2×n 或 m×2 矩阵博弈的混合策略价值 w（玩家 1）。
    用线性规划：max w  s.t. 对每个列 j: sum_i p_i*m_ij >= w, sum p_i=1, p>=0。
    这里用 scipy.optimize.linprog（依赖 numpy/scipy，竞赛常用手写消元）。
    """
    from scipy.optimize import linprog
    import numpy as np
    m = len(matrix)
    n_cols = len(matrix[0])
    # 变量 x = [p_1..p_m, w]
    c = [0.0] * m + [-1.0]          # 最小化 -w
    A_ub = []
    b_ub = []
    for j in range(n_cols):
        row = [-matrix[i][j] for i in range(m)] + [1.0]  # -sum p_i m_ij + w <= 0
        A_ub.append(row)
        b_ub.append(0.0)
    A_eq = [[1.0] * m + [0.0]]
    b_eq = [1.0]
    bounds = [(0, 1)] * m + [(None, None)]
    res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method="highs")
    if not res.success:
        return None
    w = res.x[-1]
    strat = res.x[:m]
    return w, strat


if __name__ == "__main__":
    # 叶子根
    assert minimax(5, True) == 5
    # max 节点
    assert minimax([1, 2], True) == 2
    assert minimax([1, 2], False) == 1
    # 2 层：max(min(3,7), min(1,9)) = max(3,1) = 3
    assert minimax([[3, 7], [1, 9]], True) == 3
    # 3 层
    assert minimax([[[5, 2], [8, 1]], [[3, 4], [6, 0]]], False) == 3

    # Alpha-Beta 与朴素一致
    assert minimax_ab([[3, 7], [1, 9]], True, float("-inf"), float("inf")) == 3

    # 同时零和：2x2 矩阵博弈价值
    # [[1, 3], [4, 2]]：混合策略价值 w=2.5, p=(0.5,0.5)
    if __import__("importlib").util.find_spec("scipy"):
        r = solve_matrix_game([[1, 3], [4, 2]])
        if r:
            w, strat = r
            assert abs(w - 2.5) < 1e-6, w
            assert abs(strat[0] - 0.5) < 1e-6 and abs(strat[1] - 0.5) < 1e-6
        print("scipy matrix game OK")
    else:
        print("scipy 未安装，跳过同时零和 LP 验证（核心 Minimax 已验证）")

    print("All tests passed.")

易错点

• minimax 树中玩家轮次决定取 max 还是 min，递归参数 (not maximizing) 别写反
• Alpha-Beta 剪枝条件 beta<=alpha，且必须更新 alpha/beta 后才比较
• 同时零和的纯策略可能不存在（石头剪刀布），此时不能直接说'有纯策略均衡'
• LP 模型符号：玩家 1 求 max w，约束 sum_i p_i m_ij >= w（对每列），转 linprog 时把不等式乘 -1
• 记忆化 key 要包含轮到谁（同一状态不同行动者值不同）
• 叶节点估值是玩家 1 视角，玩家 2 的收益是 -v

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/game-theory/zero-sum-game/
• OI Wiki✓ https://oi-wiki.org/math/game-theory/intro/
• 书籍✓ CPH ch25 Game theory（含 minimax 区间 DP 例子）