Minimax（有时称为Minmax、MM或鞍点）是一种决策规则，用于人工智能、决策论、组合博弈论、统计学和哲学中。它旨在最小化最坏情况（最大损失）下可能发生的损失。当涉及收益时，它被称为“maximin”，，即最大化最小收益。最初为多人零和博弈论而制定，涵盖玩家交替行动和同时行动两种情况，后来也被扩展到更复杂的博弈以及存在不确定性时的一般决策中。
这一概念在对抗性环境中至关重要，其中一方的收益即另一方的损失。在此类情境下，minimax提供了一种保守策略：假设对手总是会选择对你最不利的行动，然后选择能最大化你保证收益的举动。这一原则支撑了机器学习和深度学习中的许多算法，特别是在训练生成模型和设计鲁棒系统时。
博弈论基础
在博弈论中，maximin值是指玩家在不了解其他玩家行动的情况下能确保获得的最高值；等价地，它是其他玩家在知道该玩家行动时能迫使该玩家获得的最低值。其正式定义为：v_i_underline = max_{a_i} min_{a_{-i}} v_i(a_i, a_{-i})，其中i是玩家的索引，a_i是玩家i采取的行动，a_{-i}表示所有其他玩家的行动，v_i是玩家i的收益函数。
计算maximin值采用最坏情况方法：对于玩家的每个可能行动，检查其他玩家的所有可能行动，并确定最差的组合，，即产生最小值的组合。然后，选择使这个最小值尽可能高的行动。例如，考虑一个两人博弈，其中行玩家可以选择T、M或B，列玩家可以选择L或R，收益如表所示。行玩家可以玩T，保证至少获得2的收益（B有风险，可能为−100，M可能产生−10），所以v_row_underline = 2。列玩家可以玩L，确保至少获得0（R有风险，可能为−20），所以v_col_underline = 0。如果双方都采用其maximin策略（T，L），收益向量为（3，1）。
玩家的minimax值是指其他玩家在不了解该玩家行动的情况下能迫使该玩家获得的最小值；等价地，它是该玩家在知道其他玩家行动时能确保获得的最高值。其正式定义为：v_i_overline = min_{a_{-i}} max_{a_i} v_i(a_i, a_{-i})。在零和博弈中，每个玩家的minimax值等于maximin值，从而引出minimax定理。
Minimax定理与零和博弈
Minimax定理由约翰·冯·诺依曼于1928年证明，指出在有限、两人、零和博弈中，采用混合策略时，maximin值等于minimax值。该定理为均衡分析提供了基础。在此类博弈中，博弈的值是双方都最优行动时的期望收益。该定理确保玩家至少能保证获得这个值，而对手最多只能将其限制在这个值。
对于同时行动的博弈，这一概念扩展到混合策略，即玩家在纯行动上随机化。Minimax定理保证了混合策略中鞍点的存在，鞍点是一对策略，其中任何一方都无法通过单方面偏离来改善其收益。这一结果在神经网络训练中至关重要，其中对抗样本使用类似的最坏情况原则进行分析。
人工智能中的应用
在AI中，minimax广泛用于博弈和对抗场景中的决策。经典例子是用于国际象棋、跳棋或井字棋等两人回合制博弈的minimax算法。该算法递归评估博弈树，假设对手最优行动。在每个节点，玩家选择最大化其最小收益的行动，而对手选择最小化玩家最大收益的行动。这通常与alpha-beta剪枝结合使用，以降低计算复杂度。
在大型语言模型和transformer架构中，minimax原则出现在对抗训练中，其中模型被训练以对最坏情况扰动具有鲁棒性。例如，生成对抗网络（GAN）使用minimax目标：生成器试图最小化判别器区分真实与虚假数据的能力，而判别器试图最大化其准确性。这一对抗过程是minimax在深度学习中的直接应用。
扩展与变体
Minimax已被扩展到更复杂的博弈，包括带有随机性的博弈（如西洋双陆棋），使用expectiminimax，以及不完全信息博弈，使用反事实遗憾最小化等技术。在强化学习中，minimax用于鲁棒控制和多智能体环境，其中智能体必须考虑最坏情况的对手行为。这一概念也出现在优化和统计学中，其中minimax估计量最小化最大风险。
在计算机国际象棋和其他博弈AI中，带alpha-beta剪枝的minimax仍是核心技术，尽管现代系统如OpenAI和Google DeepMind通常使用包含minimax式目标的机器学习方法。这一原则在决策论中也相关，用于在不确定性下选择行动，其中决策者选择最小化最坏情况损失的选项。
历史背景与相关概念
Minimax规则源于博弈论和决策论，贡献者包括数学家约翰·冯·诺依曼和奥斯卡·摩根斯坦。它与优化中的鞍点概念以及非零和博弈中的纳什均衡密切相关。在哲学中，minimax用于讨论理性和风险规避。
在现代AI中，minimax常与贝叶斯决策论对比，后者使用先验概率而非最坏情况假设。虽然minimax是保守的，但贝叶斯方法可能更灵活。两者之间的选择取决于概率信息的可用性。在AI研究中，minimax仍是评估决策算法的基准，尤其是在对抗环境中。
参见
- Alpha-beta剪枝
- 博弈论
- 零和博弈
- 对抗性机器学习