国际象棋:高分支因子

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附近。目前它是这样工作的:

游戏树节点具有其子链接列表；最初，捕获和提升位于安静的 Action 之前

在搜索过程中，将alpha增加或导致截止的子级放置在列表

的开头

在下一次加深PV的迭代中，应首先搜索

这是订购移动的正确方法，并且可以预期得到的分支因子吗？目前，我正在使用一个简单的静态评估函数，该函数仅考虑到职位的实质差异-这可能是截止率偏低的原因(如果还考虑数字的流动性，我会得到类似的结果)？零举动减少或杀手启发法之类的技术是否会显着帮助(不是10-15％，而是一个数量级)？我不认为我的引擎会很强大，但是我希望分支因子约为6。

Answer 1

我也用C#开发了一个象棋引擎，它的分支因子约为2.5。绝对有可能将您的引擎改进许多数量级。如今，一般的策略是基于良好的移动顺序使用非常主动的移动修剪。您牺牲了一些正确性，因为他们能够看到一些深层次的战术思路。

这是我发现最有效的技术概述。请注意，某些组件是互补的，而其他组件是替代的，因此我给出的结果是一般准则。如果您没有坚实的基础，那么榜单末尾的巨大 yield 是不可能的。

与negamax一起使用alpha-beta pruning:3秒内深度为4。

添加iterative deepening和null move heuristic:深度5。迭代加深在这一点上并没有真正的帮助，但是很容易实现。空值
移动包括跳过转弯，看看是否仍然可以
浅层搜索的beta截止值。如果可以的话，可能是
安全修剪树，因为它几乎总是有利于
移动。

Killer heuristic:深度为6。这涉及存储移动
导致Beta终止，如果下次合法，请先尝试
你在同一深度。你似乎在做类似的事情
已经。

MVV/LVA ordering:深度为8。基本上，您想将捕获的内容
在移动的顶部有很多潜在的实质性净 yield
列表。因此，如果典当捕获了女王，则显然应该首先对其进行搜索。

Bitboard representation:深度为10。这不会改善分支
因素，但这就是我达到这一点时所做的。沟渠
数组，请使用UInt64代替，并使用make/unmake代替copy-make。如果发现困难，则无需使用魔术位板；有些较简单的方法仍然非常快。位板极大地提高了性能
并简化编写评估组件的过程。我从
perft(6)耗时数分钟至3秒钟。 (顺便说一句，编写一个perft函数是确保移动生成正确性的好方法)

Transposition table:深度13。这虽然有很大的收获，但也
很难做到正确。绝对确定您的位置哈希
在实现表之前是正确的。大部分好处来自
订购 table 的惊人举动给了您。始终存储最好的
移到 table 上，只要有合适的位置，就尝试一下
第一的。

Late move reductions:深度16。这会大大扩大您的搜索深度，但强度增加得更多
人为的，而不是其他技术。基本上，您的移动订购
现在非常好，您只需要完全搜索前几个
在一个节点中移动，您可以通过浅层搜索来检查其他节点。

Futility pruning:深度17.通过跳过移动来修剪叶节点
在寻找潜力时，很少有机会提高节点的值(value)
物质 yield 。如果该位置的移动+静态评估的净净潜在 yield 低于该位置的当前值，请跳过
评估的举动。

还有其他各种组件也有帮助，但是大多数都是次要的，有些是专有的。 :D然而，这并不仅仅与高搜索深度和低分支因子有关。诸如 quiescence search之类的东西会使搜索深度变差，但是对于任何引擎而言，这几乎都是必需的。没有它，您的引擎将遭受巨大的战术错误。您可能还需要考虑 check extensions和 single reply extensions。我还建议至少将 piece-square tables引入您的评估功能。这是极大地提高程序位置知识的一种非常简单的方法。您可能会看到您的引擎打出更常见的空缺。国际象棋编程是一个有趣的爱好，希望信息量不要让您感到沮丧!