Measuring Hash Collisions (once again)

[Rebel]

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.

[bob]

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]

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.

[hgm]

And just for the record, I already pointed that out in 2007:

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.

[Rebel]

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 , 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:

[d]8/8/k7/1pK5/p1p5/B1P5/1P6/4n3 b - - bm Nc2; acd 29; ce 9.92; acs 1.8s;
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.

[hgm]

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.

[Rebel]

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?

[hgm]

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.