使用Negamax+alpha-beta修剪和转置表的多线程评估



我刚刚为检查器实现了一个很好的工作评估函数。当前的实现使用线程,并为每个线程使用单独的换位表。

我为根节点(初始板位置)中可用的每一个移动生成一个线程,然后使用negamax和alpha-beta修剪对其进行分析。我总是这样做是为了让CPU玩家找到最好的动作。我不分析用户可用的移动。

现在我有两个考虑因素:

  1. 我能在所有这些线程之间安全地共享一个换位表吗(线程当然会同步)?

  2. 每次我开始新的分析时,我应该清除这些表还是它们可以安全使用?

有什么想法吗?

1:您应该在所有线程中共享一个换位表,因为主要思想是通过不同的路径到达相同的位置,而不仅仅是通过单个线程的子节点。

2:这取决于情况。你可能不需要在每次分析时清除整个表格,但你必须确定它的限制。所有可能的位置都太多了,无法存储在内存或磁盘中。

另一个考虑因素是清除当前游戏中无法再获得的位置(即拥有更多棋子的位置)。

即使在开始新的分析时清除了整个表,根据您的搜索深度,您仍可能达到之前定义的极限。

因此,换位表只不过是缓存,您必须定义并应用驱逐策略。这可能是不同因素的组合,您还应该检查常见的缓存驱逐策略,如"最近最少使用(LRU)"https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)

最新更新