国际象棋AI如何确定其中一位玩家是否可以声称平局？

Question

我正在实验国际象棋AI和目前试图实现的可能性检测声称平局。

在以下情况下，玩家可以要求平局：

1. 在过去的50步中，每个玩家都没有被捕获或典当移动。
2. 相同的董事会位置已经发生了三次。

因此，程序必须存储以前位置的历史记录，以便能够验证这些条件。在人类玩家要求平局的情况下，这是可以的。但人工智能正在评估数以百万计的头寸。因此，一方面，它应该能够发现由自己或对手提出这样的要求的可能性，以便能够阻止它在获胜的位置上或试图在失败的情况下执行它。另一方面，由于深度搜索期间创建的历史表的所有副本，这种验证可能导致性能上的巨大损失。

是否有这样一个特性的标准实现/优化？

注:如果答案是特定于实现，我的AI是基于极小的变化与α-β剪枝。

Answer 1

对于第1项，标准解决方案是将计数器存储在当前状态；每次典当移动或捕获时，计数器重置为0，每次没有时增加1，如果每次移动大于50，则在每次移动时检查计数器。

对于第2项，一些程序在每次移动时都要进行跟踪和检查，但这需要时间和空间，正如您所注意到的。因此，许多程序只跟踪过去的动作，而忽略了在游戏树中通过三倍重复绘制的可能性。另一种可能是跟踪任何重复的位置已经发生，并只检查一个前瞻性的立场是不是相同的其中之一。

Answer 2

对于第1项，我建议在发生捕获/典当移动时重置计数器。(如前所述)

对于第2项，我建议在您的董事会类中设置一个Zobrist散列数组，您可以在其中跟踪已经发生的位置。如果找到了这样的位置(当前的==遍历所有的变体区)，那么您将相应的计数器提高一个。如果计数器达到3，则其绘制=>返回0作为位置值。

这个方法在运行时会运行得非常快，因为您比较了obly ~50个整数的最大值。Im --你已经有了tts/hashtable，这很容易实现，因为你已经有了zobrist代码的代码。

编辑:顺便说一句，这不是唯一的抽签机会，参见“僵局”。

Answer 3

为了避免评估成本，国际象棋程序始终跟踪相同的位置& e4e5，g4与g4e5、e4是相同的位置，因此具有相同的价值，完全避免了评估后者的成本。你所做的就是跟踪这个位置出现了多少移动，如果它是不同的至少两个移动，你做一些特殊的情况处理。