8

我正在尝试开发一个简单的国际象棋引擎，但我正在努力解决它的性能问题。我已经使用 alpha-beta 修剪和迭代加深（没有任何额外的启发式方法）实现了 Negamax，但我无法获得超过 3-4 层的合理搜索时间。这是游戏开始时我的程序日志的摘录：

2013-05-11 18:22:06,835 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 1
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 28
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 28
2013-05-11 18:22:06,835 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A4->A6 
2013-05-11 18:22:06,835 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 2
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 90
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 118
2013-05-11 18:22:06,897 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 B7->B6 
2013-05-11 18:22:06,897 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 3
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 6027
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6414
2013-05-11 18:22:08,005 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: A2->A3 A6->B8 A4->A7 
2013-05-11 18:22:08,005 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 4
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 5629
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 6880
2013-05-11 18:22:10,485 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 
2013-05-11 18:22:10,485 [9] INFO  CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Searching at depth 5
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Leaves searched: 120758
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Nodes searched: 129538
2013-05-11 18:22:34,353 [9] DEBUG CoevolutionaryChess.Engine.MoveSearchers.NegamaxMoveSearcher [(null)] - Found PV: D2->D4 A6->B8 C4->C5 A7->A6 A4->A6

它表明分支因子大约是 10。我已经读过，通过正确的移动排序，我应该得到大约 6 的东西，所以我怀疑我的排序是错误的。它目前以这种方式工作：

  1. 游戏树节点有一个其子节点的链表；最初，捕获和提升是在安静的移动之前放置的
  2. 在搜索过程中，增加 alpha 或导致 cutoff 的 child 被放置在列表的开头
  3. 在下一次迭代加深 PV 时应先搜索

这是一种正确的方式来订购移动和我得到的分支因子是可以预期的吗？目前我正在使用一个简单的静态评估函数，它只考虑位置的材料差异 - 这可能是截止率低的原因（如果还考虑了数字的流动性，我会得到类似的结果）？诸如减少无效移动或杀手启发式等技术是否会显着帮助（不是 10-15%，而是一个数量级）？我不希望我的引擎很强大，但我希望分支因子约为 6。

4

2 回答 2

39

我还用 C# 开发了一个国际象棋引擎，它的分支因子约为 2.5。绝对有可能将您的引擎提高多个数量级。如今，一般策略是基于良好的移动顺序使用非常激进的移动修剪。为了能够看到一些深刻的战术路线，你牺牲了一些正确性。

以下是我认为最有效的技术概述。请注意，有些组件是补充，有些是替代品，所以我给出的结果是一般指导方针。如果你没有坚实的基础，那么列表末尾的巨大收益是不可能的。

  1. 只是带有alpha-beta 修剪的negamax：深度 4 在 3 秒内。

  2. 添加迭代加深和空移动启发式：深度 5。迭代加深在这一点上并没有真正的帮助，但很容易实现。空手包括跳过你的回合，看看你是否仍然可以通过浅搜索获得 beta 截止。如果可以，那么修剪树可能是安全的，因为移动几乎总是有利的。

  3. 杀手启发式：深度 6。这涉及存储导致 beta 截止的移动，并在下次您处于相同深度时，如果它们是合法的，则首先尝试它们。你似乎已经在做类似的事情了。

  4. MVV/LVA 排序：深度 8。基本上，您希望将具有大量潜在材料净增益的捕获放在移动列表的顶部。因此，如果一个棋子捕获了一个皇后，你显然应该先搜索它。

  5. 位板表示：深度 10。这不会提高分支因子，但这是我在达到这一点时所做的。抛弃数组，使用UInt64s 代替，并使用 make/unmake 而不是 copy-make。如果您觉得困难，则无需使用魔术位板；有一些更简单的方法仍然非常快。位板极大地提高了性能并使编写评估组件变得容易。我从 perft(6) 需要几分钟到需要 3 秒。（顺便说一句，编写 perft 函数是确保移动生成正确性的好方法）

  6. 换位表：深度 13。这提供了很大的收益，但也很难做到正确。在实施表格之前，请绝对确定您的位置散列是正确的。大部分好处来自订购桌子给您的惊人举动。始终将最好的移动存储到表中，每当您获得匹配的位置时，请先尝试。

  7. 后期移动减少：深度 16。这大大增加了您的搜索深度，但强度增益比其他技术更加人为。基本上，您的移动顺序现在非常好，您只需要完全搜索节点中的前几个移动，您可以通过浅搜索检查其他移动。

  8. 无用修剪：深度 17。叶节点通过跳过在查看潜在材料增益时提高节点价值的机会较低的移动来修剪。如果移动的净潜在收益+仓位的静态评估低于仓位的当前值，则跳过移动评估。

还有各种其他组件也有帮助，但大多数都是次要的，有些是专有的。:D 然而，这不仅仅是高搜索深度和低分支因子。诸如静止搜索之类的事情会恶化搜索深度，但对于任何引擎来说几乎都是必需的。没有它，您的引擎将遭受巨大的战术错误。您可能还需要考虑检查扩展和单一回复扩展。我还建议至少介绍一块方形桌子到您的评估功能。这是一种非常简单的方法，可以极大地提高程序的位置知识；您可能会看到您的引擎播放更常见的开口。国际象棋编程是一种有趣的爱好，我希望信息量不会让您灰心！

于 2013-05-20T04:50:54.763 回答
3

您可以使用多种启发式方法来减少分支因子。

首先，您应该使用转置表 (TT)来存储位置结果、深度和最佳移动。在搜索移动之前，您首先检查它是否已经在深度 >= 到您计划搜索的深度进行搜索。如果是，您可以简单地使用表中的结果。如果不是，您可能仍会使用表格中的移动作为您搜索的第一步。

如果 TT 中没有匹配位置（在搜索中），您可以使用迭代深化 (ID)。不是搜索深度为N，而是首先搜索深度为N-2。这将非常快，并且会让您先进行深度搜索N。

还有空移动修剪。与 Alpha-Beta（Negamax 是 Alpha-Beta 的变体）结合使用将大大降低您的分支因子。这个想法是在搜索位置之前，您尝试空移动（不玩）并进行减少搜索（N-2 或 N-3）。减少搜索将非常快。如果空移动搜索的结果仍然高于 beta，则意味着该位置非常糟糕，以至于您不再需要搜索它（并非总是如此，但大多数情况下都是如此）。

当然，您可以使用多种其他启发式方法来改进您的移动排序，这些都将改善您的分支因子。

于 2013-05-16T12:49:03.743 回答