What a strategy has to remember

What a value leaves out opens this anchor by naming the quantities the equivalence discards, and how many moves are worth making counted the first of them: over the catalogue of Domineering regions, 63 of 125 values have two regions disagreeing about how many placements are worth making, and 52 disagree about whether there is a choice at all.

That page closed on the second quantity:

A player who knows the value knows the outcome; a player who has to achieve it has to keep track of which region to answer in and which square in it, and the size of that bookkeeping is measurable in the same way this page measured the move count. The natural measure is the number of distinct positions a winning strategy has to distinguish, against the number of distinct values among them, and the gap between those two counts is what a value costs a player who wants to win rather than to predict.

The two counts are 4,269 and 128.

What is being counted #

The population is every position reachable by play inside the catalogue of regions of at most eight squares. That includes the disconnected leftovers, because a played region falls apart, and each position is counted once however many regions it arises in — a two-square domino gap is one thing to remember whether it turns up inside an L, a T or a square.

There are 4,269 such positions and they carry 128 distinct values. A value therefore stands for thirty-three positions on average, and the commonest of them stands for six hundred and eighty-two.

That compression is not a defect. It is the whole benefit of the theory: a player who knows a region is worth $1\ast$ knows everything about how it behaves in every sum it will ever sit in, and does not have to know which of the 335 boards worth $1\ast$ is on the table. What the compression cannot do is name a move, because a move is a square on a particular board.

Four kinds of turn #

To count what a strategy must remember, each position is taken twice — once with Left to move in it and once with Right — and each of those 8,538 turns falls into one of four kinds.

• No move at all — 1,498 turns. Nothing to decide.
• One placement — 2,214 turns. Nothing to remember: the move is forced, and a player who can see the board can see it.
• Every placement a best one — 1,518 turns. This is the value’s slack, and it is the pleasant case: the theory does not care, so neither need the player.
• Some best and some not — 3,308 turns. Each of these is an entry in a table.

So a winning strategy over this whole catalogue is a book of 3,308 lines. Against it, the predictive theory is 128 numbers. The ratio is twenty-six to one, and that number is the answer to the rung below’s question.

The rung below, in these terms #

The rung below found two regions of the same value differing in how many of their placements are best, and treated that as a statement about the value’s silence. In the accounting here it is a statement about the table: those two regions are two entries, and they are two entries because the value does not separate them.

That is worth making explicit, because it is the mechanism behind the twenty-six. If values and positions were in step — one board per value — the strategy table would be the value list, and the theory would name moves for free. The ratio between the two counts is exactly how far from that the subject is, and it is not close.

Where the memory is #

The distribution is sharp enough to be worth stating as a rule of thumb. Below five squares a strategy is empty: every turn is forced, impossible or free, and 4 of the 793 four-square turns are decisions. From five squares the decisions arrive, and by seven they are almost the whole of it — 332 decisions against 10 forced moves.

That has a plain reading. A small region has few placements and they are usually equivalent or unique; a large one has many, and they differ. So the bookkeeping a player carries is concentrated in the early part of a region’s life, which is exactly the part a player is most likely to meet on a full board, and it thins out as the endgame arrives — the reverse of the usual picture of an endgame as the hard part.

The reverse is right for a sum, though, and that is the tension this whole subject lives in. The hard part of a large board is not any one region, since each region is small; it is which region to move in, and that decision is made from the values. The values are the cheap part and the squares are the dear part, and a player needs both.

Why a value cannot carry a move #

The mechanism is a counting argument, and it is worth stating plainly because it is not about Domineering.

A value is an equivalence class. Two positions with the same value are interchangeable in every sum, which is what the substitution theorem says and what makes the arithmetic legitimate. But interchangeable in every sum says nothing about their internal structure: one may be a four-square L and the other a pair of separated dominoes, with completely different placements available.

So a function from values to moves cannot exist, because 128 values would have to name a move on each of 4,269 boards. Where the value does help is one step back: it tells the player which component is worth playing in, and once the component is chosen the move inside it is found by looking at the board.

That two-stage shape is what a player actually does, and it is why both counts matter. The value is the index and the board is the entry.

The forced moves, which are the pleasant surprise #

Two thousand two hundred and fourteen turns have exactly one placement, and it is worth pausing on how large that is: a quarter of all turns in the sweep, and more than half of every turn in the four- and five-square positions.

A forced move needs no theory, no value and no memory — the player looks at the board and plays the only thing available. So a great deal of what looks like skill in a Domineering endgame is not skill at all, and a great deal of what a strategy table would contain, if it were built naively, is entries recording that the player must do the only thing they can do.

Add the 1,518 free turns to them and 44 per cent of the sweep needs nothing stored: either there is one move, or every move is as good. The genuinely demanding part is the other 39 per cent, and the remaining 17 per cent is positions where the player has no move at all — which, in normal play, is the position that has already decided the game.

That split is the honest reason a player can do well with rules of thumb. Most turns are not decisions; the decisions are concentrated in the large positions; and the count of dominoes each side can still place is a reading that gets a great many of them right without any value being computed at all.

What a solver does instead #

A machine has the same problem in a different currency, and the answer it reaches for is a table.

A position reached eleven ways is one position is where a transposition table is established here: keying a search on the position rather than on the path collapses a tree into a graph, and the collapse is worth an order of magnitude. This page is the same measurement one level up. A solver keying its table on the value would have 128 entries instead of 4,269 — but it could not use them to move, for the reason above, so what it stores is positions and what it computes is values.

The interesting consequence is that the two tables have different lifetimes. A table of values is good for ever and for every board: a region worth $1\ast$ is worth $1\ast$ in every game anybody plays. A table of moves is good for the regions it was built for, and every new shape needs its own lines. That asymmetry is the practical reason value theory is worth having, and it is not visible from either count alone.

Who counted this before #

Nobody has counted it for Domineering, and the reason is worth a paragraph, because the question is not obscure.

The strategy of a game is a well-studied object in the branch of the subject that measures things — the strategy complexity of a game asks how large a machine has to be to play it, and the answers are usually stated as bounds rather than measured. What is unusual here is that this site has both halves in the same place: a solver that computes exact values, and a catalogue small enough to enumerate every position in it. The two counts are then a subtraction rather than a theorem.

The idea being measured is much older than the vocabulary. Bouton’s 1902 solution of Nim is the canonical case of a value that does name a move — the binary condition says not only who wins but which counter to remove — and it is the reason players expect a theory to hand them moves. Partizan values do not do that, and Conway’s construction never claimed they would: it is a theory of what positions are worth in sums, and the move is a separate question that this ladder exists to keep separate.

The number this page produces is a way of saying how separate. Twenty-six lines of table for every number the theory supplies is not a criticism of the theory; it is a measurement of a division of labour.

A strategy table is not a strategy either #

The 3,308 lines are the size of one particular object, and it is worth saying which one, because two other things are also called a strategy and are much smaller.

A table of choices is what is counted here: for every reachable position, which move to make. It is complete, it answers instantly, and its size is the number of positions a player might face.

A rule is what a person actually carries — three sentences about the geometry, applied in order — and its size is the sentences. The rung above shows that a rule of that kind answers 94.5 per cent of this table, so the two objects differ in size by three orders of magnitude while agreeing on nearly everything.

And a proof that a strategy exists is smaller than both and useless at the board. Hex is solved by a strategy-stealing argument that names no move whatever, and that is a complete answer to who wins and no answer at all to what to play.

So a count of 3,308 is a measurement of the exhaustive form and not of the difficulty. It is the right thing to measure — it is what the value fails to supply, stated exactly — and it would be a mistake to read it as the amount a player has to know. The right reading is that the value supplies none of it, that a lookup table supplies all of it at that size, and that the question of how much of the table compresses into rules is a separate one with a much happier answer.

That three-way split is the same one the certificate essay makes for proofs: a tree, a table and an invariant are three sizes of the same claim, and quoting one where another is meant is the standing way to make this subject sound either harder or easier than it is.

What this does not say #

Four limits.

A best move is one that maximises what its player keeps — the right stop of the position left over, for Left. That is the rung below’s definition, adopted here so the two censuses are comparable, and it is not the only reasonable one: a move that preserves the outcome class but not the stop is not counted as best here, and a strategy that only had to win rather than to keep the value would be smaller than 3,308 lines.

The bookkeeping is measured over a catalogue, not over a game. A real Domineering board is a sum of regions, and a strategy for it needs the region choice as well as the square. Those are the two stages named above and only the second is counted here, so 3,308 is a floor on what a player has to know rather than the whole of it.

Eight squares. The population grows very fast with the size of the region, and the decision share is still climbing at the top of this sweep. Nothing here extrapolates: what happens at twelve squares is a different measurement and a much larger one.

And the counts are of distinct positions, not of memory. A person does not store 3,308 lines; a person stores patterns that generate them, which is what a good player’s intuition is. The measurement says how much a rule of thumb has to compress, not how hard the compression is.

The convention, named #

Normal play, Domineering, with Left placing vertically and Right horizontally.

A position is a set of free squares up to translation, so the same shape in two places is one position; positions are counted once across the whole catalogue for the same reason. A position may be disconnected, since play breaks a region up, and its value is then the sum of its components’ values.

A turn is a position with a player to move in it. A decision is a turn at which the player has at least two placements and at least one of them is not a best move; a free turn is one where every placement is a best move. The two are kept apart deliberately, because a strategy that stored an answer for both would be counting the turns where it does not matter what it says.

There is a last count worth stating plainly, because it is the one a reader will remember. The theory of this game is 128 numbers and the practice of it is 3,308 lines. Both are small; what is large is the ratio, and the ratio is the price of turning a prediction into a move. It is also the reason a strong player of a partizan game looks like somebody who has memorised a great deal rather than somebody who has understood one thing: the understanding is the 128 and the memorising is the rest.

Where the ladder goes next #

The tempo anchor has three rungs to here: what a value leaves out, how many moves achieve it, and now how large the table of choices actually is.

The rung above compresses that table, and it compresses most of it. Three rules and a tie-break applies three geometric rules in order — leave the opponent fewest replies, then keep the region whole, then take whichever placement comes first — and answers 94.5 per cent of the 3,308 lines. The fourth and fifth rules anybody would add answer not one more.

So the strategy this page prices at 3,308 entries is very nearly three sentences, which is a much better outcome than the count suggests and is worth knowing before anybody builds the table. What is left is 181 decisions where every rule scores the candidates alike and one of them is worse.

Seventy-two of them were not silence then takes those 181 apart, and the first thing it finds is that they are not one thing. Seventy-two of them are the rules speaking and being wrong, which is a different failure from falling silent and a worse one — a rule that declines can be backed up by a search, and a rule that answers confidently and wrongly cannot.

On the 109 that really are silence, a rule chosen per value answers more than half, and the star class this page singles out is settled outright by a rule nobody would have guessed: leave the younger position. Which says the residue is not one hard case but several small ones, each with its own answer, and the reason three rules stall at 94.5 per cent is that the last 5.5 is a handful of unrelated situations rather than a single missing idea.