Staged move generation done right
Yesterday, I got staged move generation to work for the first time! The previous attempts that I have made, were all centered around the following stages:
- Hash move, if one is found.
- Generation and scoring of captures.
- Good and equal captures.
- Generation and scoring of quiets.
- Quiets
- Bad captures
Although this order seems reasonable enough, I never got it to work, and I think the reason for that is two-fold: 1) The bad captures needs to be identified with SEE which was done at fetch-time, and a failed SEE - resulting in trying a new capture - slowed the engine down greatly. 2) Due to the way I update the move ordering heuristics, I need the entire list of moves searched and that wasn't really possible without doing a lot of deleting and copying during move fetching. This was also a big slowdown.
Now, this time I decided to do something similar to Erik Madsen (MadChess author) with the following stages:
- Hash move if one is found.
- Generation and scoring of captures
- All captures, good and bad.
- Generation and scoring of quiets.
- All quiets.
This is not only simpler, but faster and easier to implement. I suppose the speed gain of this method compared to the earlier one relies on bad captures being refuted very quickly. Thus, if the search function is faster at refuting them, than the fetching function is at storing them in a "bad captures list", there will be a speed gain.
I ran an SPRT test on this implementation yesterday, and this was the results (elo0 = 0, elo1 = 10):
Code: Select all
Score of Lokidev vs Loki350: 309 - 232 - 321 [0.545] 862
... Lokidev playing White: 164 - 105 - 162 [0.568] 431
... Lokidev playing Black: 145 - 127 - 159 [0.521] 431
... White vs Black: 291 - 250 - 321 [0.524] 862
Elo difference: 31.1 +/- 18.4, LOS: 100.0 %, DrawRatio: 37.2 %
SPRT: llr 2.98 (101.2%), lbound -2.94, ubound 2.94 - H1 was accepted
Which is not at all bad
The implementation can be found in movestager.h and movestager.cpp in the staged-move-generation branch of Loki's repository. In the future these files will of course be in the master branch.
The only thing I need to do before merging this into master is to clean up my search_root method. I would like to add a derived class of MoveStager called RootMoveStager which will work exactly as search_root does at the moment. The only reason for this is the easier maintainability from not having two entirely different move ordering implementations.
The future of Loki
As a last thing, I feel like I should mention what Loki's future holds... I just graduated high-school in June (celebrations of this is also the reason I haven't worked much on Loki the last weeks) and because of that, I will have to start working. This in turn means that I probably won't have as much time for developing Loki as I have had previously

Although it is exciting to not be in school anymore, it really saddens me that I can't work as much on Loki as I used to. Chess engine development has really become addicting

But fear not, despite of slower progress, Loki 4.0 will be released some day; And it will be a lot stronger than version 3.5
