使用极小极大和AB剪枝同时搜索博弈树。这有可能吗？

Question

我将在我的学校参加一个棋盘游戏AI竞赛，并试图想出一些关于并发的想法来获得优势。我很可能处于不利地位，因为我将用java实现它，而且我知道c或c++会快得多。

看起来你不能因为移动顺序而将游戏树一分为二，这应该首先留下最好的动作，而且似乎很难甚至不可能在给定的深度上与当前的alpha/beta进行沟通。我还将使用需要同步的转换表。

除了搜索，是否有第二个线程可以做一些事情，可以帮助搜索或提供某种类型的速度提高。每个AI将有5秒的时间进行移动，而你的程序可以在对手思考的时候工作。

任何意见，无论多么晦涩难懂，都将不胜感激。

Answer 1

可以在国际象棋编程维基的parallel search article中找到概述。即使您的实际游戏不是国际象棋，许多概念也将适用。该站点还涵盖了shared transposition tables的复杂解决方案。

但是，当您没有太多时间时，我不会从并行搜索开始。并行性可以增加搜索算法的强度，这一点您是正确的。然而，要做到这一点是非常困难的，而且好处远低于人们的预期。

如果你想尝试并行性，那就来吧。这是一个有趣的话题。然而，如果你只是想在有限的时间内获得最好的结果，我建议你坚持顺序搜索，而不是专注于移动顺序和正确性。

Answer 2

这是可能的。您必须在线程之间进行通信才能获得AB剪枝帮助。此外，移动顺序必须调整，如果一个线程有最好的移动来分析，而其他线程没有。