algorithm - 国际象棋 AI 如何确定任何一位棋手是否可以平局？

Question

我正在对国际象棋 AI 进行试验，目前正在尝试检测平局的可能性。

如果出现以下情况，玩家可以要求平局:

1. 在每个玩家的最后 50 步棋中没有吃到或走棋。
2. 相同的棋盘位置出现了 3 次。

因此，程序必须存储先前持仓的历史记录才能验证这些条件。这在人类玩家要求平局的情况下是可以的。但人工智能正在评估数百万个职位。因此，一方面，它应该能够通过自身或对手 x 向前移动来检测这种声明的可能性，以便能够阻止它处于获胜位置或尝试在失败位置强制执行它。另一方面，由于在深度搜索期间创建了历史表的所有副本，此验证可能会导致性能的巨大损失。

是否有此类功能的标准实现/优化？

注意:如果答案是特定于实现的，我的 AI 是基于带有 alpha-beta 剪枝的极小极大变体。

Answer 1

对于第1项，标准的解决方案是在当前状态下存储一个计数器；每次有 pawn 移动或捕获时，计数器重置为 0，每次没有时增加 1，并在每次移动时检查它是否大于 50。

对于第 2 项，某些程序会跟踪并检查每次移动，但正如您所指出的那样，这会花费时间和空间。因此，许多程序只跟踪过去的移动，而忽略了在游戏树中向前看时通过三次重复抽签的可能性。另一种可能性是跟踪任何已经出现的重复位置，并且只检查前瞻位置是否与其中一个相同。