问题标签 [alpha-beta-pruning]

我正在使用 Python 为游戏 2048 编写 AI。它比我预期的要慢得多。我将深度限制设置为 5，但仍然需要几秒钟才能得到答案。起初我以为我所有功能的实现都是垃圾，但我想出了真正的原因。搜索树上的叶子比应该有的多得多。

这是一个典型的结果（我数了树叶、树枝和展开的数量）：

还有一个，很好的衡量标准：

如您所见，搜索树上的叶子比我使用朴素极小极大时的叶子要多得多。这里发生了什么？我的算法发布在下面：

有人请帮帮我。我多次查看此代码，但无法确定问题所在。

我想使用 alpha beta pruning 在 c++ 中实现井字游戏。我使用这个链接来帮助我。 http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGame_TicTacToe_AI.html

我用 c++ 编写了这段代码。但这没有运行。每次轮到计算机时，它都会返回在 minimax 函数中默认设置的位置 [-1,-1]。我不知道错误在哪里。请帮助。谢谢。

我正在为国际象棋编写 Minimax 算法。

我得到了不带 alpha beta 剪枝的 minimax 和带 alpha beta 剪枝的 minimax 的不同最终结果值。

我的伪代码如下。谁能帮我？

极小最大值（）

字母()

Board 代表一个董事会。对于每一步，我都会在传递的 Board 对象的副本上进行移动，然后将这个临时 Board 传递给进一步的调用。

evaluateBoard(Board b) 接收一个 Board 并根据给定的 Board 场景计算分数。

我目前正在为国际象棋编写一个带有 alpha beta 修剪的 minimax 算法。

从我看到的所有示例中，极小极大算法将返回一个 int 值，该值表示最佳得分或最佳棋局将产生的棋盘状态。

我的问题是我们如何返回与得分返回值相关的最佳移动？

例如，我的字母表（）在下面的伪...

在我的 minimax/alphabeta 的实现中，我有一个 Board 对象，它代表棋盘，棋子可以在其上移动以代表不同的棋盘纹理/游戏状态。

我的函数evaluateBoard(Board b)接受一个板并计算参数板的板状态值。

本质上，evaluateBoard() 为我提供了作为最佳移动值的字母表的最终 int 结果值。但是，我看不到 evaluateBoard() 返回导致最终得分的移动的方法。即使我要返回一些包含分数值和片段信息的对象，我也不确定如何在树的顶部获得给我最终最佳分数的片段的信息。

有谁知道我如何访问/返回给出最佳分值的最佳动作的信息？我是否错过了 mini max 算法中的一个关键元素和/或我是否必须以不同的方式实现 alphabeta()？

编辑：

例如，假设 minimax 从以下移动中返回最佳分数：e4、e5、nf3、nc6。我所拥有的将返回棋盘情况的数值。我怎样才能返回“e4”？E4 是导致最高值的移动。

谢谢。

我已经为类似国际象棋的游戏制作了一个 negamax 算法，我想知道如何使用最终的棋盘值结果。我知道 negamax 算法的最终回报代表了玩家采取最佳行动后棋盘的价值，但这并不是完全有用的信息。我需要知道那个动作是什么，而不是它的价值。

这是代码：

我想在确定 bestValue 后重新评估当前匹配状态的孩子。然后我遍历它们并找出其中哪些孩子的 stateScore 等于 bestValue。但这行不通，因为无论如何他们中的很多人都会有相同的 stateScore，这是他们可以导致的结果......

Alpha-Beta Pruning 的 MinMax 如何应用于 Stratego 游戏？你能模拟一下它是如何工作的。谢谢！

通过基本的 Minimax 搜索，使用 OMP For 在多个线程之间拆分工作似乎很容易。例如 -

然而，似乎这对于 Alpha-Beta 修剪来说是不可能的，至少在我的理解中是这样。

在 OpenMP 中，如果要使循环并行，则要求 For 循环只能有一个入口/出口点。然而，Alpha-Beta 剪枝打破了这个规则，因为只要需要完成剪枝，就有可能跳出循环（在上面的伪代码中，这将在 β 小于或等于 α 时发生）。

所以我的问题是，有没有办法解决 OpenMP 的这种限制？我想使用 OpenMP 并行运行我的 Alpha-Beta 搜索，但这个限制让我现在很难过。

我正在尝试在 Connect Four 类型的游戏中实现计算机播放器。Alpha-beta 修剪似乎是实现这一目标的最佳方法，但我似乎无法弄清楚我做错了什么。

以下是我想出的代码。它从初始根状态开始。对于每一个可能的有效移动（如果没有修剪），算法：制作状态的深层副本，更新状态（增加深度，切换转弯，添加一块，设置启发式值），并将这个新状态添加到根的继任者列表。

如果新状态不是叶子（即在最大深度），它会递归地继续。如果它是叶子，算法检查根的值和适当的局部 alpha/beta 值并相应地更新。在检查了所有可能的有效选项后，算法将返回适当的本地 alpha/beta 值。

至少，这是我的本意。每次运行返回值 0。这里要求的是初始化代码：

有人可以帮我理解如何使用 alpha-beta 修剪算法吗？我正在制作一个类似于连接四的游戏。唯一的区别是没有对角线获胜，玩家可以在任何给定时间标记一个正方形（当然，除非它已经被占领）。我想我理解如何编写算法，我只是觉得我用错了。我一直在做的是有一个看起来像这样的 for 循环

我遇到的问题是alphabet的第一次运行返回最大值，因此下一个值都不是更大的，并且板将设置为板[0] [0]。有谁知道我做错了什么？

这是使移动的功能

所以这是我更新的代码，仍然无法正常工作

我稍微改变了算法，这样我就可以清楚地看到 min 和 max 发生了什么，但是它仍然不能正确播放

我正在学习游戏树（国际象棋），并且想知道 alpha beta 修剪是否基于两个玩家是“完美玩家”的假设。如果一个不完美的人玩了一个坏棋，会发生什么？当对手并不总是选择最佳移动时，alpha beta 修剪如何工作。