THE FOLD / RESPAWN / SECOND WIND / THE ZOBRIST HASH
THE ZOBRIST HASH
undo by doing the same thing again
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
One random key per piece-and-square. A position’s hash is the exclusive-or of the keys present, so moving a piece costs two operations rather than a rescan of the board — and un-moving it costs the same two, because exclusive-or is its own inverse. There is no separate undo path to get wrong.
LIT verified live. The incremental update reproduces a full recomputation exactly. Undoing restores the original hash bit for bit, and 500 random move-then-unmove pairs all return to the starting value. At 32-bit keys, over a billion positions, the probability of some collision is essentially 1 — which is where the risk lives, not in the trick.
LIT verified live. The incremental update reproduces a full recomputation exactly. Undoing restores the original hash bit for bit, and 500 random move-then-unmove pairs all return to the starting value. At 32-bit keys, over a billion positions, the probability of some collision is essentially 1 — which is where the risk lives, not in the trick.
2 HOW IT WAS WEAVED · AI + HUMAN
Albert Zobrist published the scheme in 1970, for a Go program. It is now in essentially every chess engine, because the alternative — rehashing the board after each move in a search that makes and unmakes millions — puts the hash in the hot loop.
AVAN (AI) would separate the exactness from the safety, since they are usually stated together. The incremental identity is exact: no approximation, no drift, verified against full recomputation and round-tripped 500 times. The collision risk is a separate matter entirely, governed only by key width, and at 32 bits it is not a risk but a certainty. A structure can be perfectly correct and still be the wrong size.
AVAN (AI) would separate the exactness from the safety, since they are usually stated together. The incremental identity is exact: no approximation, no drift, verified against full recomputation and round-tripped 500 times. The collision risk is a separate matter entirely, governed only by key width, and at 32 bits it is not a risk but a certainty. A structure can be perfectly correct and still be the wrong size.
3 ONE DIMENSION
A move, an unmove, and the hash returning.
4 TWO DIMENSIONS · INTERACTIVE
Move pieces and walk back.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a path that retraces itself exactly.
AVAN’s addition (the inverse-companion): the forward reading is “undo is free because XOR is an involution.” The inverse is that a hash which forgets how it was reached cannot tell you that it is wrong. Two different positions colliding produce one value with no record of either, and the engine reads a stored evaluation for a board it has never seen. Read backwards, the property that makes undo free — that the hash depends only on the set of pieces, not the route — is exactly the property that makes a collision undetectable.
LIT the incremental update reproduces a full recomputation exactly, undoing restores the original hash bit for bit, and 500 random move-then-unmove pairs all return to the starting value; at 32-bit keys over a billion positions the probability of some collision is essentially 1, which is where the risk lives rather than in the trick
FIG Albert Zobrist published the scheme in 1970, for a Go program. It is now in essentially every chess engine, because the alternative - rehashing the board after each move in a search that makes and unmakes millions - puts the hash in the hot loop. AVAN separates the exactness from the safety, since they are usually stated together: the incremental identity is EXACT, verified against full recomputation and round-tripped 500 times, while the COLLISION risk is a separate matter governed only by key width. A structure can be perfectly correct and still be the wrong size.
FIG Albert Zobrist published the scheme in 1970, for a Go program. It is now in essentially every chess engine, because the alternative - rehashing the board after each move in a search that makes and unmakes millions - puts the hash in the hot loop. AVAN separates the exactness from the safety, since they are usually stated together: the incremental identity is EXACT, verified against full recomputation and round-tripped 500 times, while the COLLISION risk is a separate matter governed only by key width. A structure can be perfectly correct and still be the wrong size.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SECOND WIND · David Lee Wise (ROOT0), with AVAN