java draughts AI (多线程)

Question

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

我目前正在用Java制作一个draughts游戏。事实上，除了人工智能，一切都能工作。人工智能目前是单线程，使用极小和α-β剪枝.我认为这个代码很慢，我只能深入到我的游戏树中。

1. 我有一个接收我的主板的函数，一个深度(从0开始)和一个最大深度。在这个最大深度，它停止，返回球员的值(-1,1或0)与棋盘上的大部分，并结束递归调用。
2. 如果还没有达到最大深度，我会计算出所有可能的移动，然后逐一执行，以某种方式将更改存储到主板上。
3. 我也使用α-beta剪枝，例如，当我发现一个移动，可以使玩家获胜，我不关心下一个可能的移动。
4. 我递归地从主板状态计算下一组移动。当递归调用结束时，我会撤消这些更改(从第2点开始)。我存储这些递归调用返回的值，并在这些调用上使用minimax。

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

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

有谁能帮我一下吗？

Answer 1

1. AI的可能移动(例如AI可以选择的移动)的值总是0，这是否正常？

我觉得很奇怪。如果可能的移动数是0，那么该球员就不能发挥他的回合。这不应该很普遍，还是我误解了什么？

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

2.我不知道它是否有用，但我如何将这个递归转换为多线程递归。我认为这可以把工作时间除以一定的值.

我相信这将是非常有用的，特别是考虑到现在大多数机器都有几个核心。

让它变得复杂的是你的“尝试一个移动，记录它，撤销它，尝试下一个移动”方法。这表明您使用的是可变的数据结构，这使得对算法进行并行化非常复杂。

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

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

Answer 2

我强烈建议读这本书：

一跃而起:电脑完美无缺

它将给你一个深刻的历史，计算机人工智能在游戏中的检查，并可能会给你一些帮助，你的评价功能。

而不是有一个评估函数，只给1/0/-1，为不同的部分，给100分的每一个常规的部分，200为一国王。那就给片状结构加成奖金。例如，如果我的作品构成了一个安全的结构，无法被捕获，那么我就得到了奖励。如果我的作品都在董事会的中间，那么我会得到一个负面的奖励。正是这种丰富的功能片段配置，将使您的程序发挥良好。最后的分数是两名球员在评价上的差异。

此外，你也不应该停止搜索在一个统一的深度。一个安静的搜索延伸搜索直到董事会是“安静”。在检查员的情况下，这意味着板上没有强制抓捕。如果你不这样做，你的程序将发挥极差。

正如其他人所建议的那样，转位表在缩小搜索树的大小方面做得很好，尽管程序运行速度会稍微慢一些。我也会推荐历史启发，这是很容易编程，并将大大改善在树中的移动顺序。(有关这方面的更多信息，Google历史启发。)

最后，你董事会的表现会有很大的不同。搜索的快速实现不会在每次应用移动时复制板，而是尝试快速修改板以应用和撤消移动。

Answer 3

(我想，在美国，你的意思是我们所谓的检查员。)

我不确定我是否理解你在游戏树中的得分系统。你是在说，“如果球员比对手有更多的棋子，那么位置得分是1分，1分是指球员有更少的棋子，0分是如果他们有相同的棋子数？”

如果是这样的话，那么您的算法可能只是前五步的捕捉厌恶，或者事情正在进行，以便所有捕获都是平衡的。我对跳棋不是很熟悉，但这似乎并不是不可能的，因为只有五步棋才能完成。如果只有5步棋(一杆是一位球员的移动，而不是一组完整的相反的动作)，那可能根本就不寻常了。

你可能想要测试这一点，在一个棋盘位置，你知道绝对正确的答案，也许只有两个棋盘在棋盘上，一个在一个位置捕捉。

不过，作为一般原则，董事会的评估功能没有多大意义--它忽略了一块一块和一件加冕件之间的区别，它把一块三件的优势视为一件一件的优势。