问题标签 [alpha-beta-pruning]

我正在尝试将 alpha beta 修剪算法应用于这个给定的树。

当我点击节点 C 时我被卡住了，因为在展开 B 的所有子节点后，我给 A >= -4，然后我展开 C 得到 I =-3，它大于 -4 (-3 >= -4) . 因此，我是否将 A 更新为 -3？如果是这样，那么我之后是否修剪 J 和 K 因为 -3 >= -3 ？当我完成这个例子时，我修剪了 J、K、M 和 N。我真的不确定这个 =(

编辑：

另一个问题：在探索 B 并将 B 的值传递给 A 之后，我们是否将该值传递给 C 进而传递给 I？我看到一个例子就是这种情况。这是：http ://web.cecs.pdx.edu/~mm/AIFall2011/alphabeta-example.pdf

然而，在这个例子中，http://web.cecs.pdx.edu/~mm/AIFall2011/alphabeta-example.pdf，它似乎没有传递值，而是它似乎只向上传播值。我不确定哪一个是正确的，或者它是否有什么不同。

我正在尝试在 Python 中使用 minimax for Connect 4 作为个人项目来实现 AI。目前我有这个。

但是，由于某种原因，计算机不会做出获胜的举动。例如，给定这个棋盘，计算机应该在第 4 列进行游戏，从而获胜。但是，它实际上在第 3 列中播放。

好的，我的问题对于玩过棋盘游戏编程的人来说应该很熟悉，所以这里是：

• 我已经实现了 MiniMax 算法的一个变体（返回移动而不是最小/最大值）。
• 我也尝试将其设置为 alpha-beta，尽管它最终完全失败了。

所以，这是我的 MiniMax 代码：

有什么想法可以调整上述内容以使其成为 Alpha-Beta 搜索吗？

这是我对 Alpha-Beta 转换的尝试（失败得很惨）：

提示（避免任何误解）：

• 该this->eval()函数从玩家 A 的角度返回一个分数。例如，+100 分表示该位置有利于玩家 A，而 -100 分表示该位置有利于玩家 B。

• MINUS_INF并PLUS_INF分别被定义为一些任意小的和大的值。

• 这不像家庭作业或任何东西（如果是的话，我很可能永远不会有兴趣玩这些东西......哈哈）

• Move是一个简单的类，包含有关移动的详细信息，以及它的相应值（由eval函数分配。

• HASHMAKE并且UNHASHMAKE只是 2 个 move-(un)making 和 move-(un)hashing 宏，应该没什么区别。

• MAXMOVE定义如下：#define MAXMOVE(A,B) (((A)->value>=(B)->value)?(A):(B))

• MINMOVE定义如下：#define MINMOVE(A,B) (((A)->value<=(B)->value)?(A):(B))

我必须为 Android 实现一个黑白棋游戏。我已经设法实现了所有游戏，功能齐全，但问题是我没有人工智能。事实上，每走一步，计算机都会移动到使他获得最多棋子的位置。

我决定实现和 alpha-beta 修剪算法。我在互联网上做了很多关于它的研究，但我无法得出最终结论如何去做。我尝试实现一些功能，但无法实现所需的行为。

我的棋盘存储在 Board 类中（在这个类中，每个玩家占用的棋子存储在一个二维 int 数组中）。我附上了一张小图（对它的外观感到抱歉）。

图表：https ://docs.google.com/file/d/0Bzv8B0L32Z8lSUhKNjdXaWsza0E/edit

我需要帮助来弄清楚如何在我的实现中使用 minimax 算法。

到目前为止，我所理解的是，我必须对董事会的价值进行评估。

为了计算棋盘的价值，我必须考虑以下因素： - 自由角（我的问题是我必须只关心自由角，或者我现在可以采取的那个？！这里的困境） . - 棋盘移动性：检查当前移动后可移动的棋子数。-棋盘的稳定性……我知道这意味着棋盘上不能翻转的棋子数量。- 移动将提供给我的件数

我计划实现一个新的 Class BoardAI，它将我的 Board 对象和部门作为参数。

你能告诉我我应该如何实现这个人工智能的逻辑思路吗？在进行深度计算时，我需要一些有关递归的帮助，但我不明白它是如何计算最佳选择的。

谢谢！

我将参加我学校的棋盘游戏 AI 比赛，并试图提出一些关于并发的想法以获得优势。我很可能会处于劣势，因为我将在 java 中实现它，而且我知道 c 或 c++ 会快得多。

似乎您不能将游戏树分成两半，因为移动顺序应该首先留下最好的移动，而且在给定深度传达当前的 alpha/beta 似乎很困难，甚至可能是不可能的. 我也将使用需要同步的转置表。

除了搜索之外，是否有第二个线程可以做的事情可以帮助搜索或提供某种类型的速度提升。每个 AI 将有 5 秒的时间进行移动，并且您的程序可以在对手思考的同时运行。

任何输入，无论多么晦涩，都将不胜感激。

我知道以前有人问过这种问题，但我无法解决我的疑问。我有一个简单的黑白棋引擎（实际上它玩得很好），它使用下面的类来获得最好的移动：

我有一个bestFound实例变量，我的疑问是，为什么必须调用

并传递它？该代码有效，但对我来说似乎很奇怪！

是否有“更好”的方法来获得最佳移动或主要变化？我真的不是递归专家，这很难调试和可视化。谢谢！

**PS：您可以在https://github.com/fernandotenorio/克隆它

我正在尝试用 alpha-beta 修剪为 Java 中的跳棋游戏实现 minimax。我的极小极大算法完美运行。我的代码使用 alpha-beta 代码运行。不幸的是，当我与标准 minimax 算法玩 1000 场比赛时，alpha-beta 算法总是落后 50 场左右。

由于 alpha-beta 修剪不应该降低移动的质量，只是实现它们所需的时间，所以一定是有问题的。但是，我已经拿出纸笔，画出了假设的叶节点值，并使用我的算法来预测它是否会计算出正确的最佳移动，并且似乎没有任何逻辑错误。我使用了这个视频中的树：Alpha-Beta Pruning来跟踪我的算法。它在逻辑上应该做出所有相同的选择，因此是一个有效的实现。

我还将打印语句放入代码中（它们已被删除以减少混乱），并且值正在正确返回它出现并且确实发生了修剪。尽管我尽了最大的努力，我还是无法找到逻辑错误的所在。这是我实现这一点的第三次不同尝试，他们都遇到了同样的问题。

我这里不能贴出完整的代码，太长了，所以我已经包含了与错误相关的方法。我不确定，但我怀疑问题可能出在非递归 move() 方法中，尽管我无法在其中找到逻辑错误，所以我只是在它中翻来覆去，可能会做一些事情没有押韵或理由，更糟而不是更好。

是否有从 for 循环中的递归调用中恢复多个整数值的技巧？它适用于我的 minimax 和 negamax 实现，但 alpha-beta 修剪似乎会产生一些奇怪的结果。

我对 PLINQ 有一些奇怪的结果，我似乎无法解释。我一直在尝试并行化 Alpha Beta 树搜索以加快搜索过程，但它实际上减慢了搜索速度。我希望当我提高并行度时，我会线性增加每秒的节点数......并在修剪被推迟到以后处理时处理额外的节点。虽然节点数符合预期，但我的时间没有：

非 plinq，访问的节点：61418，运行时间：0:00.67

并行度：1，访问节点：61418，运行时间：0:01.48

并行度：2，访问节点：75504，运行时间：0:10.08

并行度：4，访问节点：95664，运行时间：1:51.98

并行度：8，访问节点：108148，运行时间：1:48.94

有人帮我找出可能的罪魁祸首吗？

相关代码：

然后是用于在树的各个级别之间共享 Alpha Beta 参数的数据结构......

我正在尝试学习人工智能以及如何在程序中实现它。最容易开始的地方可能是简单的游戏（在本例中为井字游戏）和游戏搜索树（递归调用；不是实际的数据结构）。我在有关该主题的讲座中发现了这个非常有用的视频。

我遇到的问题是对算法的第一次调用需要很长时间（大约 15 秒）才能执行。我已经在整个代码中放置了调试日志输出，似乎它调用了算法的某些部分的次数过多。

以下是为计算机选择最佳移动的方法：

makeMove如果该点为空并返回一个值（-1 - 人类获胜，0 - 平局，1 - 计算机获胜，-2 或 2 - 否则），则该方法进行移动。虽然我相信错误可能出在getAllLegalMoves方法中：

总而言之：是什么导致我的电话，选择最好的举动，花了这么长时间？我错过了什么？有没有更简单的方法来实现这个算法？任何帮助或建议将不胜感激，谢谢！

我必须创建一个必须与其他 AI 竞争的 AI。

两个 AI 将在相同的硬件上运行，具有相同的处理时间和内存。我知道对手 AI 将使用带有 alpha beta 剪枝的 minimax 算法。

现在我的问题是 - 有什么方法可以击败这样的对手？如果我自己使用 minimax - 那么两个 AI 都可以完美地预测彼此的动作，并且游戏会根据游戏的固有属性（先手获胜等）来解决。

显而易见的解决方案是以某种方式进一步了解可能的移动，这将允许更好的评估 - 因为处理器时间相同，我无法评估更深入的深度（假设相反的 AI 代码同样优化）。我可以使用预先计算的树来获得额外的优势，但如果没有超级计算机，我当然无法“解决”任何非平凡的游戏。

故意选择一个非最佳节点，例如 alpha beta 会修剪的节点，是否有一些价值？这可能会对对手造成 CPU 时间损失，因为他们必须返回并重新评估树。这会对我造成惩罚，而且我必须评估 minimax 树 + alpha beta 以查看 alpha beta 会修剪哪些节点而不会获得任何直接收益。

还有哪些其他策略可以针对这样的对手进行优化？