问题标签 [negamax]

我有一个尽可能简单的负最大算法，用于评估井字游戏中的位置。游戏状态以数组形式存储在 numpy 中，X 的棋子用 1 表示，O 的棋子用 4 表示。

我刚才在测试这个，发现：

这意味着我的算法认为它已经找到了一种方法，让 X 在井字游戏中赢得七层，这在体面的游戏中显然是不可能的。我不知道如何让它打印它找到的最佳动作，所以在调试它时遇到了真正的麻烦。我究竟做错了什么？

至少我已经为此工作了几天。测试似乎显示正在返回正确的值。我的问题是能够获取best_move价值并将其打印出来。我设置了suggested_move方法并尝试使用return suggested_move(best_move)，但它会触发每个级别备份树的方法。它还返回错误的值，我猜这是因为它在深度回到 0 之前就停止了。

在我的 minimax 中，我有一个类似的设置，不同之处在于深度在连续调用时增加（而不是减少）。重点是我可以说if depth == 0 p best_move。所以我摸不着头脑，因为使用相同的条件我在这段代码中得到一个 nil 类错误。

我正在尝试使用转置表实现 alpha beta 修剪，我在维基百科中找到了该算法的伪代码：https : //en.wikipedia.org/wiki/Negamax#cite_note-Breuker-1 但是我相信这个伪代码是错了，我认为 alphaOrig 没用，而不是：

它应该是：

谁能确认我是否正确或向我解释为什么我错了，谢谢！

这里的伪代码：

我正在为“连锁反应”游戏实施 Negamax 版本。这里有一个运行良好的算法版本：

现在，我想将 alpha-beta 修剪添加到我的代码中。所以我在网上看到了伪代码，我修改了这样的代码：

问题是 alpha-beta 版本返回给我一个错误的结果，我不知道为什么。有人可以帮我弄这个吗？

我正在根据此处的伪代码使用 alpha/beta 转置表实现 negamax ，大致使用以下算法：

我也在使用迭代加深，用逐渐更高的深度调用 NegaMax。

我的问题是：当我确定我已经没有时间了（2a. 在移动循环的开始）时，正确的做法是什么？我是立即放弃（不更新换位表）还是只是打破循环（保存我所做的任何部分工作）？

目前，我在该点返回 null，表示搜索在“完成”该节点之前被取消（无论是通过尝试每一步还是通过 alpha/beta 切割）。null 被向上传播并向上传播，并且向上传播的每个节点都通过返回来保释，因此第 3 步永远不会运行。

本质上，我只在节点“完成”时将值存储在 TT 中。随着迭代深化，我不断看到的场景：

1. 我很快就通过了 1-5 的深度，所以 TT 的深度 = 5，类型 = 精确条目。
2. depth = 6 搜索需要很长时间，所以我放弃了。

我最终返回转置表中的最佳移动，这是我在深度 = 5 搜索期间找到的移动。问题是，如果我开始一个新的 depth = 6 搜索，感觉就像我从头开始一样。但是，如果我保存我发现的任何部分结果，我担心我会损坏我的 TT，可能是通过用不完整的深度 = 6 条目覆盖完成的深度 = 5 条目。

I keep getting weird behavior in my negamax-based AI when I try to implement QuiesenceSearch. I based it on the pseudo-code from here:

And this is my code:

Namely, the AI seems to behave as-if making the absolute worst move (killing it self) is the way to go.

CalculateBoardScore always returns from the color == 1 side, hence the multiply by color.

有没有办法并行化以下 negamax 算法？

我一直在尝试为用 Unity3D 制作的跳棋游戏实现一个好的 AI，通过在线搜索我发现最好的选择是 MiniMax/Negamax，所以我创建了这个类：

其中 IMiniMaxNode 是以下接口：

实际的实现是这样的：

然后我在我的 CheckersAI 类中使用它：

AI 在大部分比赛中似乎都可以正常工作，但有时会做出明显错误的决定（例如，无缘无故地牺牲 2 个棋子），有时它会反转“无可能移动”情况的价值，因为它会将其分配为正数无穷大（胜利），而它应该是负无穷大（失败）。

我 90% 确定问题出在某个地方的错误标志上，但我一直在尝试每种方法中所有可能的标志组合，而 AI 总是做出意想不到的决定，我正在以黑队 (-1) 和白队（+1）。

谁能帮助我，指出我可能做错了什么？我试图包含所有相关的代码并评论每一个重要的段落。谢谢你！

我刚刚为跳棋实现了一个很好的评估功能。当前的实现使用线程和每个单独的转置表。

我为根节点（初始棋盘位置）中可用的每个移动生成一个线程，然后使用带有 alpha-beta 修剪的 negamax 对其进行分析。我总是为 CPU 玩家找到最佳动作。我不分析用户可用的动作。

现在我有两个考虑：

1. 我可以在所有这些线程之间安全地共享一个转置表吗（线程当然会同步）？

2. 每次我开始新的分析时，我应该清除表格还是可以安全使用？

有什么想法吗？

我是人工智能的新手。我的任务要求我用 Python 编写一个程序，以最佳方式玩 Nim 游戏（使用NegaMax算法）。

如果您对游戏不熟悉，这里有一个简短的说明：

Nim 是一款简单的两人游戏。我们从一堆 n 匹配开始，其中n ≥ 3。

两个玩家，Max 和 Min，轮流从堆中移除 k 个匹配项，其中k = 1, k = 2, or k = 3。拿下最后一场比赛的玩家输了。

这是我已经写的：

无论state我投入多少，Min 和 Max 总是在每一轮中进行 1 场比赛。

我认为问题在于评估是错误的，但我看不出我在哪里做错了。任何帮助，将不胜感激！谢谢！