国际象棋：高分支因子

Question

我正在尝试开发一个简单的国际象棋引擎，但我正在为它的性能而苦苦挣扎。我已经通过 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或导致截止的子项被放在列表的开头
3. 在下一次深化迭代中，应该首先搜索PV

这是一种正确的移动顺序方法吗？我得到的分支因子是预期的？目前我使用的是一个简单的静态评估函数，它只考虑了位置的物质差异-这是否可以成为低截止率的原因（如果还考虑了数字的流动性，我会得到类似的结果）？零移动减少或杀手试探等技术会有很大帮助吗（不是10-15%，而是一个数量级）？我不希望我的引擎很强，但我希望分支因子大约为6。

Answer 1

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

首先，您应该使用换位表 （TT） 来存储仓位结果、深度和最佳移动。在搜索移动之前，首先要检查它是否已被深度搜索

如果某个位置（在搜索内部）的 TT 中没有匹配项，则可以使用迭代深化 （ID）。您首先对深度 N-2 进行搜索，而不是对深度 N 进行搜索。这将非常快，并且会让你首先在深度N进行搜索。

还有空移动修剪。与α-β(Negamax是α-β的变体)结合使用，将大大降低您的分支系数。想法是在搜索一个位置之前，你尝试一个空移动(不玩)并且做一个减少搜索(N-2或N-3)。简化搜索将会非常快。如果空移动搜索的结果仍然高于beta，这意味着位置很糟糕，你不需要再搜索它了(不总是这样，但大多数时候是这样)。

当然，还有其他多种启发式方法可以用来改进你的移动顺序，这些方法都会提高你的分支因子。

Answer 2

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

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

>

只需negamax和alpha-beta修剪：3秒内深度4。

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

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

MVV/LVA排序：深度8。基本上，您希望将具有大量潜在材料净收益的捕获放在移动列表的顶部。所以，如果一个小卒抓住了一个王后，你显然应该先搜索它。

Bitboard表示：深度10。这并没有改善分支因子，但当我达到这一点时，我就是这么做的。抛弃数组，改用UInt64s，并使用mon/unmon而不是复制-制作。如果你觉得困难，你不需要使用神奇的位板；有更简单的方法仍然很快。Bitboard大大提高了性能，使编写评估组件变得容易。我从perft（6）需要几分钟变成了需要3秒。（顺便说一下，编写perft函数是确保移动生成正确性的一个很好的方法）

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

后期移动减少:深度16。这极大地增加了你的搜索深度，但是力量的增加比其他技术更加人为。基本上你的移动顺序是如此之好，现在你只需要完全搜索一个节点的前几个移动，你可以用浅层搜索来检查其他的移动。

徒劳修剪：深度 17。叶节点通过跳过移动来修剪，在查看潜在材料增益时，这些移动提高节点价值的机会很小。如果仓位的移动静态评估的净潜在增益低于头寸的当前值，请跳过移动的评估。

还有其他各种组件也有帮助，但大多数是次要的，有些是专有的。： D然而，这并不全是关于高搜索深度和低分支因素。像静止搜索这样的东西会恶化搜索深度，但几乎是任何引擎的必需品。没有它，你的引擎将遭受巨大的战术错误。你可能还想考虑检查扩展和单回复扩展。我还建议至少在你的评估功能中引入方块表。这是一个非常简单的方法，可以大大提高程序的位置知识；你可能会看到你的引擎玩更多常见的开口。国际象棋编程是一个有趣的爱好，我希望信息量不会让你气馁！