Measuring Hash Collisions (once again)

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Rebel
Posts: 5254
Joined: Thu Aug 18, 2011 10:04 am

Re: Measuring Hash Collisions (once again)

Post by Rebel » Tue Mar 03, 2020 6:07 pm

syzygy wrote:
Tue Mar 03, 2020 7:55 am
Rebel wrote:
Tue Mar 03, 2020 7:21 am
Now I have heard an experienced programmer say, Stockfish doing 75 million NPS will generate hundreds of collisions each second. Not my experience, ProDeo produces zero.
Stockfish stores just 16 bits in a TT entry. With 3 entries per bucket, this means 1 false hit per 2^16/3=21845.33 probes that should not have hit.
Tried a 16 bit key, on average 10,000 - 20,000 - 30,000 collisions per second depending on a filled hash table. Still plays okay, amazing.
90% of coding is debugging, the other 10% is writing bugs.

bob
Posts: 20912
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Measuring Hash Collisions (once again)

Post by bob » Tue Mar 03, 2020 7:44 pm

Told you to read the paper I wrote with Cozzie. :) Surprised the heck out of us as well. And you can stand even more without the program blowing up.

syzygy
Posts: 4577
Joined: Tue Feb 28, 2012 10:56 pm

Re: Measuring Hash Collisions (once again)

Post by syzygy » Tue Mar 03, 2020 10:20 pm

hgm wrote:
Tue Mar 03, 2020 1:36 pm
Rebel wrote:
Tue Mar 03, 2020 1:13 pm
How can that function, any idea?
Well, as Bob pointed out, collisions have virtually zero impact on Elo (even when they are what you call 'transpositions', so that their score is used). Unless they are more frequent than one every 10K nodes. Which with a 16-bit signature and 3-way bucket they aren't.

It can be added that even if thec ollisions would cause a measurable Elo-decrease, this is not without compensation. By storing a 16-bit signature instead of a 48-bit key you can nearly double the number of hash entries for the same TT size, and that in itself should be worth about 8 Elo. So if the collisions by themselves cause an Elo drop smaller than 8, this actually is the superior design. As the FishTest apparently demonstrated.
Indeed. The cost of the false hits is outweighed by the gain of having more TT entries. At least at the time controls (and hash sizes) at which SF is tested.

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

Re: Measuring Hash Collisions (once again)

Post by hgm » Wed Mar 04, 2020 6:39 am

And just for the record, I already pointed that out in 2007:
hgm wrote:And finally: If the number of key collisions is so small that you never have to worry about them, it simply means that you use too long a key. Your engine would do better with the same resources if you shrunk your hash entry by carving away a few key bits, as the ncreased number of entries would benefit you more than the increased collissions would hurt you.

User avatar
Rebel
Posts: 5254
Joined: Thu Aug 18, 2011 10:04 am

Re: Measuring Hash Collisions (once again)

Post by Rebel » Wed Mar 04, 2020 8:46 am

bob wrote:
Tue Mar 03, 2020 7:44 pm
Told you to read the paper I wrote with Cozzie. :) Surprised the heck out of us as well. And you can stand even more without the program blowing up.
1. I remember we (shortly) talked about 32-bit hash keys, not 16-bit.

2. I ran 2 matches, the 16-bit version scored 48.2%, still a miracle to me :D, the 1.8% loss can be explained mainly by loss in move ordering due to all the fake best- or illegal moves from the HT. The 32-version did much better 49.6%, move ordering was slightly worse.

3. Nevertheless I think a 16-bit key is quite tricky, while statistically it might score better but IMO it's inevitable that occasionally Murphy's law will get the upperhand and Stockfish will blunder. A close example would be this position from a match:


The 9.92 score is crazy.

4. I finished the key=64 bits + 8 bit zobrist collision check tests. Played 10 games at 7-8 minute average per move and one game with 30 minutes per move and it never produced a collision.
90% of coding is debugging, the other 10% is writing bugs.

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

Re: Measuring Hash Collisions (once again)

Post by hgm » Wed Mar 04, 2020 9:00 am

Well, I suppose the 16 bits you test have no overlap with the 22 bits you use to determine the TT index. So effectively you are still using a 38-bit key.

And yes, looking only at Elo sweeps many things under the rug. A hilarious blunder every 100 games only costs you 0.5% in score expectancy, something you could only determine with confidence in 25K games. But they will stick out like a sore thumb, and cause your engine to be ridiculed in public in many places.

User avatar
Rebel
Posts: 5254
Joined: Thu Aug 18, 2011 10:04 am

Re: Measuring Hash Collisions (once again)

Post by Rebel » Thu Mar 05, 2020 10:39 am

hgm wrote:
Wed Mar 04, 2020 9:00 am
Well, I suppose the 16 bits you test have no overlap with the 22 bits you use to determine the TT index. So effectively you are still using a 38-bit key.
Apples and oranges. You can't just say Stockfish with a HT of 4Gb is using a 44-bit key.

How is your Zobrist key independence thing going, any progress made?
90% of coding is debugging, the other 10% is writing bugs.

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

Re: Measuring Hash Collisions (once again)

Post by hgm » Thu Mar 05, 2020 3:47 pm

Actually one can say something like that. It uses a 44-bit key, of which it takes 28 bits as index, and 16 other bits as signature. In one of your previous experiment you were storing the full 48-bit key, but the index part was (by definition) redundant, and the signature was thus the remaining 26 bits. I assume the 16 bits you tried now have no overlap at all with the index, and thus is purely signature.

I haven't had time these past days to continue with the collision reduction, but I will surely get back to it.

Post Reply