Data structure choice for TT

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 26108
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Data structure choice for TT

Post by hgm » Wed Aug 12, 2020 7:43 am

In practice the randomness of the Zobrist keys doesn't have to be very good; Zobrist hashing is a very forgiving scheme. People even have tried deriving the keys from just 12 truly random numbers (for the piece types), and derive the keys from those by making 64 bit-rotated versions of those for the squares. This seems to work fine too, even though rotating a bit pattern can hardly be called a good random generator.

To save (cache) memory I often use a scheme where the piece-square keys are calculated on the fly, by multiplying (32-bit) piece and square keys. If you are dealing with a board of 256 squares, and some 64 piece types per player, that is a big saver.

OliverBr
Posts: 669
Joined: Tue Dec 18, 2007 8:38 pm
Location: Munich, Germany
Full name: Dr. Oliver Brausch
Contact:

Re: Data structure choice for TT

Post by OliverBr » Thu Aug 13, 2020 4:19 pm

hgm wrote:
Wed Aug 12, 2020 7:43 am
In practice the randomness of the Zobrist keys doesn't have to be very good; Zobrist hashing is a very forgiving scheme.
I thought that good randomness helps in filling the hash-slots effectively. As soon as you have some pattern in your keys, many slots will never be populated.
Anyway, I tried this simple random-generator and can verify that the playing strength is the same, so I replaced it in my new version 5.6.3.
Chess Engine OliThink: http://brausch.org/home/chess
OliThink GitHub:https://github.com/olithink

User avatar
hgm
Posts: 26108
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Data structure choice for TT

Post by hgm » Thu Aug 13, 2020 7:28 pm

The number of keys that you combine in a typical position is so large that it would be a miracle if they would conspire to systematically avoid some slots.

OliverBr
Posts: 669
Joined: Tue Dec 18, 2007 8:38 pm
Location: Munich, Germany
Full name: Dr. Oliver Brausch
Contact:

Re: Data structure choice for TT

Post by OliverBr » Mon Aug 17, 2020 12:21 am

hgm wrote:
Thu Aug 13, 2020 7:28 pm
The number of keys that you combine in a typical position is so large that it would be a miracle if they would conspire to systematically avoid some slots.
Of course, this is correct.
Nevertheless I would guess that a better random generator yold in a better distribution over the slots.
Chess Engine OliThink: http://brausch.org/home/chess
OliThink GitHub:https://github.com/olithink

User avatar
Kotlov
Posts: 232
Joined: Fri Jul 10, 2015 7:23 pm
Location: Russia

Re: Data structure choice for TT

Post by Kotlov » Mon Aug 17, 2020 7:23 am

OliverBr wrote:
Mon Aug 17, 2020 12:21 am
Nevertheless I would guess that a better random generator yold in a better distribution over the slots.
Not better, just different.
Eugene Kotlov
Hedgehog 2.1 64-bit coming soon...

User avatar
hgm
Posts: 26108
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Data structure choice for TT

Post by hgm » Mon Aug 17, 2020 7:36 am

The performance is also not very sensitive to the distribution over buckets, if you use a good replacement algorithm inside the buckets. Say due to a poor distribution half the buckets get 60% of the hits, the others 40%, instead of the perfect 50-50. The buckets that get 60% of the hits now perform like they would in a table 5/6 = 0.83 times the size. But the other perform like they are in a table 1.25 times the size. On average you hardly lose anything.

The crux is that the buckets are large enough to hang on to the important entries anyway, even when they are more heavily used. It just means the relatively unimportant entries survive a bit shorter there.

Post Reply