Improving searching speeds

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
SrcEngine
Posts: 2
Joined: Sun Mar 22, 2020 2:04 pm
Full name: Luke Kong

Improving searching speeds

Post by SrcEngine » Sun Mar 29, 2020 4:03 am

I have already implemented prunings into my engine. It has alpha-beta pruning, SEE, principle variations, null-move prunings, which should all speed up the searchings substantially. It is able to get to depth 9 under seconds. Stash-bot (https://gitlab.com/mhouppin/stash-bot), a 1500 lines 1700 engine, however, was able to get to depth 14 under the same time period. Why is Stash searching so much faster than my engine? Does multi-threading make that much of a difference? Or is it just implementing much better pruning algorithms?

Dann Corbit
Posts: 10857
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Improving searching speeds

Post by Dann Corbit » Sun Mar 29, 2020 5:30 am

Pruning is a very complicated and touchy subject.
The only fully sound pruning method is alpha-beta. All other pruning methods take chances.
If you want to know how effective your pruning methods are, look at your branching factor.
Pure alpha-beta, executed perfectly, will be about 6 in the midgame.
Null move pruning will reduce that significantly. If you examine the stockfish code, you will find a very sophisticated null move reduction that also verifies under certain conditions.

Late move reductions offer important gains, but it is a very fiddly thing to get right.

As for razoring the Rybka engine did a very simple and incredibly effective technique to drop into qsearch :
https://www.chessprogramming.org/Razoring
See the strelka comments near the bottom of the article

If you want to search faster, reduce the branch factor. But beware, it is a very dangerous tipping point.

After all, we want to search more deeply in the most promising paths, and spend less efforts in the least promising paths. The best engines achieve this with an incredible branching factor of about 1.5 or so
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Dann Corbit
Posts: 10857
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Improving searching speeds

Post by Dann Corbit » Sun Mar 29, 2020 5:35 am

As evidence that branch factor is not the end-all be-all determining factor in strength, consider that the branching factor champion was a version of ExChess, which achieved the greatest depth per unit time on identical hardware out of all the engines I have ever measured. But it was not strongest. Clearly, you can cut off muscle with the fat if you are not careful enough
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

Dann Corbit
Posts: 10857
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Improving searching speeds

Post by Dann Corbit » Sun Mar 29, 2020 5:38 am

Another side point:
Early in engine development the most important thing to strive for is correctness.
I invite you to read Fabian Letouzy's Fruit source code for an illustration on how to do your code work.
It is a general software principle that holds in all disciplines: first make it right, then make it fast
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

User avatar
mvanthoor
Posts: 217
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

Re: Improving searching speeds

Post by mvanthoor » Sun Mar 29, 2020 1:07 pm

As Dann said: first make it right, then make it fast. Before you add any new functionality, be absolutely 100% sure that your existing functionality is bug free.

As you might have seen, I posted a thread with regard to hashing in the perft function to make it faster. I got the wrong perft results when using a hash.

I did the following:

- stripped all zobrist key updates from make_move() and used the function build_zobrist_key() to calculate the key from scratch at the end of make_move(). This halved the speed of make_move(), but this way, I could be sure that I wasn't forgetting to set/unset parts of the zobrist key anywhere.

I still got the wrong results, so I started checking the "zobrist" module; I found a mistake there, in returning the en-passant keys. I followed BlueFever's VICE tutorial on how to calculate the zobrist keys, understood a part of it (the ep part) wrong, and thus implemented it the wrong way.

- I fixed this implementation, and now perft 7 speed was MUCH higher when using the hash, with correct output, even though handicapped by having to reconstruct the zobrist key from scratch for each move.

- I took build_zobrist_key() out of make_move() and re-instated zobrist key updates in make_move(). The result stayed correct, and speed rose even more.

At this point I can be (almost) certain that move generation and hash usage are bug free, so I can now start to implement the a/b-search.

Apart from mistakes/bugs/incorrect results because of those, there are other things that can slow your engine down. If you're using a programming language that has a C-compatible ABI (such as Rust and Go, or C itself or C++ etc...) then profile your code. I'm using Intel VTune for this. It's normally very expensive, but for opensource/non-corporate use, it's free. (AMD has a similar profiler, but I don't know anything about this because I don't have an AMD CPU.) Look into this; it can tell you exactly where your program is spending the most time. It does require some technical know-how on how to set it up and compile your program appropriately to be profiled tough. That might take you some time to learn and find out if you don't know this already.

User avatar
hgm
Posts: 24450
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Improving searching speeds

Post by hgm » Sun Mar 29, 2020 1:53 pm

There are two independent issues here: number of positions you search per second (nps), and how a given number of nodes translates to a (nominal) search depth.

I think you are asking for the latter; the nps would never allow you to do 14 ply instead of 9 unless you could speed it up by a factor 1000 or more.

The answer is: prune and reduce more.

jdart
Posts: 3924
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Improving searching speeds

Post by jdart » Sun Mar 29, 2020 2:22 pm

Intel VTune for this. It's normally very expensive, but for opensource/non-corporate use, it's free
VTune is only free for non-commerical use on Linux. If you're on the Windows platform, you can get a free trial version, though.

Terje
Posts: 173
Joined: Tue Nov 19, 2019 3:34 am
Location: https://github.com/TerjeKir/weiss
Full name: Terje Kirstihagen

Re: Improving searching speeds

Post by Terje » Sun Mar 29, 2020 2:58 pm

Dann Corbit wrote:
Sun Mar 29, 2020 5:30 am
Pruning is a very complicated and touchy subject.
The only fully sound pruning method is alpha-beta. All other pruning methods take chances.
...
Mate distance pruning is also sound, though not nearly as useful (if at all) as most other pruning techniques.

User avatar
mvanthoor
Posts: 217
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

Re: Improving searching speeds

Post by mvanthoor » Sun Mar 29, 2020 3:16 pm

jdart wrote:
Sun Mar 29, 2020 2:22 pm
Intel VTune for this. It's normally very expensive, but for opensource/non-corporate use, it's free
VTune is only free for non-commerical use on Linux. If you're on the Windows platform, you can get a free trial version, though.
Is it free for open-source use on Windows? I've installed VTune without any problems. If this stops working, I don't know what I'd be using. The Linux profiling tools don't work on Windows/MSYS2, and I don't like the Windows Performance Analyzer.

https://software.intel.com/en-us/vtune/ ... standalone

Here, it says "Download a free copy backed by community forum support."

Through that page, you need to enter your details. I used this page, which I actually found through Talkchess:

https://software.intel.com/en-us/system ... e-download
Use Intel® System Studio with a free license backed by community forum support. This license allows you to use the software for one year. You can refresh the license an unlimited number of times, allowing you to use the latest version.
That doesn't look like a trial; all functionality is actually working. According to the text above, it'll work for one year, and then you'd have to download and install the latest version.

I downloaded this (without having to fill in any forms) and installed without problems.

If at some point I'd need a paid license, that'd be no problem, provided I'm still actively working on my engine, and the license is not too expensive.

Post Reply