几天来，我一直在努力为井字游戏 AI 实施 miniMax 算法。现在，我遇到的问题是，当我调用 minimax() 函数时，我在“returnBoard”输入中得到一个空板。我知道我的算法正在遍历一系列棋盘，因为我已经打印出了孩子们，我看到计算机正在移动并给棋盘打分。有什么建议么？

这是整个可运行的内容。

我目前正在为一个名为Skat的基于技巧的纸牌游戏开发一个求解器，它在完美的信息情况下。虽然大多数人可能不知道这个游戏，但请多多包涵；我的问题是一般性的。

Skat简介：
基本上，每个玩家交替打一张牌，每三张牌形成一个花样。每张卡都有特定的价值。玩家获得的分数是相应玩家赢得的技巧中包含的每张牌的值相加的结果。我遗漏了一些对我的问题不重要的事情，例如谁和谁比赛或者我什么时候赢得一墩。
我们应该记住的是，有一个运行分数，并且在调查某个位置（->它的历史）时谁玩过什么与该分数相关。

我用 Java 编写了一个 alpha beta 算法，它似乎工作正常，但它太慢了。似乎最有希望的第一个增强是使用转置表。我读到，在搜索 Skat 游戏的树时，您会遇到很多已经调查过的位置。
这就是我的问题发挥作用的地方：如果我找到一个之前已经调查过的位置，那么导致这个位置的动作会有所不同。因此，一般来说，分数（以及 alpha 或 beta）也会有所不同。
这引出了我的问题：如果我知道相同头寸的价值，但历史不同，我如何确定头寸的价值？
换句话说：我怎样才能解耦从其路径到根的子树，以便可以将其应用于新路径？
我的第一个冲动是这是不可能的，因为 alpha 或 beta 可能受到其他路径的影响，这可能不适用于当前位置，但是......

似乎已经有一个解决方案
......我似乎不明白。在 Sebastion Kupferschmid 关于 Skat 求解器的硕士论文中，我发现了这段代码（可能是 C-ish / 伪代码？）：

这应该是不言自明的。succ(p)是一个返回当前位置所有可能移动的函数。t(q)是我认为是各个位置的跑分（庄家到目前为止所获得的分数）。因为我不喜欢在不理解的情况下复制东西，所以这应该只是对任何想帮助我的人的帮助。当然，我已经对这段代码进行了一些思考，但我无法理解一件事：通过在再次调用函数之前从 alpha/beta 中减去当前分数 [例如] ab_tt(q, res - t(q), beta - t(q))，似乎存在某种解耦上。但是，如果我们将位置的值存储在转置表中而不在这里也进行相同的减法，那么究竟有什么好处呢？如果我们找到了一个之前调查过的位置，为什么我们可以只返回它的值（如果它是VALID）或者使用 alpha 或 beta 的绑定值？在我看来，从转置表存储和检索值都不会考虑这些位置的特定历史。还是会？

文献：
几乎没有英文资料涉及 skat 游戏中的 AI，但我发现了这个：A Skat Player Based on Monte Carlo Simulation by Kupferschmid, Helmert。不幸的是，整篇论文，尤其是对转置表的阐述相当紧凑。

编辑：

为了让每个人都能更好地想象在所有牌都打完之前，在 Skat 游戏中比分是如何发展的，这里有一个例子。游戏进程显示在下表中，每行一招。每墩牌后的实际分数在左侧，其中+X是庄家的分数（-Y是防守方的分数，与alpha beta 无关）。正如我所说，一招的获胜者（宣布者或防守队）将这一招中每张牌的价值添加到他们的分数中。

卡值如下：

我正在为计算机国际象棋程序的 alpha-beta 搜索实现迭代深化，并希望包含搜索的时间限制。我想知道在深度为 5 的搜索中达到时间限制的后果。如果这个不完整的搜索找到了一个新的主要变体，那是否可以保证至少与深度为 4 的完整搜索发现的主要变异？否则，我似乎应该丢弃在 5 深度处通过不完整搜索找到的任何内容。

我正在尝试使用机会节点在游戏树中学习 alpha beta 修剪，所以我找到了一个示例并在解决我的树后对其进行了研究，它看起来像这样：

现在我有几个问题：

• 首先，如果我们想象叶子的范围是 -infinity 和 +infinity，我可以说只有被修剪的节点是最右边的节点吗？

• 另一个问题是，如果我们想象叶子的范围是从-2到2，我可以说只有下图中的圆圈区域会被修剪（或者也许我错了，它不应该被修剪）？

有一个代码实现函数，它为每个状态分配一个值（min-max 方法的两个部分）

是否有任何情况可以说 Alpha-Beta 修剪效率低下。换句话说，假设我们有一场比赛，你必须达到 27 才能获胜，而你和你的对手每次加起来可能只能使用 1,2,5。那么Alpha-Beta修剪在这里有效吗？以这种方式评估它是不是有点令人困惑，尤其是在我们的案例开始时，有很多我们并不真正关心的可能性？

我觉得我可以解释这一点，但我不能！帮助。

我想用 minimax 算法实现 PacMan 游戏，但我不能流利地理解算法的含义。我写了这段代码

我已经考虑到 Wikipedia 伪代码编写了这段代码，但是我有一个问题，我不知道如何将评估函数计算为整数，然后决定返回一个动作，我应该只返回一个动作。评估函数是计算一次移动还是在节点的所有可能移动中选择一个？

更新

更新 1

我试过这个（第 2 行）：我添加了更改节点颜色作为字母函数中的第一条指令。我得到这个结果：

绿色节点是访问节点。看起来，算法会正确抛出节点，对吧？但是如何在节点中输出正确的值——我也需要这样做？子值的最小值，子值的最大值（不包括修剪的分支）。

更新 2

我试图将 alpha 和 beta 输出到树节点，但没有得到正确的结果。这是代码（添加了第 18 行和第 31 行）。这是代码的结果：

在这张图片上，我展示了奇怪的地方：

第一个箭头：为什么 7 和 6 的最小值是 5？第二个箭头：为什么 4、3 和 2 的最大值是 5？奇怪的。这就是为什么我认为它现在工作正常。

老问题

曾几何时，我在这里创建了类似的问题。就像：“为什么我会收到这个错误？”。让我们回滚并创建一个新的。这个问题将是：“如何显示 Alpha Beta Pruning 算法结果？”

我在 wiki 上找到了这个算法的伪代码。可以在这里找到。

我的实现如下（它是在 JavaScript 上，但我不认为要回答这个问题你必须了解 JS 或 Java 或 C++ 等）。问题是如何在图（树结构）上输出该算法的结果？一开始我有这个树结构：

注意：我有树结构（一些链接node的 s），我将在其上使用 alpha beta 修剪算法，并且我有另一个树结构（为了显示结果，我们称之为“图”）。我用来显示图形的树的节点与我用来查找算法结果的节点相连。

因此，alpha beta 剪枝算法的代码如下。你能澄清一下我必须输出什么以及在哪里正确显示算法的过程/结果吗？

我的假设是输出 alpha 和 beta，但我认为，这是错误的。我试过了，但它不起作用。

我想显示修剪并用正确的值填充树中的所有节点。

这是我对带有 alpha beta 剪枝的 minimax 的实现：

我正在尝试实现一个侦察算法作为奥赛罗游戏的实现，我已经使用 alpha beta 修剪实现了极小极大（和负极大），现在我看不出这两种算法之间的区别，并且在线帮助不大. 我真的不想要伪代码，只是帮助理解侦察方法背后的想法，以及它与带有 alpha beta 的 minimax 有何不同。

我创建了在图表上执行 alpha beta 算法的程序。

（图片可点击查看大图）

我有这张图：

算法结果：

此图显示了问题区域：

为什么要修剪这两个节点？组的第一个节点是 5，前一个顶点的父节点是 2，所以我们比较 5 和 2。5 不小于 2，但是程序做了截断。为什么？只有当节点值小于 2 时，它才必须这样做，但在我们的情况下不是这样。

我是否误解了 alpha-beta 修剪理论中的某些内容，所以我在比较错误的值？还是我实现的问题？之前所有其他分支都运行良好，那么为什么问题只出现在这里？另一方面，看看这张图片：

程序必须修剪，修剪完成。当第一个子顶点为 5 或 1 时，为什么要修剪？

我的 alpha beta 函数（在 GitHub 上）：

这个函数是维基百科上的伪代码到 JavaScript 的翻译。

注意：如果你打开完整的源代码，你会注意到我在alpha_beta_blank这里展示了这个函数——这个函数是维基百科伪代码的翻译。实际上，我在我的程序中使用了另一个函数，但都没有正常工作，如上所述。

关于调试。您可以查看此函数（带有所有调试语句的原始函数）并看到我正在打印调试消息。调试跟踪中的这部分属于问题顶点：

带有名称的图表的一部分（以便您可以理解日志）：

GitHub 上的完整存储库。