mvanthoor wrote: ↑Tue Mar 02, 2021 11:33 pm
Mike Sherwin wrote: ↑Tue Mar 02, 2021 10:26 pm
Hmm, I was not trying to fool anyone. So, I'm glad you pointed that out.
And here I am, implementing hash move sorting... it does seem to work (the hash move gets a score high enough to move it to the front of the move list, as it is added to the MVV-LVA score that may have already been there, and is higher than the highest MVV-LVA score), and in most positions, there's a massive cut in the search tree... but it still only gains me some time; not even enough to make an extra ply in the middle game.
Talk about expectations.
I'm half expecting that one of these sorting options will "magically" get me from depth 7-8 to somewhere around 14, but it seems that, to some extent, the gain the hash move sorting makes, is partially off-set by the speed loss the engine incurs due to the probe.
Note the following (I might be doing something wrong here):
- I am NOT yet cutting off the entire search by hash value; I'm ONLY probing for the move to test the move sorting.
- I do the probe right before the moves are generated, and if there's a hash entry, I get the move from it; without paying attention to the depth the hash entry was stored for. Can this be done for the move, or should the depth be equal or greater, just as for the values?
- Then I sort the moves.
- I save a "best_move" for the move loop, to put in the hash table when Alpha is raised (where the PV is also updated)
- I put this best move into the hash table when I write the entry. I write an entry where Beta is raised, and just before Alpha is returned (same as is shown on Bruce Moreland's site). I also save the hash flags and evaluation score, but as said, I don't use them yet.
- I write "depth" into the hash entry... intuitively, this feels correct, but by checking some engines, I have seen one that writes ply's.
Some results:
For example, this is a run in a K+P vs. K endgame, without a hash table:
Code: Select all
info score cp 140 depth 1 seldepth 1 time 0 nodes 7 nps 0 pv e2e4
info score cp 90 depth 2 seldepth 2 time 0 nodes 26 nps 0 pv e2e4 e8f7
info score cp 140 depth 3 seldepth 3 time 0 nodes 100 nps 0 pv e1f2 e8f7 e2e4
info score cp 110 depth 4 seldepth 4 time 0 nodes 394 nps 0 pv e1f2 e8d7 e2e4 d7c6
info score cp 140 depth 5 seldepth 5 time 0 nodes 843 nps 0 pv e1d2 e8d7 d2c3 d7c6 e2e4
info score cp 110 depth 6 seldepth 6 time 0 nodes 3666 nps 0 pv e1d2 e8d7 d2c3 d7d6 c3d4 d6c6
info score cp 180 depth 7 seldepth 8 time 2 nodes 11114 nps 5557000 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4
info score cp 180 depth 8 seldepth 10 time 7 nodes 52829 nps 7547000 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6b5 e2e4 b5c6
info score cp 190 depth 9 seldepth 10 time 27 nodes 141749 nps 5249963 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4 d6c6 e4e5
info score cp 190 depth 10 seldepth 12 time 90 nodes 624560 nps 6939556 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4 d6e6 e4e5 e6f5
info score cp 190 depth 11 seldepth 14 time 293 nodes 1523320 nps 5199044 pv e1d2 e8d7 d2c3 d7c6 c3c4 c6d6 c4d4 d6c6 e2e4 c6d6 e4e5 d6c6
info score cp 190 depth 12 seldepth 16 time 829 nodes 5604808 nps 6760926 pv e1d1 e8d7 d1c2 d7c6 c2d3 c6b5 d3d4 b5c6 e2e4 c6d6 e4e5 d6e6 d4e4
info score cp 190 depth 13 seldepth 18 time 3158 nodes 16045639 nps 5080950 pv e1d1 e8d7 d1c2 d7c6 c2c3 c6c5 e2e4 c5d6 c3d4 d6e6 e4e5 e6f5 d4d5
info score cp 190 depth 14 seldepth 20 time 9473 nodes 62300713 nps 6576661 pv e1d1 e8d7 d1c1 d7c6 c1c2 c6b5 c2c3 b5c5 e2e4 c5c6 c3d4 c6d6 e4e5 d6e6 d4e4
info score cp 190 depth 15 seldepth 22 time 44420 nodes 215290136 nps 4846694 pv e1d1 e8d7 d1c1 d7c6 c1c2 c6b5 c2c3 b5c5 e2e4 c5d6 c3d4 d6e6 e4e5 e6f5 d4d5
Same run with a 32 MB Hash table (which in the end is only used 6.1%, because there are a lot of transpositions)
Code: Select all
info score cp 140 depth 1 seldepth 1 time 0 nodes 7 nps 0 pv e2e4
info score cp 90 depth 2 seldepth 2 time 0 nodes 21 nps 0 pv e2e4 e8f7
info score cp 140 depth 3 seldepth 3 time 0 nodes 55 nps 0 pv e2e4 e8f7 e1f2
info score cp 110 depth 4 seldepth 4 time 0 nodes 185 nps 0 pv e2e4 e8f7 e1f2 f7e6
info score cp 140 depth 5 seldepth 5 time 0 nodes 412 nps 0 pv e2e4 e8f7 e1f2 f7e6 f2e3
info score cp 110 depth 6 seldepth 6 time 0 nodes 2449 nps 0 pv e1d2 e8d7 d2c3 d7d6 c3d4 d6c6
info score cp 180 depth 7 seldepth 8 time 1 nodes 7339 nps 7339000 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4
info score cp 180 depth 8 seldepth 10 time 6 nodes 36287 nps 6047833 hashfull 2 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6b5 e2e4 b5c6
info score cp 190 depth 9 seldepth 10 time 23 nodes 100365 nps 4363696 hashfull 3 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4 d6c6 e4e5
info score cp 190 depth 10 seldepth 12 time 85 nodes 526843 nps 6198153 hashfull 6 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4 d6e6 e4e5 e6f5
info score cp 190 depth 11 seldepth 13 time 270 nodes 1274079 nps 4718811 hashfull 10 pv e1d2 e8d7 d2c3 d7c6 c3c4 c6d6 c4d4 d6c6 e2e4 c6d6 e4e5 d6c6
info score cp 190 depth 12 seldepth 16 time 780 nodes 4822260 nps 6182385 hashfull 14 pv e1d1 e8d7 d1c2 d7c6 c2d3 c6b5 d3d4 b5c6 e2e4 c6d6 e4e5 d6e6 d4e4
info score cp 190 depth 13 seldepth 18 time 2862 nodes 13443760 nps 4697331 hashfull 22 pv e1d1 e8d7 d1c2 d7c6 c2c3 c6c5 e2e4 c5d6 c3d4 d6e6 e4e5 e6f5 d4d5
info score cp 190 depth 14 seldepth 20 time 8767 nodes 53252243 nps 6074169 hashfull 36 pv e1d1 e8d7 d1c1 d7c6 c1c2 c6b5 c2c3 b5c5 e2e4 c5c6 c3d4 c6d6 e4e5 d6e6 d4e4
info score cp 190 depth 15 seldepth 22 time 39418 nodes 178134146 nps 4519107 hashfull 61 pv e1d1 e8d7 d1c1 d7c6 c1c2 c6b5 c2c3 b5c5 e2e4 c5d6 c3d4 d6e6 e4e5 e6f5 d4d5
As can be seen, at depth 15, the time without the hash table is 44.4 seconds. With hash table, the time is 39.42 seconds. The search tree has been cut from ~215 million moves, down to ~178 million moves. So yes, it does seem that the hash move sorting is working, but I had expected a lot more from it. One of the CCRL-testers said: "As soon as you implement a hash table, your engine will be at least at 2200 Elo". I don't really believe that anymore, except if the search cuts by hash value gives a massive improvement. I also still need to implement all the other sorting options, such as PV Move sort, killers, and heuristics. It could of course be that all of these sorting options, together with the search cut by hash value, gives a huge boost: in the same way as ELO_GAIN(PST + SQ) > (ELO_GAIN(PST) + ELO_GAIN(SQ))
I have a feeling my expectations are somewhat out of line here.
PS: I have checked the scoring. It works. I have a MOVE 64-bit int (within a struct), which also holds the sort score. The struct has a function called "add_value"; this is used to add the MVV_LVA value, and also the hash move value. It basically gets the current score, XOR's it out of the move, adds current+value together, shifts it left the correct number of bits, and XOR's it in again. I have checked the before and after, and the hash move score is correctly added.