Elo gain from transposition table

[niel5946]

Hi.

I am in the middle of reworking my search and eval since I, and others, have noted the lack of strength despite all the features the engine has. I have just finished some relatively quick tc tests for the baseline elo (~1250 elo - too little for bare alphabeta with material+pst?), then killers, history, MvvLva and quiescence. I have recorded the individual gains from each of these additions (tested with baseline vs killers, then killers vs history etc..), and I am now doing the transposition table, with the default size of 16MB.

My problem is that the tt (cutoffs in non-PV nodes + move ordering) only gives around 35 elo, which I would suspect is way too little seeing as hashtables are a main feature of nearly _all_ engines. Therefore, before hunting bugs, I am wondering what you guys think the normal elo gain from a 16MB transposition table would be? Because I really don't have any idea, but I'd suspect it to be pretty significant...

PS: I use a depth based replacement strategy with the condition (entry->depth >= depth - 1), and I have tested that cutoffs and hash-move scoring do occur.

Thank you in advance!

[abulmo2]

I am wondering what you guys think the normal elo gain from a 16MB transposition table would be?

I recently posted this http://talkchess.com/forum3 /viewtopic. ... 20#p887487.
So the gain is about 180 Elo for a 2000 Elo engine and 350 for a 2650 Elo engine (Elo from CCRL scale), with a 64 MB hashtable. I have not tested it on my strongest engine Amoeba (~3000 Elo) which uses a more sophisticated implementation than in Dumb(er).
I really think you should avoid a fixed size transposition table. GUI can send some option values to set the size of your transposition table. Having a fixed size can be considered as a bug ad you get an unexpected behaviour by the user that may ask for another transposition table size. 16 MB is also very tiny.

before hunting bugs

Hunting bugs is very important. Among the 3000 Elo of Amoeba, I guess more than 200 came from bug exterminations.

[niel5946]

I recently posted this http://talkchess.com/forum3 /viewtopic. ... 20#p887487.

I can't open the link. Can you give a title of the post or a working link?

I really think you should avoid a fixed size transposition table. GUI can send some option values to set the size of your transposition table. Having a fixed size can be considered as a bug ad you get an unexpected behaviour by the user that may ask for another transposition table size. 16 MB is also very tiny.

before hunting bugs

Hunting bugs is very important. Among the 3000 Elo of Amoeba, I guess more than 200 came from bug exterminations.

I know that bug-hunting is _very_ important! What I was trying to say was that since I didn't know the expected elo gain - and therefore didn't know whether I have a bug or not - I didn't want to begin hunting bugs in the TT that possibly didn't exist.

Additionally, I don't have a fixed size transposition table, so it can be changed by the GUI. It just defaults to a small 16MB when the engine starts. I know this is small, but I thought that it would at least give some improvement over a no-tt version...

Thank you for the answer!

[Ajedrecista]

Hello Niels:

I recently posted this http://talkchess.com/forum3 /viewtopic. ... 20#p887487.

I can't open the link. Can you give a title of the post or a working link?

[...]

From the number of the post (#887487), it looks like the working link is this one:

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

Regards from Spain.

Ajedrecista.

[mvanthoor]

Hi.

I am in the middle of reworking my search and eval since I, and others, have noted the lack of strength despite all the features the engine has. I have just finished some relatively quick tc tests for the baseline elo (~1250 elo - too little for bare alphabeta with material+pst?),

Depends. Lithander provided me with a private compile of MinimalChess 0.3 that implements the PeSTO tapered and tuned evaluation. That caused a +230 Elo jump. The PST's, and having a tapered evaluation, can have a HUGE difference. However, if your engine has bare alpha-beta, no move ordering, and only PST/Material, 1250 seems ok. If you have alpha-beta, MVV-LVA move ordering, and somewhat good PST's/Material values, high 1500 (like MinimalChess) should be possible; at LEAST. My engine scores 1675-1695 (depending on the opponent and time control) with only Alpha-Beta, QSearch, MVV-LVA, Material, and PST's.

then killers, history, MvvLva and quiescence. I have recorded the individual gains from each of these additions (tested with baseline vs killers, then killers vs history etc..), and I am now doing the transposition table, with the default size of 16MB.

If you have Alpha-Beta, QSearch, MVV-LVA, Material and PST, you're on par with Rustic Alpha 1's feature set. 1650 Elo should be in the cards. If you have killers and history on top of that, I should expect _at least_ 1700 Elo. (Killers and History are next for me, on top of Alpha 2, which is Alpha 1 + Transposition Table.)

PS: A 16 MB TT is tiny. It'll be full in a few seconds:

Code: Select all

go depth 9
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 274616 nps 9153867 hashfull 16 pv e2e4 e7e5 d2d4 d7d5 c1e3
info score cp 5 depth 6 seldepth 18 time 70 nodes 566965 nps 8099500 hashfull 39 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 21 time 198 nodes 1632723 nps 8246076 hashfull 99 pv d2d4 d7d5 e2e3 e7e6 c1d2 c7c5 f1e2 c5d4 e3d4
info score cp 5 depth 8 seldepth 23 time 582 nodes 4156201 nps 7141239 hashfull 294 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c2c4 f8d6 c4d5 e6d5
info score cp 15 depth 9 seldepth 27 time 3726 nodes 28034333 nps 7523976 hashfull 967 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c1d2 f8d6 g1f3
bestmove d2d4

My problem is that the tt (cutoffs in non-PV nodes + move ordering) only gives around 35 elo, which I would suspect is way too little seeing as hashtables are a main feature of nearly _all_ engines.

You must have a bug somewhere, either in the hash table itself, the zobrist hash, or sorting the move. I had a bug storing the wrong move in the hash table during the beta cutoff, which cost me 50-60 Elo. And I already gained 105 Elo which I thought to be disappointing. Fixing this gained another 60-65 Elo, for a total gain of +/- 170 Elo for the TT + TTMove sorting.

In one of the tests done by the author of Dumb & Dumber, the engine Dumb (which is on par with Rustic Alpha 1, except it has a tuned evaluation), gained 180 Elo from TT Cuts + TT Move sorting. Rustic gained about 170 Elo (160-170, depending on the opponents and time controls). As the engine gets more advanced, the hash table's impact becomes bigger: in Dumb (Dumber is a cut-down version of Dumb), disabling the TT, made the engine lose -350 Elo.

So yes, 35 Elo is too little, and there must be something wrong somewhere. 150+ Elo for a simple engine can be expected.

Because the impact of the TT becomes bigger, features added AFTER you already have a TT will therefore seem to gain more Elo. (Either you have 160 Elo for the TT in a simple engine, and then gain more Elo per feature, or you gain a little bit of Elo per feature and then a massive gain for the TT, depending which you implement first.)

[niel5946]

Hi.

I am in the middle of reworking my search and eval since I, and others, have noted the lack of strength despite all the features the engine has. I have just finished some relatively quick tc tests for the baseline elo (~1250 elo - too little for bare alphabeta with material+pst?),

Depends. Lithander provided me with a private compile of MinimalChess 0.3 that implements the PeSTO tapered and tuned evaluation. That caused a +230 Elo jump. The PST's, and having a tapered evaluation, can have a HUGE difference. However, if your engine has bare alpha-beta, no move ordering, and only PST/Material, 1250 seems ok. If you have alpha-beta, MVV-LVA move ordering, and somewhat good PST's/Material values, high 1500 (like MinimalChess) should be possible; at LEAST. My engine scores 1675-1695 (depending on the opponent and time control) with only Alpha-Beta, QSearch, MVV-LVA, Material, and PST's.

then killers, history, MvvLva and quiescence. I have recorded the individual gains from each of these additions (tested with baseline vs killers, then killers vs history etc..), and I am now doing the transposition table, with the default size of 16MB.

If you have Alpha-Beta, QSearch, MVV-LVA, Material and PST, you're on par with Rustic Alpha 1's feature set. 1650 Elo should be in the cards. If you have killers and history on top of that, I should expect _at least_ 1700 Elo. (Killers and History are next for me, on top of Alpha 2, which is Alpha 1 + Transposition Table.)

PS: A 16 MB TT is tiny. It'll be full in a few seconds:

Code: Select all

go depth 9
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 274616 nps 9153867 hashfull 16 pv e2e4 e7e5 d2d4 d7d5 c1e3
info score cp 5 depth 6 seldepth 18 time 70 nodes 566965 nps 8099500 hashfull 39 pv d2d4 d7d5 e2e3 c8d7 c2c4 e7e6 c4d5 e6d5
info score cp 15 depth 7 seldepth 21 time 198 nodes 1632723 nps 8246076 hashfull 99 pv d2d4 d7d5 e2e3 e7e6 c1d2 c7c5 f1e2 c5d4 e3d4
info score cp 5 depth 8 seldepth 23 time 582 nodes 4156201 nps 7141239 hashfull 294 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c2c4 f8d6 c4d5 e6d5
info score cp 15 depth 9 seldepth 27 time 3726 nodes 28034333 nps 7523976 hashfull 967 pv d2d4 d7d5 e2e3 e7e6 f1e2 c8d7 c1d2 f8d6 g1f3
bestmove d2d4

My problem is that the tt (cutoffs in non-PV nodes + move ordering) only gives around 35 elo, which I would suspect is way too little seeing as hashtables are a main feature of nearly _all_ engines.

You must have a bug somewhere, either in the hash table itself, the zobrist hash, or sorting the move. I had a bug storing the wrong move in the hash table during the beta cutoff, which cost me 50-60 Elo. And I already gained 105 Elo which I thought to be disappointing. Fixing this gained another 60-65 Elo, for a total gain of +/- 170 Elo for the TT + TTMove sorting.

In one of the tests done by the author of Dumb & Dumber, the engine Dumb (which is on par with Rustic Alpha 1, except it has a tuned evaluation), gained 180 Elo from TT Cuts + TT Move sorting. Rustic gained about 170 Elo (160-170, depending on the opponents and time controls). As the engine gets more advanced, the hash table's impact becomes bigger: in Dumb (Dumber is a cut-down version of Dumb), disabling the TT, made the engine lose -350 Elo.

So yes, 35 Elo is too little, and there must be something wrong somewhere. 150+ Elo for a simple engine can be expected.

Because the impact of the TT becomes bigger, features added AFTER you already have a TT will therefore seem to gain more Elo. (Either you have 160 Elo for the TT in a simple engine, and then gain more Elo per feature, or you gain a little bit of Elo per feature and then a massive gain for the TT, depending which you implement first.)

I have just tested the transposition table again, and only got ~90 elo (this time NMP was on for both sides though. Before I re-added NMP i got around 120 elo) with 128MB, but I'm still not really satisfied... I have removed the lockless hashing and made the entries a lot smaller, so I had expected some gains.

I have also checked the incrementally updated zobrist hashkey to be right with a lot of searches and perft tests in different positions and different depths. Additionally, I have checked the alphabeta code for errors (numerous times) and removed _nearly all_ sources of possible errors in the table itself, so I really can't grasp how it shouldn't be working or where the bug would be...

What size did you use when testing your hashtable?

[mvanthoor]

I have just tested the transposition table again, and only got ~90 elo (this time NMP was on for both sides though. Before I re-added NMP i got around 120 elo) with 128MB, but I'm still not really satisfied... I have removed the lockless hashing and made the entries a lot smaller, so I had expected some gains.

I have also checked the incrementally updated zobrist hashkey to be right with a lot of searches and perft tests in different positions and different depths. Additionally, I have checked the alphabeta code for errors (numerous times) and removed _nearly all_ sources of possible errors in the table itself, so I really can't grasp how it shouldn't be working or where the bug would be...

I'd need to look into the code to see if I can see something amiss with the TT.

My advice would be to test the TT on top of alpha/beta + qsearch, mvv-lva, material + pst for evaluation, and nothing else. Then you would be testing the TT on top of an engine that has the minimal feature set required to play somewhat decent chess. That feature set is what Rustic Alpha 1 has, and as said, a fully working TT + TTMove ordering on top of that gained close to +170 Elo. (In Dumber, with the same feature set but a tuned evaluation, the TT gained +180 Elo.)

What size did you use when testing your hashtable?

256 MB @ 2 min + 1 second, because that is wat CCRL also uses. It takes about half the game for the table to become full. Everything over 512 MB @ 2 min + 1 second, on an i7-6700K, would probably be massive overkill. If the TT doesn't get full, making it even bigger won't get you anything.

I do have buckets in the TT. It can hold 4 entries at one index. That makes the TT A LOT more efficient. Make sure your entire bucket fits into 64 bytes for maximum speed. You can see in my code how it's done:

https://github.com/mvanthoor/rustic/blo ... osition.rs

The reason why it's more efficient is you can save two different positions at the same index (in different slots in the bucket at that index), so you have to overwrite positions less often. Instead of having to overwrite the position in case of an index collision, you can store 4 of them before you have to start overwriting. (Sorry if you already have this; I haven't checked the code yet.)