A key is a code, and two squares come free

A check bit halves the average and not the key found that a Zobrist key does not confuse positions one pair at a time. Two boards share every kept bit exactly when the words of the squares they differ on cancel, and that condition mentions only which squares differ, so every stored pair differing on those squares is confused together. The confusions come in families, a bit of key removes a family whole or not at all, and the worst key at eighteen bits kept a family of a hundred pairs differing on four squares.

It ended with a question about construction. All sixty keys there were random. The largest family of the worst one differed on only four squares, which suggested that a key whose words were chosen so that no small set of squares cancels would lose its dangerous families first. Whether such keys exist, and whether they beat an extra check bit, is a question with a precise shape. That shape turns out to be one of the oldest objects in applied mathematics, and the obvious answer to it is wrong.

The families are the words of a code #

Cut to L bits, a Zobrist key is a linear map. Each of the twenty squares carries a word of L bits, a board’s key is the exclusive-or of the words of its covered squares, and exclusive-or is addition over the field of two elements. The sets of squares whose words add to nothing therefore form a subspace: add two such sets as indicator vectors, which is to take their symmetric difference, and the words still cancel. A subspace of twenty-bit vectors is a binary linear code, and the matrix whose columns are the square words is, in the language of coding theory, its parity-check matrix.

The earlier measurement already contained the proof, unnoticed. Its worst key at eighteen bits confused 136 pairs in three families, on four, eight and twelve squares. The four-square set and the eight-square set share no square, and together they are exactly the twelve-square set. That is not a coincidence of one key. A code of dimension two has three nonzero words, and each is the sum of the other two; the three families of that key are the three words of its code.

The first panel draws them. The lower panel counts codewords over all sixty keys. Twenty square words in L bits have at least twenty minus L independent dependencies, so a key at sixteen bits has a code of at least dimension four and at least fifteen nonzero words; the sixty keys average 16.1, since a few have one dependency more. At eighteen bits the average is 3.8 words, at twenty 0.68.

Then comes the fact that decides everything below. About half of every key’s codewords are free. A domino covers two squares, so every position has an even number of covered squares, and two positions can only differ on an even number of them. An odd codeword is a set of squares no two positions differ on, and cancelling there costs nothing. The families are the even words, and only the even words. Over the five lengths drawn, the sixty keys hold 909 even codewords between them, and 908 are sets on which some two of the 48,670 positions reachable in play differ. A random key spends half its code on sets that cannot hurt it and the other half on sets that almost always do.

A code has a distance, and the textbook maximises it #

Coding theory has a standard answer to the question the earlier essay posed. A code’s minimum distance is the fewest ones in any nonzero word, and every error-correcting code in use is chosen to make it large, because a large distance means that no small set of flipped bits turns one codeword into another. Read back into the table, a key whose code has minimum distance d confuses no two positions differing on fewer than d squares. The hundred-pair family on four squares would be impossible under any code of distance five.

The subject has met this object before. The losing positions are a code found that the lost rows of a coin-turning game on eight coins are the extended Hamming code, distance four, produced by a rule that knows nothing about codes, and the dual was the value table found the parity checks sitting in the Grundy values. There that code was a property of the game. Here it is a choice somebody makes when writing a solver, and the textbook tells that person which to make.

It is the wrong advice, and the reason is a count the textbook never asks for.

Wide sets are not safe sets #

Maximising distance assumes that a wide codeword is a cheap one: that differences on many squares are rare, the way errors on a channel are, where a few bits flip often and many bits flip seldom. For Domineering positions that holds only half way across the board.

Over all 48,670 reachable positions the mean number of pairs a set holds falls from 3,243 at two squares to 1,051 at twelve, and then rises again, to 1,978 at eighteen and 4,499 at all twenty. Among the 5,988 positions a who-wins search stores the same shape is shallower: about 165 pairs at two squares, 8.0 at sixteen, 21 at the whole board.

The rise at the far end has a plain cause. Two positions differing on every square are a covered set and its complement, and the complement of a set covered by dominoes can itself be covered by dominoes, with the counts of the two orientations close enough for both to be positions with the same player to move: 4,499 such pairs are. A code whose only even word is the whole board — the widest word there is — pays for every one of them.

The bottom row of the figure carries the other half of the story. Among sets of two to eight squares there are a few hundred that no two reachable positions differ on at all: 48 of two squares, 208 of four, 208 of six, 48 of eight. From ten squares up there are none. So the sets a key can cancel on for free are not the wide ones. They are all narrow, and they have a structure the next section draws.

The two squares a key never needs #

Every one of the 48 free two-square sets is a pair of squares of the same shade, in rows of different parity, and every such pair is free. The rule is checked in both directions, and its reason takes four facts about the game, each drawn beside the board.

A domino covers one shaded square and one plain one, so any position has as many covered squares of one shade as of the other. If the two marked squares are both shaded, the other eighteen squares therefore say exactly how many of the two are covered: nought, one or both. The only case left open is one.

A vertical domino covers one square in an odd row and one in an even row; a horizontal domino covers two squares in a single row. So the number of covered squares in odd rows has the same parity as the number of vertical dominoes. Turns alternate, and Left places the vertical ones, so with Left to move the vertical dominoes equal the horizontal ones or fall one short, according to who began. With the player to move known, the total covered count therefore fixes how many dominoes are vertical, and so the parity of the covered squares in odd rows. One marked square sits in an odd row and the other in an even row, so that parity says which of the two is covered.

That is the whole argument, and it means the board holds eighteen squares of information, not twenty. A key that simply leaves out those two squares — gives them no word, or equivalently the same word as nothing — separates every pair of positions with the same player to move. Checked directly, over all 48,670 reachable positions, no two collide.

In the language of the first section, leaving out square a and square b is choosing a code, the one spanned by the one-square set {a} and the one-square set {b}. Its three nonzero words are {a}, which is odd and free, {b}, likewise, and {a, b}, which is one of the 48. A code of dimension two with no costly word needs a key of 20 − 2 = 18 bits.

Squares less two, on every board #

Can a cleverer code do better, with seventeen bits and a code of dimension three? It is a finite question and it has a finite answer. The even words of any code form a subspace containing at least half its words, so a code of dimension three has an even part of dimension at least two: three nonzero even words, each the sum of the other two, and all three would have to be sets no pair differs on. A search over every subspace of the 512 free even sets finds none of dimension two. The largest has dimension one, which is the single two-square set above.

So no seventeen-bit key is exact on 4 × 5, and eighteen is the shortest. The same search on six more boards returns the same answer every time: six bits on 2 × 4, ten on 2 × 6 and 3 × 4, thirteen on 3 × 5, fourteen on 4 × 4, sixteen on 3 × 6. On each board the pair-free two-square sets number exactly as the shade-and-row rule predicts — 8, 18, 16, 24, 32, 36 and 48 — and leaving out one of those pairs is checked to be exact.

A random key reaches none of these lengths. Below the number of squares its words are always dependent, so its code has even words, and 908 of 909 even words were sets some pair differs on. The earlier measurement found that at twenty bits, a full square’s worth of key, thirteen of sixty random keys still confused some pair, because their twenty words happened to be dependent. A random key needs luck to be exact at twenty bits. A chosen one needs no luck at eighteen.

The textbook code, the parity-aware code, and the board #

With the pair counts in hand, three ways of choosing a code can be set against the sixty random keys at every length from twelve bits to nineteen. The first is the textbook: the largest minimum distance. The second knows one fact about the game, that only even sets matter, and maximises the fewest squares in any even word. The third reads the board: it minimises the pairs over every reachable position directly. The search for each is a seeded local search, and a distance does not pick one code among those attaining it, so the distance designs are reported as the mean over every restart that reached the best distance found.

The textbook code loses to a random key at fourteen bits, at sixteen and at nineteen. At fourteen it confuses 904 stored pairs against the random keys’ 535. At sixteen, 177 against 127. At nineteen it is worst of all, and instructively so: a code of dimension one has a single word, the largest distance a word can have is twenty, and the textbook choice is therefore the whole board, the one even set that holds 21 stored pairs. A random nineteen-bit key averages 11.75. At seventeen and eighteen bits the textbook does beat random keys — 39 against 63, and 9.4 against 29 — so its failure is not a failure of distance to mean anything. It is a failure to mean the right thing at every length.

The parity-aware code repairs the nineteen-bit case, where it chooses a single odd word and confuses nothing, and does better than the textbook at fourteen and sixteen. At eighteen bits it chooses the whole board again, as its one even word, and confuses 21.

The board-read code confuses 30 stored pairs at sixteen bits, where random keys average 127, and 12 at seventeen. Sixteen bits of the right code confuse about as many stored positions as eighteen random bits. From eighteen bits on it confuses none, over every reachable position, as the previous section proves it can. Below sixteen bits the advantage thins to nothing: at fourteen the best code found confuses 544 stored pairs against the random keys’ 535. It was chosen for every reachable position rather than the stored ones, and at that length every code holds dozens of even words and no choice among them helps much. It is also the best a search found, not a proved minimum, and the figure says so.

What each code spends its words on #

The sixteen-bit case shows the mechanism most clearly, because each code there has fifteen words and all of them can be drawn.

The random key’s words cluster around ten squares, as the words of any random subspace do, and eight of its fifteen are odd. It confuses 90 stored pairs, below the random keys’ mean of 127.

The largest-distance code has no odd word. All fifteen are even, eleven of them on ten squares and the rest on twelve and fourteen, and every one is a set on which some reachable positions differ. That is not an accident of the one drawn: every one of the 24 codes the search found at distance ten had fifteen even words and no odd one. Packing fifteen words of at least ten squares into twenty squares leaves almost no room, and the arrangements that fit are made of even words. The design spends every word where the board charges, and the one drawn confuses 161 stored pairs.

The parity-aware code is forced to hold at least seven even words — any code of dimension four has an even part of dimension three — and puts them at ten to fourteen squares, confusing 71. The board-read code holds the same number of even words and chooses them differently. One of them is a free two-square set, drawn in green at the left. The others sit at ten, twelve and sixteen squares, where the stored pairs a set holds are fewest, and together they confuse 30.

So the lesson of distance is inverted in one direction and refined in another. Distance is the right thing to maximise when every word costs the same and narrow ones cost most. Here half the words cost nothing, the narrowest free words cost nothing either, and the wide words come back into price at the edge of the board. A good key is a code fitted to that price list rather than to a distance.

An exact key in the table #

A key is only as good as the table it addresses, and the earlier measurement divided the key into an address and a check. An exact key cannot store a wrong verdict at any split, since a wrong verdict needs two positions sharing every kept bit. What the split still decides is how much the table searches again.

At eighteen bits the exact key stores no wrong verdict at any split and names the right winner of the empty board every time. Random keys at the same length store 12.3 wrong verdicts on average with the whole key as address, and the worst stores 134; at ten bits of address and eight of check the average is 1.5 and the worst 15.

The searching is where the layout of the words matters. The exact key can be written literally as the eighteen remaining squares, one bit each, in order. Used as an address, that key is simply whether each of the first ten or fourteen squares is covered, and those bits are far from uniform: early in a search the top rows are nearly empty and late in it nearly full, so positions crowd into few slots, and a crowded slot turns lookups into searches. At fourteen bits of address it searches 16,832 positions again and at ten bits 25,038. The same code with its eighteen bits mixed by an invertible matrix — same cancellations, same exactness — spreads over the slots as a random key does, and searches 222 again at fourteen bits of address and 10,110 at ten. A random key at ten plus eight searches 9,718 again. The exact key costs the same search as a random one and never lies.

At sixteen bits no key is exact, and the table ranks the three codes as their pair counts do. With the whole key as address the board-read code stores 12 wrong verdicts, the random keys 48.1 on average, and the largest-distance code 63. At ten plus six the board-read code stores one wrong verdict, the random keys 5.8, the textbook code 18. Both designed codes are one key each, and a count of wrong verdicts is not the whole of their damage. The board-read code names the wrong winner of the empty board at both of those splits — at ten plus six on the strength of a single wrong verdict — and the largest-distance code does so with the whole key as address. The order a solver tries the moves in explains how one error can be enough: a wrong verdict travels upward only along the lines the answer turns on, and one that lands on such a line decides the root.

Three pieces of information a position does not have #

What counts as the same position identified positions by symmetry and found a saving of at most four; what it costs to notice a repetition found the price of that identification unbounded. A key shorter than the position identified positions that differ, at a rate set by chance. This essay’s identification is of a different kind from all three. Leaving out two squares identifies nothing, because the two squares were never information: the position, with its player to move, already determined them.

That is the surprising part, and it is a fact about dominoes, not about keys. A Domineering board of twenty squares, read the way a key reads it, has twenty bits of layout, and a reachable position with a known player to move carries at most eighteen of them. The two bits that are missing are two conservation laws — the shades balance, and the row parity follows the number of vertical dominoes — and a code designer who knew nothing of the game spent key bits storing what the game already knew. A strategy is not a certificate is the reminder that knowing who wins is expensive. Knowing what a position already implies is cheap, and here it is worth two bits of every entry — the currency space is the resource counts a table in.

The broader connection runs the other way through the subject as well. The losing positions are a code found a code in the answer to a game. Here a code sits in the question: which positions a solver is allowed to mistake for each other.

What the seven boards cannot show #

The boards are small. Every exact length here is found by exhaustive search over the sets no two reachable positions differ on, and that set is computed from every pair of positions with the same player to move — 592 million pairs on 4 × 5. The pattern of squares less two holds on all seven boards measured and is explained by two invariants that hold on any board, but nothing here proves there is no third invariant on a larger board that would make a code of dimension three safe.

The positions are Domineering positions. The free odd words come from a domino covering two squares and the free two-square sets from shade and row parity; a game whose pieces cover one square, or three, would have a different price list and a different best code. In chess, where a key’s words are square-and-piece pairs and a single move changes two to four of them, the analogous question is which sets of square-and-piece changes no two legal positions differ by, and it is not measured here.

The designs below eighteen bits are the best a search found. A seeded local search over codes, with 24 restarts at each length. They are upper bounds on what a designed code can do; the exact result at eighteen bits and the impossibility at seventeen are proved by exhaustion.

The table never replaces an entry, as in the essays before it, and the random keys are the same sixty.

The convention the count rests on #

Normal-play Domineering on a rectangular board: Left places vertical dominoes, Right horizontal ones, and the player who cannot place loses. A position is a set of covered squares together with the player to move, and positions with different players to move live in different tables, so only pairs with the same mover can be confused. Reachable means reachable from the empty board in alternating play with either player moving first. The row parity in the invariant is counted from the top; the rule is symmetric, and counting from the bottom exchanges odd and even without changing which pairs are free.

Still open: whether the price list travels #

The board-read code was chosen from the pair counts of all reachable positions on one board, which a program for a larger board could not afford to compute. The two invariants behind the exact key can be written down for any rectangle in advance, but the rest of a good code below the exact length was fitted to a count. Whether the shape of that count — cheapest near half the board, dearer at both ends, free on odd sets and on the shade-and-row pairs — is regular enough that a code built from the shape alone, on a board too large to enumerate, beats random keys by the factor of four this board shows at sixteen bits, is the measurement this leaves.