About move ordering and TT hitrate

[JVMerlino]

From the initial position, Myrddin gets about 9.2% tt hits after a one-minute search (which is just after it reports the first PV at depth 18). Just as important to determine is the percentage of tt cutoffs, which for Myrddin is about 4.3% during the same search.

The classic position for testing your tt implementation is Fine 70:
[d]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1

Your engine should reach at least depth 30, and choose Kb1 with a winning (at least +3) score, very quickly - like within a second or two. For this position, Myrddin gets about 54.6% tt hits and 37.4% tt cutoffs in a one-minute search.

So it turns out my stats were not accurately reported above, because the test was including eval and pawn hash probes/hits (but not cutoffs, of course). So the real data for just the tt on a 1-minute search with 512 MB hash is:
12.7% tt hits and 6.8% cutoffs for initial position
61.8% tt hits and 43.0% cutoffs for Fine 70

And, thanks to this thread, I discovered that logging hash stats was turned on in the release version, so I got a nearly unmeasurable speed boost as
well by turning it off.

[diep]

Gioviok - not to break in as a blast from the past knowing last code change in Diep was end december 2012...

..yet do not focus too much upon hitrates.

This depends upon so much. Also the position shown is not interesting at all initially to test. Sure it is important test position to see if you can search very deep. Yet take some middle game positions. Do not use tactical testset positions. Use normal human middle game positions and then measure accurately your cutoff rate at cutnodes.

So if you know afterwards that a node gave a cutoff - what is the odds that the first move selected gave a cutoff?

That also includes obviously the best move from hashtable and doesn't include nullmove obviously.

And then focus upon if you know a node gave a cutoff and the position was found in hashtable - so you previously visited this position somewhere - what is the odds that the first move gave a cutoff in this situation?

If that percentage is very low - it could have multiple reasons of course - many many reasons why things go wrong (edit: yet you worry really about this statistic most).

Starting with young engines from the start with the quiescencesearch. That is the most tricky thing to get correct initially.
Ignore all the definitions done there in books. Just use some chessknowledge to give each move some scoring and then pick the highest score out of the list.

At the depths engines search nowadays you want to do everything to order moves as good as possible.

[JVMerlino]

Gioviok - not to break in as a blast from the past knowing last code change in Diep was end december 2012...

Good to see you again, Vincent.

[flok]

Hmmm, caffeinatedpawn finds a1b1 at the first ply.

Code: Select all

position fen 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
go movetime 60000
# think time: 60000
info depth 1 score cp 168 hashfull 0 time 36 nodes 7 nps 111 pv a1b1
...
info depth 27 score cp 159 hashfull 0 time 6603 nodes 5004789 nps 526880 pv a1b1 a7b7 b1c2 b7b8 c2d1 b8c7 d1c1 c7b7 c1b1 b7c7 b1b2 c7c8 b2a1 c8b8 a1a2 b8b7 a2b2
info depth 28 score cp 159 hashfull 0 time 48791 nodes 65179109 nps 904987 pv a1b1 a7b7 b1c2 b7b8 c2d1 b8c7 d1c1 c7b7 c1b1 b7c7 b1b2 c7c8 b2a1 c8b8 a1a2 b8b7 a2b2
bestmove a1b1
# tt lookups: 27718083, hits: 99.98%

99.98% TT hit rate?!! That is indeed impressive.

However, i do have some questions though.

Why does it take so long from d27 to d28 ? Having such high hit rate, I would imagine it should reach it instantly. Could it be that although hits are high, cutoffs are low? Notice you didn't report cutoff rate

I don't know yet.

If the cut-off rate is the rate where the score/move from tt is used directly and no more search is invoked, then it is 39.73%

[diep]

Gioviok - not to break in as a blast from the past knowing last code change in Diep was end december 2012...

Good to see you again, Vincent.

Most welcome - yet you don't know - nor do i - when my next logon will be. Could be 10 years from now

[federico]

Hmmm, caffeinatedpawn finds a1b1 at the first ply.

Code: Select all

position fen 8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
go movetime 60000
# think time: 60000
info depth 1 score cp 168 hashfull 0 time 36 nodes 7 nps 111 pv a1b1
...
info depth 27 score cp 159 hashfull 0 time 6603 nodes 5004789 nps 526880 pv a1b1 a7b7 b1c2 b7b8 c2d1 b8c7 d1c1 c7b7 c1b1 b7c7 b1b2 c7c8 b2a1 c8b8 a1a2 b8b7 a2b2
info depth 28 score cp 159 hashfull 0 time 48791 nodes 65179109 nps 904987 pv a1b1 a7b7 b1c2 b7b8 c2d1 b8c7 d1c1 c7b7 c1b1 b7c7 b1b2 c7c8 b2a1 c8b8 a1a2 b8b7 a2b2
bestmove a1b1
# tt lookups: 27718083, hits: 99.98%

99.98% TT hit rate?!! That is indeed impressive.

However, i do have some questions though.

Why does it take so long from d27 to d28 ? Having such high hit rate, I would imagine it should reach it instantly. Could it be that although hits are high, cutoffs are low? Notice you didn't report cutoff rate

I don't know yet.

If the cut-off rate is the rate where the score/move from tt is used directly and no more search is invoked, then it is 39.73%

That sounds good. Can you tell what is your replacement scheme and what TT size did you use ? I too want a 99% TT hit rate !

As as side note, i noticed that if you take the tt probes of 27718083 and the last node count reported of 65179109, wouldn't that imply that about ~37M nodes were not probed? could there be something wrong there ?

For reference, after 10sec search with a 256mb hash size and single thread, Ceibo reports 45M nodes and 40M probes for this position.

[flok]

That sounds good. Can you tell what is your replacement scheme and what TT size did you use ? I too want a 99% TT hit rate !

https://github.com/folkertvanheusden/Ca ... t.java#L61

* first check if age is different
* then the smallest depth

As as side note, i noticed that if you take the tt probes of 27718083 and the last node count reported of 65179109, wouldn't that imply that about ~37M nodes were not probed? could there be something wrong there ?

I did no longer have the original log-file, but QS is about 28% there and I don't probe in tt.

For reference, after 10sec search with a 256mb hash size and single thread, Ceibo reports 45M nodes and 40M probes for this position.

It has 2097152 tt entries with 8 slots.

[Gioviok]

Well, I did what I normally do when I can't understand what is going on or where the error is located. I have just finished rewriting the whole search,
changing a lot of stuff, like:

• Removing razoring

• Not reducing moves that give check

• Removing pv move scoring from pv table, which just introduced SO MUCH noise in the move ordering (yes I still use those because I can't get pv retrieving from hash table to work, I am just stupid)

• Adding LMP, on depth <= 2 on quiet moves that are in the second half of the ordered move list

• When I extend search on check, if depth was < 0 (because of LMR mostly), depth is automatically set to 1

• Adding mate distance pruning (I don't think it makes a lot of difference here, but I figured I will not have to deal with it later)

• New formula for LMR that seems to work very well

• Differenciating side to move in historyMoves and counterMoves heuristic

• Not reducing moves that land a piece very close to enemy king

• Other stuff...

and, while I still get stomped by fine 70, at least i get stomped @ depth 30 in less than 1 second .
Also, while hit rate didn't seem to improve to much, the move ordering surely did:

Code: Select all

info score cp 47 depth 18 nodes 9767588 pv e2e4 e7e5 g1f3 g8f6 b1c3 b8c6 f1c4 f8d6 d2d4 e8g8 d4d5 c6a5 c4d3 c7c6 h1f1 c6d5 c3d5 a5c6  speed 3254kN/S
For scoring hash accesses: 159249/4966528 (3.20645%)
For move probing accesses: 14662/413874 (3.54262%)
As for move ordering accuracy the best move was the first analyzed 221449/285032 times (77.6927%)
It was in the first 3 moves analyzed 261497/285032 times (91.743%)
It was in the first 5 moves analyzed 271597/285032 times (95.2865%)
It was in the first 10 moves analyzed 275928/285032 times (95.2865%)
bestmove e2e4

Now I have a suspect, and I hope that it is true. In order to solve fine 70, does the eval function need to know endgame specific stuff, blockades and opposition? Does it need to disable NMP, since it is a zugzwang related problem?

Thank all of you in advance

[Joost Buijs]

You don't need special evaluation features to solve fine70. It can be solved on pure tactical grounds but you have to disable NMP (like most engines do when there are only pawns and kings on the board).

[JVMerlino]

You don't need special evaluation features to solve fine70. It can be solved on pure tactical grounds but you have to disable NMP (like most engines do when there are only pawns and kings on the board).

Ah yes, this is critical. If I always allow null move pruning, Myrddin jumps to depth 66 in three seconds, but with a draw score and the move Kb2. Depth doesn't mean anything if you've selected the wrong move. So I disable NMP if the side to move has only pawns.