algorithm - 我对极小极大算法有什么不明白的地方

Question

我对极小极大算法有疑问。

假设我有以下游戏树，并且我添加了一些随机启发式值。

正如我所理解的极小极大算法，它将选择绿色路径。但是，在这种情况下，这可能不是最好的选择。因为顶部节点的右子节点具有它可以获得的最高值，所以这不是最好的移动......

因为如果其他玩家采取其他行动，我的获胜机会就会少得多......

对不起，我很难表达我在这个问题上的意思。但是我在这里怎么想错了？

Answer 1

The usual way to solve this is to proceed backwards from the lower layers of the tree. Let's check the lowermost four leaves first (the 10-20-15-20 part). Player 2 gets to choose from these if the game ever gets there, so P2 will choose the smaller ones, i.e. 10 and 15. We can then prune the 10-20-15-20 branches of the tree and replace them with 10 (for the leftmost two leaves) and 15 (for the rightmost two). Similarly, we can prune the -100 - 50 pair at the middle and replace them with -100 (not 50 as you did, because at this level it is player 2's turn and he will choose the smaller outcome), the -200 - -100 pair with -200 and so on. So, for me, it seems to be the case that you are taking the maximum at each branching point instead of alternating between the maximum and the minimum.

Answer 2

该算法假设你和第二个玩家都想赢，并且总是选择最好的动作。因此，在问题的树中 - 正如我在评论中所说，最后一步（第二个玩家做出）是左而不是右。这导致整个右子树 - 对于第一个玩家来说不值得，并且 minmax 算法将选择以下路径（而不是如问题中描述的那样）：left->left->right->left

这是真的算法“给你更少的获胜机会”这是因为事实上，有一个第二个玩家，他也想赢！

看看他的例子。
在这里，x 玩家想要避免失败，所以他在第一步中说服了“0”。请注意，如果（在示例中）他先向左走，那么第二个玩家再次向左走并获胜！该算法确保了最佳可能性 - 假设第二个玩家的行为也相同（并假设它知道整个游戏树）

Answer 3

您应该交替取最小值和最大值。如果要取 50，即 30 和 50 中的最大值，则应该选择右侧低一级的 -100，等等。这就是该算法被称为 minimax 的原因。