问题标签 [alpha-beta-pruning]

我正在为游戏开发 AI，我想将MinMax算法与Alpha-Beta pruning一起使用。

我对它的工作原理有一个粗略的想法，但我仍然无法从头开始编写代码，所以我花了过去两天在网上寻找某种伪代码。

我的问题是，我在网上找到的每个伪代码似乎都是基于找到最佳移动的值，而我需要返回最佳移动本身而不是数字。

我当前的代码是基于这个伪代码（源代码）

如您所见，此代码返回一个数字，我想这是使一切正常工作所必需的（因为在递归期间使用了返回的数字）。

所以我想我可能会使用一个外部变量来存储最好的移动，这就是我改变之前代码的方式：

现在，这对我来说是有意义的，因为只有在轮到玩家并且该动作比之前的动作更好时，我们才需要更新最佳动作。

所以，虽然我认为这是正确的（即使我不是 100% 确定），但源代码也有一个java实现，它更新了bestMove这种score < beta情况，我不明白为什么。

尝试使用该实现导致我的代码选择对面玩家的最佳移动，这似乎不正确（假设我是黑人玩家，我正在寻找我可以做出的最佳移动我期待的是“黑色”动作而不是“白色”动作）。

我不知道我的伪代码（第二个）是否是使用带有alpha-beta 修剪的MinMax找到最佳移动的正确方法，或者即使在score < beta的情况下我也需要更新最佳移动。

如果您愿意，请随时提出任何新的和更好的伪代码，我不受任何约束，如果它比我的更好，我不介意重写一些代码。

编辑：

由于我无法理解这些回复，我想也许这个问题并没有问我想知道什么，所以我想在这里写得更好。

假设我只想为一个玩家获得最佳移动，并且每次我需要新移动时都会将这个玩家（即最大化器）传递给MinMax函数（这样会minmax(2, black, a, b)返回黑色玩家的最佳移动，同时minmax(2, white, a ,b)返回最适合白人玩家），您将如何更改第一个伪代码（或源代码中的java实现）以将这个给定的最佳移动存储在某处？

编辑2：

让我们看看我们是否可以让它以这种方式工作。

这是我的实现，你能告诉我它是否正确吗？

编辑 3：

基于@Codor 的回答/评论的新实现

我不知道我做对了还是做错了，但是我又回到了发布问题时遇到的问题：

调用minMax(Integer.MIN_VALUE, Integer.MAX_VALUE, 1, PlayerType.Black)返回只能由白色玩家完成的移动，这不是我需要的。

我需要给定玩家的最佳移动，而不是整个棋盘的最佳移动。

我试图为我的游戏构建一个游戏树，以便找到我的下一步行动。首先，我使用递归算法构建树，然后，使用 alpha - beta 剪枝算法找到最佳移动 Im。我想使用 alpha - beta 修剪来构建游戏树，以最小化游戏树的大小，但我在编写算法时遇到问题。你能帮我在扩展算法中添加 alpha - beta 修剪吗？

这是扩展算法：

这是 alpha - beta 修剪代码：

谢谢你！

我最近尝试实现连接 4 的 minimax 算法来为其创建一个机器人，以保持简单（可能使事情复杂化）我使用了 Python。

这是我到目前为止所拥有的：

有时，它有点工作。我认为它没有正确评估每一步。我已经玩了一段时间了，似乎找不到哪里出了问题。

任何帮助将不胜感激，谢谢。

我正在尝试在 java 中实现 Mini Max & Alpha Beta Pruning 算法，由于某种原因，尽管算法访问了 24,911 个节点，但 Pruning 算法不执行单个修剪。GameNode 值初始化为 MaxNodes 的 -99 和 MinNodes 的 99 以及 Alpha=-99 \ Beta=99。游戏称为“Nim”，数值为 1 或 -1，输赢，不得分。知道为什么修剪不会发生吗？

这是修剪的代码：

您好，我正在尝试从以下代码中以国际象棋为例来理解 alpha beta 剪枝算法：

这是我从中获得的博客的链接：LINK（如果您喜欢突出显示的语法，可以从链接中查看代码）

我不明白的是，在 alpha beta 修剪中，当你在树上更高时，alpha 和 beta 变量的值有时必须改变。我附上了一张图片来解释我的问题 - 虽然我理解步骤 1)、2) 和 3)，但我没有得到 4) 步骤。我知道 4) 步骤应该如图所示，但我不知道值发生变化的那一步代码中发生了什么。我仔细地遵循了代码，但由于某种原因，我最终在 4) 步骤中得到了 a = 5 和 b = 5，这很荒谬，因为这意味着右边的分支将被删除，这显然是错误的。

我有一个经典的极小极大问题求解器，带有额外的 alpha-beta 修剪实现。

没有 alpha-beta 实现的 Minimax 基本上是对整个树进行深度优先搜索，直到某个最大深度。对于 alpha-beta，它的作用相同，只是它会修剪一些分支，这无论如何都会导致更糟糕的结果。

编辑：在进一步检查代码后，我在一行代码中发现了一个错误，导致程序“作弊”而不遵循某些动作。现在实际的加速因子是 3.6。很抱歉浪费大家的时间.. 今天在计算方面没有突破。：/

我想为类似跳棋的游戏实现 AI（人工智能）

我写了以下方法：

-方法

这将返回按权重排序的所有有效移动的列表，其中权重是根据移动的类型和位置计算的

-方法

将这些移动应用到棋盘上，如果某个棋子被杀死，则返回 1

-方法

恢复板子以前的状态。

这是一个零和游戏，因此 AI 应该最大化玩家颜色的棋子并最小化对手的棋子。

为此，最好的方法似乎是使用带有 alpha-beta 修剪的 min-max。这具有以下伪代码

但我不明白如何适应我的问题。有人可以帮助我吗？

编辑

我有这个 MinMax 但没有修剪

如何编辑以获得 alpha beta 修剪？

这个周末我的编程乐趣是用 F# 写一个 300 行的黑白棋程序。可能需要几个周末才能了解如何使字母搜索并行化，这实际上超出了这个问题的范围。

我发现，虽然我无法想出一些“纯功能”的方式来实现字母函数。即没有任何可变状态。

有什么好主意吗？

我想到的唯一想法是编写类似 Seq.foldUntil() 函数，其中累加器状态用于存储状态更改。并且可以通过传入的 lambda 函数取消。

也许看起来像这样：

这里不纯的alphabeta函数......

在等待答案的同时，我决定尝试一下我的 transformWhile 想法，这就是它的结果：

一些交互式测试表明它适用于一些琐碎的东西，所以我决定编写一个新版本的字母表，现在看起来像这样：

这看起来像函数式编程专家会做的事情吗？或者你会怎么做？

虽然我之前的蛮力搜索是尾递归的（没有建立调用堆栈），但这个纯函数版本不再是尾递归。谁能找到一种方法让它再次尾递归？

晚上好。如果问题格式不正确，我深表歉意，因为这是我第一次在这里发帖。

我正在寻找特定练习的帮助，因为我已经集思广益了将近两个小时，但找不到任何合适的解决方案。练习如下：给定一定数量的货车，两个小偷将争夺最高的利润。

第一个小偷，比方说 A，首先开始采摘。窃贼可能会选择列表中当前可用的第一辆或最后一辆马车。然后从列表中删除选中的货车，并将其值添加到相应小偷的计数器中。练习的目的是为小偷 A 获得尽可能高的利润，同时确保小偷 B 也尝试这样做。

例如，如果我们有以下输入：

6
10
150
3
7
9
9

这意味着有 6 辆货车，其值分别为 10、150、3、7、9 和 9。如果遵循最优策略，则输出应该是 166，假设两个小偷都遵循最优策略。不过到现在为止，我得到的只有169，理论上这是无论小偷B怎么玩，小偷A都能得到的最高成绩。

我没有看到如何确保两个小偷都遵循代码方面的最佳策略。据说这是一个练习，您必须检查所有可能的组合，但是我如何查看结果并找出两个小偷都遵循了最佳策略？有任何想法吗？

编码：

我正在用 javascript 编写井字游戏。我完成了 GUI 等，但我仍然对 AI 有问题。我使用 Alpha-beta-Prune 来找到获胜的动作。但是，我的代码从来没有给出可以赢得比赛的动作。我做了很多研究，但仍然不知道我的代码有什么问题。你们能在这里看看我的主要人工智能部分吗？我的想法是创建一个存储移动的二维数组：1 是人类，-1 是 AI，0 是空的。初始化调用： var test = getBestMove(-1); `

获得最佳移动功能：

阿尔法-贝塔搜索：

我没有使用评估功能，因为我认为 alpha-beta 应该能够在没有它的情况下找到胜利。