A key shorter than the position

Two identifications have already been priced. What counts as the same position folded a Domineering table by the board’s symmetries and found a saving that can never exceed four. What it costs to notice a repetition found the price of that folding, and ended beside a better identification nobody can use: positions with the same value, which would collapse a 3 × 4 table fourteen-fold if the values were not the thing the search was for.

Both of those identify positions that really are the same, by a relation that is true. There is a third identification, and it is the one every practical game program makes. It stores a position’s answer not under the position but under a key computed from it — a number short enough to index a table — and two positions with the same key are, as far as the table can tell, one position. That relation is false for some pairs. The questions are how many, what it costs when they collide, and what it costs not to let them.

What a short key gets wrong #

The search is the plain memoised one from the tree and the graph, asking only who wins, and on 4 × 5 it stores 5,988 positions — a board together with the player to move. The key is the standard one for boards, Zobrist hashing: every square is given a random 32-bit word, a position’s key is the exclusive-or of the words of its covered squares, and the key is cut to its top b bits to make an address. The table trusts its addresses: a lookup that finds an entry takes its verdict.

At 16 bits the damage is nearly universal. 59 of 60 random keys store at least one wrong verdict, and 19 of the 60 name the wrong winner of the empty board — they conclude that the first player loses a board the first player wins, or the reverse. At 18 bits 49 keys store a wrong verdict and 3 get the empty board wrong. At 20 bits, 9 and none. From 22 bits no run of the sixty stores a single wrong verdict.

The table is honest about the mechanism. A lookup that lands on another position’s entry is handed that position’s verdict, and in these runs a borrowed verdict was wrong a little under half the time — scarcely better than a coin. A wrong verdict, once handed over, becomes part of the answer of the position that asked, and is stored under that position’s own address in turn.

The birthday count, and a key that beats it #

How many stored positions share an address is a question with a textbook answer. With n positions and m addresses, if keys behave like independent random numbers, the expected number of pairs sharing an address is n(n − 1)/2 divided by m — the arithmetic of the birthday problem, in which 23 people are enough for an even chance that two share a birthday. Here, with 2,902 positions for Left to move and 3,086 for Right, that predicts 8,759 shared pairs at 10 bits, 547 at 14, 137 at 16 and about one half at 24.

The same arithmetic says how a key has to grow with its table. Each extra bit halves the expected number of shared pairs, and doubling the number of positions stored quadruples it, since pairs grow with the square of the count. A table that doubles in size must lengthen its key by two bits merely to stay as safe as it was — which is why the key lengths that are comfortable on a board this small are nowhere near enough on a board a program would actually be asked to solve.

Two keys are measured against it. A multiplicative key — the position’s mask multiplied by a random odd word, top bits kept — gives 8,769 pairs at 10 bits, 547 at 14 and 0.53 at 24: chance, almost to the digit, with a dip between 16 and 22 bits. The Zobrist key gives 8,685, 535 and 127 up to 16 bits, also chance. Then it leaves the curve. At 20 bits it gives 3.3 against the predicted 8.6; at 22, 0.10 against 2.1; at 24 and beyond, none at all in sixty keys.

The last column says why, and it is a small piece of linear algebra. A Zobrist key is an exclusive-or, and exclusive-or is addition of bit vectors. Two boards share a key exactly when the words of the squares covered in one board and not the other add up to zero in the bits that are kept. A 4 × 5 board has 20 squares and so 20 words; once a key keeps a few bits more than 20, those 20 words are likely to be linearly independent, and independent words cannot add up to zero — so no two boards on the whole board can share a key. 23 of the 60 keys at 20 bits have that property, 54 at 22, 59 at 24.

So on a board with fewer squares than key bits, a Zobrist key is not a hash in the birthday sense at all; it is a relabelling. That is a fact about small boards rather than a recommendation. A chess position has hundreds of square-and-piece words and a key of sixty-four bits, so the words are necessarily dependent and the birthday count is what governs; and on this board a 20-bit address could simply be the position itself. What the measurement shows is the regime a real table lives in — more words than key bits — and that there both keys follow chance closely.

Trusting the address, or paying to check it #

The alternative to trusting an address is to store the position with its verdict and compare on every lookup. A table that does so can never hand one position another’s verdict; at worst it finds its address taken and has to search the position again. In sixty runs at every length it never stored a wrong verdict.

The price of checking is paid in search, and it is small exactly where trusting was dangerous. At 16 bits a checking table searches 83 positions again, 1.4 per cent more work, where a trusting table stored a mean of 48 wrong verdicts. At 20 bits the extra is 1.4 positions. Only when addresses are very scarce does it grow: 384 positions at 14 bits, 1,837 at 12, and at 10 bits more than the whole search again.

The trusting table has a perverse advantage that the first column shows, and it is worth naming because it looks like a saving. Trusting a short key makes the search smaller. At 12 bits a trusting search expands 2,649 positions of 5,988, because every borrowed verdict ends a line that should have been searched. A table whose answers are wrong can finish sooner than the one whose answers are right, and a solver timed on its speed would prefer it.

The other price of checking is memory: a checking entry holds the position, or at least enough of its key to tell positions apart, as well as the verdict. That is the same trade space is the resource describes for the table as a whole, now inside a single entry, and it is the reason real programs compromise — storing some of the key’s remaining bits as a check, which makes a collision rarer rather than impossible.

The average and the one bad key #

Every number so far is an average over sixty random keys, and a program does not run with sixty keys. It runs with one.

The multiplicative key at 24 bits makes the point sharply. Its mean is 0.53 shared pairs, exactly what chance predicts, and it looks as harmless as the birthday count says it should be. But 31 of the 32 shared pairs across all sixty keys belong to a single key, and that key stored 30 wrong verdicts. The other 59 keys shared at most one pair between them. A multiplier that happens to map some families of boards close together produces collisions in clusters, and an average over keys spreads a cluster thinly into a small, reassuring number.

The Zobrist key is less extreme but not uniform either: at 20 bits the worst key holds 46 of the 199 shared pairs, nearly a quarter, and stored 23 wrong verdicts while fifty-one of the sixty stored none. An average collision rate is a statement about the family of keys. A program’s reliability is a statement about the key it was compiled with, and the two can be very different.

At 22 bits the Zobrist keys make the complementary point. Six of the sixty are not one-to-one on the board, and across all sixty only six pairs of stored positions share an address — every one of them produced by a single key. That key’s search borrowed a verdict twelve times and was never handed a wrong one, because each pair it confused happened to have the same answer. A shared address is a chance of harm rather than a harm, and it becomes one only when the two positions it confuses disagree.

Why most wrong verdicts never reach the answer #

At 20 bits nine keys stored at least one wrong verdict, and none of them named the wrong winner of the empty board. At 18 bits 49 keys stored wrong verdicts and only 3 got the empty board wrong. A wrong verdict somewhere in the table usually stays where it is.

The reason is the asymmetry the order a solver tries the moves in measured. A won position needs only one move to a lost position. If one of its children is handed a wrong verdict, the parent is unaffected whenever it has another winning move that the search finds instead. A lost position needs every child won, so a child wrongly called lost does make its parent a false win — but that false win matters to the grandparent only if it is the move the grandparent’s own verdict turns on. At every level an error has to be the deciding one to travel upward, and most are not.

That is why the damage is so uneven, and why a count of wrong verdicts in the table says little about the answer a program returns. At 16 bits the table holds 48 wrong verdicts on average and is still right about the empty board in two runs of three. Errors travel only along the lines that decide the result.

Three identifications, and the currency of each #

Set the key beside the two identifications priced before, and each turns out to be characterised by what it collapses, what it has to know, and how it can be wrong.

Symmetry — one representative board per orbit, the positional cousin of a canonical form — collapses by at most the size of the group and needs to know nothing about the position’s value. It is never wrong, because every symmetry of the board maps Left’s moves to Left’s and Right’s to Right’s; its price, measured in the essay on noticing a repetition, is canonicalisation at every lookup. Value collapses far more — 550 positions into 39 — and is never wrong, but it needs to know the answer before it can be applied. A short key collapses as much as its length decides, needs to know nothing, and is wrong at a rate the birthday count predicts on average and nothing predicts for a particular key.

It is the only one of the three whose error is a probability, and the only one that can be made cheaper by being made less correct. What two numbers cannot tell apart found the same shape in the theory rather than in a table: two numbers too short to describe a game identify games that differ, and the count of those collisions is large. A key is the engineering form of that sentence.

The fold the key does not replace #

A key and a fold do different jobs and a real table uses both. The fold decides how many distinct things the table has to hold — 1,522 rather than 5,700 on 4 × 4 — and the key decides where each is put. Folding first makes the key’s job easier by the same factor, since the birthday count grows with the square of the number of things stored: a little over a quarter of the positions means about a fourteenth of the expected shared pairs at the same length. That is a genuine interaction between the two identifications and it is one of the few places the fold’s small, bounded saving is squared.

It also changes what the key has to respect. A key for a folded table must be the same for every member of an orbit, or two boards the fold treats as one get different addresses and the fold is undone. Computing the key from the canonical board does that and pays the canonicalisation that essay priced before the key is even formed, which throws away what makes Zobrist keys attractive: one exclusive-or per move, updating the key as moves are made. The standard way to keep it is to maintain one key per symmetry, updating all four with every move, and address by the least of them — four exclusive-ors a move instead of one, the fold’s price paid again in a cheaper currency.

Names: Zobrist, birthdays and replacement #

Albert Zobrist described the key in a 1970 report on hashing for game-playing programs, and it has been the standard for board games since: a move changes a key by one exclusive-or for each square it changes, so a search can update the key as it makes and unmakes moves instead of recomputing it. The birthday problem is older and anonymous; it is the reason a table with a million addresses has an even chance of a shared address once it holds about twelve hundred entries.

A table that finds its address taken must also decide whether to keep the old entry or replace it, and a replacement policy is a large subject of its own. The tables measured here never replace, so the first position to claim an address keeps it; the table that changes its mind measured what eviction choices do for a table of component values, and the same questions return for a table of verdicts.

What sixty keys cannot show #

The board is small. On 4 × 5 the whole search stores under six thousand positions, so every key length that matters is short, and a real table’s collisions occur at lengths and densities these runs cannot reach. What transfers is the arithmetic, which is the same at every size.

The damage depends on the search. A wrong verdict handed to a position near the top of the search spoils more than one handed to a position near the end, and this search’s order decides which positions ask for which addresses — the order the order a solver tries the moves in prices. A different order would redistribute the same collisions over different victims.

A who-wins verdict is one bit. A table storing values, as knowing who wins and knowing what it is worth prefers, would be wrong in a richer way when it borrowed an entry — a borrowed value is almost never the right value, where a borrowed verdict is right a little more than half the time. The one-bit case understates the harm.

The convention, named #

Normal play Domineering: Left places vertical dominoes, Right horizontal ones, and a player who cannot place loses. A position is a board together with the player to move, and the key is computed from the board with the player to move kept alongside it, so the two players’ positions never share an address with each other. A run is one random choice of the twenty square words, or of the multiplier, followed by one complete search.

Still open: how many check bits are enough #

A checking table here stores the whole position, and on 4 × 5 that is only twenty bits. Real tables store part of the key’s remaining bits and accept a smaller error. The measurement that would settle how many is exactly this one extended: a long key cut into an address and a check of c bits, with the wrong verdicts counted as c grows, on a board large enough that the words outnumber the bits. The birthday count says each check bit should halve the error; the bad-key measurement says the average may be the wrong thing to halve.