如何证明每个子部分，策略在最低限度算法中最优？

Question

问题是标题建议。

我知道最小的算法为2人游戏做到这一点（假设我们想要最大化A的利润）：当它是一个转弯时，我们会占据儿童价值的最大值，因为我们最大化A的利润，而且B轮转，我们采取了儿童价值的最小值，因为我们希望尽量减少B的利润。

但是，我不认为以上逻辑证明每个子问题，策略在最低限度算法中最优。我提出的问题的任何提示或解决方案？如果以上逻辑确实如此，那么你能详细说明吗？

Answer 1

索赔Minimax是：如果其他玩家也使用相同的策略，那么Minimax正在提供最佳策略。

base ：对于游戏树中的叶子 - 只有一个策略，这显然是最佳选择，而且它是最佳的 - 因为它是唯一一个。
假设：minimax选择深度世代游戏的最佳策略。
证明：

让我们看看深度世代游戏。显然有2个可能的场景：

1. 它轮流 - 这是d阶段。在这种情况下，我们可以执行的所有可能的动作 - Minimax递归地评估每个此类策略的最小值值，并为我们提供“子游戏”的最佳结果，我们选择了这一移动。这些调节中的每一个都是深度生成的，并且从归象假设，它是最佳的。
   由于这是最大相位 - Min-Max算法选择最大值，这是我们的最佳解决方案。
它是对手的转弯 - 这是d+1阶段。与上述逻辑类似，Minimax拆分对对手可以做的所有可能的移动，并评估其结果。从诱导假设，评估是最佳的，我们选择了它们的最小值 - 这将是对手所选择的，并且对他来说是最佳的策略（并且假设对手为每一步时最佳地选择） - 因此对手选择最小的评估，这最大限度地减少了我们的利润，从而最大限度地提高了他的利润。

qed

基于它，您可以得出另一个最小的索赔 - 策略返回的价值不低于您实际达到的价值（无论对抗的策略如何）。这可以通过非常类似于上述诱导来证明这一点。

指南：

base ：仅一个策略，当'树'实际上是一片叶子时，你正在返回它。
索赔：Minimax返回的值对于深度max的游戏是一个从这个级别播放的所有游戏的较低限制，在那里根据Minimax选择，并且对对手没有限制。
证明：

让我们看看深度生成的游戏。

1. 如果轮到你，你就会在所有的叶子中选择最大值，因为你 在这里选择。每个叶子都保证了你（印度人 假设）至少有一些值，并通过选择它们的最大 - 您还保证了所选值。
2. 如果是对手的转折 - 你没有控制选择。你只能确定他会选择一些举动，不知道这一点。但是，对于所有可能的移动 - 您获得了深度生成的新的“Subgame”，其中归纳假设持有。对手可以选择这些动作中的任何一个，因此可以保证在此移动之后，您将具有至少生成的值，这正是最小相位返回的内容。

qed 。

Answer 2

您无法证明这最小化最大化玩家的利润，因为Minimax并不试图最大化玩家的利润。

是什么Minimax是最小化播放器可能的损失;也就是说，其决定是保守的，并且假设最糟糕的情况（其他玩家的最佳播放）。尝试证明一个;你会发现它更加直截了当。