问题标签 [alpha-beta-pruning]

上个月，我一直在用 c# 创建一个简单的国际象棋引擎，并取得了一些不错的进展。它使用简单的 Alpha-Beta 算法。

为了纠正地平线效应，我尝试实现静止搜索（并且在它起作用之前失败了几次）。引擎的力量似乎从那开始变得安静了一点，但速度非常慢！

以前，我可以在大约 160 秒内搜索到 6 层深度（处于游戏中期状态的某个地方），使用静止搜索，计算机需要大约 80 秒才能在搜索深度 3 上移动！

暴力节点计数器在深度 3 处约为 20000 个节点，而静态节点计数器高达 2000 万！

由于这是我的第一个国际象棋引擎，我真的不知道这些数字是否正常，或者我是否可能在我的静止算法中犯了错误。如果有经验的人能告诉我BF节点/静止节点的通常比率是多少，我将不胜感激。

顺便说一句，只是看一下：（每当 searchdepth 为 0 时，BF 树都会调用此方法）

我正在实现一个简单的井字游戏，只是为了尝试使用 Alpha Beta 修剪算法的 Minimax，但我被卡住了......我面临的问题是：AI 没有正确响应玩家的最后一步，我想不出我的错误在哪里。这是极小极大代码：

变量“bestMove”是一个类成员，初始调用是：

我将非常感谢一些帮助。

我正在尝试使用 alpha beta 修剪实现一个抽象的 minimax 算法。极小极大部分效果很好，但是一旦我添加了 alpha beta 剪枝，IA 就开始表现得非常愚蠢，甚至会跳过明显的动作。我不确定发生了什么事。

这就是我的递归函数的样子：

我最初的电话是这样的：

据我了解，对于相同的游戏状态，alpha-beta 剪枝应该给我与没有它的 minimax 完全相同的动作，但对于这个实现，显然不是这种情况。

编辑 1

在建议的修改之后还有另一个错误，那就是我正在修剪根节点。我编辑了代码以反映正确的答案。在执行此操作并在使用和不使用 alpha-beta 修剪的情况下运行 minimax 之后，我现在可以看到两者都产生了相同的结果，而且我能够检查从 alpha beta 加法中获得的更好性能。

编辑 2

上面发布的代码实际上没有按预期工作。我遵循了 xXliolauXx 的建议，但仍然无法正常工作。我在 depth = 0 或游戏结束时得到了正确的值，但似乎它们没有递归地传递回相应的根移动。例如，我可以看到我的启发式方法对于第一个根移动的孩子返回 -3，而对于其余的孩子返回 0。所以我希望第一个根移动报告 -3 而不是 0，因为这是计算机在执行该移动时可能发现的最坏情况。

这是我的新代码：

请注意，当 beta < alpha 时，我会在最大化时进行修剪。否则，它将始终在扫描第一个根移动后进行修剪。

这就是我启动递归的方式：

编辑 3

我想我明白了。我没有返回 alpha 或 beta，而是返回最好（或最差）的分数。我需要清理我的代码以使其更具可读性，但现在看起来是这样的：

虽然我了解 MiniMax 树和 alpha-beta 修剪概念，但我不明白为什么在许多（例如维基百科）关于 alpha-beta 修剪的资源中存在像 α >= β 这样的条件。具体来说，等于是令人困惑的。据我了解， alpha beta 返回移动 minmax 会返回，但大多数情况下它会更快。但这个例子与之矛盾：

上面是原始的 min-max 树。正如我们所看到的，它会选择得分为 3 的一步。现在让我们进行 alpha-beta：

它切断了最右边的移动，因为 3 >= 3。但是算法可以在 2 个移动之间进行选择，因为它们具有相同的分数，但是正如我们在 min-max 中看到的那样，正确的选择稍微差一些。如果算法仅指定 α > β，则不会发生这种情况，因此它也需要搜索 2。

那么这是维基百科伪代码（和许多其他资源）中的错字吗？或者我在这里误解了一些非常大的东西。

我已经实现了一个 connect 4 AI 来为我的班级参加比赛。我已经使用 alpha-beta 修剪实现了深度受限的 minimax。我们可以给出一个深度作为比赛的论据。我的程序将采取行动，然后另一个学生将采取行动，这种情况一直持续到有赢家为止。它也是一个修改过的连线 4，其中 6×7 棋盘上的全部 42 个位置都被填满，每排 4 个为一个点，最多的点获胜。

我的问题是关于 alpha-beta 修剪。我们的动作必须花费“大约 1 秒”，所以任何低于 2 秒的都应该没问题。在没有 alpha-beta 修剪的情况下运行我的程序允许在深度 6 处移动大约 1.3 秒或更短。深度 7 是不可接受的。现在，通过 alpha-beta 修剪，我可以保证我可以改变我的深度以更深吗？平均而言，我知道它会让我更深入，但我相信在最坏的情况下没有任何东西被修剪，而且我会超过时间限制。这个对吗？

我用 C 语言实现了一个国际象棋游戏，具有以下结构：

move - 表示在字符板上从 (a,b) 到 (c,d) 的移动[8][8]（棋盘）

move - 这是一个带有头部和尾部的动作的链接列表。

变量： playing_color 是 'W' 或 'B'。minimax_depth 是之前设置的 minimax 深度。

这是我的带有 alpha-beta 修剪的 Minimax 函数和 getMoveScore 函数的代码，它应该返回之前设置的某个 minimax_depth 的 Minimax 树中移动的分数。

我也在使用 getBestMoves 函数，我也会在这里列出，它基本上会在 Minimax 算法期间找到最佳移动并将它们保存到全局变量中，以便我以后可以使用它们。

我必须补充一点，我将在此处添加的三个函数中列出的所有函数都可以正常工作并经过测试，因此问题要么是alphabetaMax算法的逻辑问题，要么是getBestMoves/getMoveScore的实现。

问题主要是，当我在深度 N 处获得最佳移动（也没有正确计算）然后使用 getMoveScore 函数检查它们在相同深度上的分数时，我得到的分数与分数不匹配那些实际的最佳动作。我花了几个小时调试这个并且看不到错误，我希望也许有人可以给我一个关于找到问题的提示。

这是代码：

正如尤金指出的那样——我在这里添加一个例子：http: //imageshack.com/a/img910/4643/fmQvlm.png

我目前是白色玩家，我只有king-k和queen-q，相反的颜色有king-K和rook-R。显然，我在这里最好的举动是吃掉车或至少引起检查。棋子的移动经过测试，它们工作正常。虽然当我在深度 3 调用 get_best_moves 函数时，我在该深度得到了很多不必要的移动和负分数。也许现在它更清楚了。谢谢！

在我的方法 newminimax499 中，我有一个利用记忆和 alpha beta 剪枝的 minimax 算法。该方法通常适用于 3x3 游戏，但是当我玩 4x4 游戏时，我会为计算机做出奇怪的、意想不到的位置选择。他仍然从不输球，但他似乎并没有为赢球而战。为了说明这里的问题，我们以 2 场 3x3 和 4x4 游戏的场景为例。首先是一个来自 3x3 游戏的场景，其中玩家是 X 并迈出了第一步：

这还不错，事实上这是人们期望计算机做的事情。现在来看一个 4x4 游戏的场景。O 又是计算机，X 启动：

如您所见，计算机只是将 Os 一个接一个地按系统顺序排列，并且只有在 X 有可能获胜时才打破该顺序以阻止 X。与 3x3 比赛中看到的不同，这是一种非常防守的比赛。那么为什么 3x3 和 4x4 的方法表现不同呢？

这是代码：

以下是你们运行代码所需的其他组件和补充方法。我的 State2 类中使用的字段和构造函数：

补充方法：

getAvailableMoves，返回一个包含棋盘上空槽的数组（即可能的下一步动作）。

isGameOver2()，简单地检查棋盘的当前状态是否游戏结束。返回一个 char 'X'、'O'、'D' 和 'N'，分别代表 X won、O won、Draw 和 Not gameover。

boardShow，返回板子当前状态的矩阵显示：

score，是一个简单的评估函数，O 获胜返回 +10，X 获胜返回 -10，平局返回 0：

播种机：

还原，只是还原一个动作。例如，如果 X 已放置在位置 0，revert(0) 会在其位置设置一个“-”并更新由 setX 更改的变量：

主要方法可能如下所示：

我尝试应用其他线程关于 EXC_BAD_ACCESS 消息的建议，但没有成功。注释出现在 旁边Node Create_Child (Node Parent_Node, int item) {。

有什么见解吗？内存分配似乎不是问题，但我可能什么也没看到。

我一直在研究井字游戏，以便更好地理解极小极大算法的工作原理。以下实现无法正常工作，因为计算机可能会丢失游戏。如果程序正常运行，理论上这应该是不可能的......

我在执行极小极大或获得最佳移动方面犯了错误吗？

我以前从未实现过该算法：s

评价功能

极小极大

寻找最佳动作

谢谢你。

在试图破译主要变异 (PV) 结果时遇到问题。

“主变体是从根到叶节点的路径，其中每个节点具有相同的值。这个叶节点的值决定了根的极小最大值，称为主叶。”

PV (move,eval) 下面的游戏演示显示了这一行：

这怎么可能是一个有效的 PV，因为不是所有的 eval 节点都具有相同的值？AI永远不会输，但由于令人眼花缭乱的PV看起来很假，它给AI逻辑蒙上了一层阴影。:( 希望这只是一个 PV 错误！

如果有人在我的代码中看到错误，请告诉我。谢谢。