问题标签 [alpha-beta-pruning]

我正在尝试为两人 8x8 棋盘游戏创建一个 AI 对手。经过研究，我发现 Minimax 算法足够方便完成这项工作。我正在创建的 AI 对手将与其他 AI 对手或人类对战。

我对理解 minimax 算法有疑问。

我正在尝试只创建一个 AI 对手，但在网上找到的解释说我需要为两个玩家（最小玩家和最大玩家）编写代码，正如我从下面的伪代码中所理解的那样。

我可以进一步理解，最大玩家将是我要开发的 AI，而最小玩家是对手。

我的问题是为什么我必须为最小和最大玩家编写代码才能返回最佳移动？

下面给出的伪代码基于 C#。

提前致谢。

所以我为我的基于国际象棋的益智游戏实现了一个极小极大搜索。在这种情况下，搜索确定下一步的 AI 棋子。

它自己的极小极大工作正常，它返回预期的移动，但是当我实现 alpha beta 修剪时，极小极大每回合返回相同的两个值。例如，当前位于 (0,0) 的 AI Rook 在从极小极大移动时可能会收到 (1,0)，而下次它向极小极大询问它的移动时，它将收到 (0,0)。无论我在评估函数中进行什么更改，都会发生此循环。

游戏状态由用户的位置、棋子的位置和代表棋盘本身的瓷砖阵列组成。我在这里使用我自己的节点类（实际上应该称为 Pair），以便将每个 Tile 与评估函数给出的相应值一起存储。

我如何实现我的 alpha beta 修剪有问题吗？任何意见是极大的赞赏。如果需要更多信息，请询问，我会提供我所能提供的。

我正在为国际象棋编写一个带有 alpha-beta 修剪的 minimax 算法，除了它生成的第一步之外，无法让算法返回任何内容。我一直在敲我的头，但无法弄清楚出了什么问题。代码有点乱，急需重构，但也许你能看到我没有看到的东西。

我已经验证了我的 evalNaive' 函数按预期工作（非常简单，只需根据材料评估板）。

编辑：

我的一些数据类型的定义：

其中 Flags 是一个字符串列表，告诉你一些事情，例如白色的后翼车可以城堡，而 Color 是轮到谁的颜色。

编辑2：

下面是调用 alphaBeta 减去 maxGame $ 的结果，产生包含分数的元组列表和获得分数的移动：

（坐标 (x,y) 是 x 文件和 y 等级）

如您所见，它们都返回为 0。知道 evalNaive' 有效，问题出在递归函数的某个地方。

EDIT3：以 5 的深度运行相同的代码并获得以下潜在动作列表：

因此，就我的算法而言，它遇到的第一步似乎是最好的。我是否没有深入到搜索树中以获得任何有意义的东西？

我正在尝试使用 alpha/beta 修剪实现 MiniMax 算法。完全卡住了，看不到我错在哪里。MiniMax 类包含一个状态和一个动作。getAction 方法返回一个 Action（应该是最好的操作）。Game 对象有两个方法，如果状态是“结束状态”，isTerminal 返回 true，即该状态没有更多的孩子。getUtility 返回与结束状态关联的值。

我试图通过使用反击来决定是 Max 还是 Min 转弯。目前算法没有返回正确的动作，在这个阶段我只专注于让扩展顺序正确，让修剪位工作。

}

我正在尝试使用转置表实现增强的 alpha-beta min-max 修剪。我使用这个伪代码作为参考：

http://people.csail.mit.edu/plaat/mtdf.html#abmem

该算法的三个问题：

1. 我相信我应该在每个保存的转置表条目中存储深度（= 到叶层的距离），并且仅在 entry.depth>=currentDepth （= 条目与叶层的距离更大或相等）时才使用条目。上面的伪代码中没有显示，也没有在那里讨论，我想确保我理解正确。

2. 我想为每个位置存储最佳移动，以将其用于移动排序并在搜索停止后提取最佳移动。在纯粹的 min-max 中，哪个动作是最好的很明显，但是当使用 alpha-beta 截止值迭代时哪个动作是最好的？我可以假设给定位置的最佳移动是循环结束时找到的最佳移动（有或没有截止）吗？

3. 在迭代深化方案中执行此算法时 - 我应该在每次深度增加之前清除转置表吗？我认为不是，我希望您使用先前迭代中存储的位置，但我不确定这些信息是否足以进行更深入的搜索（应该在检查表条目深度时）？

将转置表和 MTD(f) 添加到国际象棋的纯 alpha beta 修剪中的预期性能增益是多少？

在我的纯 alpha beta 修剪中，我使用以下移动排序：

• 主要变化（来自先前的迭代深化迭代）
• 换位表的最佳移动（如果有的话）
• 捕获：最高捕获然后最低捕获
• 杀手锏
• 历史启发式

通过上述设置，我得到以下深度 9 的平均结果：

• 纯 alpha beta：访问的 X 个节点
• alpha beta+TT：访问了 0.5*X 个节点
• MTDF(f)：访问了 0.25*X 个节点

我期望得到更好的结果，我想确定它是否能得到最好的结果，或者我的实现是否有问题？

我以 0.1 pawn 的精度搜索。

我正在使用 alpha-beta 修剪和在 MTD(f) 算法内部调用的转置表向我的国际象棋引擎添加静止搜索。在我的主要搜索中，在达到 depth=0（叶节点）后，我调用 Quiescence 搜索，它被实现为没有转置表的简单 alpha beta 修剪（因为测试表明，没有 TT，搜索只捕获工作得更快）

我注意到有关此主题的伪代码中未涵盖的内容：当我在主搜索中处于 depth=0（叶）并且我调用静止搜索函数来获得节点评估时，我认为我也应该获得评估类型：精确，阿尔法或贝塔：

在典型示例中，叶节点评估始终作为“精确”值存储在 TT 中，但是当节点评估基于通过捕获的 alpha beta 搜索并且此搜索以非 (-inf,+inf) 的 alpha-beta 边界开始时，我认为 QuiescenceAlphaBetaSearch 的结果并不总是准确的值，如果它存储在 TT 中，它应该标有从静止搜索返回的标志，我正确吗？

我不确定将当前的 alpha 和 beta 从主搜索传递到 Quiescence 搜索是否在数学上是正确的，所以我也希望能确认这个主题。

我已经为我的国际象棋游戏实现了 alpha beta 算法，但是最终做出一个相当愚蠢的举动需要很长时间（4 层数分钟）。

两天来我一直试图找出错误（我假设我犯了一个），我非常感谢我的代码中的一些外部输入。

getMove 函数：为根节点调用，它为它的所有子节点（可能的移动）调用 alphaBeta 函数，然后选择得分最高的移动。

alphaBeta 函数：

编辑：我应该注意，evaluateBoard 只评估棋子的移动性（可能的移动次数，捕获移动根据捕获的棋子获得更高的分数）

谢谢你。

我正在探索如何在带有 alpha-beta 修剪的四人游戏中使用 Minimax 算法。

因此，我查看了有关 Connect4 播放器策略的源代码，发现了这个评估函数：

我在这个 PDF 中找到了所有这些代码：http ://ryanmaguiremusic.com/media_files/pdf/ConnectFourSource.pdf

我只是想了解此评估功能的工作原理并决定要采取的最佳行动……有人可以帮我吗？这将不胜感激。

我正在为游戏筷子制作一个 C++ 程序。

这是一个非常简单的游戏，总共只有 625 个游戏状态（如果考虑到对称性和无法到达的状态，它会更低）。我已经阅读了 minimax 和 alpha-beta 算法，主要用于井字游戏，但我遇到的问题是，在井字游戏中，不可能循环回到以前的状态，而这很容易在筷子中发生。因此，在运行代码时，最终会出现堆栈溢出。

我通过为以前访问过的状态添加标志来解决此问题（我不知道这是否是正确的方法。）以便可以避免它们，但现在我遇到的问题是输出不像预期的那样对称。

例如，在游戏的开始状态下，每个玩家都有一根手指，所以它们都是对称的。程序告诉我，最好的动作是用左手击打我的右手，而不是相反。

我的源代码是 -

我将移动以一种以 5 为底的十进制系统传递，因为每只手的值都可以从 0 到 4。

在我输入状态的代码中 -

输出说我应该将右手 (1) 击到对手的右侧 (3)，但没有说我应该将其击到对手的左侧 (也是 3)

我认为问题在于我处理无限循环的方式。

什么是正确的方法？或者，如果这是正确的方法，那么我该如何解决这个问题？

另外请让我知道如何改进我的代码。

非常感谢。

编辑：

我已将我的 minimax 函数更改如下，以确保无限循环的得分高于失败，但我仍然没有得到对称性。我还做了一个函数来增加乐谱的深度

这是增加深度的功能 -