国际象棋:高分支因子

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的迭代中应首先搜索

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

Answer 1

我在C#中开发了一个国际象棋引擎,它的分支因子大约为2.5.绝对有可能通过多个数量级的数量来改进您的发动机.如今,一般的策略是基于良好的移动顺序使用非常积极的移动修剪.你为了能够看到一些深刻的战术线而牺牲了一些正确性.

以下是我发现最有效的技术概述.请注意,某些组件是补充组件而其他组件是替代组件,因此我给出的结果是一般准则.如果你没有坚实的基础,那么列表末尾的巨大收益是不可能的.

1. 只需使用alpha-beta修剪的negamax:3秒内深度4.

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

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

4. MVV/LVA排序:深度8.基本上,您希望将具有大量潜在物质净增益的捕获放在移动列表的顶部.因此,如果一个pawn捕获了一个女王,你应该首先搜索它.

5. 位板表示:深度10.这不会改善分支因子,但这是我达到这一点时所做的.抛弃数组,UInt64改为使用s,并使用make/unmake而不是copy-make.如果你觉得困难,你不需要使用魔术位板; 有更简单的方法仍然非常快.位板极大地提高了性能,使编写评估组件变得容易.我从笨蛋(6)开始花费几分钟到3秒钟.(顺便说一下,编写一个perft函数是确保移动生成正确性的好方法)

6. 换位表:深度13.这提供了很大的收益,但也很难做到正确.在实施表格之前,请确保您的位置哈希是正确的.大多数好处来自于桌子给你带来的惊人动作.始终将最佳移动存储在桌面中,无论何时获得匹配位置,请先尝试.

7. 延迟移动减少:深度16.这极大地增加了您的搜索深度,但强度增加比其他技术更加人为.基本上你的移动顺序是如此之好,因为你只需要完全搜索节点中的前几个移动,你可以用浅搜索检查其他移动.

8. 无效修剪:深度17.通过跳过移动来修剪叶节点,这些移动在查看潜在材料增益时提高节点值的可能性很小.如果移动的净潜在增益+位置的静态评估低于位置的当前值,则跳过对移动的评估.

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