问题标签 [alpha-beta-pruning]

我已经为 Checkers 游戏编写了一个带有alpha beta 修剪的minimax算法，现在我正在尝试使用negamax方法重写它。我希望两者是等价的，因为 negamax 只是一种编写 minimax 的技术。但由于某种原因，我的两种算法表现不同。当我在相同的输入上运行它们时，negamax 版本似乎评估了更多的状态，所以我认为 alpha beta 修剪一定有问题。

下面的代码显示了算法（minimax和negamax函数），并在底部显示了play我调用它们的函数。该evaluate函数是我用来评估两种算法状态的基本启发式方法。

任何发现错误的帮助都会非常有用。

我正在为国际象棋游戏制作人工智能。

到目前为止，我已经成功实现了 Alpha-Beta Pruning Minimax 算法，如下所示（来自 Wikipedia）：

由于这花费了太多时间复杂性（一棵一棵地遍历所有树），我遇到了一种叫做“历史启发式”的东西。

原始论文中的算法：

所以基本上，这个想法是跟踪以前的“移动”的哈希表或字典。

现在我很困惑这个“移动”在这里意味着什么。我不确定它是指单次移动还是每次移动后的整体状态。

例如，在国际象棋中，这个哈希表的“关键”应该是什么？

1. 像（女王到位置（0,1））或（骑士到位置（5,5））这样的个人移动？

2. 还是个别走法后棋盘的整体状态？

如果是1，我猜在将“移动”记录到我的历史表时没有考虑其他棋子的位置？

在实现 alpha-beta 修剪算法和接受的答案时，我正在查看函数中的奇怪行为，其中指出：“您rootAlphaBeta不会更新 alpha 值”。我想知道对代码的必要补充是什么。

我目前正在使用 expectiminimax 算法，该算法在我目前的情况下效果很好：

我无论如何都做不到

由于游戏的运作方式。

如果我继续转换我的算法，我觉得好像 alpha 会不准确。

使用我当前的设置实施修剪（除了地平线效应）是否有任何副作用，或者我只是想多了？

我一直在为 Connect Four 游戏编写 alpha-beta 修剪代码，但我似乎无法做到正确。我以为我一开始就正确地实现了它，但是算法每次都会返回第 1 列。我有两个intvalnodeVal用于确定我的 alpha 和 beta 值。当我在alphaBetaPruning()算法中将它们实例化为 0 时，该alphaBetaSearch()方法返回的列始终为 1。如果我在算法之外实例化这些值alphaBetaPruning()，alphaBetaSearch()算法会产生Null Pointer Exception

.

注意：ConnectFourBoard班级拥有董事会州最好的孩子。

任何帮助，将不胜感激！

（井字游戏：15x15 棋盘上的 2 人游戏（玩家 x 和玩家 o），其中一个玩家首先形成 5 个棋子链，然后获胜）

更多描述

所以我实现了一个井字游戏算法，它使用简单的 alpha beta 修剪..

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

这很好用，但很明显，代理返回动作需要太多时间。

然后我遇到了威胁空间搜索的想法，它的主要目的是放置“威胁”。

在这个井字游戏中，威胁正在攻击诸如“.ooo”之类的序列。“呜呜。” （如果我是玩家 o）

问题是，我不知道我应该把这个威胁空间搜索放在哪里

阿尔法贝塔函数....

我很确定这个想法是将威胁空间搜索与原始的 alpha beta minimax 结合起来

算法，，，但我不确定应该在哪里以及如何完成......

有人可以给我一些解释或真正简短的伪代码..吗？

谢谢！

我正在做一个关于 4x4 井字游戏的小项目。我正在使用 Alpha Beta Search 来寻找下一个最佳动作。在 alpha beta 搜索中，我使用了在以下算法的“实用程序”函数中调用的截止评估函数

我成功地实现了一切，但问题是效用函数没有返回负值，我真的不知道为什么！以下是函数

isMin从 MinValue 函数调用时设置为 true

isMin是 O 的移动，而 AI 的移动是 X。如果 O 获胜，实用程序应该返回 -50。但它只返回 0。我调试了程序，它实际上将 -50 分配给nodeValue（nodeValue调试器中的更改为 -50），但是当我在 Min 或 Max 函数中收到时，它为零。

注意：整个项目中使用的所有 int 都是signed int. unsigned如果您认为函数调用者是无符号的，则不使用关键字

alpha-beta 搜索的完整代码在这里： http: //pastie.org/8538015

请朋友们尽快帮忙。

我正在尝试在 C 中实现一个最佳的跳棋游戏。

为了找到机器可以做出的棋盘的最佳移动，我通过固定深度，基于棋盘的当代状态，使用 C 中的 (GLib)生成了一个n 元博弈树。

并且，为游戏树中存在的所有叶节点计算启发式值，该值定义为棋盘中剩余的机器棋子数减去玩家对手的棋子数，因为国王比棋子具有更强大的能力，启发式计数每个国王作为两个普通棋子，使用它应用 alpha beta 搜索。

更有可能的是，增加游戏树的深度最终会产生优化的移动，如果我尝试增加深度，它会花费大量时间来生成树并进行启发式搜索。

我的想法是独立生成树的第一级并在可用处理器之间分配子节点，以便使用 MPI 进一步执行？

可能吗？如果是，我如何使用 MPI 并行化树生成和启发式搜索？

如果它效率不高，请向我建议一些其他方法来实现它。谢谢。

我开发了一个使用 alpha beta 剪枝的并行跳棋（英语选秀）游戏，以便找到机器可以做出的最佳移动。我想知道增加游戏树的深度/级别并使用 alpha beta 剪枝算法搜索它是否必然会演变出最佳可能举动？

我在一台低级机器上运行，我无法将深度加起来超过 9。我已经使用以下测试用例检查了我的程序，但考虑到从 1 到 9 的深度，我得到了相同的可能移动如下。

解释在哪里，

我计算了博弈树叶节点的启发式值，即棋盘中剩余的机器棋子数减去玩家对手的棋子数，因为国王的能力比棋子强大，启发式将每个国王视为两个正常pawns，使用它应用 alpha beta 搜索。

我想我的程序运行良好，但是当我将深度增加到 9 时，为游戏树的叶节点计算的启发式值最终没有改变（如果我进一步增加深度，它可能会改变）。任何人都可以请提供一些测试用例，我可以使用它们来证明深度 9 内的效率？

我正在尝试使用 alpha-beta 修剪实现井字游戏的极小极大算法。现在我的程序正在运行，但它似乎没有工作。每当我运行它时，它似乎都会在所有方块中输入垃圾。我已经实现了它，以便我的 minimax 函数采用棋盘状态并修改该状态，以便在完成时，棋盘状态包含下一个最佳移动。然后，我将“this”设置为等于修改后的板。这是我的极小极大算法函数：

如果有人想尝试运行它，这是我的完整文件：

.cpp：http://pastebin.com/ydG7RFRX .h： http: //pastebin.com/94mDdy7x