Hash move ordering vs. Hash cuts: savings in number of nodes visited

[mvanthoor]

With MVV_LVA, No TT Move ordering, No TT cuts:

Code: Select all

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 267 nps 0 pv d2d4 d7d5
info score cp 60 depth 3 seldepth 8 time 0 nodes 3688 nps 0 pv d2d4 d7d5 e2e3
info score cp 0 depth 4 seldepth 11 time 5 nodes 46380 nps 9276000 pv d2d4 d7d5 c1g5 c8g4
info score cp 20 depth 5 seldepth 15 time 60 nodes 573867 nps 9564450 hashfull 7 pv d2d4 d7d5 c1f4 c8g4 f4e5
info score cp 5 depth 6 seldepth 18 time 439 nodes 3913694 nps 8915021 hashfull 53 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 24 time 3651 nodes 33252202 nps 9107697 hashfull 332 pv c2c4 b8c6 d2d3 e7e5 e2e4 f8b4 c1d2 d7d6 d2b4 c6b4
info score cp 5 depth 8 seldepth 26 time 30279 nodes 261511445 nps 8636727 hashfull 955 pv e2e4 d7d5 e4e5 c8d7 d2d4 e7e6 c2c4 f8e7 c4d5 e6d5

30.3 seconds to depth 8, 261.5 million nodes visited.

With MVV_LVA, With TT Move ordering, No TT cuts:

Code: Select all

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 6373 nps 6373000 pv e2e4 e7e5 d2d4 d7d5
info score cp 20 depth 5 seldepth 14 time 31 nodes 289480 nps 9338065 hashfull 4 pv e2e4 e7e5 d2d4 d7d5 c1e3
info score cp 5 depth 6 seldepth 18 time 74 nodes 607036 nps 8203189 hashfull 11 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 21 time 314 nodes 2603220 nps 8290510 hashfull 42 pv c2c4 d7d5 c4d5 d8d5 b1c3 d5d4 e2e4
info score cp 5 depth 8 seldepth 23 time 883 nodes 6557067 nps 7425897 hashfull 124 pv e2e4 d7d5 e4e5 e7e6 d2d4 c8d7 c2c4 f8e7 c4d5 e6d5
info score cp 15 depth 9 seldepth 27 time 7780 nodes 61081212 nps 7851056 hashfull 760 pv g1f3 d7d5 d2d4 e7e6 e2e3 c8d7 c1d2 f8d6 f1e2

0.883 seconds to depth 8, 6.557.067 visited.

30.3 seconds -> 0.883 seconds

That's the massive improvement I was reading about with regard to TT Move / PV Move ordering.

With MVV_LVA, With TT Move ordering, With TT cuts:

Code: Select all

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 274223 nps 9140767 hashfull 4 pv e2e4 e7e5 d2d4 d7d5 c1e3
info score cp 5 depth 6 seldepth 18 time 69 nodes 566483 nps 8209899 hashfull 9 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 21 time 193 nodes 1629078 nps 8440819 hashfull 24 pv d2d4 d7d5 e2e3 e7e6 c1d2 c7c5 f1e2 c5d4 e3d4
info score cp 5 depth 8 seldepth 23 time 551 nodes 4117188 nps 7472211 hashfull 74 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c2c4 f8d6 c4d5 e6d5
info score cp 15 depth 9 seldepth 27 time 3377 nodes 26204953 nps 7759832 hashfull 426 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c1d2 f8d6 g1f3
info score cp 10 depth 10 seldepth 33 time 21782 nodes 160635780 nps 7374703 hashfull 997 pv d2d4 d7d5 e2e3 e7e6 g1f3 g8f6 f1b5 c7c6 b5e2 f8b4 c1d2 d8b6

TT Cuts improve depth to 8 from 0.883 to 0.551 seconds.
Nodes visited is reduced from 6.557.067 to 4.117.188

Time to depth 9 is about halved, nodes visited reduced from 61 million to 26 million.

The engine can now reach depth 10 in almost 9 seconds LESS than it could reach depth 8 without the TT.

It seems I now finally get the performance from the TT which I was expecting sine I began testing it.

Thanks for your help again, guys. I'll have to update my credits again

[Mike Sherwin]

With MVV_LVA, No TT Move ordering, No TT cuts:

Code: Select all

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 267 nps 0 pv d2d4 d7d5
info score cp 60 depth 3 seldepth 8 time 0 nodes 3688 nps 0 pv d2d4 d7d5 e2e3
info score cp 0 depth 4 seldepth 11 time 5 nodes 46380 nps 9276000 pv d2d4 d7d5 c1g5 c8g4
info score cp 20 depth 5 seldepth 15 time 60 nodes 573867 nps 9564450 hashfull 7 pv d2d4 d7d5 c1f4 c8g4 f4e5
info score cp 5 depth 6 seldepth 18 time 439 nodes 3913694 nps 8915021 hashfull 53 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 24 time 3651 nodes 33252202 nps 9107697 hashfull 332 pv c2c4 b8c6 d2d3 e7e5 e2e4 f8b4 c1d2 d7d6 d2b4 c6b4
info score cp 5 depth 8 seldepth 26 time 30279 nodes 261511445 nps 8636727 hashfull 955 pv e2e4 d7d5 e4e5 c8d7 d2d4 e7e6 c2c4 f8e7 c4d5 e6d5

30.3 seconds to depth 8, 261.5 million nodes visited.

With MVV_LVA, With TT Move ordering, No TT cuts:

Code: Select all

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 6373 nps 6373000 pv e2e4 e7e5 d2d4 d7d5
info score cp 20 depth 5 seldepth 14 time 31 nodes 289480 nps 9338065 hashfull 4 pv e2e4 e7e5 d2d4 d7d5 c1e3
info score cp 5 depth 6 seldepth 18 time 74 nodes 607036 nps 8203189 hashfull 11 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 21 time 314 nodes 2603220 nps 8290510 hashfull 42 pv c2c4 d7d5 c4d5 d8d5 b1c3 d5d4 e2e4
info score cp 5 depth 8 seldepth 23 time 883 nodes 6557067 nps 7425897 hashfull 124 pv e2e4 d7d5 e4e5 e7e6 d2d4 c8d7 c2c4 f8e7 c4d5 e6d5
info score cp 15 depth 9 seldepth 27 time 7780 nodes 61081212 nps 7851056 hashfull 760 pv g1f3 d7d5 d2d4 e7e6 e2e3 c8d7 c1d2 f8d6 f1e2

0.883 seconds to depth 8, 6.557.067 visited.

30.3 seconds -> 0.883 seconds

That's the massive improvement I was reading about with regard to TT Move / PV Move ordering.

With MVV_LVA, With TT Move ordering, With TT cuts:

Code: Select all

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 274223 nps 9140767 hashfull 4 pv e2e4 e7e5 d2d4 d7d5 c1e3
info score cp 5 depth 6 seldepth 18 time 69 nodes 566483 nps 8209899 hashfull 9 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 21 time 193 nodes 1629078 nps 8440819 hashfull 24 pv d2d4 d7d5 e2e3 e7e6 c1d2 c7c5 f1e2 c5d4 e3d4
info score cp 5 depth 8 seldepth 23 time 551 nodes 4117188 nps 7472211 hashfull 74 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c2c4 f8d6 c4d5 e6d5
info score cp 15 depth 9 seldepth 27 time 3377 nodes 26204953 nps 7759832 hashfull 426 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c1d2 f8d6 g1f3
info score cp 10 depth 10 seldepth 33 time 21782 nodes 160635780 nps 7374703 hashfull 997 pv d2d4 d7d5 e2e3 e7e6 g1f3 g8f6 f1b5 c7c6 b5e2 f8b4 c1d2 d8b6

TT Cuts improve depth to 8 from 0.883 to 0.551 seconds.
Nodes visited is reduced from 6.557.067 to 4.117.188

Time to depth 9 is about halved, nodes visited reduced from 61 million to 26 million.

The engine can now reach depth 10 in almost 9 seconds LESS than it could reach depth 8 without the TT.

It seems I now finally get the performance from the TT which I was expecting sine I began testing it.

Thanks for your help again, guys. I'll have to update my credits again

Bricabrac does not have a TT yet. The reductions have been removed. The PV move has been disabled. And I'm using SISSY bitboards instead of magic. The move ordering that Bric has is sorting of the root moves. Every move generated in Qsearch and regular search gets this scoring: m->score = (value[board[ts]] << 4) - value[m->type];. The only other move ordering I do is in Search();

Code: Select all

if (depth > 3) {
    for (mi = 0; mi < n; mi++) {
      mov = m + mi;
      MakeMove(t, mov);
      mov->score = -Qsearch(t, m + n, -beta - 1000, -alpha + 100);
      TakeBack(t, mov);
    }
  }

If depth is 3 or less the only move sorting is from the gen move functions as I showed.

FEN: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1

Bricabrac:
1 00:00 20 20 +0.36 g1f3
2 00:00 87 87 0.00 g1f3 g8f6
3 00:00 679 679 +0.35 g1f3 g8f6 d2d4
4 00:00 4k 4k 0.00 g1f3 g8f6 d2d4 d7d5
5 00:00 19k 19k +0.33 g1f3 g8f6 d2d4 d7d5 b1c3
6 00:00 112k 11,221k 0.00 g1f3 g8f6 d2d4 d7d5 b1c3 b8c6
7 00:00 700k 14,003k +0.28 g1f3 g8f6 d2d4 d7d5 b1c3 b8c6 c1e3
8 00:00 5,080k 10,584k +0.08 e2e4 e7e5 g1f3 g8f6 b1c3 b8c6 d2d4 f8d6
9 00:01 22,014k 13,423k +0.36 e2e4 e7e5 g1f3 g8f6 b1c3 f8d6 d2d4 b8c6 c1e3

Actually 1.64 seconds.

I might be old and not as bright as I used to be but I'm not totally worthless. Maybe you can test some of this.

[Ras]

depth 10 seldepth 33

First, congrats to unlock the TTs

What I noticed is a huge seldepth here, and I'm pretty sure that these are not useful lines. Probably mutual queen plunder races or something like that. You can prevent that in quiescence if, after a certain quiescence depth of a few plies, you only allow re-captures to the square that the previous (oppenent) move was to.

[mvanthoor]

depth 10 seldepth 33

First, congrats to unlock the TTs

Thanks. I knew something was wrong during the entire week I've been testing, even though the performance was up by +100 Elo. Thanks to mar and emadsen for thinking with me on this problem. Their pointers allowed me to finally see it. I ran a quick 100 match between Alpha2/TT-with-bug (which was up by +100 against Alpha 1), and Alpha2/TT-without-bug... the version without this bug scored +110 against the version with the bug. That gives a possible total increase of +210 over Alpha 1. Instead of scratching at the 1800 door, I may be near or even just over 1900 with some luck.

What I noticed is a huge seldepth here, and I'm pretty sure that these are not useful lines. Probably mutual queen plunder races or something like that. You can prevent that in quiescence if, after a certain quiescence depth of a few plies, you only allow re-captures to the square that the previous (oppenent) move was to.

I know. I don't worry about these things for now. Some of those optimizations (SEE, recapture on same square, futility pruning, etc) will be added step by step. I don't know how to implement this yet. I'm researching all those topics one by one, and then implementing them from scratch (with pseudo-code as reference only, as much as possible).

Alpha 2 will only have a TT and TT Move sorting added.
Alpha 3 will have Killer and History ordering added, and probably Aspiration Windows and PVS (if those aren't too large/difficult to implement; or they'll be shoved towards the next version).

[mvanthoor]

I might be old and not as bright as I used to be but I'm not totally worthless. Maybe you can test some of this.

If you can reach depth 9 in that position in less than two seconds without a TT and without move sorting except basic sorting in the root, while it takes my engine almost 8 seconds, WITH TT, WITH MVV-LVA, AND TT Move sorting, then you're doing something that I can't understand yet. So, I'd test it, if I understood it... maybe I just haven't encountered the concept you're using.

[Mike Sherwin]

I might be old and not as bright as I used to be but I'm not totally worthless. Maybe you can test some of this.

If you can reach depth 9 in that position in less than two seconds without a TT and without move sorting except basic sorting in the root, while it takes my engine almost 8 seconds, WITH TT, WITH MVV-LVA, AND TT Move sorting, then you're doing something that I can't understand yet. So, I'd test it, if I understood it... maybe I just haven't encountered the concept you're using.

I have this move structure.

Code: Select all

struct SMove {
  u08 fs;
  u08 ts;
  u08 mt;
  u08 ct;
  s32 score;
};

Therefore every move has a score. When I generate moves I score them: (matPst[ts] << 4) - matPos[fs]. So it is MVV - LVA including PST values except the victim is weighted more heavily. If SEE was used the << 4 would not be needed because it would be known if the victim was defended.

Then there is this in search.

Code: Select all

  if (depth > 3) {
    for (mi = 0; mi < n; mi++) {
      mov = m + mi;
      MakeMove(t, mov);
      mov->score = -Qsearch(t, m + n, -beta - 1000, -alpha + 100);
      TakeBack(t, mov);
    }
  }

I use this in RomiChess. I got a lot of criticism from Bob over this 16 years ago. So maybe that is why no one else tried it, idk. The idea is very simple. It is a form of IID. In RomiChess it is done as a last step in the move ordering however, Romi was just about as fast to depth when all the other move ordering was disabled. The open window is the key as each move gets a more accurate score. Therefore better move ordering. When I added only this one ply + Qsearch open window IID to the one trick pony TSCP, TSCP got 1.5 average ply deeper searches.

[mvanthoor]

Then there is this in search.

Code: Select all

  if (depth > 3) {
    for (mi = 0; mi < n; mi++) {
      mov = m + mi;
      MakeMove(t, mov);
      mov->score = -Qsearch(t, m + n, -beta - 1000, -alpha + 100);
      TakeBack(t, mov);
    }
  }

I use this in RomiChess. I got a lot of criticism from Bob over this 16 years ago. So maybe that is why no one else tried it, idk. The idea is very simple. It is a form of IID. In RomiChess it is done as a last step in the move ordering however, Romi was just about as fast to depth when all the other move ordering was disabled. The open window is the key as each move gets a more accurate score. Therefore better move ordering. When I added only this one ply + Qsearch open window IID to the one trick pony TSCP, TSCP got 1.5 average ply deeper searches.

So this is a search extension, executed only when depth > 3. How is it limited? Normally qsearch only takes alpha and beta, and then whatever parameters you decide for yourself; but I can't determine what t or m are.

[Mike Sherwin]

Then there is this in search.

Code: Select all

  if (depth > 3) {
    for (mi = 0; mi < n; mi++) {
      mov = m + mi;
      MakeMove(t, mov);
      mov->score = -Qsearch(t, m + n, -beta - 1000, -alpha + 100);
      TakeBack(t, mov);
    }
  }

I use this in RomiChess. I got a lot of criticism from Bob over this 16 years ago. So maybe that is why no one else tried it, idk. The idea is very simple. It is a form of IID. In RomiChess it is done as a last step in the move ordering however, Romi was just about as fast to depth when all the other move ordering was disabled. The open window is the key as each move gets a more accurate score. Therefore better move ordering. When I added only this one ply + Qsearch open window IID to the one trick pony TSCP, TSCP got 1.5 average ply deeper searches.

So this is a search extension, executed only when depth > 3. How is it limited? Normally qsearch only takes alpha and beta, and then whatever parameters you decide for yourself; but I can't determine what t or m are.

Sorry, I should have just posted pseudo code. The "t" is a thread structure pointer although only one thread is currently used. The "m + n" is a move list pointer with m being the first element in the list, n being the number of moves in the list and m + n being the element just after the last move.

I guess search extension is correct. It is performed before the main search loop just to score the moves. Well depth > 2 is okay as well but anything less will be slower. "Normally qsearch only takes alpha and beta" Yes, that is true however this is not looking for scores inside the a/b window. It is looking for more accurate scores than that so the window is widened. Unless there is a tactic deeper than one ply it returns very accurate scores for very little cost. If all you have so far is the TT move then put this right after. If there is no TT move then you can do a reduced search with a/b to get a best move and after that put this. This will order the list better because the moves and captures have a full Qsearch to score them.

[mvanthoor]

...

Thanks for the explanation. I'll take search extensions such as this into account when my engine gets to that point

Let's first implement all the "normal" stuff correctly

[abulmo2]

I made a little experiment to see which one, of hash move ordering or hash cutoff brings more Elo. I use Dumb-1.8, with full hash (dumb hash), hash used for cutoff only (dumb hash cutoff) , hash used for move ordering (dumb hash bestmove) only and Dumb with no hashtable at all (dumb no hash). I repeat the experiment with Dumber 1.2 using the same hashtable code as in Dumb. I play a round-robin tournament at bullet time control (10" + 0.1") between the Dumb versions and a few other opponents of similar strength, and another round-robin tournament with the Dumber versions and a few other opponents.

Voilà the results for Dumber:

Code: Select all

   # PLAYER                      : RATING  ERROR   POINTS  PLAYED    (%)
   1 dumber hash bestmove        :    4.3   27.7    663.5     800   82.9%
   2 dumber hash                 :    0.0   27.8    660.5     800   82.6%
   3 dumber hash cutoff          : -167.4   22.8    529.5     800   66.2%
   4 dumber no hash              : -183.1   24.5    516.0     800   64.5%

In this case, the hash cutoff brings very little improvements (within the error bar) over no hash at all; on the other hand, using hash for move ordering brings as much Elo (within the error bar) as using a full hashtable.

Now with Dumb:

Code: Select all

   # PLAYER               : RATING  ERROR   POINTS  PLAYED    (%)
   1 dumb hash            :    0.0   17.3    455.0     700   65.0%
   2 dumb hash cutoff     :  -69.4   15.9    385.5     700   55.1%
   3 dumb hash bestmove   : -159.3   17.5    293.5     700   41.9%
   4 dumb no hash         : -347.2   21.7    128.0     700   18.3%

The results are inverted. Hash cutoffs leads to more Elo gain than hash used just to sort the bestmove. The gain for the full hash over no hash are almost twice bigger than for Dumber.

The explanation for this two different behaviours resides in the differences between Dumb and Dumber. Dumber uses plain alphabeta, whereas Dumb uses PVS and aspiration windows, ie Dumb practices a lot of re-researches of the same tree, making hash cutoffs more frequent. Move ordering is also improved in Dumb with killers and history tables. Finally Dumb uses a lot of prunings, extensions and reductions that produces deeper searches were transpositions are more likely to occur. All this render the hashtable more efficient in Dumb than in Dumber.

The final conclusion is that your mileage may vary. A heuristic that may not work well at some stages of the development of a chess engine may get more important at a later stage. It is also better to not draw any definitive conclusion about an algorithm. What may not work at a time can be a brilliant idea later.