A turn is not a bit

Every reading in these essays so far has taken one turn to be one quantifier. It is the identification the whole thing rests on — read the prefix left to right and it is the order of play — and it is exact for the formulas the reduction builds, where a variable is a bit and a turn sets it.

A board is not like that. A turn offers however many moves the position has, and a choice among eight is not a choice among two. So a board’s prefix is longer than its game, and the first job is to find out by how much.

Twelve moves and twenty-four bits #

Nim on heaps of 3, 4 and 5 runs twelve moves and carries 23.57 bits of choice between them. The first turn offers all twelve moves there are; the second offers 9.42 on average over the positions reachable; by the eleventh there is roughly one move left and the game finishes itself.

So the prefix that board is equivalent to has about twenty-four quantifiers in it rather than twelve, and the arithmetic of the earlier essay prices a twenty-four-quantifier alternating prefix at 4,095 decisions where a twelve-quantifier one costs 63. Sixty-five times more, from nothing but noticing that a Nim turn is a choice among a dozen things.

The profile is the interesting part, not the total. The bits are front-loaded: the first three turns hold 10.6 of the 23.6, and the last five hold under three between them. A Nim game is almost entirely decided at the top, in the sense of choice available, and a prefix that charged every turn equally would be charging for an endgame that has nothing in it.

And eleven moves worth two bits #

The other extreme is the strip that has already appeared twice in these essays.

Two toads, two gaps, two frogs: eleven moves in the longest line and two bits in total. Seven of its twelve plies have a mean branching of exactly one, which is the census of forced turns in another notation — twenty-six of its thirty-four turns offer a single move.

A prefix read off the length has eleven quantifiers. A prefix read off the branching has two. The two readings differ by a factor of five and a half on one strip, and they differ by a factor of two in the other direction on Nim. Nothing about a ruleset predicts which.

The Domineering profile, which is the well-behaved one #

Between those two extremes sits a board where the bits and the turns very nearly agree.

Three rows by four gives 9.04 bits over six plies: 1.5 quantifiers a turn. The decline is smooth and the profile has no surprises in it — eight, six, 3.75, 2.23, 0.73, nothing — because a Domineering move covers two squares of twelve and the board shrinks by the same amount every time whoever plays it.

That regularity is what makes this the one family where the naive reading is nearly right, and it is worth naming the property rather than the game. A game whose every move removes the same amount of the position has a branching that falls predictably and lines that all end at the same depth, which is exactly the two assumptions the model makes. Nim breaks the first — a move can take one counter or five — and Toads and Frogs breaks the second, because its pieces can block each other into positions with nothing to do.

So the model is not merely an approximation with an error bar. It is a model of a particular kind of game, and it happens to be the kind the board games mostly are and its counter games mostly are not.

The prediction, and both ways it fails #

There is now a model with every part of it defensible: a turn is log₂ of its branching in quantifiers; the quantifiers alternate, because the players do; and a winning strategy costs $2^k$ summed over the chooser’s turns.

Its prediction is checkable against a strategy computed on the board.

It is 539 times too high on three heaps of five. The model predicts 131,071 decisions and the strategy needs 243.

It is 67 times too low on the Toads and Frogs strip. The model predicts one decision and the strategy needs 67.

A model wrong in one direction is a model missing a constant, and this one is not that. It is wrong in both directions on eight positions of four games, and the sizes of the misses are not related to each other.

Why it is too high #

The model runs every line to the full depth at the mean width. A real game’s lines do not all reach the bottom, and on Nim most of them do not come close.

Three heaps of five has a longest line of fifteen moves. It also has lines of one — take everything from one heap, then the other two, and the game is over in three — and the proportion of short lines is enormous. A prefix of thirty-two bits charges for thirty-two alternations on every line there is; the strategy pays for them only on the lines that go that far, and the branches that end early cost it nothing at all.

That is the same distinction the tree and the graph is about, arriving from a different side. There the trouble is that a tree counts a position once per route; here it is that a uniform depth counts a route once per possible length. Both replace a distribution by its maximum and both overcharge by orders of magnitude.

The correction is not a constant, because how much a game’s lines vary is a property of the game. Domineering’s lines are all nearly the same length — a board of twelve squares takes six dominoes or fewer, and every line ends within one move of every other — so the model misses by a factor of between 1.7 and 3.0 there. Nim’s vary from one move to fifteen, and it misses by 539.

Why it is too low #

The other failure is the mirror of the third essay and is more interesting, because it is not an approximation going wrong. It is a unit mismatch.

A quantifier over one value costs the model nothing: $\log_2 1 = 0$, so a forced turn contributes no bits and no decisions. A forced move is still a move, and a strategy has to contain it — the strategy is a plan for playing the game, and a plan that omitted the forced moves would not be a plan.

So on a strip where twenty-six of thirty-four turns are forced, the model charges for nothing and the strategy holds sixty-seven decisions, nearly all of them moves that could not have been anything else. The model is measuring the information in a strategy and the strategy is being measured by its length, and those two quantities come apart exactly where a game is forced.

Both measurements are right and they are measurements of different objects. A strategy compressed — written as the choices that had to be made, with the forced moves reconstructed — really is about two decisions long on that strip. A strategy written out, move by move, is sixty-seven. Which one is the honest size depends on whether the reader of the strategy is assumed able to work out the forced moves, and that is a convention rather than a fact.

The two failures are not the same size on the same games #

The pattern in the misses is worth reading off, because it splits the four families cleanly.

The two Nim rows are too high by 13.7 and 539. The three Domineering rows are too high by 3.0, 2.3 and 1.7, which is the residue of the same cause on a family whose lines barely vary. The two Toads rows are too low by 67 and 40. The Clobber row is too low by 2.4.

So the direction of the miss is a property of the family and not of the board, and the size of the miss grows with the board in both directions — 13.7 to 539 going up on Nim, and 40 to 67 going down on Toads and Frogs as the strip gains choices. Neither failure washes out at scale, which is the answer to the obvious hope that a small board is what makes a model of asymptotics look bad.

It also says which correction matters where. A game with uniform move sizes needs the forced-turn correction and not the line-length one; a game with uneven move sizes needs the reverse. Nothing here needs both badly at once, which is luck rather than a finding, and a game that did — uneven moves and long forced runs — would be the one to try next.

What survives #

The model fails and the unit it introduced does not. Three things are left standing.

A turn is worth log₂ of its branching, and that number is not one. Every prefix in these essays before this essay was too short by that factor, and the factor runs from 0.17 to 1.96 bits a turn across these six positions — an elevenfold spread between games.

The bits are not spread evenly over the game. Every profile here falls: widest at the opening, narrowest at the end, with the last two or three plies contributing almost nothing. That shape is the reason the total is a poor summary and the reason a search cut short does so well near the leaves — there is very little choice down there to get wrong.

And the two failures are separable. Correcting for varying line length would fix the Nim rows and leave the Toads rows exactly as wrong; counting forced moves would fix the Toads rows and leave the Nim rows exactly as wrong. A model that did both is available and is not attempted here, because at that point it is a description of the game tree rather than a prefix, and the whole value of a prefix is that it is shorter than the thing it describes.

What this does to the three readings before it #

Three readings in these essays quoted a prefix length and each of them has to be re-read.

A claim over twelve turns prices three arrangements at 6, 63 and 384 decisions. Those are the right numbers for a formula over twelve variables and they are the wrong numbers for a game of twelve moves, which is between two and twenty-four bits depending on the game. The ratios between the three arrangements survive, because they depend on the arrangement and not on the length; the absolute sizes do not.

The census of deciding turns counts a turn as one turn whether it offers two moves or twelve, which for its purpose is right — it is asking whether the choice changes the answer, and a choice among twelve that changes nothing is as empty as a choice among two. But its shares are not directly comparable between games with very different branchings, and the Nim figure of four deciding turns in five reads differently once each of those turns is known to be a choice among a dozen.

The cost of proving a loss already carries this correction, because it measures over the position graph rather than over a prefix — which is why its ratios are small constants where every prefix estimate here is out by orders of magnitude. A proof sized on the actual options is a proof sized correctly, and that is the reason to trust it over anything derived from a length.

What none of that undoes is the identification itself. The prefix and the sequence of turns are the same object; what this essay establishes is only that the exchange rate between them is not one, and that it is a different number for every game.

What a ply is, and what a bit is #

A ply is a turn along a line, and a position is counted once at every ply it can be reached at. That is the right unit for a question about turns and it is not the unit for a question about positions — the same board contributes to several plies if several lengths of play reach it.

The branching at a ply is averaged over the positions reachable at it, not taken along one line and not taken at the worst case. A branching quoted from one game is a number about that game, and the maximum would make every profile a profile of its widest position.

The bits are the mean of the logarithms, not the logarithm of the mean. Those differ, and the first is the right one: a strategy answers each position’s options, so the cost is a sum over positions of what each costs, and the logarithm belongs inside.

And the strategy sized against it is the winner’s decisions, not its nodes. The two differ by a factor of about two on every board here, because a strategy tree holds a node for each player’s move and only one of the players is deciding.

What the picture cannot settle #

Six positions of four games. The elevenfold spread in bits a turn is a statement about these, and the explanation offered for the two failures is a reading rather than a proof.

Nothing here measures the largest board. Every position swept is small enough to solve completely, which is what makes the comparison possible and what makes it unrepresentative: the whole point of a complexity class is behaviour as the board grows, and a board that can be solved is a board whose growth has not begun.

And the prefix a game is equivalent to is not actually built. The reduction runs the other way — from a formula to a graph, as the completeness result does — and nothing on this page constructs a formula from a board. What is measured is the size such a formula would have if it existed with the obvious shape, which is an estimate about an object rather than a measurement of one.

Where the count would matter #

It is worth saying what the bit count is for, since the model built on it has just failed.

A prefix length is the natural way to compare games of different kinds, and the move count is the one everybody reaches for. Chess lasts about eighty moves and Go about two hundred and fifty is a sentence about two numbers that mean different things, because a Go turn is a choice among a few hundred and a chess turn a choice among a few dozen. In bits the two are far closer together than the move counts suggest, and that is the comparison the number is good for.

It is also what a record of a game costs. Writing down a played game means writing which move was chosen at each turn, and that is exactly the sum of the logarithms — the same quantity, arrived at without any quantifiers in it. Nim on heaps of 3, 4 and 5 takes 23.6 bits to record and three heaps take thirty bits to write down at a thousand counters each, so a game of it costs about as much as the position it started from, which is a coincidence of this board and a striking one.

What the number is not good for is predicting a strategy, and the failure above is complete enough to say so plainly. The bits in a game are the information in one line of play; a strategy is a plan for every line, and the step between them is where the whole difficulty of the subject lives.

Still open: the compressed strategy #

The unit mismatch above has a measurement hiding in it that would settle which number is honest.

A strategy can be written out as a move at every turn, or as a decision only where there was one, with the forced moves left to be reconstructed. The first is what the sizes here count and the second is what the bits predict, and the gap between them on these boards is between a factor of one and a factor of sixty-seven.

What has not been checked is whether the reconstruction is cheap. Working out the forced move from a position is finding the unique legal move, which is a scan of the board — so a compressed strategy is genuinely smaller and genuinely slower to use, and how much slower is a number nobody here has produced. If the scan is cheap the compressed size is the honest one and every strategy measured in this collection is inflated by its forced moves; if it is not, the two are different objects and both are worth their sizes.