A check bit halves the average and not the key

A key shorter than the position addressed a who-wins table for 4 × 5 Domineering by a Zobrist key cut to a number of bits, trusted whatever it found at the address, and counted the damage. At sixteen bits 59 of 60 random keys stored a wrong verdict. It then measured the other extreme, a table that keeps the whole position beside its verdict and so is never wrong. It ended where real programs sit, between the two: they keep part of the key’s remaining bits beside each verdict, as a check, and accept a smaller error in exchange for a smaller entry.

That essay also left a warning about how to measure the result. Its averages over sixty keys concealed one multiplicative key that held 31 of all 32 shared pairs. The question it posed was how many check bits are enough, and whether the average is even the right thing to halve.

A check beside each verdict #

The table here is the same memoised search asking only who wins, storing 5,988 positions — a board with a player to move — on 4 × 5. The key is the same one, Zobrist hashing: a random 32-bit word for each square, exclusive-ored over the covered squares. The sixty keys are the very sixty words the earlier measurement drew, key for key.

What changes is how the key is used. Its top a bits choose a slot, one table for each player to move. Its next c bits are written into the slot beside the verdict. A lookup that finds the slot occupied trusts the verdict only when the check matches; if the check differs, the slot belongs to some other position, and the search searches this one again without storing it, since the table never replaces an entry.

The address is held at ten bits, which is deliberately cramped: 1,024 slots for about three thousand positions a side, so the table fills and most of the measurement is about what happens at a full slot. With no check at all, the table stores 103 wrong verdicts on average and 45 of the 60 keys name the wrong winner of the empty board. With eight check bits it stores 1.47 on average, and one key in sixty is wrong about the winner.

In between, the fall is steady from two check bits: 78.8, 45.5, 24.3, 12.9, 5.8, 3.0, 1.5. The first check bit is the exception, and the exception is instructive. A check that sends a lookup back to search does not store the position it searches, so the search passes through more positions and puts more questions to a crowded table. With no check, a run meets another position in the slot it looks up 403 times on average and believes it every time. With one check bit it meets another position 1,437 times — 790 turned away by the check and 647 believed — because every position turned away is searched, left unstored, and looked up again later. The bit roughly halves how often a stranger in a slot is believed, the crowding more than triples how often a stranger is met, and on a ten-bit address the two nearly cancel.

The two right-hand columns of key counts carry a second finding, and it is the reason a table can survive a surprising number of wrong entries. At eight check bits 27 of the 60 keys still store at least one wrong verdict, and only one of them names the wrong winner of the empty board. At four check bits it is all sixty against twenty-seven. The order a solver tries the moves in measured the asymmetry behind that: a won position needs only one winning move, so a wrong verdict on one of its children changes nothing when another winning move is found, and a wrong verdict travels upward only along the lines that decide the answer. Most of a key’s confusions land on lines nobody’s answer turns on.

Each bit halves the average #

The steady part of the fall has a reason, and the reason is the arithmetic the earlier essay called the birthday count.

Two positions can only hand each other a verdict if they agree on every kept bit, address and check together. Each added bit halves the chance that a given pair agrees, so it halves the expected number of such pairs, and the first column of the table shows exactly that: the pairs sharing every bit are multiplied by between 0.46 and 0.51 per bit. The mean of the wrong verdicts follows, a little less tidily, at between 0.45 and 0.58. On average, each check bit halves the error, and that is the whole of what the birthday count promises.

The last column is where the promise stops applying. The worst of the sixty keys at each length falls more slowly than the mean on five of the six bits, and over the last two it keeps 95 per cent and then 83 per cent of its wrong verdicts: 19, 18, 15. At eight check bits the worst key stores ten times the average. A program is compiled with one key and cannot know in advance whether it is that one.

Confusions come in families #

Why a key’s errors resist halving is a question about which pairs a key confuses, and for a Zobrist key the answer is exact rather than statistical.

A Zobrist key is an exclusive-or, and two boards share it exactly when the words of the squares covered in one and not the other add up to nothing in the kept bits. That condition mentions only which squares differ. So if one pair of positions differing on some set of squares shares a key, every stored pair differing on exactly that set of squares shares it too. The confusions of a key are not scattered pairs; they are families, each family the set of all stored pairs that differ on one particular set of squares whose words happen to cancel.

The counts bear it out. At fourteen bits the mean key confuses 535 pairs in 26.9 families; at eighteen, 29 pairs in 1.6; at twenty, 3.3 pairs in 0.25. The families halve with each bit as the pairs do, and the pairs a family holds stay near twenty until the last row, where the few families left are mostly small ones.

This is also the sharpest form of what what two numbers cannot tell apart found in the theory: a summary too short to describe a game identifies games that differ, and the identifications are not random but follow the structure of the summary. A pair of numbers merges games with the same mean and temperature; an exclusive-or key merges boards whose differences cancel. In both cases what is merged is decided by the shape of the shortening, and a count of the collisions is a count of that shape’s consequences.

That is the mechanism of the halving, stated the other way round. One more bit of key is one more bit that the cancelling squares’ words have to sum to nought in. For a random key that happens with probability one half, independently for each family. So a bit keeps each family with probability a half, and it keeps or removes the whole family — there is no way for it to separate two pairs that differ on the same squares.

The average halves and a key does not #

While a key has a dozen families, a bit removes about half of them and the share of pairs it keeps clusters near the middle. From fourteen bits to fifteen, 58 of the sixty keys keep between a quarter and three quarters of their confused pairs.

By eighteen bits the mean key has fewer than two families, and the halving is a coin toss per key. From eighteen bits to nineteen, thirty of the fifty-eight keys with any confusion keep none of it and fourteen keep every pair. Only fourteen land anywhere in between. The mean share kept is 36 per cent, and almost no key keeps anything like it.

So the answer to whether the average is the thing to halve is that the average is the only thing a bit halves. A single key’s count of confused pairs does not decay; it drops away in whole families, and it may keep its largest family through several bits in a row. The worst key at each length is simply a key whose large family has survived. Adding check bits makes such keys rarer — by half, each time — and never makes one of them less bad.

One family, drawn #

The worst of the sixty keys at eighteen bits confuses 136 pairs of stored positions, in three families. The largest holds a hundred of them. Every one of those hundred pairs consists of two boards that agree on sixteen squares and differ on the same four — the corners of the top row, a square in the middle of the second row, and the bottom-left corner — and the four squares’ words cancel in the top eighteen bits.

The drawing shows two of the hundred, with Left to move in both. Filled squares are covered and the four marked squares are covered in one board and empty in the other. Nothing about the two positions is alike in the way a player would describe them; they are identified because four random numbers happened to sum to nothing in eighteen places, and they are identified together with ninety-nine other pairs for the same reason.

That also says what decides the size of a family, and it is not the key. It is how many pairs of stored positions differ on exactly those squares, which is a fact about the positions a search of Domineering stores. The key contributes only whether the squares’ words cancel. A key that cancels on a set of squares no two stored positions differ on costs nothing at all, and one that cancels on a set many pairs differ on costs a hundred confusions at a stroke.

The other two families of the same key are smaller and wider: twenty-five pairs differing on eight squares and eleven differing on twelve. On this key the family on the fewest squares is also the largest by far. Whether that holds for keys in general — whether small sets of differing squares are where large families come from — is not something one key can establish, and nothing here counts it over all sixty.

An address bit against a check bit #

Every figure so far holds the address at ten bits. A real table is sized by memory, and the choice is between spending bits on slots or on checks.

A pair of positions that shares all sixteen bits is confused whatever the split. So a first guess is that only the total should matter, and it is wrong by a factor of eight. At sixteen bits, sixteen of address and none of check stores 48.1 wrong verdicts on average; ten of address and six of check stores 5.8; eight and eight stores 0.15. The keys wrong about the winner of the empty board fall from nineteen to seven to one.

The price is paid in search. The table with a sixteen-bit address stores 5,506 positions and actually searches fewer than the plain search does, because its borrowed verdicts end lines early. The ten-bit address stores 1,911, and turns so many would-be borrowings into misses that it searches about 8,800 positions more than the plain search; the eight-bit address searches about 25,600 more, more than four times the plain search’s own 5,988.

The slots column makes a second price legible, and it runs the other way. Count a table’s memory as its slots times the bits each slot holds — one bit of verdict and the check, and nothing for recording which slots are taken, which every one of these tables would need equally. A sixteen-bit address with no check is 131,072 slots of one bit each, 131,072 bits. Ten bits of address with six of check is 2,048 slots of seven bits, 14,336 bits — about a ninth of the memory — and it stores an eighth as many wrong verdicts. On this board an address bit doubles the table and a check bit adds one bit to every slot, so for the same total key length the check is enormously cheaper in memory and dearer in search, and which of those a program can afford is the real content of the question how many check bits are enough.

The mechanism is in the rule a slot follows. A borrowing needs the slot’s occupant to be the colliding partner. In a table with few slots, the occupant is usually some other position with a different check, and the lookup becomes a search instead. So a crowded address with a check is not a cheaper way to buy the same safety; it is a way of converting confusions into searching, and the table measures the exchange rate.

At eighteen bits the story repeats with smaller numbers: 12.3 wrong on average with an eighteen-bit address, 10.4 with fourteen and four, 1.5 with ten and eight. And the worst keys follow the families rather than the split: 134, 109 and 15.

The memory of a search is the quantity where a search may stop found deciding the price of a certificate: a table keyed by depth as well as position cannot answer across depths, and pays again for each iteration. A check is the same trade in miniature, at the level of one slot — a few bits held beside a verdict so that a stranger in the slot is searched rather than believed.

Three identifications, and now a fourth currency #

What counts as the same position folded positions by symmetry and found a saving with a ceiling of four and no errors. What it costs to notice a repetition priced the folding and found the price had no ceiling. The short key collapsed as much as its length allowed and was wrong at a rate the birthday count predicted on average. The check adds a fourth line to that account.

A check spends entry space to turn wrong verdicts into searches. It does not change which positions a key confuses, only whether a confusion is trusted, and on the positions it declines to trust it pays in exactly the currency the table was built to save. That is the same trade space is the resource describes for a table as a whole, made one slot at a time.

And what it buys is governed by families, not by pairs. A family is removed by a bit or not; a key’s errors therefore fall in lumps; and the reassuring average is a statement about a population of keys that no program contains.

Names: Zobrist, and what tables do #

Albert Zobrist’s 1970 report introduced the key, and the property that makes it standard is the one that makes families: a move changes the key by one exclusive-or per square changed. The transposition table of a chess or go program stores a verdict or a value under such a key, and nearly all of them keep some of the key’s bits in the entry as a check — commonly enough that a collision is rare over a whole game rather than impossible. The families measured here are what that rare collision looks like when it does occur: never one pair of positions alone.

What sixty keys cannot show #

The board has twenty squares. On 4 × 5 every key length measured here is below the number of square words, so the words are dependent and families exist; at twenty bits and beyond, many keys have no family at all. A chess position has hundreds of square-and-piece words and a sixty-four-bit key, which is the same regime at a far larger scale — and there the families would be sets of square-and-piece changes, several of which a single move makes, rather than single covered squares.

The table never replaces an entry. Every miss here searches again and stores nothing. A table that replaced the older or the shallower entry would change which positions occupy the slots, and so which borrowings become misses; the families would not change, since they are a property of the key alone.

Only verdicts are stored. The earlier measurement found a little under half of borrowed verdicts wrong, since two different positions often have the same winner, which is why the wrong-verdict counts sit below the borrowing counts. A table of values would be wrong on almost every confusion, and the families would carry their whole size into the error.

Sixty keys are sixty keys. The shares in the lumps table are counts of keys, and the worst key at each length is the worst of sixty. What is exact is the structure: that every confusion belongs to a family and that a bit decides a family whole is a consequence of the exclusive-or, checked on every confused pair found.

The rules the counts assume #

Normal play Domineering on a 4 × 5 board: Left places vertical dominoes, Right horizontal ones, and the player who cannot place loses. A position is a board with a player to move, and the two players’ positions are kept in separate tables, so a Left position is never confused with a Right one. A search trusts a slot only when the slot’s stored check equals the check of the position asking; a verdict found under the position’s own board is always trusted. Every stored verdict is compared with the exact answer after each run.

Still open: a key that avoids the families #

Nothing here chooses the square words; all sixty keys are random. But a family is large only when many stored positions differ on its squares, and the largest family of the worst key at eighteen bits differs on only four. A key whose words are chosen so that no small set of squares cancels in its kept bits would lose its large families first and keep only the wide ones, which hold few pairs. Whether such keys can be constructed for a given length, and whether they cut the worst case on a board this size by more than one extra check bit would, is the measurement this leaves.