Improving searching speeds

[SrcEngine]

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]

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

[Dann Corbit]

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

[Dann Corbit]

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

[mvanthoor]

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.

[hgm]

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]

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]

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.

[mvanthoor]

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.