我要参加我学校的棋盘游戏 AI 竞赛,我正在尝试想出一些关于并发的想法以获得优势。我很可能会处于劣势,因为我将在 Java 中实现它,而且我知道 C 或 C++ 会快得多。
似乎你不能将游戏树分成两半,因为移动顺序应该先留下最好的移动,而且似乎很难甚至不可能传达当前的 alpha/beta给定的深度。我还将使用需要同步的换位表。
除了搜索之外,第二个线程是否可以做一些事情来帮助搜索或提供某种类型的速度提升。每个 AI 将有 5 秒的时间采取行动,您的程序可以在对手思考时运行。
任何输入,无论多么晦涩,都将不胜感激。
最佳答案
可以在 Chess Programming Wiki 的 parallel search article 中找到概述。 .即使您的实际游戏不是国际象棋,许多概念也适用。该网站还涵盖了 shared transposition tables 的复杂解决方案.
但是,当您没有太多时间时,我不会从并行搜索开始。你是正确的,并行性可以增加搜索算法的强度。不过,要做到这一点非常困难,而且 yield 远低于人们的预期。
如果您想尝试并行性,请继续。这是一个有趣的话题。但是,如果您只想在有限的时间内获得最佳结果,我建议坚持顺序搜索,而不是专注于移动顺序和正确性。
关于java - 使用 minimax 和 AB 剪枝同时搜索博弈树。那可能吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14817497/