国际象棋优化

Question

好的,所以我一直在为我的国际象棋程序工作一段时间,我开始碰壁了.我已经完成了所有的标准优化(negascout,迭代深化,杀手动作,历史启发式,静态搜索,典当位置评估,一些搜索扩展),我完全没有想法!

我希望尽快让它多线程化,这应该会给我带来很好的性能提升,但除此之外还有其他任何狡猾的技巧吗？我考虑过切换到MDF(f),但我听说这是一个麻烦,并不值得.

我最感兴趣的是某种学习算法,但我不知道是否有人用国际象棋程序有效地完成了这项工作.

那么,切换到一块板有意义吗？我目前正在使用0x88.

Answer 1

在我的国际象棋引擎(www.chessbin.com)的最后一年开发中,大部分时间都用于优化我的代码,以便更好,更快地进行移动搜索.在那段时间里,我学到了一些我想与你分享的技巧.

衡量绩效

从本质上讲,您可以通过两种方式改善绩效:

• 更快地评估您的节点
• 搜索较少的节点以得出相同的答案

您在代码优化中的第一个问题是测量.你怎么知道你真的有所作为？为了帮助您解决此问题,您需要确保在移动搜索期间可以记录一些统计信息.我在国际象棋引擎中捕获的是:

• 搜索完成所花费的时间.
• 搜索到的节点数

这将允许您对您的更改进行基准测试和测试.进行测试的最佳方法是从开始位置,中间游戏和结束游戏创建多个保存游戏.记录搜索黑白节点的时间和数量.在进行任何更改后,我通常会针对上述保存游戏执行测试,看看我是否对上述两个矩阵进行了改进:搜索的节点数或速度.

为了进一步复杂化,在进行代码更改后,您可以运行引擎3次,每次获得3个不同的结果.让我们说你的国际象棋引擎在9,10和11秒内找到了最好的动作.这是一个约20%的差价.所以你的发动机改进了10%-20%,或者只是你的电脑负载不同.你怎么知道的？为了解决这个问题,我添加了一些方法,可以让我的引擎对抗自己,它会为白色和黑色进行移动.通过这种方式,您不仅可以测试一次移动的时间差异,还可以测试游戏过程中一系列多达50次的移动.如果上次游戏需要10分钟而现在需要9分钟,那么你的引擎可能会提高10%.再次运行测试应该确认这一点.

寻找业绩增长

既然我们知道如何衡量性能增益,那么就讨论如何识别潜在的性能提升.

如果您在.NET环境中,则.NET分析器将成为您的朋友.如果您有Visual Studio for Developers版本,它是免费内置的,但您可以使用其他第三方工具.这个工具节省了我几个小时的工作量,因为它可以告诉你你的引擎大部分时间花在哪里,让你专注于你的麻烦点.如果您没有分析器工具,则可能需要以某种方式记录时间戳,因为引擎会执行不同的步骤.我不建议这样做.在这种情况下,一个好的剖面仪是值得的黄金重量.Red Gate ANTS Profiler价格昂贵但是我曾经尝试过的最好的.如果你负担不起,至少可以用它进行为期14天的试用.

你的探查器会为你确定一些东西,但是这里有一些我学过C#的小课程:

• 让一切都私密
• 无论你不能私密,都要密封
• 尽可能多地使静态方法.
• 不要让你的方法很健谈,一个长方法比4个小方法更好.
• 作为数组存储的棋盘[8] [8]比[64]的数组慢
• 尽可能用int替换int.
• 尽早从你的方法返回.
• 堆栈比列表更好
• 数组比堆栈和列表更好.
• 如果您可以在填充列表之前定义列表的大小.
• 铸造,拳击,非拳击是邪恶的.

进一步的业绩增长:

我发现移动生成和排序非常重要.但是我认为这是问题所在.如果您在排序和运行Alpha Beta之前评估每个动作的得分,您将能够优化您的移动顺序,以便您获得极快的Alpha Beta截止.这是因为你将能够首先尝试最好的举动.但是,您花在评估每个动作上的时间将被浪费掉.例如,您可能已经评估了20次移动的得分,对移动进行排序尝试前2次并且在移动次数2上获得截止.理论上,您花费在其他18次移动上的时间被浪费了.

另一方面,如果你做一个更轻,更快的评估说只是捕获,你的排序将不会那么好,你将不得不搜索更多的节点(多达60%).另一方面,你不会对每一个可能的举动进行大量评估.总的来说,这种方法通常更快.

在获得足够的信息以获得良好排序并且不对您不会使用的移动做额外工作之间找到这种完美平衡,将使您在搜索算法中获得巨大收益.此外,如果您选择较差的排序方法,您将首先想要进行更浅层的搜索,然后再进行更深入的搜索(这通常称为迭代深化).这将显着改善您的排序,并允许您搜索更少的移动.

Answer 2

回答一个老问题.

假设你已经有一个工作的转置表.

延迟减少.这给了我的程序大约100个elo点,实现起来非常简单.

根据我的经验,除非您的实现效率非常低,否则实际的板表示(0x88,位板等)并不重要.

虽然你可以将国际象棋引擎的性能降低,但闪电般快速移动的发生器本身并不能使程序变得更好.

使用的搜索技巧和评估功能是决定整体实力的压倒性因素.

到目前为止,评估中最重要的部分是材料,通过的典当,国王安全和典当结构.

搜索中最重要的部分是:Null Move Pruning,Check Extension和Late Move reduction.

只需要这些简单的技术,你的程序就可以走很长的路!

Answer 3

假设“历史启发式”涉及某种过去动作的数据库，学习算法不会为您提供更多信息，除非它与同一玩家进行很多游戏。您可能可以通过对玩家进行分类并调整历史数据库中的动作选择来实现更多目标。