如何证明每个子段、策略是最优的最小极大算法？

Question

问题就像标题所暗示的那样。

我知道minimax算法是针对2人博弈的(假设我们想要最大化A的利润)：当它是A的时候，我们取子值的最大值，因为我们是最大化A的利润，当是B的时候，我们取子值的最小值，因为我们想要最小化B的利润。

然而，我认为上述逻辑并不能证明每一个子问题，策略是最小极大算法中最优的。对我提出的问题有什么暗示或解决办法吗？如果上面的逻辑是这样的话，你能详细说明一下吗？

Answer 1

索赔的最小值是: minimax给出了最优策略，如果另一个玩家也使用相同的策略。

Base：对于游戏树中的一片叶子，只有一种策略，这显然是极小极大选择的，而且它是最优的，因为它是唯一的策略。

假设：minimax为深度d博弈选择最优策略。

证明

让我们看一场深度d+1的游戏。显然有两种可能的情况：

1. 这是退出-这是max阶段。在这种情况下，在所有可能的移动中，我们可以做-极小极大递归地评估每种策略的最小-最大值值，并给出“子博弈”的最优结果，在这里我们选择了这个移动。每个子博弈都是深度d，从归纳假设来看，它是最优的。 由于这是最大阶段-最小-最大算法选择最大，这是我们的最优解。
2. 这是对手的回合-这是min阶段。类似于上面的逻辑，极小极大地将情况分解为对手可以做的所有可能的动作，并评估他们的结果。从归纳假设来看，评价是最优的，我们从它们中选择最小值--这将是对手会选择的最优策略，也是他的最优策略(假设对手在每一步中都最优地选择)--因此对手选择了最小的评价，从而最小化了我们的利润，从而最大化了他的利润。

QED

在此基础上，您可以得出另一个minimax声明--该策略返回的值不少于实际得到的值(不管oppnent的策略如何)。这一点可以通过归纳证明非常类似于上面的一个。

准则：

Base：只有一种策略，当“树”实际上是一片叶子时，您将返回它。

Claim：minimax为深度游戏d返回的值是从这个级别上所玩的所有游戏的下限，在这个级别上，您根据极小值选择，并且没有对对手的限制。

证明

让我们来看看深度d+1游戏。

1. 如果轮到你，你从所有的叶子中选择最大的，因为你在这里有选择。每一片叶子都保证你(诱导假设)至少有一些价值，并且通过选择它们的最大值-你也保证选择的价值。
2. 如果轮到对手，你就无法控制选择。你只能确定他会选择一些行动，不知道是哪一个。然而，对于所有可能的移动-你得到了一个新的深度d的“子游戏”，在那里的归纳假设成立。对手可以选择这些移动中的任何一种，因此您可以保证在此移动之后，您的值至少为min{game after opponent move}，这正是最小相位返回的值。

QED.

Answer 2

你不能证明极小极大会使玩家的利润最大化，因为极小值不会试图使玩家的利润最大化。

minimax所做的是将玩家可能的损失降到最低；也就是说，它的决定是保守的，并且假设最坏的情况(其他玩家的最佳游戏)。试着证明这一点，你会发现它要简单得多。