A board that is a sum of its regions

The values of every small board tabulated the rectangles and named what the table cannot do: everything above is a rectangle and a partly played board is not.

That is not a quibble about presentation. A Domineering game starts on a rectangle and stops being one immediately — after two moves the free squares are an irregular region, after ten they are usually several irregular regions, and the whole apparatus of a table of rectangles has nothing to say about the position on the board.

The pieces are the object #

A domino covers two squares that touch. So it can never straddle two pieces of the board that do not touch, and a board whose free squares fall into disconnected pieces is the disjunctive sum of those pieces — arrived at by the geometry rather than assumed.

That is the point at which the sum is the object stops being a slogan about theory and becomes a way of reading a position. The board in front of a player is a sum; the parts are visible; and the whole apparatus of values exists to add them up.

What is missing is a table of the parts. This is that table.

What a shape is, up to what #

A shape is a set of free squares, taken up to translation and to two reflections: left-to-right and top-to-bottom.

Not the quarter turn. Left plays vertically and Right horizontally, so rotating a shape by ninety degrees exchanges the players — a $1 \times 3$ strip is worth $-1$ and a $3 \times 1$ strip is worth $1$, and treating them as the same shape would lose the sign of every entry.

The catalogue holds every connected shape up to six squares: 104 of them, one of size one, two of size two, three of size three, nine of size four, twenty-one of size five and sixty-eight of size six.

Between them they carry 33 distinct values, and 44 of the 104 shapes are numbers.

Thirty-three values for 104 shapes is a collapse worth noticing on its own. Three shapes in every ten carry a value no other shape carries; the rest share, and the sharing is what makes a catalogue a small object rather than a list as long as the shapes. It is the same collapse 256 forms carrying 22 values exhibits in the abstract, arriving here as a fact about pieces of a board.

Reading the small shapes #

The first nine entries are worth reading one by one, because the catalogue’s whole vocabulary is already present in them.

A single square is worth nought: neither player can place a domino, so the piece is dead. Any number of isolated squares is worth nought, which is why a board late in a game can look busy and be finished.

A vertical domino is worth $1$ and a horizontal one is worth $-1$. One free move for Left, one for Right, and the sign convention of the whole game visible in two cells.

A vertical tromino is worth $1$ and a horizontal one $-1$: three cells in a line give one move to the player who plays along them and none to the other, and the extra cell buys nothing. An L-shaped tromino is worth $\ast$ — whoever moves first takes the only domino that fits, and the piece is confused with nought.

Among the nine four-cell shapes the values are $-2$, $-\tfrac12$, $\ast$, $\{1 \mid -1\}$, $\tfrac12$, $\{0 \mid -1\}$, $\ast$ again, $\{1 \mid 0\}$ and $2$. Four squares, nine shapes, and already a switch, a half and a star.

That progression is the reason the catalogue is worth building rather than reasoning about. Nothing about an L-shaped tromino announces a star, and nothing about a $2 \times 2$ square announces $\{1 \mid -1\}$; the values come out of the recursion and have to be looked up.

Checked against the evaluator #

A catalogue is only a tool if it gives the same answer as the thing it replaces, so it was checked on every position of a 3×4 board — all 4,096 of them, counting each pattern of covered squares.

Two thousand nine hundred and sixty-nine of the 4,096 positions have their free squares in two or more pieces. Three thousand two hundred and twenty-seven have every piece inside the catalogue — the rest have a piece of seven squares or more, which is past where the table reaches.

Of those 3,227, the two methods agree on 3,227.

That is what the disjunctive sum theorem promises, and it is worth checking rather than assuming for a specific reason: the theorem says the value of a sum is the sum of the values, and the step this catalogue takes is the geometric one — that the pieces of a board really are independent components. A shape identified wrongly, a reflection applied that should not have been, a piece that touches another diagonally and was treated as separate, and the agreement would break.

One board, worked #

The piece of five is worth $\{1 \mid -1\}$ — a fight worth a move to whoever takes it, with nothing in it on average. The piece of four is worth $\tfrac12$, which is half a free move for Left. The board is worth $\{\tfrac32 \mid -\tfrac12\}$, which is the sum, and which the recursion confirms.

A player reading the board this way learns two things a single number would not tell them: that the position is worth half a move to Left on average, and that there is a fight in it worth a whole move to take. The second is the one that decides what to play.

The shapes with values no rectangle has #

Among the 104 are two shapes worth $\uparrow$ and $\downarrow$.

An up is an infinitesimal: positive, and smaller than every positive number. A region worth an up is one Left wins by a margin no count of free moves can express — Left does not have half a move in hand, or a quarter, but something below every fraction and above nothing.

No rectangle is worth an up. The rectangles produce integers, halves, switches and stars, and the all-small values appear only once the shape stops being a rectangle. Both of the shapes in question have six squares and both are the same tree-like arrangement, one reflected.

Both are six-square arrangements with a stem and a branch, the sort of shape that arises when a domino is placed across the middle of a small board and leaves a fringe on either side. Neither is exotic and neither could be guessed.

That is the sharpest thing the catalogue has to say and it is the reason a table of rectangles is not merely incomplete but misleading about the game’s range. A player who has only ever seen the rectangle table would conclude that Domineering deals in halves and switches; a player who has taken a board apart late in a game meets values that a whole different part of the theory is needed for. The consequence is concrete: two regions worth an up and a down cancel exactly, and two regions worth an up beat any single region worth a down, and neither fact is available to somebody counting free moves.

How a board actually falls apart #

The catalogue describes pieces and says nothing about how a board comes to have them, which is worth a section because the process is not what a reader expects.

Domineering boards do not split neatly down the middle. They fray. A vertical domino placed near an edge leaves a column of one or two squares cut off from the rest; a horizontal one across a narrow board can sever it entirely. So the pieces that appear are small and irregular, and they appear early — of the 4,096 positions of a 3×4 board, 2,969 already have their free squares in two or more pieces, which is 72 per cent.

That number is the practical argument for the whole enterprise. Decomposition is not a technique for the endgame; on a small board it is the normal state of affairs almost immediately, and a player who evaluates the board as a whole is doing exponentially more work than the position requires from the third move onward.

It also explains why the catalogue’s coverage improves as the game goes on. Early positions have one big piece and are not covered; late ones have several small pieces and are covered completely. The table is weakest exactly where a player needs it least, since the opening of a rectangle is the case the rectangle table already handles.

What the split is worth #

The reason to decompose is not tidiness. It is that evaluating a region of $n$ free squares costs something exponential in $n$, and evaluating two regions of $n/2$ costs twice something exponential in $n/2$, which is enormously less.

The board falls apart measures that saving directly and finds it turning a product into a sum. The catalogue is the same saving taken to its limit: the exponential work is done once per shape, in advance, and a position is then evaluated by table lookup and addition.

The extreme case in the sweep is a board with seven free squares in five pieces, the largest of which has two squares. Evaluating it directly means a search over the positions of a seven-square region; evaluating it by parts means five lookups and four additions, and the largest thing looked up is a domino.

Compare that with the worked board earlier, where the same twelve squares held a five-piece and a four-piece and the catalogue had to be consulted for both. The same board size gives completely different amounts of work depending on where the dominoes went, and the quantity that decides it is the size of the largest piece rather than how many pieces there are or how full the board is.

What the catalogue cannot do #

It stops at six squares. Eight hundred and sixty-nine of the 4,096 positions of a 3×4 board have a piece too large for it, which is 21 per cent — and on a larger board the proportion would be much worse early in the game and much better late, since the pieces get smaller as play proceeds.

Extending it is not free. The number of connected shapes grows quickly — one, two, three, nine, twenty-one, sixty-eight — and each one costs a full evaluation, so the table is exactly the exponential work being paid for in advance rather than avoided.

The second limitation is that the catalogue answers what is this piece worth and not what should be played here. A value tells a player which component to move in, by comparing incentives or temperatures; it does not name the square. That is a separate lookup and the catalogue does not carry it.

And a piece’s value is a value, not a strategy: two pieces of the same value are interchangeable in any sum, and the moves available in them may be completely different.

What the numbers among them look like #

Forty-four of the 104 shapes are numbers, and the numbers that appear are $0$, $\pm\tfrac12$, $\pm\tfrac34$, $\pm 1$, $\pm\tfrac32$, $\pm 2$ and $\pm 3$ — every one a dyadic rational with a small denominator, as every value of a short game must be.

A shape worth a number is one where the fighting is already settled: both players know how many free moves they have and there is nothing to contest. A shape worth $\tfrac34$ is one where Left has, in effect, three-quarters of a free move — a quantity that means nothing on its own and exactly the right thing in a sum, since four such regions are worth three moves.

The other sixty carry switches, stars, and the two infinitesimals. Those are the pieces where the move order matters, and a player looking at a decomposed board can tell at a glance which of its pieces are finished and which are still live, which is more than the total value says.

The convention, and one thing it hides #

Normal play: the player who cannot place a domino loses. Left vertical, Right horizontal, throughout, which is the convention every Domineering table in the literature uses and which fixes the sign of every entry.

The convention hides something worth naming. A piece worth nought is not necessarily a piece with no squares in it — a single free square is worth nought, an L-shaped tromino is worth $\ast$ and is confused with nought, and a diagonal chain of twenty squares is worth nought exactly. The catalogue’s zeroes are of two kinds and the distinction matters in a sum: a zero may be ignored and a star may not.

That is the same trap outcomes do not add is about, in miniature and on a board a reader can see.

What the region decomposition is buying, in this game #

Domineering decomposes and it does not decompose often, and the distinction decides how much this page’s machinery is worth on a real board.

A Domineering board is one region at the start and stays one for a while: a domino placed in the middle of open space leaves the space connected around it, and it takes several placements before a wall runs far enough to cut the board. So the early game has nothing for the region arithmetic to do, and the positions where it does the most work are the ones where each piece is small enough to look up.

That is the opposite of the situation in Amazons, where every move burns a square permanently and the board is in pieces within a dozen moves. The same theorem is worth completely different amounts in the two games, and the difference is not about the theorem: it is about how fast the rules destroy connectivity.

It also explains why a Domineering solver keeps testing for components rather than testing once. The board that has just split is the board whose remaining work has collapsed, and the splitting happens in the middle of the game rather than at its start — so a solver that decomposed at the root and never again would carry the whole undivided board down every line until the very end.

And it sets the ceiling on what the region catalogue below can ever be worth. A catalogue answers pieces; a board with no pieces in it gets nothing. The measurements this ladder goes on to make are all, in the end, measurements of how much of a played Domineering game is in pieces at all — and the answer is about half of it, which is enough to matter and nowhere near enough to replace a search.

The geometry the whole thing rests on #

Four-connectivity, and it is worth stating because a reader could reasonably assume otherwise.

Two free squares that touch only at a corner are in different pieces, because no domino covers them: a domino is two squares sharing an edge. So a board whose free squares form a diagonal chain is a sum of single squares, each worth nought, and the whole thing is worth nought however long the chain is.

That is the geometric fact doing all the work, and it is the one the check above would have caught had it been got wrong. A catalogue built on eight-connectivity would merge pieces that are genuinely independent, produce shapes that are not shapes, and disagree with the evaluator immediately.

Where the ladder goes next #

The domineering anchor has three rungs to here, and the six above it are one question pursued until it becomes arithmetic: what is a region worth, and can a player see it?

Which shapes are worth fighting over takes this page’s claim that no visible property predicts which regions are numbers and finds half of it wrong. A region only one orientation fits in is a whole number, on all eleven of them, for a reason a reader can supply in a sentence. The other half stands, and thirty-three shapes are what makes it stand.

Counting the moves each side has then tries the obvious count — how many dominoes each player could still place, subtracted — and gets the value on 141 of the 315 regions worth numbers, landing between the stops on 619 of the other 727. The moves a player can be talked out of notices why one number cannot do the job at all, since a packing count is optimistic for its owner and pessimistic for the opponent, and replaces it with an interval that collapses to a point on 505 of 1,042 regions and is never more than two moves wide.

Two errors that cancel then asks the question that decides whether any of it is usable on a board: does the reading survive addition? It does, and better than the exact count — over boards of one to four regions the count decays from exact on 45 per cent to 11, while the interval’s containment rises from 67 to 74, because widths add and errors do not.

The last two rungs make the whole interval readable off a drawing. Half the difference in odd runs gives the optimistic end as half the difference between a region’s odd horizontal and odd vertical runs; one domino every three cells gives the pessimistic end as $\sum \lceil (\ell-1)/3 \rceil$ over the runs, exact on all 1,042 shapes — a rule about spacing rather than the parity formula anybody expected. And they end the ladder honestly: regions with the same runs have different values, so no reading built out of runs can ever reach the value.