Minimax 与 ab 剪枝和转置表

Question

我正在尝试使用 alpha-beta 剪枝和转置表来实现极小极大算法。这是针对可能循环的 pacman 代理，因此必须特别注意这一点。如果一个状态（游戏和回合的状态（pacman 或 Ghost））在换位表中，并且之前看到的状态是该节点的父节点（祖父节点，...），则可以将其丢弃。这适用于没有 ab 剪枝的极小极大。从之前的搜索来看，tt（转置表）与ab的实现似乎要困难得多。我试图使代码尽可能清晰，它基于伪代码Artificial Intelligence: A Modern Approach。我希望使用第一种方法使最终结果尽可能接近。

我发现的每个伪代码都以非常不同的方式定义：

第一个伪代码； 第二个伪代码；第三个伪代码

大多数差异看起来只是表面上的。但这些代码都没有完全符合我正在寻找的结构：用 ab 剪枝除以 minValue 和 maxValue 的 minimax

提前致谢，

请询问任何进一步的解释

Answer 1

对于更高级的人工智能优化，我还是个新手，但我会分享我所学到的知识。其中两个伪代码链接（1 和 3）都是 Negamax，这比 minimax 更棘手，因为它不太直观。1 和 3 中 Negamax 的两种不同实现需要不同的评估函数，这是它们差异的主要原因（更多内容见下文）。您发布的第二个链接是针对 MTD(f) 的，我之前没有实现过，但我相信它仍然与 Minimax 和 Negamax 不同。我相信 MTD(f) 被认为更快。最后，我见过的带有换位表的 Minimax 的唯一资源就在这里，我真的不确定它是否正确。Negamax 几乎是标准，如果您可以使用 Minimax，那么您可能也可以使用 Negamax。

\n\n

虽然 Negamax 和 Minimax 看起来不同，但它们本质上做的是相同的事情。这篇博文很好地描述了它们之间的关系，但没有解释它们之间的差异。我将在下面尝试解释为什么它们不同。

\n\n

为什么 minimax 和 negamax 看起来不同但本质上是相同的，在考虑了一些与 Minimax 相关的事情后就变得更加明显了：

\n\n

\n
• Minimax 仅适用于 2 人游戏，其中一名玩家是最大化者，另一名是最小化者。Tic Tac Toe 是一个简单的例子。
\n
• 如果 X 在最终状态下获胜，Minimax 的典型评估函数将返回 +100；如果 O 在最终状态下获胜，则返回 -100；如果平局，则返回 0。
\n
• 请注意分数如何彼此相反。玩家 1 获得的每一分都会让玩家 2 失去一分。这是一个零和游戏。
\n

\n\n

关于 Negamax 的几点：

\n\n

\n
• Negamax 也仅适用于 2 人零和游戏。玩家 1 的每一分都会让玩家 2 失去一分。
\n
• Negamax 使用的评估函数与 Minimax 略有不同。它要求评估始终从当前玩家的角度进行。也就是说，如果在最终状态下X获胜并且轮到X了，则评估应该是+100。如果处于 X 获胜但轮到 O 的最终状态，则评估将为 -100。这与 Minimax 的预期不同（Minimax 总是希望 X 获胜的价值 +100）。伪代码 1 需要这种类型的评估函数。
\n
• 一些 Negamax 伪代码，例如 3 中的维基百科文章，尝试使用与 Minimax 相同的评估函数，通过在“返回颜色 \xc3\x97 节点的启发值”这一行中使用颜色来否定评估函数值。这也有效，但我从来没有这样做过（链接到我如何做的下面）。请注意，对于最少玩家，颜色值仅为 -1。我发现这种方式更加令人困惑。
\n
• 现在描述了评估函数......请注意这一行“value := max(value, \xe2\x88\x92negamax(child, height \xe2\x88\x92 1, \xe2\x88\x92\xce\xb2,伪代码 3中的 \xe2\x88\x92\xce\xb1, \xe2\x88\x92color))" 。请注意，返回的值（某些评估值）始终从当前玩家的角度来看是反转的。这是因为回合是交替的，并且评估来自子状态，即另一个玩家的回合。alpha 和 beta 值也颠倒。
\n

\n\n

通过 Minimax，我们提出了积极和消极的评估。使用 Negamax，我们总是创建积极的评价，然后根据需要反转它们，因此是 Nega。这是可能的，因为游戏是零和游戏，玩家 1 的一分意味着玩家 2 失去一分。

\n\n

为什么使用Negamax？因为它更简单。第一次实施更具挑战性，但会让事情变得更简洁。我还认为 Minimax 的换位表条目需要以不同于 Negamax 的方式处理（更复杂）。最重要的是，其他人都使用它。我希望我能更好地解释原因。

\n\n

这是我找到的用于使用 Negamax 实现换位表的最佳资源（大多数伪代码并不是很有帮助）：

\n\n

\n
• 带有 alpha beta 剪枝和转置表的迭代深化 NegaScout
\n
• 我还使用换位表实现了普通 Negamax，但我无法再找到我使用的资源。要将上面的内容转换为普通 Negamax，只需将第 504 行（以 // 空窗口搜索开始）替换为第 521 行“goodness = -minimax(state, height - 1, -beta, -alpha);” 该代码块中的额外行是“侦察”部分，它以狭窄的搜索 alphaBeta 窗口开始，并根据需要加宽。一般来说，NegaScout 比 NegaMax 更好。我可以分享我的完整来源，但我需要一些时间来准备适合发布到 SO 的内容。
\n

\n\n

如果由于某种原因您无法实现 Negamax，这是我找到的用于使用 Minimax 实现换位表的唯一资源。

\n\n

最后，我想抛出几点：

\n\n

\n
• 使用转置表时，您可能需要使用迭代深化，因为当时间受到限制时，它提供了自然的截止点
\n
• 使用换位表时，您需要考虑同构板。也就是说，您需要考虑同一块董事会来反映立场。示例：在 tic tac toe XOX|---|X-- 中评估该板与评估 X--|---|XOX（垂直翻转）相同。不确定这是否适用于吃豆人，但如果可用的话，这是一个巨大的改进。在 Tic Tac Toe 中，它导致 70-90% 的搜索状态被换位表削减。如果您想讨论，请在评论中回复。
\n
• 如果您在 JavaScript 中实现游戏，请注意标准 Zobrist 键将不起作用，因为 JS 二进制运算符在 32 位而不是 64 位上运行。有几种不同的方法可以做到这一点，但我建议从使用字符串作为 {} 对象中的键。
\n
• 如果您正在寻找多人 AI，您应该考虑Hypermax / Max-N。Minimax 和 Negamax 在 2 名玩家以上失败。
\n

\n