极小化极大算法

极小化极大算法是一种为具有完全信息的有限两人零和博弈确定最优博弈策略的算法。

用极小化极大算法计算的策略称为极小化极大策略。 由双方玩家的极小极大策略形成的策略对构成纳什均衡。

在非零和博弈中，对手的输不一定与你的赢同时发生，极小化极大算法可能无法提供最佳策略。

极小化极大算法的变体构成了象棋程序等下棋程序的核心元素。 与此同时，计算机计算能力的增强导致即使是象棋这样复杂的游戏，现在每个人都可以轻松被计算机打败。

如果玩家 A 获胜，理想的评分函数会为某个位置分配值 +1，如果玩家 B 获胜则为 -1，如果平手则为 0。 如果您可以构建从所有游戏位置到xxx深度的搜索树，那么该算法将玩出完美的游戏。

在几乎所有其他游戏中，这计算量太大。因此，人们满足于仅在给定搜索深度（范围）内构建搜索树。修改了评估函数，A 的非常好的游戏位置获得非常高的值， B 的非常好的游戏位置收到非常高的值非常低的值。为了确定值，人们使用启发式方法进行估计。

该算法从叶子的底部开始，然后上升到根。 在级别 3 中，算法选择子节点的最小值并将其分配给父节点（已最小化）。 在级别 2 中，xxx的子节点然后被分配给父节点（它被最大化）。 这是交替进行的，直到到达根。 根被赋予xxx子节点的值。

极小化极大算法在要检查的可能移动数量方面是线性的。 通常，搜索深度越长，所需时间越长。另一方面，搜索结果的质量通常随着搜索深度的增加而增加（取决于数值评估）。

因此有各种优化的变体，例如

• 可变搜索深度：如果每种游戏情况只有少数可能的移动，例如因为游戏场上只剩下几块棋子位于，可以增加搜索深度。
• 动态搜索深度：如果搜索树中某一点的数值从一级到另一级发生显着变化，则可以局部增加搜索深度。

存储先前检查的位置及其评估可显着节省时间。 如果从起始位置通过不同的移动序列到达一个位置，则不必每次都搜索整个底层搜索树。 在实践中，高效的哈希表通常用于这种存储。

迭代加深尤其适用于搜索时间有限的情况。 搜索从要检查的位置开始反复开始，逐渐增加所需的搜索深度。 如果已经检查过的位置如上所述被保存，那么只有自上次搜索以来已经到达的位置需要用评价函数来评价。 这个过程一直持续到超过可用的搜索时间或获得“相当不错”的结果。

如果没有迭代深度优先搜索，如果超过了时间限制，在最坏的情况下只会检查一个单一的移动，但这是一个非常大的深度。 下一步可能只需要一次反击就可以确保获胜，但一开始就不会尝试。

为了简化代码并能够以相同的方式对待搜索树的每个节点，定义每个玩家都试图为自己获得xxx结果，即评估函数的xxx值。 为此，后续位置的评估必须乘以 − 1。 不再需要区分是 A 还是 B 的走法，因此应该计算xxx值或最小值，但在每个位置只计算后续位置的否定评估的xxx值。