algorithm - 没有树的极小极大

Question

Minimax 经常用树来说明，但我知道它可以在没有树的情况下实现！但是，我不知道如何在没有树的情况下实现它！你能为我澄清一下吗？

Answer 1

根据定义，Minimax 总是像一棵树一样工作，无论您如何实现它。你如何想象它是另一回事。

通常，Minimax 是递归实现的（可以使用树进行最好的可视化）或迭代实现，它仍然通过 minimax 树的节点，只是使用另一种方法。

Answer 2

正如第一条评论中所指出的，minimax 是在树结构上正式定义的，但对于许多实际应用来说，没有必要对整个树进行正式计算，甚至不需要事先知道博弈树结构——如果可能的下一个移动和终止（游戏结束）状态是已知的，可以在算法运行时构建树。对于不可逆游戏（如井字游戏），树的不同点的重复状态具有相同的部分子树；因此，唯一需要学习的结构是每个状态的值，由 minimax 计算；这些值也可以被缓存以在算法期间重复使用。

顺便说一句，这种使用 minimax 的“非显式树结构”的一个有趣且流行的应用是Generative Adversarial Networks：

从摘要

..a generative model G that captures the data distribution, and a discriminative model D that estimates the probability that a sample came from the training data rather than G. The training procedure for G is to maximize the probability of D making a mistake. This framework corresponds to a minimax two-player game.