This weekend I've finally written some code for Rustic again. I implemented killer moves. It has 2 for now, even though I can make it 3 or more by just setting a constant. I've tried 2-8 killer moves. If you have more than 2 killer moves, it seems that actually looking if a move is in the killer move list costs more time than the better sorting will gain. I observed a decreased number of nodes with each increase of the number of killer moves, but the time to depth got worse.
1 works, 2 works, 3 is inconclusive (depends on the position, some gain, some loss), 4-6 is wonky (all over the place), 7 is similar to 2 killer moves, and 8 gives some improvement in some positions on high depths. I think I'll be sticking with the traditional 2 killer moves.
According to the start position, the implementation seems to work well if using 2 killer moves:
Code: Select all
Startpos, 32 MB TT, no killers
info score cp 70 depth 1 seldepth 1 time 0 nodes 21 nps 0 pv e2e4
info score cp 0 depth 2 seldepth 4 time 0 nodes 132 nps 0 pv e2e4 e7e5
info score cp 60 depth 3 seldepth 8 time 0 nodes 1068 nps 0 pv e2e4 e7e5 d2d4
info score cp 0 depth 4 seldepth 10 time 1 nodes 6372 nps 6372000 pv e2e4 e7e5 d2d4 d7d5
info score cp 20 depth 5 seldepth 14 time 30 nodes 274535 nps 9151167 hashfull 8 pv e2e4 e7e5 d2d4 d7d5 c1e3
info score cp 5 depth 6 seldepth 18 time 71 nodes 566795 nps 7983028 hashfull 19 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 21 time 210 nodes 1631280 nps 7768000 hashfull 49 pv d2d4 d7d5 e2e3 e7e6 c1d2 c7c5 f1e2 c5d4 e3d4
info score cp 5 depth 8 seldepth 23 time 603 nodes 4131456 nps 6851502 hashfull 148 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c2c4 f8d6 c4d5 e6d5
info score cp 15 depth 9 seldepth 27 time 3659 nodes 26807077 nps 7326340 hashfull 737 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c1d2 f8d6 g1f3
info score cp 10 depth 10 seldepth 33 time 24720 nodes 173647599 nps 7024579 hashfull 1000 pv d2d4 d7d5 e2e3 e7e6 g1f3 g8f6 f1b5 c7c6 b5e2 f8b4 c1d2 d8b6
Startpos, 32 MB TT, 2 killers
info score cp 70 depth 1 seldepth 1 time 0 nodes 21 nps 0 pv e2e4
info score cp 0 depth 2 seldepth 4 time 0 nodes 98 nps 0 pv e2e4 e7e5
info score cp 60 depth 3 seldepth 8 time 0 nodes 707 nps 0 pv e2e4 e7e5 d2d4
info score cp 0 depth 4 seldepth 9 time 0 nodes 3301 nps 0 pv e2e4 e7e5 d2d4 d7d5
info score cp 20 depth 5 seldepth 14 time 3 nodes 23491 nps 7830333 pv e2e4 e7e5 d2d4 d7d5 c1e3
info score cp 5 depth 6 seldepth 18 time 19 nodes 114759 nps 6039947 hashfull 6 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 18 time 62 nodes 409997 nps 6612855 hashfull 17 pv d2d4 d7d5 e2e3 e7e6 c1d2 c7c5 f1e2 c5d4 e3d4
info score cp 5 depth 8 seldepth 21 time 276 nodes 1640289 nps 5943076 hashfull 83 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c2c4 f8d6 c4d5 e6d5
info score cp 15 depth 9 seldepth 23 time 1231 nodes 8143084 nps 6615015 hashfull 339 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c1d2 f8d6 g1f3
info score cp 10 depth 10 seldepth 26 time 6945 nodes 42409207 nps 6106437 hashfull 976 pv d2d4 d7d5 e2e3 e7e6 g1f3 g8f6 f1b5 c7c6 b5e2 f8b4 c1d2 d8b6
Depth 9: 26.8 mln nodes => 8.1 mln nodes, time 3.7 seconds => 1.2 seconds
Depth 10: 173.6 mln nodes => 42.4 mln nodes, time 24.7 seconds => 6.95 seconds
And the output is exactly the same. That is a massive improvement. In other positions such as KiwiPete, the Killer Moves are much less effective. (It's logical for a quiet move to be less effective in a very busy, tactical position, in general.)
What I didn't expect is that implementing _only_ killer moves as an extra on top of the hash table seems to not gain any Elo. It does _cost_ any Elo either. I've deleted the testrun I did, because all engines I picked except 2 were at least +50 over Rustic; so maybe I picked too engines that are too strong.
I'll do another testrun with engines between 1750 and 1850 Elo, and 1-2 under 1750 and 1-2 at around 1900. I'll also do a testrun of Alpha 2 against this new dev version.
If this (and maybe the history heuristic) actually don't gain any strength yet, I may postpone the release of Alpha 3 so I can first add Aspiration Windows and PVS. Even so, I wonder why the dev-version performed almost exactly the same as Alpha 2, even though tests like the above clearly show that the killer moves can save a lot of calculation. (At least, in some positions.)