The values of every small board

The first essay on Domineering gave the rules — Left places vertical dominoes, Right horizontal ones, and whoever cannot place loses — and reported that the values are a mess. It said so from five or six boards. This essay does the whole arithmetic instead: every rectangle the evaluator on this site can reach, with its canonical value, its outcome, its temperature and its mean.

That is thirty rectangles, and their transposes come free: rotating the board by ninety degrees swaps the players and negates the value, so a table over 1×n, 2×n, 3×n and the two 4×n boards that finish covers every small rectangle in both orientations.

The point of computing all of them is that the table then says things a handful of boards cannot, and three of those are the substance of this essay. The values are not a formula in m and n, and the way they fail to be one is specific and measurable. A deep canonical form is not a complicated position — the four-deep forms here sit on boards of sixteen squares. And exact evaluation stops for a reason that is not slowness: the board is a bitmask, thirty-one cells is a wall, and the shape of the rectangle matters more than its area.

The row that is only ever a number #

Start with the family that does behave, because the contrast is the argument.

A 1×n board is a single row. Left, who places vertically, has no move on it at all — a vertical domino needs two rows. Right has n − 1 placements, every one of them overlapping its neighbours, so the only question the row ever asks is how many disjoint dominoes fit in it. The computed values for n = 1 through 8 are 0, −1, −1, −2, −2, −3, −3, −4: every one a plain integer, every board from n = 2 upwards a win for Right whoever moves, and the whole row given by −⌊n/2⌋.

This is what a solved family looks like: one formula, no exceptions in range, and a reason behind it that survives inspection. A row of n cells holds exactly ⌊n/2⌋ non-overlapping horizontal dominoes, Left can never interfere, and the position is worth that many free moves to Right — so a reader who wanted the value of a 1×1000 board would not need the evaluator. The temptation is then to expect the next family to do something similar. It does not, and the failure is not a near miss.

Three periods of the outcome, and then a board worth nothing #

The 2×n family is where a formula would be most welcome — it is the family a partly played board decomposes into most often — and it is the family that most clearly refuses.

Take the outcome class alone, ignoring the value, for n = 1 through 12. It runs L N N R · L N N R · L N N R. Three complete periods of length four, twelve terms without a break: a Left win, two first-player wins, a Right win, and again, and again. Any reasonable reader would call it settled. A period is a proof in the impartial theory, where a repeated block of Grundy values genuinely does continue for ever once a short condition is checked. No periodicity theorem of that kind exists for partizan outcome sequences, and this one has nothing behind it but twelve terms.

The thirteenth term is not L. The 2×13 board is worth exactly 0 — a second-player win, a plain number, and the only board in the entire catalogue outside the 1×n row that is worth nothing at all. The pattern says L and the computation says P.

The break is a single term rather than a shift in periodicity. 2×14 comes out N, which is where the pattern’s second slot puts it, so whatever happened at n = 13 did not knock the sequence into a new phase. It is one board out of step, and there is no reason visible in the position for it to be that board rather than another.

Not a formula in m and n #

The outcome is the coarsest thing a board has, so if the outcomes break a twelve-term pattern the values underneath them are unlikely to be tidier. The temperatures are where that shows most sharply, temperature being the one number about the shape of the fight rather than about who is ahead. Here is the whole 2×n sequence as computed, for n = 2 to 14, with “—” for the boards that are numbers and have no fight in them:

1 · 5/4 · 0 · — · 1 · 1 · 9/8 · 9/8 · 19/16 · 19/16 · 0 · — · 9/8.

It rises to 5/4, collapses to 0, returns to 1, edges up through 9/8 to 19/16, drops to 0 again at n = 12, and comes back at 9/8. It is not monotone, not periodic, and not converging on anything the range can see. What it does do is land on a finer grid as the boards get longer: the denominators run 1, 4, 8, 16, and 19/16 sits between 9/8 and 5/4 rather than beyond either of them. The fights are all about one move’s worth, and the exact worth of one move keeps needing more binary places to write down.

The mean values drift more slowly. For n = 2 to 14 they are 0, 3/4, 0, 1/2, 0, 1/2, −1/8, 3/8, −5/16, 3/16, −1/2, 0, −5/8: Right gains ground as the row lengthens, which is what the geometry predicts, but not monotonically, and on denominators that grow the same way.

The strongest single piece of evidence against a formula is not in the 2×n row at all. It is that a number turns up in the middle of a hot family, more than once, with nothing distinguishing its board. 2×5 is worth 1/2 and 2×13 is worth 0, sitting among switches. 3×4 is worth −3/2 and 3×5 is worth −1, sitting between 3×3, which is the switch {1 | −1}, and 3×6, which is the fight {−1 | −7/2} at temperature 5/4. And 4×5 is worth 1 while 4×4, one column narrower, is a form 114 characters long.

The middle two are the ones to stare at. Nothing about a 3×4 board announces that the fighting is over before it starts; it is three squares larger than a board worth $\{1 \mid -1\}$ and three smaller than one worth $\{-1 \mid -7/2\}$, and it is worth a number outright. Whatever a formula in m and n would have to do, it would have to do that twice in this row and then stop.

A formula in m and n would have to produce a bare integer at 4×5 and a 114-character tree at 4×4. Nothing about the two boards suggests where such a discontinuity would come from, and after four decades of attention nobody has proposed one.

Four extra squares, and the value goes from a tree nobody can read aloud to the integer one. That is the discontinuity in its sharpest available form, and it is worth noticing that it runs in the direction nobody would guess: the larger board is the simple one. This is the same condition as the strip nobody has a formula for: the values exist, they are computable one at a time, and the sequence of them is not the sort of object that has a closed form. It is also the ordinary condition of a partizan game that was invented without the theory in mind, which is most of them.

The hottest board a figure can hold #

The hottest board in the whole catalogue is 3×8, at temperature 21/16, with value { {−1/2 | −3} | {−13/4 | −11/2}} and mean −49/16. That board took 160 seconds in a fresh process and is measured here but not drawn, because a figure that spends nearly three minutes to render is a figure this site will not build.

Within reach of a drawing, the hottest are 2×3 and 3×6, both at exactly 5/4.

That tie is worth pausing on. One board has six cells and the other eighteen, one is a first-player win with a positive mean and the other a Right win with mean −9/4, and the amount at stake in a single move is identical. Temperature never gets far above 1 anywhere in the catalogue, at any size the evaluator reaches: on a board this small nobody ever has much more than one move’s worth at stake.

The 2×3 board is small enough to work through move by move, and the essay that opens this ladder does exactly that: three vertical placements for Left, four horizontal ones for Right, and $\{2 \mid -1/2\}$ out of them. What is worth having here instead is the diagram that turns that value into the two numbers this table is built on.

Two boards worth less than every number #

Two of the thirty boards are neither numbers nor switches, and they are the surprise in the table.

2×4 is worth { {2 | 0} | 0}. Its outcome is R: Right wins it whoever moves first. And yet the board is an infinitesimal — smaller in magnitude than every positive number, and larger than every negative one. That was checked by direct comparison against ±1/2^k for k = 0 through 10, which is the only way to establish it: the value is compared with each of those numbers by playing out the difference, and it comes out below every positive one of them.

So here is a board Right wins outright, whichever player is on move, and whose worth is less than a thousandth of a free move — and, since infinitesimal is the conclusion rather than the last line of the check, less than every positive number there is. Winning is an outcome; magnitude is a comparison; a game can be decisive and negligible in the same breath, and holding both together is most of what it takes to read partizan values correctly.

4×4 is the other one. Sixteen squares, a canonical form 114 characters long, fuzzy with zero and infinitesimal — the whole board worth less than the smallest fraction anybody would bother to name.

One distinction has to be made here, because the two words are constantly confused. Infinitesimal is a statement about size; all-small is a statement about who has a move. An all-small game is one in which either both players have a move or neither does, all the way down, and every all-small game is infinitesimal. The converse fails, and 2×4 and 4×4 are the demonstration: neither is all-small — a board can easily leave one player with placements and the other with none, as every 1×n board does — and both are infinitesimal anyway.

A deep form is not a complicated position #

Look again at the 2×n figure and read the values rather than the temperatures. 2×6 is { { {3 | 1} | 1} | −1} — three levels of braces on twelve squares. 2×8 is { { { {4 | 2} | 2} | 0} | {−1/2 | −2}}, four levels on sixteen. 2×10, 2×12 and 2×14 are four levels deep as well.

Sixteen squares is a position a reader can draw on the back of an envelope in five seconds. Its canonical form nests four deep and takes a line and a half to write out.

That mismatch is the clearest available statement of what the notation is for. A value is a compression, not a description. The braces do not record the board, the shape of the region, or the twenty-odd placements available; they record what is left after every dominated option has been deleted and every reversible one bypassed. Four levels of nesting means four successive rounds of genuine choice in which the best reply itself has a best reply, and that can happen in sixteen squares as easily as in a hundred. The reverse holds too: the simplest value in the catalogue, 0, belongs to 2×13, the second-largest board in it.

The compression is measurable and it is severe. A 3×3 board’s position graph holds eighteen distinct games and produces a value with four nodes in it; 3×4 holds seventy-eight and produces another four-node value; 4×4 holds 562 and keeps fourteen. Almost all of the search is discarded, and what survives is the only part worth storing.

Two different counts of “position” are in play there and they measure different things. Those figures count distinct games — two boards whose option structure is identical are one node. Counting distinct sets of occupied squares instead, with no folding of one position into another, a 4×4 has 5,700. The evaluation therefore compresses twice: 5,700 board states collapse to 562 distinct games, and those reduce to a value with fourteen nodes in it.

Where the search stops, and why #

Every value above came from domineering(rows, cols), which builds a board directly from the rules as a bitmask over rows × cols cells, with Left’s options the boards carrying one more vertical domino and Right’s one more horizontal. The site’s evaluator applies the standard recursion to that and reduces it to canonical form; the temperature and mean come off the thermograph. Nothing in the table was looked up.

The bitmask is the first wall on exact evaluation and it is a hard one. No board of more than 31 cells can be written down at all, whatever machine it runs on. That is not a performance limit and no amount of patience moves it.

The second wall arrives well before the first, and it is about shape rather than area. Two 24-cell boards make the point on their own: 3×8 evaluates in 160 seconds, and 4×6 exhausts an 8 GB heap. Same cell count, same rules, and one finishes while the other cannot be done at all. 5×5 has 25 cells and exhausts an 8 GB heap after about 245 seconds — while 2×14, at 28 cells, evaluates in 100 seconds, because a board two cells high has far fewer reachable positions than a squarish one of the same area. 2×15 has 30 cells, is inside the bitmask limit, and dies. At the easy end, 4×5 takes 5.6 seconds and 3×7 takes 7.8.

So the honest boundary of this essay is: the catalogue is complete out to the boards listed, and nothing whatever is claimed about 4×6, 5×5, or any square board above 4×4. That is the whole of this site’s exact-evaluation ceiling for the game, and it is low. Three different claims are called “solved” and this is the weakest of them — particular positions evaluated, no family settled, no general algorithm improved. The published literature reaches further than thirty rectangles, by decomposition and long searches rather than by new theory: Göran Andersson invented the game, Martin Gardner’s column carried it in 1974 as Crosscram, On Numbers and Games and Winning Ways named and first analysed it, and David Wolfe, Dan Garcia, Michael Lachmann and others pushed the table of known rectangle values outwards through the 1990s and 2000s. Four decades produced a longer table and no formula, which is exactly what thirty boards computed here look like.

What the catalogue cannot show, and under what convention #

A table of values is not a table of plays. Every figure here reports what a board is worth and none of them shows a game being played. {2 | −1/2} says the 2×3 board is a first-player win worth three quarters on average and 5/4 to move in; it does not say which of Left’s three placements is the good one, and the figure that shows the moves does not say which option produced the value.

The truncation is visible and the value is not. The 4×4 form runs to 114 characters, wider than any column this site draws. Where that happens the figure shortens the text and states on its own face that it has done so; the alternative is a 1,276-pixel-wide figure, and quietly printing a prefix as though it were the value is not an option at all. So the one board most worth staring at is the one whose value cannot be read off the page.

And an absence has no picture. The strongest claim in this essay is that no formula in m and n is known, and the evidence for it is thirty computed values that do not fall into one. No figure can draw the formulas that were tried and failed.

The convention behind every number above is normal play: the player who cannot place a domino loses. Change that one word and nothing survives. Under misère play the player who cannot move wins, and the values here do not merely change — they stop being values, because misère games have no comparable canonical theory to be values in. The infinitesimal 2×4, the switch 2×2, the temperature 5/4 of the 2×3 board: all of it is normal play or it is nothing.

The second convention is that these are single boards. A real position late in a game is a disjunctive sum of disconnected regions, and regions are not rectangles. This catalogue is the rectangle case — the case decomposition reduces to, not the case a player actually holds.

Where the ladder goes next #

Four rungs stand on this table directly.

The square-board outcome pattern. 2×2, 3×3 and 4×4 are all first-player wins, and 2×2 and 3×3 have the identical value {1 | −1}. The outcomes of larger squares are known — established by computation and by nothing else — and the pattern in them is one of the better-known open questions about the game. The table here can say only that the coincidence at 2×2 and 3×3 is real and has no proof behind it.

Domineering as a sum of regions. Everything above is a rectangle and a partly played board is not. A rung that catalogues region values, and evaluates a real position by decomposing it and adding, is the one that turns this table into something a player could use.

The temperature analysis of a full endgame. With regions catalogued and temperatures attached, the question becomes move order across several hot components at once, which is the play-the-hottest machinery applied to a game nobody designed for it.

Misère Domineering, which changes the losing condition and loses the theory. Every number in this catalogue is a normal-play number, the misère table would have to be recomputed from scratch, and its entries would not add.

And sideways rather than up: Cram is the same board with the orientations shared, which makes it impartial — one game, one set of moves, Grundy values instead of switches. The same thirty rectangles, a different theory, and a different answer on nearly every one of them.