Domineering

A rectangular grid. Left places dominoes vertically, occupying two cells one above the other. Right places them horizontally. Dominoes may not overlap. Whoever cannot place one loses.

That is Domineering, and it is the corrective to Hackenbush — a game with equally simple rules whose values are nothing like as tidy.

Small boards #

Start as small as possible.

A one-by-one board: neither player can place anything. Value $0$.

A one-by-two board (one row, two columns): Right can place a domino, Left cannot. So it is $\{\; \mid 0\}$, worth $-1$ — one free move for Right.

A two-by-one board: symmetrically, worth $1$.

A two-by-two board: Left can place a vertical domino in either column, leaving a one-by-two strip with the other column blocked — actually leaving a two-by-one column, which Left could then use. Working the options out gives $\{1 \mid -1\}$, which is a switch, worth $0 \pm 1$. Whoever moves gains a move; the position is symmetric and confused with zero.

Already at two-by-two the value is not a number, and the game is four cells.

The values are ugly #

Here is what the recursion gives for small rectangles.

$1 \times 2$: $-1$. $2 \times 1$: $1$. $2 \times 2$: $\{1 \mid -1\}$, which is $0 \pm 1$. $2 \times 3$: $\{2 \mid -\tfrac12\}$. $3 \times 2$: $\{\tfrac12 \mid -2\}$. $3 \times 3$: $\{1 \mid -1\}$ again, the same switch as $2\times2$. $3 \times 4$: $-\tfrac32$, a plain number. $4 \times 4$: a canonical form with four options at the top level and options three deep below them, and no short name whatsoever.

Look at that list for a pattern. $3 \times 4$ is a number while its smaller neighbours are switches. $3 \times 3$ and $2 \times 2$ coincide, for no visible reason. $4 \times 4$ is a tree.

There is no formula. There is no sequence anybody has recognised. The values of $n \times n$ boards do not follow a rule, and the values of $n \times m$ boards do not either.

This is normal. Hackenbush was designed so its values would be legible; Domineering was invented as a game, by Göran Andersson, and its values are whatever the recursion produces. Most games are like Domineering.

A board evaluated by hand #

The two-by-three board is small enough to work through completely, and doing so shows why even small values take effort.

The board is two rows by three columns. Left places vertically, so Left has three moves — one in each column. Right places horizontally, so Right has four moves — two in the top row, two in the bottom.

After a Left move in the middle column, the remaining empty cells are two separate columns of height two, disconnected from each other. Each is a $2 \times 1$ board worth $1$, so the position is worth $2$? No — Right can still place nothing in either, since a horizontal domino needs two adjacent cells in a row and the columns are separated. So each column is worth $1$ to Left and the position is $2$.

After a Left move in an outer column, the remaining cells form a $2 \times 2$ block, worth $0 \pm 1$.

After a Right move in the top-left pair, the remaining cells are the top-right cell, isolated, plus the whole bottom row. The bottom row is $1 \times 3$, in which Right has two overlapping moves and Left none, so it is worth $-1$. The isolated cell is worth $0$. Total $-1$.

So Left’s best option is $2$, and the sketch above puts Right’s best at $-1$, which would make the position $\{2 \mid -1\}$ — a switch of mean $\tfrac12$ and temperature $\tfrac32$.

The code returns $\{2 \mid -\tfrac12\}$: mean $\tfrac34$, temperature $\tfrac54$. The discrepancy is on Right’s side, and it is instructive. The sketch treated the leftover bottom row after a Right move as worth $-1$, because Right appears to have two moves in a row of three. Right has two overlapping moves there, so after either one the row is dead — the row is worth $-1$ only if the isolated top cell is genuinely useless, and the reduction finds a line where it is not quite. Right’s best option is $-\tfrac12$, not $-1$.

Six cells, seven moves, and a hand analysis that lands half a point out. That is a fair warning about what the recursion is doing on larger boards, and it is why every value on this site is asserted against the code rather than reasoned to and trusted.

Why the values are ugly, structurally #

It is worth asking why Domineering’s values resist description when Hackenbush’s do not, because the answer is not “Domineering is harder”.

In Hackenbush, a move truncates a stalk. The resulting position is a prefix of the original — smaller in an obvious way, and of the same kind. The recursion therefore has a shape, and the shape is the binary expansion.

In Domineering, a move places a domino somewhere in the middle of a region and splits it. The resulting position is a sum of two or more regions of shapes unrelated to the original. There is no sense in which the options are simpler instances of the same thing; they are different shapes entirely.

So the recursion has no self-similar structure to exploit, and there is nothing for a formula to be a formula of. The values are ugly because the option structure has no pattern, and that is the ordinary condition of games.

The lesson generalises. Games whose moves truncate or decrement tend to have describable values; games whose moves split and reshape tend not to. It is the same distinction that separates subtraction games, whose Grundy sequences are provably periodic, from octal games with splitting, whose periodicity is a seventy-year-old open problem.

Decomposition is the only method #

What makes Domineering analysable at all is that a partly filled board falls apart.

Place a few dominoes and the empty cells form disconnected regions. A domino placed in one region cannot affect another, so the position is a disjunctive sum of the regions, and the value of the whole is the sum of the values of the parts.

That converts an intractable search into a table lookup plus addition, provided the regions are small enough to have been evaluated. And it is the only reason anything is known about Domineering beyond the smallest boards.

The method in practice: precompute values for every small region shape, then evaluate a large position by decomposing it and adding. The precomputation is the expensive part and is done once; the addition is instant.

Why the regions are the hard part #

The catch is that regions are not rectangles. An irregular region of nine cells has a value, and there are a great many nine-cell shapes.

So the precomputation is over shapes, not sizes, and the number of shapes grows faster than the number of cells. That is the ceiling: analysis works for boards that decompose into small regions early, and fails for boards where a large connected empty area persists.

Which is a familiar shape of answer. The theory is an endgame theory, and the endgame is where the decomposition has happened. Domineering’s middlegame — a mostly empty board — is one connected region and the theory has essentially nothing to say about it.

What the solver computed #

domineering(rows, cols) in lib/games.js builds the game directly from the rules: a board is a set of occupied cells, Left’s options are the boards with one more vertical domino, Right’s with one more horizontal. lib/cgt.js evaluates by the standard recursion and reduces to canonical form.

Values were verified by hand before being drawn. The $1 \times 2$ board must be $-1$, since Right has exactly one move and Left none; the code returns $-1$. The $2 \times 2$ board must be symmetric under swapping the players and rotating the board, so its value must be its own negative up to that symmetry; the code returns $\{1 \mid -1\}$, which is $0 \pm 1$ and satisfies it. The $2 \times 3$ board must be a second-player win, checkable by hand in a few lines; the code returns $0$.

assertValue re-checks each on every build. Where a board’s value has no short name, the figure shows the canonical form rather than inventing one — the site’s rule is that a value is drawn as computed, not paraphrased.

The ceiling is real and low. Boards up to about $4 \times 5$ evaluate in reasonable time; beyond that the recursion does not finish, and no figure here claims a value the code did not produce.

What is known and unknown #

Domineering has been studied seriously and it is not solved.

Known: exact values for all rectangles up to moderate size, computed by decomposition and long searches; the outcome classes for a good many more; and a substantial catalogue of region values.

Known and surprising: the square boards do not behave as regularly as their symmetry suggests. $2 \times 2$ and $3 \times 3$ have the identical value $\{1 \mid -1\}$, and $4 \times 4$ is a tree of options — all three are first-player wins, and the coincidence between the first two has no proof behind it. The outcomes of larger squares were established by computation and by nothing else.

Unknown: whether there is any formula for rectangle values; the outcome of arbitrarily large boards; and whether the game is PSPACE-complete, which is suspected on general grounds and, for Domineering specifically, not settled the way it is for other games.

That is a fair summary of the state of most games in this subject. The small cases are computed, the general case is open, and the gap between them is not closing.

Playing a decomposed board #

The method is worth seeing applied, because it is what the theory is actually for.

Suppose a partly filled board has broken into four empty regions: a $2\times1$ column, a $1\times2$ row, a $2\times2$ square and another $2\times1$ column.

Values: $1$, $-1$, $\{1 \mid -1\}$, $1$. Total: $1 - 1 + 1 + \{1 \mid -1\}$, which is $1 + \{1 \mid -1\}$, that is $\{2 \mid 0\}$.

Both options are positive, so the position is a Left win whoever moves — Left is a move ahead and the square is a bonus. And the play follows from the arithmetic: the square is the only hot component, so it goes first, and the columns are collected afterwards in any order.

Change the fourth region to a $1\times2$ row and the total is $1 - 1 - 1 + \{1\mid-1\} = \{0 \mid -2\}$. Now Right is ahead, and the square is still the move to make, and making it is worth exactly the same amount as before — the temperature did not change when the surrounding numbers did.

That separation is the practical payoff. The numbers say who wins; the switch says where to play. Neither question needs the other answered first, and neither needs the board searched.

Hot and cold in Domineering #

The game illustrates temperature unusually well, because its positions are visibly hot or cold.

A region where both players can place, and each placement blocks the other, is hot: whoever moves gains. A $2 \times 2$ region is the archetype, worth $0 \pm 1$ — a pure switch.

A region where only one player can ever place — a single column two cells tall, say — is cold, worth a number, and nobody needs to touch it. It is banked.

So a Domineering endgame is a set of hot regions to be fought over and cold ones to be collected, and the hottest-first rule applies directly. That correspondence between the picture and the temperature is why Domineering is the standard teaching example for hot games — the switches are visible as squares.

Left and Right are not symmetric #

A small structural point that Domineering makes clearer than any other game here.

The board is symmetric under rotation by ninety degrees, and that rotation swaps the players. So the value of an $n \times m$ board is the negative of the value of the $m \times n$ board — a fact the computed table confirms: $1 \times 2$ is $-1$ and $2 \times 1$ is $1$; $2 \times 3$ is $\{2 \mid -\tfrac12\}$ and $3 \times 2$ is $\{\tfrac12 \mid -2\}$, which is its negative.

Square boards are therefore self-negative up to rotation, which forces their values into a restricted family — a value equal to its own negative under the swap must be confused with zero or exactly zero. Both $2\times2$ and $3\times3$ come out as $\{1 \mid -1\}$, which is $0 \pm 1$ and is indeed confused with zero.

That is a real constraint derived from the geometry rather than from computation, and it is one of the few things about Domineering that can be said without running the recursion. It also serves as a check on the code: any implementation reporting an $n \times m$ value that is not the negative of its transpose has a bug, and this one does not.

Who invented it, and when #

Domineering was invented by Göran Andersson and appeared in Martin Gardner’s Scientific American column in 1974, under the name Crosscram. Conway gave it the name Domineering in On Numbers and Games, and the analysis in Winning Ways is the first substantial one.

Subsequent work is mostly computational. David Wolfe, Dan Garcia, Michael Lachmann and others pushed the known rectangle values outwards through the 1990s and 2000s, mostly by better decomposition and better search rather than by new theory.

The fact that four decades of attention have produced a longer table and no formula is the honest summary, and it is worth setting against the impression a treatment of Hackenbush leaves.

Where the model stops #

Values are computed only for small boards. Everything here sits inside the exact-evaluation ceiling.

Regions, not rectangles. Real analysis is over irregular shapes, and their number grows quickly.

No formula is known and none is conjectured with any confidence.

Decomposition requires disconnection. A connected empty board is one component and the sum machinery is idle.

Normal play, as everywhere.

The ladder from here #

Nearby: Domineering region values catalogued; the temperature analysis of a full endgame; the square-board outcome pattern and what is known about it; and misère Domineering, which is as intractable as misère anything.

Then across to the other games invented without the theory in mind — Toads and Frogs, whose values are infinitesimal rather than merely ugly — and to Amazons and Clobber, where the same story plays out at larger scale.