极小极大算法是一种在竞争情境中选择行动的算法，尤其适用于一方所得即为另一方所失的双人博弈。在人工智能中，它假定对手会选择对决策者最不利的应对方式，以此评估可能的行动。该算法沿博弈树反向回传数值，交替执行最大化和最小化操作。其更广泛的数学基础属于博弈论：极小极大策略用于防范对手能够强加的最坏结果。(inst.eecs.berkeley.edu)
博弈模型与假设
标准的博弈搜索形式适用于确定性的、双方轮流行动且具有完全信息的双人博弈：双方都知道当前局面和此前的行动。在零和博弈中，双方利益直接对立，因此可以用单一的数值收益衡量结果。一方通常称为 MAX，追求更大的数值；另一方称为 MIN，追求更小的数值。博弈树以节点表示局面，以边表示合法行动。节点标明轮到哪一方行动，终局节点则具有已知的结果值。(inst.eecs.berkeley.edu)
所有数值都必须采用一致的视角，通常以 MAX 为准。例如，获胜可记为 (+1)，平局为 (0)，失败为 (-1)。MIN 所做的是最小化这一相同的分数，而不是使用另行定义的评估。算法的最优性结论是有条件的：穷尽搜索的极小极大算法给出的是面对最优对手时能够取得的最佳结果，并不一定意味着获胜。如果对手犯错，实际结果可能好于算法所保证的值。(inst.eecs.berkeley.edu)
递归定义
设 (V(s)) 为局面 (s) 的价值函数，(U(s)) 为其终局收益，(C(s)) 为其合法后继局面的集合。对于有限博弈树，
[ V(s)= \begin{cases} U(s), & \text{若 }s\text{ 为终局},\ \max_{t\in C(s)}V(t), & \text{若在 }s\text{ 轮到 MAX 行动},\ \min_{t\in C(s)}V(t), & \text{若在 }s\text{ 轮到 MIN 行动}. \end{cases} ]
若根节点轮到 MAX 行动，算法就选择通向价值最大的后继局面的行动。计算通过递归先评估后代节点，再评估其父节点；因此，常规实现采用后序的深度优先搜索遍历。(inst.eecs.berkeley.edu)
举例来说，假设 MAX 在两个行动之间作选择。采取第一个行动后，MIN 可以选择收益为 3 或 5 的终局；采取第二个行动后，MIN 可以选择收益为 2 或 9 的终局。第一个行动的价值为 (\min(3,5)=3)，第二个行动的价值为 (\min(2,9)=2)。MAX 因而选择第一个行动，保证获得 3。看似诱人的收益 9 与这一保证无关，因为 MIN 可以避开它。这个例子直接体现了上述递推关系。(inst.eecs.berkeley.edu)
搜索成本与 Alpha–Beta 剪枝
主要困难在于指数级的时间复杂度。当分支因子为 (b)、搜索深度为 (d) 时，穷尽搜索的极小极大算法在规则树中需要访问 (O(b^d)) 个节点。即使分支数量不算很大，在许多棋类游戏中，完整搜索也不切实际。这里的计算复杂性取决于所探索的树的规模，而不只是当前可选行动的数量。(inst.eecs.berkeley.edu)
Alpha–Beta剪枝避免探索不会影响最终极小极大值的分支。它记录 MAX 和 MIN 已经能够保证的数值界限。一旦这些界限表明某个分支不可能改善相应的选择，就不必继续探索。与启发式截断不同，正确的 Alpha–Beta 剪枝会保留同一棵树的极小极大计算结果。(inst.eecs.berkeley.edu)
剪枝效果在很大程度上取决于行动的搜索顺序。优先搜索有希望的行动，能够更早获得有用的界限。在理想顺序下，搜索成本可接近 (O(b^{d/2}))；而不利的顺序可能使原有的指数级成本几乎不变。这种成本降低能让算法在相同计算预算内搜索到深得多的层次。(inst.eecs.berkeley.edu)
深度限制与评估函数
实际实现通常在固定深度停止搜索，而不是遍历至所有终局。启发式评估函数用于估计各个截断局面的价值。终局结果仍然是精确值，非终局评估则是近似值。因此，深度受限的极小极大算法优化的是经过截断和评估的树，并不一定能解出原本的博弈。(inst.eecs.berkeley.edu)
一种常见的评估设计采用可量化特征的线性组合：
[ E(s)=\sum_i w_i f_i(s). ]
在西洋跳棋中，特征可以包括双方普通棋子和王棋的数量，其正负号和权重反映这些棋子对局面价值的估计贡献。这种启发式方法之所以有用，是因为它代替了原本难以完成的后续搜索；但估计不准确时，就无法保证最优对弈。因此，搜索深度和评估质量共同影响算法的表现。(inst.eecs.berkeley.edu)
与极小极大定理的关系
基于树搜索的极小极大算法，与约翰·冯·诺依曼于 1928 年证明的极小极大定理有关，但两者并不相同。对于收益矩阵为 (A) 的有限双人零和博弈，该定理指出：
[ \max_p\min_q p^\mathsf{T}Aq
\min_q\max_p p^\mathsf{T}Aq, ]
其中，(p) 和 (q) 分别遍历双方各自的混合策略。这些策略是可用纯策略上的概率分布，而式中的表达式衡量的是收益的期望值。等式两边的共同数值就是该博弈的价值。(cs.cmu.edu)
允许采用随机化策略至关重要：如果双方都只能使用纯策略，上述等式未必成立。在零和博弈中，最优混合策略构成纳什均衡。该定理讨论的是策略所能保证的结果，而递归博弈树搜索则通过依次进行的选择计算价值；不应将二者视为同一种过程。(cs.cmu.edu)
随机事件与对手模型
极小极大算法将对手的选择视为刻意对己方不利的选择。如果结果遵循已知的概率，期望极大算法就用按概率加权的平均值代替最小化节点；同时包含对手和随机事件的博弈，则可能兼有最小化节点与机会节点。因此，应根据环境模型在这些方法之间作出选择。极小极大算法的最坏情况假设，并不是在预测每个真实对手都会始终选择最强的行动。(inst.eecs.berkeley.edu)
参考来源
- 2 Minimax | Introduction to Artificial Intelligenceinst.eecs.berkeley.edu
- CS 188, Spring 2023, Note 9inst.eecs.berkeley.edu
- CS 188, Summer 2023, Note 5inst.eecs.berkeley.edu
- Von Neumann’s Minimax Theoremcs.cmu.edu
- Session 8: Playing gamescs.cmu.edu
- Game theorycs.cmu.edu
- Game Theorycs.cmu.edu