Counting at the end changes everything

Every value on this site rests on one sentence: the player who cannot move loses. Sums, comparison, temperature and the whole vocabulary of infinitesimals are consequences of it, and none of them survives its removal.

Go does not work that way. A game of Go ends when both players pass, and the winner is whoever has more territory. Dots and Boxes counts boxes. Chess has a goal. Almost every game anybody plays for stakes ends with a number rather than with somebody stuck.

This essay is about how much of the theory that costs, measured on the simplest scoring game there is.

The simplest scoring game #

A row of coins. Each player in turn takes the coin at one end and keeps it. When the row is gone, the higher total wins.

That is the whole game. It is entirely about the numbers, and the normal-play theory has nothing to say about the numbers at all.

Run that over every four-coin row with coins from one to three — all eighty-one of them — and the normal-play column takes exactly one value while the scoring column takes two. The theory this site is built on returns a constant, and the constant is a correct answer to a question nobody is asking.

That is the cost, stated as sharply as it can be. Not that the theory gives approximate answers, or answers with caveats, but that it gives the same answer to every position of the family. And it is not a coincidence of four-coin rows: the same count at every length from two to six says the same thing.

There are only four normal-play outcome classes to begin with, and this whole family lives in one of them per parity. A class says who moves last. What a scoring game asks is by how much, and there is no class for that — which is why the column has a one in it rather than a small number.

The real games #

The coin row is a laboratory. The games in this field are not.

Dots and Boxes is the one to hold up beside the coin row, because its whole difficulty is that it keeps score and its skeleton is not degenerate. Throw the boxes away and what is left is Nimstring, a normal-play game with a real recursion in it, and the question becomes empirical: how much of the scoring answer does that skeleton still carry?

That is the best case: a scoring game whose skeleton is informative. The coin row is the worst case, where the skeleton is a constant. Real games sit between the two, and where a particular one sits is an empirical question rather than a theoretical one.

The reason Nimstring’s skeleton is informative is worth naming, because it is the general condition. In Dots and Boxes the score and the last move are coupled: a player who takes boxes must move again, so taking is what surrenders the move, and the two quantities are two readings of one exchange. The chains decide it before the boxes do is that coupling stated as a rule of play. Where a scoring game has no such coupling — the coin row has none, since taking a coin passes the turn whatever the coin is worth — the skeleton has nothing to be informative about.

What Milnor and Hanner built #

The theory of scoring games is older than the theory this site is mostly about. John Milnor’s Sums of positional games appeared in 1953 and Olof Hanner’s Mean play of sums of positional games in 1959, and both were written with Go in mind — fifteen and nine years before Conway’s construction.

What they proved is that a scoring game has a mean value, and that the score of many copies of it stays close to that mean.

That is the same statement many copies of one game makes about normal-play games and their temperature, arrived at first and for a different kind of object: a hot position copied n times tracks n means with an error bounded by its temperature. The mean is the long-run rate; the temperature is the bound on the error term; and the error does not accumulate however many copies are added.

Which half of that pair is doing the work is worth noticing. The mean is the interesting quantity and the bounded error is what makes it a rate rather than an average — a mean with an unbounded error would say nothing about any particular sum — and both theories spend most of their effort on the bound rather than on the mean.

The hypothesis, and what happens without it #

Milnor’s theory has a condition attached and the condition is the point of this section.

There must be a non-negative incentive to move. Formally: the score with Left to move is never worse for Left than the score with Right to move. Informally: nobody would rather pass.

Under that condition the mean and the temperature behave, and the score of a sum is within the sum of the temperatures of the sum of the means. Without it, the bound breaks.

Three hundred violations, none of them where the hypothesis holds. That is the shape a load-bearing condition has, and it is the reason to run the experiment twice: a bound nothing has ever broken is a bound nobody needs.

That assumption is exactly what a modern reader should notice. Go endgames mostly satisfy it — playing a point is usually worth something — and Dots and Boxes emphatically does not, because the whole subject of that game is the move a player makes in order not to have to move again.

What survived into the theory this site uses #

The connection between the two theories is a genuine inheritance rather than a resemblance.

Milnor and Hanner’s mean value is the ancestor of the temperature this site’s whole fourth field is about. The construction is different — a thermograph is built from the game recursion rather than from repeated copies — and the quantities it produces are the same shape: a mean, which says what the position is worth, and a temperature, which says how much is at stake and bounds the error in the mean.

The object the mean-value idea turned into is the thermograph, whose mast is the mean and whose width at the bottom is what is at stake — both read off a construction with no scores in it anywhere, the score having been replaced by the last-move convention along the way. A hot position in that reading is a position both players want to move in, with a mean and a spread, and Milnor’s positional games are the same idea about points on a Go board. The two theories converged because both are answers to how much is this worth, and how urgent is it.

So the honest summary is not that the normal-play theory fails on scoring games. It is that the two are different theories about the same intuition, one of which turned out to be far more general and lost the ability to count.

Two consequences of the older theory carried over intact and are worth naming, because they are the parts a Go player would recognise. Means add and temperatures do not — the mean of a sum is the sum of the means, while the temperature of a sum is bounded by the hottest part rather than by the total, which is exactly what the modern theory says. And the hottest part is the part to move in, which is Milnor’s advice about Go points and the modern rule written twice.

The parity answer, in full #

It is worth being exact about what the normal-play skeleton of the coin row says, because “it says nothing” is a strong claim and this one is literally true.

Take a row of n coins and throw the numbers away. A move takes an end coin; there is always an end coin until the row is empty; so the game lasts exactly n moves whatever anybody does. The last move belongs to the first player when n is odd and to the second when n is even.

That is the complete normal-play analysis of the family. It is a theorem, it is correct, and it depends on nothing but the length. Two rows of the same length are equal as normal-play games — not merely equal in value, but the same game, with the same value 0 or ∗ according to parity — while their scores can differ by any amount whatever.

This is a much stronger failure than the one a reader might expect. The usual worry about a simplified model is that it loses precision. Here the model is exact and loses the question: it computes a correct answer to who moves last, and who moves last is not a fact anybody in this game cares about.

The Dots and Boxes case is the instructive contrast because its skeleton is not degenerate. Nimstring is a real game with real structure, its answers vary from position to position, and it turns out to predict the scoring answer nine times in ten. So the loss when the score is discarded runs from total to slight, and which end of the range a game sits at is not something the theory can be asked.

The parity is not useless, it is in the wrong place #

There is a twist here that turns the essay’s headline half over, and it is the most useful thing the coin row has to say.

The parity gives no value, as the previous section says at length. It does give a strategy, and the strategy decides the score.

Number the squares from one. In a row of even length the two ends carry different parities: square one is odd and square $n$ is even. So the first player may choose a parity class — the odd squares or the even ones — and take an end coin from it. And having taken one, the two ends of what is left carry the same parity as each other, so whichever of them the opponent takes, an end of the chosen class is exposed again.

By induction the first player takes the whole of whichever class they picked. So the first player can guarantee

$$\max\left(\textstyle\sum \text{odd squares},\; \sum \text{even squares}\right),$$

which is at least half the row, so the first player of an even-length coin row never loses. No search is involved: two additions and a comparison, on a row of any length whatever.

Run it against the exact solver over every row of length two, four and six with coins from one to three — 819 rows — and the guarantee is never broken. What is more surprising is how little is left on the table: on 761 of the 819 the exact answer is the bound exactly, so on nine rows in ten the two additions are not merely safe but optimal.

The three rows of the hero figure are the argument in miniature. In $1\,2\,3\,4$ the even squares hold $2 + 4 = 6$ of the ten points; in $1\,9\,1\,9$ they hold $18$ of the twenty; in $3\,1\,1\,3$ the two classes tie at four each and the game is drawn. Every one of those is what the solver returns.

Why it needs the length to be even #

The parity is doing real work here rather than decorating the result, and the way to see that is to take it away.

In a row of odd length both ends are odd-numbered — square one and square $n$ with $n$ odd — so the first move cannot choose a class, and the argument fails at its first step rather than degrading. It is not that the bound gets weaker; there is no bound. Over every row of length three and five with the same coins, 270 of them, the first player actually loses on 25.

That is what makes this more than a puzzle solution. The skeleton computes exactly one thing about a coin row — the parity of its length — and the parity of its length is exactly the hypothesis the strategy needs. The normal-play analysis is not returning a useless constant; it is returning a constant that is useless as a value and load-bearing as a condition.

So the loss when the score is discarded is narrower than “everything”. What goes is the ability to say by how much. What survives is a fact about the shape of the game that turns out to be the precondition for the best cheap strategy anybody has for it — and a reader who knew only the parity, and nothing about the coins, would still know which player to be.

None of that rescues the general claim. On a row of odd length the theory says who moves last and there is nothing to be done with it; on Dots and Boxes the skeleton says something substantive for a different reason entirely. What the coin row shows is that a degenerate answer can still carry a hypothesis, which is worth knowing before dismissing one.

Where the loss is #

The specific thing that goes when the score goes is the group structure.

In normal play, positions form an additive group: every game has a negative, sums compose, and comparison is subtraction. That is what makes the whole apparatus work and it is a consequence of the last-move convention — the negative of a game is the game with the players swapped, and adding it gives a position the second player wins.

Scoring games do not form a group in the same way. A scoring game plus its mirror image is a position with a score rather than a zero, and the score depends on the game. So the operation that makes comparison a subtraction is unavailable, and comparison becomes the harder question it is in every theory that lacks it.

Milnor’s restriction to games with non-negative incentive is precisely a restriction to a class where enough of the structure survives — and the class is a subset, chosen so that the arithmetic works, rather than the whole of what people play.

Two directions of generality #

There is a way of reading the two theories that makes the trade explicit, and it is worth stating because “which is better” is the wrong question.

Normal play is more general in the games it covers. Any finite game with no chance and no hidden information, ending when somebody is stuck, has a value in Conway’s theory. That is an enormous class, and the theory has a group, a canonical form, a comparison and a complete arithmetic.

Scoring is more general in the questions it answers. A score is a number and an outcome class is one of four labels, so a scoring theory answers by how much as well as who — and by how much is what a player of a real game wants.

Neither generality contains the other, which is why both theories exist and why the older one did not simply become a special case. What Conway’s construction bought was the arithmetic; what it cost was the number at the end.

And there is one further asymmetry. A normal-play game can always be turned into a scoring game — count moves made, say — while a scoring game cannot generally be turned into a normal-play one without losing the score. So the translation runs one way, which is the usual sign that one of the two is the more primitive object. The primitive one, in this case, is the one with the score.

What the picture cannot show #

The rows above are four coins long and the sums are two rows at a time.

What that hides is how fast the state space grows. A sum of n rows of four has interval states in each row and a turn flag, so eight copies of a four-coin row is already tens of thousands of positions and twelve would be past what belongs in a page build. Every figure here is at the small end of an exponential, as usual.

The other thing not shown is the passing move. Real scoring games let a player pass — Go’s entire ending mechanism is two consecutive passes — and the coin row does not. Passing is what makes the incentive condition matter, because a player who would rather pass and cannot is a player in zugzwang, and a game that permits passing has no zugzwang at all. That is a substantive difference between the model here and Go, and it cuts in the direction of making the model harder than the real thing rather than easier.

The convention, named #

Everything in this essay is about the difference between two conventions, so naming them is the whole job.

Normal play: the player who cannot move loses. Used by every other field on this site, and by Kōnane, Nim, Hackenbush, Domineering and the switching game.

Scoring: the game ends by agreement or exhaustion and the higher total wins. Used by Go, Dots and Boxes and the coin row.

The third convention, misère play, is a different departure again and breaks different things. What is worth holding onto is that these are not variations on a theme: each one determines which theorems exist, and the theory that got built first and furthest is the one whose convention makes positions into a group.

Where the ladder goes next #

scoring opens here, and the rungs above it are both substantial.

The first is Go’s own endgame accounting, which is a scoring theory that predates the modern one, works in practice, and can be measured against it — and which this site has already touched from the temperature side in the first time it told somebody something.

The second is the modern theory of scoring games, which is a live subject rather than a historical one: guaranteed scoring games, well-tempered scoring games, and the several attempts since 2010 to recover a group structure by restricting the class. That is a rung about what it costs to get the arithmetic back.