Which shapes are worth fighting over

A board that is a sum of its regions catalogued every connected shape a played Domineering board can fall into, up to six free squares, and evaluated all 104 of them. It closed by naming what the catalogue makes askable:

Which shapes are hot, and which are worth an infinitesimal? Forty-four of the 104 are numbers and the rest are not, and there is no visible property of a shape that predicts which.

The sentence is half wrong, and the half that is wrong is the half a reader can check by eye.

Three kinds, and where they start #

Of the 104 shapes: forty-four are worth numbers, twenty-two are worth a number plus something the temperature scale cannot see, and thirty-eight are hot.

The three classes do not appear at the same time. Every shape of one, two or three squares is either a number or, in one case, at temperature nought. The first hot shape has four squares and it is the 2 × 2 box, worth {1 | −1}. By six squares hot shapes are the largest class: thirty of sixty-eight.

That growth is what a reader would expect and it is worth stating because it makes the small cases misleading. A player who has met Domineering on a 1 × n strip has met Cutcake’s cousin — a game whose every value is an integer — and nothing in it suggests a fight.

The criterion that works #

Left plays vertical dominoes and Right plays horizontal ones. That is the whole asymmetry of the game and it is the whole of the criterion.

A shape in which no two squares are vertically adjacent admits no vertical domino at all. Left has no move in it, ever, from the start and after any number of Right’s moves — because Right’s moves only remove squares, and removing squares cannot create an adjacency. So the region is a game only one player can move in, and a game only one player can move in is worth a whole number: the count of moves that player has.

The mirror statement holds for a shape with no horizontal adjacency.

Eleven of the 104 shapes admit only one orientation. All eleven are worth whole numbers, and the census asserts it rather than reporting it: a shape admitting one orientation and worth anything else would stop the build, because it would mean either the argument above is wrong or the evaluator is.

Turned round, that gives a necessary condition for a fight. A shape is hot only if both orientations fit in it, on all thirty-eight of the hot shapes, with no exception — which is the second assertion and the one the essay’s first sentence is about.

And the thirty-three that stop it working both ways #

The converse fails, and it fails on a third of the catalogue.

Ninety-three shapes admit both orientations. Thirty-three of them are worth whole numbers or fractions anyway, and twenty-two more sit at temperature nought. So of the shapes that pass the necessary condition, fewer than half are hot.

The failures are not marginal cases either. A 1 × 4 strip with one square hanging off the end admits both orientations — the hanging square is vertically adjacent to the strip — and it is worth an integer. A plus-shape of five squares admits both and is worth nought. The condition rules out fights and does not produce them.

So the rung below’s sentence survives in the form that matters. There is a visible property that guarantees a number, and there is no visible property that predicts a fight; a reader looking at a shape can sometimes be certain it is cold and can never be certain it is hot without evaluating it.

What the hot shapes look like #

Since the criterion does not predict hotness, it is worth asking what the thirty-eight actually are.

The hottest is the 2 × 3 rectangle at temperature 1¼, worth {2 | −1/2}. The next four are all at 1¼ as well and are all six squares: two are 2 × 3 rectangles with a square moved, one is a staircase, one is a 2 × 2 box with two squares in a column added. Then a band at 1 that contains the 2 × 2 box, the L of five squares, and eight others.

The pattern in that list is compactness. The hot shapes are the ones that are nearly rectangular and nearly square; the cold shapes that admit both orientations are the long thin ones with a bump. That is a description rather than a criterion, and it is a description with an obvious mechanism — a compact shape gives both players room in the middle, so both have moves that matter, so the region is contested — and it is not enough to compute anything with.

It also explains why the hot shapes arrive at four squares and not earlier. Four squares is the smallest number that can be arranged compactly enough for both players to have a move that the other cares about, and the arrangement is the 2 × 2 box.

A one-way criterion still has a use, and it is not the use a reader first reaches for.

A solver evaluating a played board splits it into regions and evaluates each. Evaluating a region is a search over its own positions, and the searches are what the time goes on: finding the parts is cheap and evaluating them is not. A test that says this region is worth an integer and here it is replaces a search with a count, and it fires on every strip the board falls into — which on a partly played board is a great many of the pieces, because a board fills up from the middle and leaves strips at the edges.

So the criterion is a shortcut rather than an insight, and shortcuts that fire often are worth having even when they explain nothing. What it cannot do is the thing the rung below wanted, which is to look at a shape and know whether it is worth fighting over. For that there is no test short of the recursion, and a later section is why.

The saving is measurable and it is not large in this catalogue, because eleven shapes of 104 is a tenth. On a real board it would be larger, since a board that has been played on for a while is mostly edges; how much larger is a question about how boards fall apart rather than about which shapes exist, and this site has the machinery for it and has not crossed the two.

The twenty-two at nought #

The middle class is the one the rung below’s sentence puts on the wrong side of the line, and it deserves its own paragraph.

A shape at temperature nought is not a number and is not a fight. Its two stops coincide, so the number it is worth plus-or-minus-something is exact, and the something is an infinitesimal — a quantity that decides who wins and contributes nothing to the count. Twenty-two of the 104 are like this and six of them are all-small, meaning every position reachable from them has a move for one player exactly when it has one for the other.

For a player, the practical difference between the twenty-two and the forty-four is real and small. Both are regions with nothing to fight over: nobody wants to move there, because every move in them loses ground. What separates them is what happens when the rest of the board runs out, and at that point an infinitesimal is the whole game.

So the honest three-way split is not number, infinitesimal, fight. It is worth moving in now, worth moving in last, and worth nothing — and the criterion above separates the third from the other two on eleven shapes and separates nothing else.

What the eleven are #

Naming the eleven is worth a paragraph, because a class defined by a negative condition is easier to trust once its members are on the page.

A shape with no vertical adjacency is a shape whose squares lie in distinct rows or, within a row, are horizontally connected — which for a connected shape means it is a single horizontal strip. So the shapes only Right can move in are exactly the 1 × n strips, and there are five of them at these sizes: lengths two to six.

The mirror gives the n × 1 columns, another five, at lengths two to six. That is ten, and the eleventh is the single square, which admits neither orientation and is worth nought — a game neither player can move in, which is the degenerate case of both statements at once.

So the criterion’s class is the strips, and the number each is worth is the number of dominoes the one player can fit end to end without leaving a stranded square: two for a strip of four, two for a strip of five, three for a strip of six. That last is the count Cutcake is made of and it is not the count of squares divided by two.

And the strips are exactly where a reader meets the game. Domineering on a strip is the introductory example in every account of it, and every value in that example is an integer, which is the least representative thing the game does.

Why an integer needs the two players never to meet #

The eleven are worth one more look, because the property that makes a shape worth a whole number is a property of the shape rather than of the value, and it is the same property that makes a whole family of games trivial.

A region is worth an integer $n$ when one player has $n$ moves in it and the other has none, all the way down. That is not the same as one player having more moves than the other; it is the stronger statement that the two players’ moves never interfere, so nothing either does changes what the other can do — because the other can do nothing at all.

On a Domineering region that means the shape admits placements in one orientation and none in the other, at every stage. A single row of squares takes horizontal dominoes and no vertical one, and stays that way however many are placed, because a horizontal placement shortens a row and never creates a column. The one-orientation property is preserved by every move, which is what carries it down the recursion and what makes the value an integer rather than merely a positive game.

The failure case is the instructive one. A shape that admits both orientations at the top may still admit only one after a move, and then it is a fight followed by a count rather than a count. That is the difference between the eleven and the twenty-two at nought: the second group is not one-orientation, it is balanced, and balance is a fact about the two counts rather than about the shapes available to either player.

Which is why Cutcake is the family this class belongs to rather than a curiosity beside it. Every Cutcake position is an integer for exactly this reason — a horizontal cut and a vertical cut never affect each other’s availability — and the eleven shapes here are the Domineering regions that happen to have the same structure. A game whose whole board has it is a game with no fights in it at all.

Why the criterion is provable and the converse is not #

It is worth being explicit about the asymmetry, because it is the general shape of what a shape can tell a player.

The criterion is a statement about what moves exist, and moves are visible. No vertical adjacency means no vertical domino means no Left move, and the argument needs nothing about values at all — it would hold if the game were scored differently, or played to a different ending.

Hotness is a statement about what the moves are worth, and worth is a function of the whole game tree. Two shapes with the same number of vertical and horizontal placements can have completely different values, because what matters is which placements interfere with which, and that is the recursion rather than a count.

So the two halves of the question are not the same kind of question, and the rung below was right to expect no criterion for the second. A property of a shape that predicted hotness would be a property that summarised a game tree, and the reason the subject has canonical forms is that game trees do not summarise.

What the catalogue does not say #

Three limits.

Six squares is where the enumeration stops. The catalogue is every connected shape of at most six free squares, which is 104 shapes; at seven it is 208 and at eight it is 730, and the evaluator reaches them. What it does not reach is the shapes a real 8 × 8 board falls into, which are routinely larger than either. Whether the criterion survives — it must, since the argument for it says nothing about size — and whether the converse’s failure rate stays near a third is a computation nobody has run.

A region is not a board. Everything here is the value of one connected piece. A board in play is a sum of pieces and its temperature is not the largest of theirs, so a board made entirely of cold regions can still have a move worth making and a board with one hot region in it need not be a fight.

The catalogue counts shapes and not occurrences. A 1 × 2 domino-shaped hole appears in a played board far more often than a six-square staircase does, and both count once here. A census weighted by how often each shape actually turns up during play would be a different table, and it is the one a solver author would want; producing it means playing games rather than enumerating shapes.

And the classification is by temperature. Temperature is one reading of a value and it is the one that answers is this worth moving in. It is not the reading that answers who wins, which is the outcome class, and the two do not line up: eleven of the forty-four numbers are worth nought and are second-player wins, and so are several of the twenty-two.

The convention, named #

Normal play, and Left plays vertically throughout. A shape is a connected set of free squares, normalised so that two shapes related by a reflection are one shape; the value of each is computed by the recursion over its own positions and reduced to canonical form, and the temperature is the height at which the two thermograph walls meet.

A number is given temperature −1 rather than nought, so the three classes in every count above are disjoint: a shape is a number, or sits at nought, or is hot, and never two of those.

Where the ladder goes next #

The domineering anchor has four rungs to here: the game, the values of every small board, the pieces a played board falls into, and now what kind of value a piece carries. The five above it all chase the count this page asks for, and they get it — as a formula, on both ends, readable off a drawing.

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

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

The last two rungs turn the interval into arithmetic. Half the difference in odd runs gives the optimistic end a closed form: half the difference between the region’s odd horizontal runs and its odd vertical runs. And one domino every three cells gives the pessimistic end one, and it is not the parity formula anybody expected — the smallest maximal packing is $\sum \lceil (\ell - 1)/3 \rceil$ over the runs, exact on all 1,042 shapes.

So the class this page describes becomes a computation a player can do by eye, and the same ladder shows what it can never be: regions with identical runs have different values, so a reading built out of runs cannot reach the value however sharp both ends get.

Two neighbours are worth the trip. Cutcake is the game every value of which is an integer for the same reason the eleven are: one player’s moves and the other player’s moves never interfere. And the values of every small board is the rectangle table this page’s compactness description is drawn from, where the outcomes of the squares are a known open problem and the temperatures are not.