algorithm - 带a-b修剪和换位表的Minimax

Question

我试图用α-β剪枝和换位表实现一个minimax算法这是为一个可能循环的pacman代理，所以必须特别小心。如果一个状态（游戏和回合的状态（pacman或ghost））在换位表中，并且前面要看到的是节点的父节点（父节点，…），则可以将其丢弃。这适用于没有a-b修剪的minimax。从之前的搜索来看，带有a-b的tt（transposition table）似乎更难实现。我试图保持代码尽可能清晰，它基于这个伪代码Artificial Intelligence: A Modern Approach。我想用第一种方法尽可能接近最终结果。
我发现的每个伪代码的定义方式都非常不同：
First pseudo-code；
Second pseudo-code；Third pseudo-code
大多数的差异看起来都是表面的但这些代码都没有我要找的结构：用minvalue划分的minimax和用a-b修剪的maxvalue
提前谢谢你，
请再作进一步解释

Answer 1

我对更先进的人工智能优化还比较陌生，但我会分享我学到的东西。其中两个伪代码链接（1和3）都是Negamax，这比minimax更复杂，因为它不太直观NegaMax在1和3中的两种不同实现需要不同的评估功能，这是它们之间存在差异的主要原因（见下文）。你发布的第二个链接是针对MTD（f）的，我以前没有实现过，但我相信它仍然不同于Minimax和NegamaxI believe MTD(f) is considered to be faster。最后，the only resource I have ever seen for Minimax with transposition tables is here我真的不确定它是否正确Negamax基本上是标准的，如果您可以使用Minimax，那么您可以使用Negamax代替。
虽然Negamax和Minimax看起来不同，但它们本质上是在做同样的事情This blog post很好地描述了它们之间的关系，但没有解释它们之间的区别。我试着解释下为什么它们不同。
为什么minimax和negamax看起来不同，但本质上是相同的？在考虑了与minimax相关的一些事情之后，这一点变得更加明显了：
Mimax仅适用于2人游戏，其中一个玩家是最大化者，另一个是极小化者。tic-tac-toe就是一个简单的例子。
如果x在终端状态下赢了，minimax的典型求值函数将返回+100；如果o在终端状态下赢了，则返回-100；如果平局，则返回0。
注意分数是如何相互倒数的玩家1获得的每一分对玩家2来说都是一分损失这是一个零和游戏。
关于Negamax的几点：
Negamax也只适用于2人零和游戏。一号选手的每一分都是二号选手丢的一分。
Negamax使用的评估函数与Minimax略有不同它要求评估总是从当前玩家的角度进行。也就是说，如果在终端状态下X赢了，轮到X了，那么计算结果应该是+100如果它处于X赢但轮到O的终端状态，则评估值为-100。这与Minimax的期望不同（Minimax总是希望X赢值+100）伪代码1需要这种类型的求值函数。
一些Negamax伪代码，如3中的wikipedia文章，试图使用与Minimax相同的求值函数，在“return color×node的启发值”这行中使用颜色对求值函数值求反这也是可行的，但我从来没有这样做过（链接到下面我怎么做）。请注意，对于最小玩家，颜色值将仅为-1。我觉得这种方式更让人困惑。
既然已经描述了评估函数注意pseudo-code 3中的这一行“value:=max（value，–negamax（child，depth–-1，–β，–α，–color））”注意，返回的值（一些评估值）总是从当前玩家的角度来看是反向的。那是因为轮换和评估来自一个孩子的状态，另一个球员的轮换。alpha和beta值也颠倒过来。
使用Minimax，我们可以得出正面和负面的评价对于Negamax，我们总是创建积极的评价，然后根据需要反转它们，因此Nega这是可能的，因为游戏是零和的，玩家1的一分是玩家2的一分的损失。
为什么使用Negamax因为它更简单。第一次实现更具挑战性，但会使事情更简洁。我还认为，对于Minimax和Negamax，需要以不同的方式（更复杂）处理换位表条目最重要的是，其他人都在使用它。我希望能有更好的解释。
下面是我找到的用negamax实现换位表的最佳资源（大多数伪代码并没有那么有用）：
Iterative Deepening NegaScout with alpha beta pruning and transposition tables
我也用换位表实现了vanillannegamax，但是我再也找不到我使用的资源了要将上面的代码转换为vanilla negamax，只需将第504行（以//null window search开头）替换为521行，替换为“goodity=-minimax（state，depth-1，-beta，-alpha）；”代码块中的额外行是“scout”部分，它以窄的搜索alphabeta窗口开始，并根据需要将其加宽。一般来说，NegaScout比NegaMax好我可以分享我的全部来源，但我需要一些时间来准备一些适合发布到so的东西。
如果由于某种原因无法实现negamax，this is the only resource I have found for implementing Transposition Tables with Minimax。
最后，我想说几句：
当使用换位表时，您可能希望使用Iterative Deepening，因为当时间是您的限制时，它提供了一个自然的截止
当使用换位表时，您将需要考虑同构板也就是说，你将要考虑在反映立场相同的董事会。示例：在tic tac toe xox----x中计算此板与计算x----xox（垂直翻转）相同。不确定这是否适用于Pacman，但如果可以的话，这是一个巨大的改进在tic-tac-toe中，它导致70-90%的搜索状态被删除，并带有换位表。如果你想讨论，请在评论中回复。
如果你用JavaScript实现游戏，请注意标准的Zobrist键不起作用，因为JS二进制运算符操作32位而不是64位有几种不同的方法可以做到这一点，但我建议从使用字符串作为{}对象中的键开始。
如果你正在寻找一个多人人工智能，你应该寻找Hypermax/max-n。minimax和negamax失败超过2个玩家。