OpenCL perft() Technical Issues

[syzygy]

How many bits should a hash signature have?

With a 64 bit signature, the program will encounter a false positive about once every 2^32 comparisons, or about once every seven minutes. That's bad.

This is only the case if you compare each new hash with every previously generated hash.

I'm not even sure about that. I see little if any logic in Steven's deduction.

He seems to argue that the probability that two randomly selected strings of N bits long are identical is 1 in 2^(N/2). The reasoning behind this seems to be that you can expect N/2 bits to be identical anyway, so the probability that the other N/2 bits coincide "must be" 2^(N/2). This is very wrong.

The probability that two randomly selected strings of N bits long are identical is 1 in 2^N. Not too much to explain about that, but maybe an example will help. Suppose the first string happens to be 0000...0 (N bits). What is the probability that the second strings will also be 0000...0? That's easy: 2^N. Now ask yourself whether the answer is different if the first string is another bit pattern. (Hopefully you'll answer "no".)

Just for fun: the probability that k bits coincide is Binomial(k,N) / 2^N.
The expected number of coinciding bits is indeed N/2: the ith bit coincides half the time, so E(# of coinciding bits) = E(\sum_i (ith bit coincides ? 1 : 0)) = \sum_i E(ith bit coincides ? 1 : 0) = \sum_i (1/2) = N / 2.

But once the table is saturated, that is not what happens because you lose old hashes, and with that the opportunity to find collisions. From that moment onwards the ratio of false hits scales only with the number of non-addressing bits minus the binary logarithm of the bucket size. This is easy to see intuitively if you start to imagine a table size of 1.

Indeed, the mathematics is very simple if you just assume that all table entries are in use (which is the normal case).

With a bucket size of 1, you can expect 1 false hit every 2^N probes that are supposed not to hit, where N is the number of bits in the hash key that were not used to identify the bucket.

With a bucket size of K, you can expect K false hits every 2^N probes.

[sje]

This is only the case if you compare each new hash with every previously generated hash. But once the table is saturated, that is not what happens because you lose old hashes, and with that the opportunity to find collisions. From that moment onwards the ratio of false hits scales only with the number of non-addressing bits minus the binary logarithm of the bucket size. This is easy to see intuitively if you start to imagine a table size of 1.

I agree that the table size has an effect; more entries makes false positives more likely. And my argument make the a priori assumption the the some N/2 bits will match which in practice may be the most common case but is not the universal case.

I will say that relying upon a short signature is hazardous, and by short I mean 64 bits or less. I've seen false positives on perft() runs lasting only a few days using 56 bit keys plus ply checking for an effective signature length of about 60 bits total. As the computers get faster and the tables get larger, the false positive rate can only increase. A chess program which stores a move with a transposition table entry can guard against a false match by testing the move for legality. A perft() program has no such capability, so it needs the extra signature bits.

A while back, I decided to bite the bullet and use 128 bit signatures. The overhead with generation and updates is very, very small and so not a real concern. The extra space needed for the table is an annoyance, and there is also the issue of using more memory bandwidth for the usually non-cached transposition table elements. Testing two 64 bit objects for a match is in practice no more costly than testing a single value, because it's rare that the first value will match and so the second value isn't compared and is not even fetched from memory.

With 128 bit signatures, Symbolic no longer has a need for checking the sanity of any retrieved move and so the sanity code was removed. This actually speeds up the move extraction process and in part makes up for the time used handling the larger signatures.

I admit that a 96 bit for a signature may be sufficient for even a year long perft() run. But I'll let someone else be the person to test that.

[Rein Halbersma]

Aren't you forgetting the birthday paradox? It roughly states that there is a 50% chance of a collision between 2^(N/2) elements from a 2^N universe. With N=64 bits hash keys, that means a 50% collision chance for every 5 billion nodes.

[syzygy]

Aren't you forgetting the birthday paradox? It roughly states that there is a 50% chance of a collision between 2^(N/2) elements from a 2^N universe. With N=64 bits hash keys, that means a 50% collision chance for every 5 billion nodes.

You can forget about the birthday paradox, because the hashtable forgets about the entries that were replaced.

[Rein Halbersma]

Aren't you forgetting the birthday paradox? It roughly states that there is a 50% chance of a collision between 2^(N/2) elements from a 2^N universe. With N=64 bits hash keys, that means a 50% collision chance for every 5 billion nodes.

You can forget about the birthday paradox, because the hashtable forgets about the entries that were replaced.

So how is filling a hash table with 5 billion different 64-bit keys different from filling a room with 23 people with birthdays from a 365 day universe? For each case, there is a 50% chance of a collision.

[syzygy]

A chess program which stores a move with a transposition table entry can guard against a false match by testing the move for legality. A perft() program has no such capability, so it needs the extra signature bits.

More importantly, a chess engine can afford some false hits that go undetected. A perft() program cannot, unless you don't care about the correctness of the calculation. 64 bit keys certainly is insufficient. With 128-bit keys it might be that the probability of a hashing error becomes smaller than the probability of a hardware error. (But one should make sure to use a new set of 128-bit Zobrist keys in a verification run if using the same program.)

[sje]

Nothing beats a lot of good old empirical testing.

Somewhere I have some Lisp code which calculates perft() while at the same time checks for minimum signature bit lengths needed to avoid false matches. I don't recall where I put this and I don't recall the exact results, either. But I do remember that at least 43 bits were needed even with relatively shallow depths.

I don't need Lisp when I have Oscar. All that is needed is to modify its hash equality testing routine:

Code: Select all

static bool HashTestEqual(const Hash * const hashptr, const Hash * const hashptr1)
{
  // This routine tests two hashes for equality.

  return (hashptr->qwrd0 == hashptr1->qwrd0) && (hashptr->qwrd1 == hashptr1->qwrd1);
}

For each call, the routine can perform a second calculation with testing for equality after masking out M successive higher order bits. The bottom Q bits (Q = log2 table entry count, here Q=24) are needed for addressing so won't be subject to masking.

The modified program could be set to to run perft(31) which would not end until long after the Sun burns out. Each time an equality test failed with M upper bits masked, the values of M and the probe counter call count would get printed and the value of M (which started at 128 - 24 = 104) would be decremented.

[bob]

How many bits should a hash signature have?

With a signature N bits long, a comparison of two randomly selected signatures will match, on average, N/2 bits. For every two bits added to the signature length, the probability of matching an extra bit is reduced by 50%.

Let's assume that a given chess program hits the transposition table at a rate of 10 MHz. With a 32 bit signature, the program will encounter a false positive about once every 2^16 comparisons, or about 153 false matches every second. That's very bad.

With a 64 bit signature, the program will encounter a false positive about once every 2^32 comparisons, or about once every seven minutes. That's bad.

With a 128 bit signature, the program will encounter a false positive about once every 2^64 comparisons, or about once every fifty-eight thousand years. That I can live with.

You are missing a key question. "How many collisions can I stand?" For chess, the answer is not "0" as the paper Cozzie and I wrote pointed out. For your perft data, a collision is a problem. So for you, the question morphs to "can I do this with zero collisions" and the kind of testing you are doing will not answer that. Just because you don't encounter a position when testing doesn't mean you won't encounter a position when testing deeper. I'm not sure this is answerable until you somehow use a signature that is at least as long as the number of bits needed to actually encode a position, which has been found to be something like 168 bits minimum. Then there is no hashing, just encoding, and zero collisions.

[mvk]

If you have memory for 5B positions. Otherwise it is as if the 23 people don't fit in the room. The bday paradox is often misapplied in the context of computer chess hash tables.

[syzygy]

Aren't you forgetting the birthday paradox? It roughly states that there is a 50% chance of a collision between 2^(N/2) elements from a 2^N universe. With N=64 bits hash keys, that means a 50% collision chance for every 5 billion nodes.

You can forget about the birthday paradox, because the hashtable forgets about the entries that were replaced.

So how is filling a hash table with 5 billion different 64-bit keys different from filling a room with 23 people with birthdays from a 365 day universe? For each case, there is a 50% chance of a collision.

I choose my hash table to have 256 entries. Now the probability of a false hit is 1 in 2^56. The probability of no collision is (1-2^(-56)) ^ (5*10^9) >= 1- 5*10^9 * 2^(-56) is quite close to 1.