Combinatorial Game Theory
who wins, and by how much
Concept

Zobrist hashing — where it appears

A key for a board position made by giving every square a random word and combining the words of its covered squares with exclusive-or. A move changes the key by one exclusive-or per square it changes, and two boards share a key exactly when the words of the squares they differ on cancel.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

What a short key gets wrong. A memoised who-wins search of 4 × 5 Domineering using a Zobrist key of 10 to 32 bits, run under 60 random keys at each length and checked against the exact answer: how many stored positions share a key, how many runs store a wrong verdict or name the wrong winner, and what checking the whole position would cost instead. At 16 bits 59 runs store a wrong verdict and 19 name the wrong winner.

A key shorter than the position

A who-wins table for 4 × 5 Domineering addressed by a 16-bit Zobrist key stores a wrong verdict in 59 runs of 60 and names the wrong winner of the empty board in 19. The pairs of positions sharing a key follow the birthday count exactly while addresses are scarce, and fall away to nothing once the key has more bits than the board has squares, because a Zobrist key is linear. Symmetry and value identify positions that really are the same; a short key identifies positions that differ, at a rate set by arithmetic.

complexity · Identification One family of confused positions. Two 4 × 5 Domineering positions with Left to move that share every bit of an 18-bit Zobrist key, differing only on 4 marked squares whose words cancel. Under that key 100 of 136 confused pairs differ on exactly those squares; its other families hold 25 and 11.

A check bit halves the average and not the key

Real transposition tables keep a few of a key's bits beside each verdict and trust an entry only when they match. On 4 × 5 Domineering each such check bit halves the average number of wrong verdicts, exactly as the birthday count says. It does not halve any one key's. A Zobrist key confuses positions in families — every pair that differs on one set of squares whose words cancel — and a bit removes a family whole or not at all, so from eighteen bits to nineteen thirty of fifty-eight keys lose every confusion and fourteen keep every one.

complexity · Identification Two squares a key never needs. A 4 × 5 Domineering board shaded like a chessboard, with two squares of the same shade in rows 1 and 2 marked. Because a domino covers one square of each shade, a vertical domino covers one square in an odd row and one in an even row, and turns alternate, the other eighteen squares determine both marked squares: a key that leaves them out confuses none of the 48,670 reachable positions.

A key is a code, and two squares come free

The families of positions a Zobrist key confuses are the words of a binary linear code — the sets of squares whose words cancel — so choosing a key is choosing a code. On 4 × 5 Domineering the textbook choice, a code with the largest minimum distance, confuses more stored positions than a random key at fourteen, sixteen and nineteen bits. The choice that reads the board confuses none at eighteen: two squares of one shade, in rows of different parity, are decided by the other eighteen, and no seventeen-bit key is exact.

complexity · Identification

Named alongside it

The objects these essays reach for when they reach for this one.

DomineeringExhaustive searchIdentificationTransposition tableMemoisationSearch costInvariantLinear codeParitySymmetry

All concepts