Eleven moves and one decision

The prefix a game is read as has one quantifier a turn. The earlier essay spends itself arguing that the arrangement of those quantifiers is what a claim costs, and leaves the count of them alone: eleven moves, eleven quantifiers, eleven alternations.

The count is generous. A quantifier is a choice, and a great many turns in a real game are not choices at all.

Four kinds of turn #

The classification is exhaustive and each kind is settled by looking at the position rather than by judging it.

No move at all. Under normal play the player who cannot move has lost, so the position is decided by the convention and nobody chooses anything. A third of a Domineering board’s turns are of this kind — 94 of 493 on three rows by four — because the two players run out at different times and every line ends with somebody stuck.

Exactly one move. The turn happens, the position changes, and no choice was made. This is where the count goes most badly wrong: a Toads and Frogs strip spends 26 of its 34 turns with one move available. A quantifier over a single value is not a quantifier.

Several moves, one verdict. The player chooses and it does not matter which; every option leads to a position with the same answer. This is the subtle kind, because a turn of this sort looks exactly like a decision from inside the position and is not one from outside it. Clobber on a two-by-three board has fifty-four such turns.

Several moves, two verdicts. Some options win and some lose. This is the only kind at which alternation does anything, and it is the only kind at which the phrase the opponent chooses means what it says.

The four kinds partition the turns exactly, which is what makes the shares comparable between games of very different sizes. A game’s turns are 493 or 34 or 1,584; what is being compared is the share of them in the last column, and that share runs from nought to four in five across seven positions of four games.

Two games that never decide #

Two of the positions swept have a count of nought in the last column, and they are not degenerate.

Clobber on a two-by-three board with alternating pieces has 114 turns and none of them decides. Twenty-eight are the end of a line, thirty-two have a single move, and the remaining fifty-four offer a choice whose branches all agree. A player on that board can play anything at all and never lose a game they were winning.

That is not the same as the board being trivial. It has four-move lines and forty-four positions the mover wins; it is a genuine game with a genuine answer. What it does not have is a moment where the answer is in the balance. The verdict is settled by the shape of the position rather than by the play, which is a statement about a parity rather than about a search — the same shape as a strategy that is a symmetry, arrived at by counting rather than by exhibiting the pairing.

The Toads and Frogs strip is the sharper case, because it is long. Eleven moves in its deepest line, and twenty-six of its thirty-four turns have exactly one move. The players shuffle; the strip fills; almost nothing is ever chosen. A prefix read off its length has eleven quantifiers in it and the position holds two.

The reason is the ruleset rather than the size. A toad moves right into a gap or jumps a frog into a gap beyond, and a strip of six cells with four pieces on it rarely offers two of those at once. Compare the same game on a strip where the pieces are interleaved, which offers considerably more.

Seven times the deciding turns on a strip of the same length with the same number of pieces. What changed is the arrangement, and the arrangement is what decides how often two moves are available at once.

Nim decides nearly always #

The opposite end is the game most often described as easy.

Nim on heaps of 3, 4 and 5 has 48 turns and 39 of them decide. Its longest line is twelve moves and eleven of those twelve are deciding turns. There is almost nowhere in a Nim position where a player can move carelessly.

This is worth holding beside the usual description of the game. Nim is easy in the sense that a formula answers it — three exclusive-ors settle any position at any size, and the answer arrives without a search. It is not easy in the sense of being forgiving. A Nim position hands its mover a dozen options, one or two of which are right, and it does that again on the next turn and the one after.

So the two senses of easy pull apart completely, and this measurement is where they separate. A game can be solved by a theorem and still be a game in which every turn is a decision; a game can have no theorem and hardly any decisions at all. The Sprague–Grundy apparatus removes the search from Nim and leaves the alternation exactly where it was.

The middle column is the one nobody expects #

The forced turns are easy to accept once they are pointed at: a player with one move has not chosen. The third column is harder, and it is the larger of the two on five of the seven positions.

A turn with several moves whose branches all agree is a turn at which a player can do anything. From inside the position it is indistinguishable from a real decision — the options differ, the resulting boards differ, the play afterwards differs. What does not differ is the answer. Domineering on three rows by four has 163 such turns against 136 deciding ones, so more of its choices are free than are binding.

That is where the intuition behind a game asks alternately does most of its overreaching. The alternation is a fact about the rules and the deciding turns are a fact about the answers, and the second is a subset of the first that can be as small as empty. Nothing about a ruleset predicts it: Clobber on two rows of three and Clobber on three rows of three share every rule and differ from nought to a fifth.

It is also the column that shrinks fastest with size. Three rows of three Domineering has twenty settled turns of ninety-two, a fifth; three by four has 163 of 493, a third. More room means more moves at a turn, and more moves at a turn means more of them agreeing.

The depth, which is the number a prefix would use #

Counting turns over every position is one reading. The other is to follow a single line, because that is what a prefix is: a sequence of turns, one after another.

Nim’s twelve-move line holds eleven deciding turns; its fifteen-move line on three heaps of five holds fourteen. Domineering’s five-move line on three rows by four holds three. Toads and Frogs runs eleven moves and decides at one. Clobber runs four and decides at none.

Those are the numbers a prefix ought to be built from, and the spread between them and the move counts is between a factor of one and a factor of eleven. A claim about a Nim position genuinely needs a prefix as long as the game; a claim about a Toads and Frogs strip needs a prefix of one alternation and a great deal of bookkeeping that is not alternation at all.

What the count is measuring instead of difficulty #

It is worth naming what the deciding share is a measure of, because the obvious reading — that a game with few deciding turns is an easy game — is not what the numbers say.

Take the two extremes together. Clobber on two rows of three decides nowhere and is settled by a parity somebody could state in a sentence. Nim on heaps of 3, 4 and 5 decides nearly everywhere and is settled by a formula somebody can state in a sentence. Both are as solved as a game gets, and their deciding shares are nought and four-fifths. Meanwhile Domineering on three rows by four sits at 28% and has no formula at all — its family is complete for the hardest class this subject reaches.

So the deciding share does not order the games by difficulty and does not pretend to. What it measures is how much of the answer is carried by the play rather than by the position. A game with no deciding turns has its answer written into the starting position, and the moves merely spend it; a game that decides at four turns in five has an answer that is manufactured, move by move, and can be thrown away at almost any point.

That is a property a player feels and a complexity class cannot see. It is also the property the forgiving games and the unforgiving ones differ in, which is why a search cut short does so much better on some boards than on others: a cut search guesses, and a guess costs nothing at a turn where every branch agrees.

Why a settled choice is still expensive #

One caution belongs here, because the natural next thought is wrong and it is wrong in a way that matters.

A turn whose options all agree is not a turn a solver gets to skip. The solver does not know the options agree until it has evaluated them, and evaluating them is the whole cost. The saving would be available only to something that knew the answer in advance, which is the thing being computed.

So the two accountings genuinely differ. The alternation of a position is a property of the answers; the cost of finding the answers is a property of the tree. The Clobber board with no deciding turn still has 114 turns to walk, and the tree and the graph prices exactly that walk. What the measurement above establishes is about the certificate rather than about the search: a claim about that Clobber board needs no strategy worth the name, because there is no line on which the choice had to be right.

And that is the connection back to the earlier essay. A strategy’s size is $2^k$ summed over the chooser’s decisions, with $k$ counting the opponent’s turns before each. If the opponent’s turn had one move, it contributes no doubling — one line rather than two. The deciding depth is therefore the exponent the strategy actually has, and the move count is an upper bound on it that can be eleven times too large.

There is one further reading of the same pair of numbers, and it is the reason the depth is reported rather than only the share. A game whose deciding turns are scattered — one here, one there, with long stretches of forced play between — has a short deciding depth however many deciding turns it holds in total, because a prefix cares about what follows what. A game whose deciding turns are consecutive has a deciding depth equal to its count. Nim is the second kind: thirty-nine deciding turns and a run of eleven, so nearly every deciding turn lies on one line. Domineering is the first: 136 deciding turns and a run of three.

That distinction is exactly the one the earlier essay measures on constructed prefixes, arriving here from a board instead. Turns that alternate in a run are expensive; the same number of turns scattered among forced ones is not, because each doubling applies only to what comes after it.

The convention this counts under #

Everything above is normal play: the player who cannot move loses, and a turn with no move is that player’s loss rather than a pass. Under the misère convention the same positions are reclassified — a turn with no move becomes a win — and the deciding turns move with them, because which options agree depends on what the answers are.

Two conventions of the sweep itself are worth naming.

A turn is a position-and-side pair, and the pair is counted once. A position reachable with either player to move contributes two turns, and a position reachable twice with the same player to move contributes one. That is the right unit for a question about turns and it is not the right unit for a question about lines, which is why the depth reading is a separate figure computed a different way.

Impartial games contribute one turn per position rather than two, because both players have the same moves and the same answer, so a second entry would be a duplicate. Nim’s 48 turns over 48 positions and Domineering’s 493 turns over fewer positions are counted on the same rule applied to different games, and the shares are comparable because the classification is inside each game rather than between them.

What the picture cannot say #

It says nothing about how often a player meets each kind. The sweep weights every position of the game equally, and a player meets the opening far more often than any particular endgame. A game whose deciding turns are all in its first two moves and one whose deciding turns are all in its last two have the same number here and are nothing alike to play.

A settled choice can be settled for very different reasons. Two options agreeing because the position is hopeless and two options agreeing because both win are the same entry in the table. That distinction would need the verdict alongside the count, and it is not drawn.

And a count of nought is a count over a stated board. Clobber on two rows of three decides nowhere; on three rows of three it has 324 deciding turns of 1,584. The finding is about the position and not about the game, which is the same caution hardness is about a family and an encoding makes from the other direction — there a family is hard and its members are not, and here a game is deciding and one of its boards is not.

One board that has it both ways #

The Domineering board of three rows by four is worth a paragraph on its own, because it is the only position swept where all four kinds of turn are well represented and none dominates.

The split is nearly even in fifths and it changes character down the game. The early turns are wide and settled: eight moves at the first turn on an empty board, and at that point almost anything is playable because the board has room to absorb a bad choice. The late turns are narrow and forced: one move, or none, and the game finishing itself. The deciding turns cluster in the middle, which is where the run of three comes from.

That shape — free at the start, decided in the middle, forced at the end — is what a player would describe as a game having an endgame, and it is being read off a census of turns rather than off anybody’s account of how the game feels. The two positions with no deciding turns at all are the boards too small to have a middle.

Still open: whether the forced turns can be removed #

The obvious response to twenty-six forced turns is that they should not be turns at all — that the game with the forced moves collapsed is the same game, shorter, and the honest prefix is the one that counts only the choices.

It is not obvious that the collapse is legitimate and nothing here settles it. A forced move changes the position, and the position after it is what the opponent chooses from; collapsing a run of forced moves into the choice that follows changes whose turn the choice is, which is exactly the quantity the prefix is made of. A run of forced moves of odd length hands the next choice to the other player, and a run of even length does not.

So the measurement that would settle it is a parity: over every line of these games, how long the runs of forced moves are and whether their lengths are odd. If they are, a collapsed prefix is a different prefix rather than a shorter one, and the twenty-six forced turns are load-bearing after all.