问题描述
好了，我一直在我的国际象棋程序一段时间，我开始碰了壁。我已经做了所有的标准优化（negascout，反复加深，杀手的动作，历史启发，静态搜索，棋子位置的评价，一些搜索扩展）和我所有的想法！
ok, so i have been working on my chess program for a while and i am beginning to hit a wall. i have done all of the standard optimizations (negascout, iterative deepening, killer moves, history heuristic, quiescent search, pawn position evaluation, some search extensions) and i'm all out of ideas!
我期待，使其多线程很快，这应该给我一个表现良好的提振，但除了在那里你们所遇到的任何其他漂亮的花样？我曾考虑切换到MDF（F），但我听说这是一个麻烦，是不是真的值得的。
i am looking to make it multi-threaded soon, and that should give me a good boost in performance, but aside from that are there any other nifty tricks you guys have come across? i have considered switching to MDF(f), but i have heard it is a hassle and isn't really worth it.
我会是最感兴趣的是某种学习算法，但我不知道是否有人已经做到了与国际象棋程序有效的呢。
what i would be most interested in is some kind of learning algorithm, but i don't know if anyone has done that effectively with a chess program yet.
也将切换到有点董事会显著？我目前使用均为0x88。
also, would switching to a bit board be significant? i currently am using 0x88.
推荐答案
在我的国际象棋引擎开发的最后一年（ www.chessbin.com ），大部分的时间花在优化我的code，以便更好，更快的移动搜索。在这段时间里我学到了一些技巧，我想与大家分享。
Over the last year of development of my chess engine (www.chessbin.com), much of the time has been spent optimizing my code to allow for better and faster move searching. Over that time I have learned a few tricks that I would like to share with you.
测量性能
从本质上讲，你可以提高你的表现在两个方面：
Essentially you can improve your performance in two ways:
- 在评估你的节点更快
- 在搜索更少的节点来了同样的答案
- Evaluate your nodes faster
- Search fewer nodes to come up withthe same answer
在code优化你的第一个问题将是测量。你怎么知道你真的发挥了作用？为了帮助你解决这个问题，你需要确保你可以在你的移动搜索过程中记录的一些统计数据。那些我捕捉到我的国际象棋引擎是：
Your first problem in code optimization will be measurement. How do you know you have really made a difference? In order to help you with this problem you will need to make sure you can record some statistics during your move search. The ones I capture in my chess engine are:
- 在时间花费在搜索完成了。
- 在搜索的节点数
- Time it took for the search tocomplete.
- Number of nodes searched
这将允许您基准，测试更改。接近测试的最佳方法是创建多个保存从开启位置，中间的游戏，游戏结束游戏。记录时间和节点数目搜寻黑白。在进行任何更改我平时执行测试对上述保存的游戏，看看我在上面的两个矩阵做了改进后：搜索节点数量或速度
This will allow you to benchmark and test your changes. The best way to approach testing is to create several save games from the opening position, middle game and the end game. Record the time and number of nodes searched for black and white.After making any changes I usually perform tests against the above mentioned save games to see if I have made improvements in the above two matrices: number of nodes searched or speed.
要进一步复杂化的东西，使得code修改，你可能会遇到你的引擎3次，一次比一次3个不同的结果后。比方说，您的国际象棋引擎发现，9，10和11秒最好的举措。即约为20％A S $ P $垫。那你有没有通过10％提高你的发动机-20％，或者说这只是不同的负载上你的电脑。你怎么知道的？为了打击这一点，我已经添加的方法，让我的引擎对自己发挥，就会出招了白色和黑色两种。这样你就可以测试不只是时间差异超过一动，而是一系列的多达50个动作在游戏的过程中。如果最后一次比赛了10分钟，现在需要9，你大概提高了10％的引擎。再次运行测试应确认这一点。
To complicate things further, after making a code change you might run your engine 3 times and get 3 different results each time. Let’s say that your chess engine found the best move in 9, 10 and 11 seconds. That is a spread of about 20%. So did you improve your engine by 10%-20% or was it just varied load on your pc. How do you know? To fight this I have added methods that will allow my engine to play against itself, it will make moves for both white and black. This way you can test not just the time variance over one move, but a series of as many as 50 moves over the course of the game. If last time the game took 10 minutes and now it takes 9, you probably improved your engine by 10%. Running the test again should confirm this.
查找性能提升
现在，我们知道如何来衡量性能提升让讨论如何识别潜在的性能提升。
Now that we know how to measure performance gains lets discuss how to identify potential performance gains.
如果你是在.NET环境中那么.NET探查会成为你的朋友。如果你有一个Visual Studio的开发者版本也内置于免费的，但也有其他第三方工具可以使用。这个工具为我节省了工作时间，因为它会告诉你，你的发动机花费了大量时间，让你专注于你的麻烦了点。如果你没有一个分析器工具，您可能必须以某种方式记录时间戳为你的引擎经过不同的步骤。我不建议这一点。在这种情况下，一个优秀的分析器是值得其重量的黄金。红门蚂蚁事件探查器是昂贵的，但最好的，我曾经试过。如果你买不起，至少将其用于自己的试用14天。
If you are in a .NET environment then the .NET profiler will be your friend. If you have a Visual Studio for Developers edition it comes built in for free, however there are other third party tools you can use. This tool has saved me hours of work as it will tell you where your engine is spending most of its time and allow you to concentrate on your trouble spots. If you do not have a profiler tool you may have to somehow log the time stamps as your engine goes through different steps. I do not suggest this. In this case a good profiler is worth its weight in gold. Red Gate ANTS Profiler is expensive but the best one I have ever tried. If you can’t afford one, at least use it for their 14 day trial.
您分析器会切切实实的识别你的东西，但这里有一些小的经验教训我已经学会了用C＃的工作：
Your profiler will surly identify things for you, however here are some small lessons I have learned working with C#:
- 请一切私人
- 不管你不能让私人的，使它的密封
- 请尽可能多的方法静态的可能的。
- 请不要让你的方法健谈，人们长方法是小于4更好的。
- 在棋盘存储为一个数组[8] [8]慢则数组[64]
- 与字节替换INT在可能的情况。
- 返回从你的方法早可能的。
- 栈比列表更好
- 在数组比栈更好，名单。
- 如果您可以定义的大小列表中，您填充它。
- 在铸造，拳击，未拳击是邪恶的。
- Make everything private
- Whatever you can’t make private, makeit sealed
- Make as many methods static aspossible.
- Don’t make your methods chatty, onelong method is better than 4 smallerones.
- Chess board stored as an array [8][8]is slower then an array of [64]
- Replace int with byte where possible.
- Return from your methods as early aspossible.
- Stacks are better than lists
- Arrays are better than stacks andlists.
- If you can define the size of thelist before you populate it.
- Casting, boxing, un-boxing is evil.
进一步的性能提升：
我觉得此举产生和排序是非常重要的。但是现在的问题是，我看到它。如果评估每次移动的得分进行排序和运行α+β之前，你将能够优化您的移动订购，这样你会得到非常快的Alpha测试版截断。这是因为，你将能够多为尝试最佳的移动第一。然而，你已经花了评估每次移动时会被浪费。例如，你可能已经评估了20的动作得分，排序你的动作尝试前2接收到移动数字2的截止从理论上说，你把时间用在了其他18个动作是浪费时间。
I find move generation and ordering is extremely important. However here is the problem as I see it. If you evaluate the score of each move before you sort and run Alpha Beta, you will be able to optimize your move ordering such that you will get extremely quick Alpha Beta cutoffs. This is because you will be able to mostly try the best move first.However the time you have spent evaluating each move will be wasted. For example you might have evaluated the score on 20 moves, sort your moves try the first 2 and received a cut-off on move number 2. In theory the time you have spent on the other 18 moves was wasted.
在另一方面，如果你做了更轻，更快评价说只是抓住，你的排序将好不到哪里去，你将不得不寻找更多的节点（高达60％以上）。在另一方面，你就不会在一切可能的举措做了沉重的评价。作为一个整体此方法是通常更快。
On the other hand if you do a lighter and much faster evaluation say just captures, your sort will not be that good and you will have to search more nodes (up to 60% more). On the other hand you would not do a heavy evaluation on every possible move. As a whole this approach is usually faster.
寻找具有足够的信息，一个很好的排序，而不是做额外的工作举措，你不会使用，可以让你找到巨大的收益在搜索算法之间的完美平衡。此外，如果你选择了较差的排序方法，你会想先以浅的搜索说帘布层3，整理你的举动之前，你进入更深层次的搜索（这通常被称为迭代深化）。这将显著提高你的排序，并允许你搜索的移动少得多。
Finding this perfect balance between having enough information for a good sort and not doing extra work on moves you will not use, will allow you to find huge gains in your search algorithm. Furthermore if you choose the poorer sort approach you will want to first to a shallower search say to ply 3, sort your move before you go into the deeper search (this is often called Iterative Deepening). This will significantly improve your sort and allow you to search much fewer moves.
这篇关于国际象棋优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！