Hash Verification Is Not Collision-Proof at Perft(15) Scale

The Lesson

GPUPerft CDP2 uses a compact transposition table entry designed for speed. The current main table stores a perft count and a compact verification value derived from the position hash:

verification = (hash.hi ^ hash.lo) ^ count;

On probe, the table checks:

(storedVerification ^ storedCount) == (hash.hi ^ hash.lo)

That is a useful hash-verification scheme. It rejects most wrong-slot collisions cheaply. But it is not an exact position comparison, and it is not collision-proof. The effective verifier is 64 bits:

hash.hi ^ hash.lo

At small scales, this can appear practically safe. At perft frontier scale, especially around perft(15), the math changes.

The Reference Scale

The Chess Programming Wiki lists the starting-position perft(15) result as:

2,015,099,950,053,364,471,960

Source: Chessprogramming Wiki, Perft Results

For a 64-bit verifier:

2^64 = 18,446,744,073,709,551,616
sqrt(2^64) = 2^32 = 4,294,967,296

The birthday-paradox threshold is not near 2^64. It is near sqrt(2^64). That means collisions among 64-bit values become likely around billions of samples, not around eighteen quintillion samples.

perft(15) is about:

469,177,018,398 times larger than sqrt(2^64)

So a 64-bit verification key cannot be treated as collision-proof at that scale.

Collision Math

Let:

N = 2,015,099,950,053,364,471,960
M = 2^64

The expected number of colliding pairs among N independent 64-bit verifier values is approximately:

N * (N - 1) / (2 * M)

For perft(15):

Expected colliding 64-bit verifier pairs
~= 110,063,537,296,327,309,111,874
~= 1.10e23

That does not mean every verifier collision becomes a wrong transposition-table hit. The table index, replacement behavior, actual probe count, occupancy, and timing all matter. But it does mean the blanket claim “64-bit verification is astronomically safe” is wrong at this scale.

False-Hit Risk Model

For a wrong occupied slot, the probability that a random 64-bit verifier falsely matches is:

1 / 2^64 ~= 5.421010862e-20

That sounds tiny, but a tiny probability repeated enough times becomes a practical engineering issue.

If we pessimistically model perft(15) as N wrong occupied probes:

Expected false hits = N / 2^64
                    ~= 109.238787181

The chance of at least one false hit is:

1 - exp(-109.238787181)
~= 0.999999999999999999999999999999999999999999999996

Even much smaller wrong-probe fractions can be material:

Wrong occupied probes	Expected false hits	Chance of at least one false hit
`100% of perft(15)`	`109.239`	effectively `100%`
`10% of perft(15)`	`10.924`	`99.998%`
`1% of perft(15)`	`1.092`	`66.46%`
`0.1% of perft(15)`	`0.109`	`10.35%`
`0.01% of perft(15)`	`0.0109`	`1.09%`

This table is not a measurement of the current executable. It is a scale analysis. The measured risk depends on how many wrong occupied TT probes actually occur in a run. The point is that 64-bit verification is not a proof of correctness at perft(15) scale.

Count Payload Risk

There is a second, separate issue: payload size.

The current compact TT count field is 64 bits. That is fast, but it is not sufficient for arbitrary-depth subtree counts. Starting-position perft(15) itself is already far larger than 2^64.

The final perft result may be accumulated in a wider integer elsewhere, but any TT payload that stores a subtree count in uint64_t must have a documented safe depth or a fallback strategy. Hash verification and count width are different problems, but both become correctness issues as depth increases.

Engineering Consequence

The current compact TT is a speed-oriented structure. That is valid for throughput experiments and bounded-depth validation, but it should not be described as collision-proof.

A correctness-grade path needs one of the following:

An exact canonical board key in the TT entry, such as a 32-byte NybbleBoard representation.
A much wider verifier, with quantified collision budget and independent validation.
A dual-run or independent-check strategy that can detect silent false hits.
A documented depth and workload limit under which the compact TT is considered acceptable.
A wide-count payload strategy for depths where uint64_t subtree counts are insufficient.

Practical Design Direction

The exact-key idea is attractive because NybbleBoard is already a compact canonical board representation:

struct ExactNybbleBoardTTEntry {
    uint8_t key[32];   // exact board identity
    uint128_t count;   // or another wide-count payload
};

That entry would be much larger than the current 16-byte TT entry, reducing TT capacity and increasing memory bandwidth. It may not be the fastest production mode. But it is the kind of structure that can support correctness-grade verification, especially for publishable frontier results.

A reasonable direction is to separate modes:

Mode	TT key strategy	Purpose
Fast mode	Compact hash verification	Maximum throughput under documented risk bounds
Verified mode	Exact board key or wider verifier	Correctness-grade result generation
Debug/certification mode	Exact NybbleBoard key comparison	Detect and quantify compact-TT false-hit risk

Conclusion

The important correction is simple:

Hash verification is not exact position verification.

At perft(15) scale, a 64-bit verifier cannot be treated as collision-proof. The compact TT remains valuable as a performance tool, but correctness-grade frontier computation needs either exact keys, wider verification, independent validation, or explicit limits. This is especially important for GPUPerft’s long-term goal: producing high-depth perft and UPC results that are not only fast, but trustworthy enough to publish.