这是我在这里提的第一个问题，如果我做错了什么，请告诉我…
我目前正在用Java制作一个跳棋游戏。事实上，除了AI之外一切都正常运作。目前AI是单线程的，使用了极小极大算法和alpha-beta剪枝。我认为这段代码是有效的，只是速度非常慢，我只能深入到游戏树的第5层。
- 我有一个函数，接收主棋盘、深度（从0开始）和最大深度。在达到最大深度时，它会停止，返回棋盘上拥有最多棋子的玩家的值（-1、1或0），并结束递归调用。
- 如果尚未达到最大深度，我会计算所有可能的移动，并依次执行这些移动，以某种方式存储对主棋盘的更改。
- 我还使用了alpha-beta剪枝，例如，当我发现一个可以让玩家获胜的移动时，我就不再考虑接下来的可能移动。
- 我从那个主棋盘状态递归地计算下一组移动。在递归调用结束时，我会撤销这些更改（来自第2点的更改）。我存储那些递归调用返回的值，并对这些值应用极小极大算法。
这就是目前的情况，现在我有一些问题。我希望能够深入到游戏树的更深层次，因此必须减少计算移动所需的时间。
- AI可能移动的值（例如，AI可以选择的移动）总是0，这是正常的吗？还是说如果我能更深入递归，这种情况会改变？因为目前我只能递归到第5层（最大深度），否则耗时过长。
- 我不知道这是否有用，但我如何将这个递归转换为多线程递归？我认为这可以将工作时间减少一些…
请问有人可以帮助我解决这个问题吗？
回答：
1. AI可能移动的值（例如，AI可以选择的移动）总是0，这是正常的吗？
这听起来很奇怪。如果可能移动的数量为0，那么那个玩家就无法进行他的回合。这种情况应该不常见，或者是我误解了什么？
如果你提到的值代表那个移动的“得分”，那么“总是0”显然表示所有移动都同样好，这显然不会是一个很好的AI算法。
2. 我不知道这是否有用，但我如何将这个递归转换为多线程递归？我认为这可以将工作时间减少一些…
我相信这会非常有用，尤其是考虑到现在大多数机器都有多个核心。
使其复杂化的是你“尝试一个移动，记录它，撤销它，尝试下一个移动”的方法。这表明你正在使用一个可变的数据结构，这使得并行化算法变得极其复杂。
如果我是你，我会让棋盘/游戏状态由一个不可变的数据结构来表示。然后，你可以将每个递归调用视为一个独立的任务，并使用线程池来处理它们。你将能够接近最大化CPU的利用率，同时大大简化代码（通过移除整个恢复到之前状态的代码）。
假设你的机器确实有多个核心，这可能会让你能够深入到树的更深层次。
