java 草稿 AI(多线程)

Question

这是我的第一个问题，如果我做错了什么，请告诉我...

我目前正在用 Java 制作一个草稿游戏。事实上，除了 AI 之外，一切正常。AI 目前是单线程的，使用 minimax 和 alpha-beta 剪枝。这段代码有效，我认为，它非常慢，我只能深入我的游戏树 5。

1. 我有一个函数可以接收我的主板、深度(从 0 开始)和最大深度。在这个最大深度处它停止，返回棋盘上棋子最多的玩家的值(-1、1 或 0)并结束递归调用。
2. 如果还没有达到最大深度，我会计算所有可能的走法，我会一个一个地执行它们，并以某种方式将我的更改存储到主板。
3. 我还使用 alpha-beta 修剪，例如当我找到可以让玩家获胜的棋步时，我不会为接下来可能的棋步操心。
4. 我从该主板状态递归计算下一组 Action 。当递归调用结束时，我撤消了这些更改(从第 2 点开始)。我存储这些递归调用返回的值，并在这些值上使用 minimax。

情况是这样的，现在我有一些疑问。我想更深入地研究我的游戏树，因此我必须减少计算移动所需的时间。

1. AI 可能移动的值(例如，AI 可以选择的移动)始终为 0 这是否正常？或者如果我可以更深入地研究递归，这种情况会改变吗？因为此刻我只能深入 5(最大深度)我的递归，否则会花费太长时间。
2. 我不知道它是否有用，但我如何才能将此递归转换为多线程递归。我认为这可以将工作时间除以一些值...

有人可以帮我解决这个问题吗？

Answer 1

1. Is it normal that the values of the possible moves of the AI (e.g. the moves that the AI can choose between) are always 0?

对我来说听起来很奇怪。如果可能的移动次数为 0，则该玩家无法进行轮到。这应该不是很常见，还是我误解了什么？

如果您所指的值代表该移动的“分数”，那么显然“始终为 0”将表示所有移动都同样好，这显然不是一个很好的 AI 算法。

2. I don't know if it's usefull, but how I can convert this recursion into a multithreaded recursion. I think this can divide the working time by some value...

我相信它会非常有用，尤其是考虑到现在大多数机器都有多个内核。

让事情变得复杂的是你的“尝试一个 Action ，记录下来，撤消它，尝试下一步”的方法。这表明您正在使用可变数据结构，这使得并行化算法变得极其复杂。

如果我是你，我会让 bord/game 状态由一个不可变数据结构来表示。然后，您可以将每个递归调用视为一个单独的任务，并使用线程池来处理它们。您将接近 CPU 的最大利用率，同时大大简化代码(通过删除整个恢复到先前状态的代码)。

假设您的机器上确实有多个内核，这可能会让您深入树中。