人工智能/搜索/对抗搜索/极小极大搜索

极小极大搜索以其在计算所有信息都可用的双人游戏中最佳行动的有效性而闻名，例如棋盘游戏或井字棋 (Muller, 2001)。它包括遍历一棵树，该树捕获了游戏中所有可能的行动，其中每个行动都以一方的得失来表示。因此，它只能用于在零和游戏中做出决策，在一方获胜的博弈中，另一方必败。理论上，这种搜索算法基于冯·诺依曼的极小极大定理，该定理指出，在这些类型的游戏中，总存在一组策略，导致双方获得相同的值，并且由于这是可以预期获得的最佳值，因此应该采用这组策略 (Kulenovic, 2008).

描述

第一步是根据玩家 1 的效用给每个节点一个值。这些值源自终端节点的值，每个终端节点都代表游戏结束。树的每一层交替进行玩家 1 的行动（她试图最大化自己的分数）和玩家 2 的行动（他试图最小化玩家 1 的分数以破坏她的成功）。如果终端节点上方的层代表玩家 2 可能的行动，那么节点的值将是其子节点中值的最低值，即最小值。另一方面，如果这一层代表玩家 1 可能的行动，那么其节点的值将是其子节点中值的最高值。最后，一旦所有节点都被分配了值，玩家 1 就可以做出决定，她只需选择会导致最高值的行动 (Russell & Norvig, 1995)。图 1 说明了此过程。

,

图 1 : 为节点分配值并决定最佳行动。

伪代码

此伪代码改编自 Russell 和 Norvig (1995) 提供的版本。

function minimaxDecision (game)
	for each possible move in game
		moveValue = minimaxValue(state, game)

	return move with highest value

function minimaxValue (state, game)
	if terminal node
		return utility

	if player 1's turn
		return highest value of children

	if player 2's turn
		return lowest value of children

复杂性、缺点和未来方向

这种搜索的一个缺点是，它假设对手将以有效地最小化你的收益并最大化其自身收益的方式行动。但是，如果你的对手是非理性的、初学者或容易犯错的人类，这将不成立。在某些情况下，最好赌一把，并希望你的对手不会注意到微妙的反击 (Moore & Knuth, 1975)。

此外，表示像井字棋这样简单游戏的行动并不困难，但是对于像棋盘游戏这样的游戏，表示所有可能的行动在计算上会变得非常昂贵。因此，程序员通常依靠进一步的算法来缩小搜索范围，例如 alpha-beta 剪枝 (Moore & Knuth, 1975)。这包括当确定一个节点的值不可能高于相邻节点的值时停止计算该节点的效用。有关称为 min/max 近似的另一种方法，请参阅 Rivest (1988)。

缩减搜索空间的另一种方法是只到某个深度，将该级别的行动视为临时的终端节点，并使用启发式方法确定其值。但是，在需要长期规划的情况下，这仍然有问题 (Sadikov & Bratko, 2006)。但是，通过寻找游戏中稳定的阶段并将这些阶段用作中间终端节点，这种方法可以变得更加可行 (Scheucher & Kaindl, 1989)。尽管有这些技术，但关于在如此复杂的情况下使用极小极大搜索是否真正有效存在争议 (Sadikov et al., 2005)。

最后，本节仅讨论了下一个状态完全由参与者行动决定的游戏。极小极大搜索的最终领域是涉及机会的游戏，例如西洋双陆棋和扑克 (Hauk et al., 2006)。

参考文献

• Hauk, T., Buro, M., & Schaeffer, J. (2006). Rediscovering *-Minimax Search. In Computers and Games (pp. 35-50). Berlin: Springer-Verlag.
• Knuth, D. E., & Moore, R. W. (1975). An Analysis of Alpha-Beta Priming. Artificial Intelligence , 6 (4), 293-326.
• Kulenovic, M. R. (2008). Game Theory . Retrieved March 8, 2009, from University of Rhode Island Department of Mathematics: http://hypatia.math.uri.edu/~kulenm/mth381pr/GAMETH/gametheory.html
• Muller, M. (2001). Global and Local Game Tree Search. Information Sciences , 135, 187-206.
• Rivest, R. L. (1988). Game Tree Searching by Min/Max Approximation. Artificial Intelligence , 34, 77-96.
• Russell, S. J., & Norvig, P. (1995). Artificial Intelligence: A modern approach . Upper Saddle River, New Jersey: Prentice-Hall.
• Sadikov, A., & Bratko, I. (2006). Learning long-term chess strategies from databases. Machine Learning , 63, 329–340.
• Sadikov, A., Bratko, I., & Kononenko, I. (2005). Bias and pathology in minimax search. Theoretical Computer Science , 349, 268 – 281.
• Scheucher, A., & Kaindl, H. (1989). The reason for the benefits of minimax search. Proceedings IJCAI-89 , 322–327.