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

衡量绩效

实际上,您可以通过两种方式提高性能:

• 更快地评估节点
• 搜索更少的节点 同样的答案

代码优化的第一个问题是度量。你怎么知道你真的改变了?为了帮助您解决这个问题,您需要确保在移动搜索期间可以记录一些统计数据。我在象棋引擎中捕捉到的是:

• 搜索所花的时间 完成。
• 搜索的节点数

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

更复杂的是,在修改代码之后,你可以运行引擎3次,每次得到3个不同的结果。假设你的象棋引擎在9、10和11秒内找到了最好的移动。这大约是20%的价差。你是把引擎提高了10%-20%,还是只是电脑的负载变化了。你怎么知道的?为了解决这个问题,我增加了一些方法,使我的引擎能够与自身对抗,它可以同时对白色和黑色进行移动。这样你不仅可以测试一次移动的时间方差,还可以测试游戏过程中多达50个移动的序列。如果上次游戏花了10分钟,现在花了9分钟,你的引擎可能会提高10%。再次运行测试应该可以确认这一点。

寻找绩效收益

既然我们知道了如何度量性能增益,那么就让我们来讨论如何识别潜在的性能增益。

如果您处于.NET环境中,.NET探查器将是您的朋友。如果您有一个visualstudiofordevelopers版本,它是免费内置的,但是您可以使用其他第三方工具。这个工具节省了我的工作时间,因为它可以告诉你你的引擎在哪里花费了大部分时间,让你集中精力在你的故障点。如果没有profiler工具,则可能需要在引擎执行不同步骤时以某种方式记录时间戳。我不建议这样做。在这种情况下,一个好的剖面仪是值得它的重量在黄金。红门蚂蚁剖面仪是昂贵的,但最好的一个我试过。如果你买不起,至少在他们14天的试用期内使用。

你的档案员会为你确定一些事情,但是这里有一些我在与C一起工作时学到的小经验:

• 把一切都私人化
• 不管你能做什么 它密封了
• 使尽可能多的方法成为静态的 可能的。
• 别把你的方法说得太多,一个 长法优于4小法 一个。
• 棋盘存储为数组[8][8] 比[64]数组慢
• 尽可能将int替换为byte。
• 尽早从你的方法中返回 可能的。
• 堆叠比列表好
• 数组比堆栈和 列表
• 如果您可以定义 在填充之前列出。
• 铸造、拳击、联合拳击是邪恶的。

进一步的业绩增长:

我发现移动生成和排序非常重要。然而,在我看来,这是个问题。如果你在分类和运行alpha-beta之前评估每一步的得分,你将能够优化你的移动顺序,这样你将得到非常快的alpha-beta截止值。这是因为你可以先尝试最好的动作。 然而,你花在评估每一步上的时间将会被浪费。例如,你可能已经评估了20个动作的得分,排序你的动作尝试前2个,并在第2个动作时收到了一个截止值。理论上,你在其他18个动作上花费的时间是浪费的。

另一方面,如果你做一个更轻和更快的评估,比如说只是捕获,你的排序将不会那么好,你将不得不搜索更多的节点(最多60%以上)。另一方面,你不会对每一个可能的行动都做一个沉重的评估。总的来说,这种方法是 通常更快 是的。

找到一个完美的平衡点,在拥有足够的信息进行一个好的排序和不做额外的工作,你将不会使用移动,这将使你在你的搜索算法中找到巨大的收益。此外,如果你选择了较差的排序方法,你会想先进行一个较浅的搜索,比如说第3层,在你进入更深的搜索之前对你的移动进行排序(这通常被称为迭代深化)。这将显著改善您的排序,并允许您搜索更少的移动。

回答一个老问题。

假设你已经有一个工作换位表。

延迟移动减少。这给了我的程序大约100个ELO点,这是非常简单的实现。

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

尽管你可以用糟糕的性能来吓唬你的象棋引擎,但一个闪电般的快速移动生成器本身并不能使程序变得好。

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

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

搜索最重要的部分是:空移动修剪、检查扩展和后期移动减少。

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

很好的移动命令!

一个古老的问题,但同样的技术现在适用于5年前。我们不是都在编写自己的象棋引擎吗?我有自己的“挪威棋局”,我希望最终能在ccrl上与其他java引擎竞争。我和其他许多人一样,用stockfish来表达想法,因为它写得很好,而且很开放。他们的测试框架fishtest及其社区也给出了大量的好建议。值得将你的评估分数与stockfish得到的分数进行比较,因为如何评估可能是国际象棋编程中最大的未知问题,而且stockfish已经远离了许多已经成为城市传奇的传统评估(如双主教奖金)。不过,最大的不同是,在我实现了与您提到的相同的技术之后,negascout、tt、lmr,我开始使用stockfish进行比较,我注意到在相同的深度下,stockfish搜索的移动比我得到的要少得多(因为移动顺序)。

移动订购必需品

有一件事是很容易忘记的是好的移动命令。为了使α-β截止有效,必须首先获得最佳的移动。另一方面,它也可能是费时的,所以只有在必要时才做。

1. 换位表
2. 根据他们的收益分类促销和好的捕获
3. 杀手招式
4. 使对手受到攻击的动作
5. 历史启发式
6. 无声移动-按psqt值排序

应该根据需要进行排序,通常对捕获进行排序就足够了,此后,您可以仅在需要时运行更昂贵的检查和psqt排序。

关于Java/C与V/C/C++/汇编的关系

Java的编程技术与使用C语言的Adam Berent给出的优秀答案是一样的。除此之外,我还提到了避免使用对象数组,而是使用许多原语数组,但与他使用字节的建议相反,我发现对于64位Java,使用字节和整数而不是64位长来保存的内容很少。我也走下了改写到C/C++ +汇编的道路,我的表现毫无收获。我对位扫描指令(如lzcnt和popcnt)使用了汇编代码,但后来我发现java 8也使用了这些代码,而不是long对象上的方法。令我惊讶的是java速度更快,java 8虚拟机似乎比c编译器做得更好。

我知道在大学的人工智能课程中有一个改进,在那里有一个庞大的完成动作的数据库。所以有一个预先计算好的游戏数据库,只剩下少量的数字。因此,如果在搜索中达到接近尾端的位置,则停止搜索并获取一个预先计算的值,该值可以改进搜索结果,例如额外的深化,您可以在不花费太多计算时间的情况下对重要/评论移动执行此操作。我认为这也伴随着在游戏后期状态下启发式的改变,但我不是一个棋手,所以我不知道游戏结束的动态。

请注意,在线程环境中正确搜索游戏可能是一个巨大的痛苦( I've tried it )中。这是可以做到的,但从我之前做过的一些文献检索来看,要从中获得任何提速都是极其困难的。

这是一个很老的问题,我只是在国际象棋上搜索问题,发现这个问题没有答案。好吧,现在它可能对你没有任何帮助,但可能对其他用户有帮助。

我没有看到空移动修剪,换位表..你在用它们吗?他们会给你很大的鼓舞…

有一件事给了我很大的鼓舞,那就是最小化条件分支…很多事情都可以预先计算出来。寻找这样的机会。

大多数现代PC机都有多个内核,所以让它多线程是个好主意。你不一定要用中密度纤维板。

我不建议把你的代码移到比特板上。工作实在太多了。即使在64位计算机上,位板也能起到推动作用。

最后,最重要的是,象棋文献支配着我们可能使用的任何优化。优化工作太多了。看看开源的国际象棋引擎,特别是狡猾的和水果/toga。水果最初是开源的。

就技巧而言,我知道在任何评估函数之前优化移动生成例程可以获得很大的收益。使该功能尽可能紧凑可以使节点/秒提高10%或更多。

如果你要转到bitboard,可以在rec.games.chess.computer档案中挖掘一些robert hyatts博士关于crafty的旧帖子(很肯定他不会再发了)。或者从 his FTP 开始挖掘。不过,我敢肯定这对你来说是一个重大转变。

迟回答,但这可能有助于:

考虑到您提到的所有优化,1450 elo非常低。我猜你的代码有点不对劲。你有没有:

1. 写了一篇 perft 例行公事,在一组位置上运行?所有的测试都应该通过,所以你知道你的移动生成器没有bug。如果你没有这个,谈论埃洛是没有意义的。

2. 写了一篇 mirrorBoard 例行程序并在一组位置中运行评估代码?正常位置和镜像位置的结果应该是相同的,否则您的评估中有一个错误。

3. 你有哈希表(又名换位表)吗?如果没有,这是必须的。这将有助于搜索和命令移动,给一个残酷的速度差异。

4. 如何实现移动订购?这个链接回到第3点。

5. 你执行了UCI协议吗?是你的吗 move parsing 功能正常吗?我的引擎里有个这样的虫子:

     /* Parses a uci move string and return a Board object */
     Board parseUCIMoves(String moves)// e2e4 c7c5 g1f3 ...{
         //...
         if (someMove.equals("e1g1") || someMove.equals("e1c1"))
             //apply proper castle
        //...
    }
   

有时在比赛时引擎会崩溃,我认为是gui的错误,因为所有的性能测试都是好的。我花了一个星期的时间才幸运地找到那只虫子。所以, 测试一切。

对于(1)你可以搜索到深度6的每个位置。我用一个大约1000个位置的文件。看这里 https://chessprogramming.wikispaces.com/Perft

对于(2)你只需要一个有数百万个位置的文件(只是fen字符串)。

考虑到以上所有因素和一个非常基本的评估功能(材料,棋子方桌,传递棋子,国王安全),它应该在+2000埃洛发挥。

• 换位表
• 开场白
• 游戏结束时的桌面基础
• 改进的叶节点静态板评估方法
• 原速位板

简介和基准。理论上的优化是很好的,但是除非您正在测量您所做的每一个更改对性能的影响,否则您将不知道您的工作是在提高还是在降低最终代码的速度。

试着把尝试不同算法的惩罚限制在你自己身上。使测试算法的各种实现变得容易。也就是说,可以轻松地构建代码的pvs版本和negascout版本。

找到热点。重构。必要时在程序集中重写。重复。

假设“历史启发式”包含了一些过去动作的数据库,那么学习算法不会给你更多,除非它与同一个玩家玩很多游戏。通过对玩家进行分类并调整历史数据库中的移动选择,您可能可以获得更多。

我已经很久没有在任何一个象棋程序上做过编程了,但是在那个时候,位板确实给了我一个真正的改进。除此之外,我不能给你太多建议。你只评估棋子的位置吗?一些关键零件的位置或移动可能会有一些(轻微)的奖励。

我不确定你想学什么类型的东西但是…