An environment made of coupons

A position, and beside it a stack of coupons worth 4, 3, 2, 1 and 0. On each turn a player either moves in the position or takes the top coupon and keeps it. When nothing is left to do, each player’s score is the total of the coupons they took plus whatever the position finally settled at.

That is Berlekamp’s idealised environment, and it is not a metaphor for a busy board. It is a game — a disjunctive sum of the position and the stack — played out by exactly the recursion every other position on this site is played out by. Nothing in it is a heuristic: both players play optimally over the whole board, and the line that results is exact.

What makes it worth building is what falls out of the play. Two quantities that are ordinarily computed — the mean value of the position, and its temperature — turn into things a reader can point at in a transcript.

The stack is the measuring instrument, so what it is worth on its own has to be settled first. It is worth its alternating sum, and always: with a top of 4 and a step of 1 the first player takes 4, the second 3, and so on, giving 4 − 3 + 2 − 1 + 0 = 2. Five stacks were solved by full recursion and every one came out at its alternating sum — top 4 step 1/2 gives 2 over nine coupons, top 3 step 1/4 gives 3/2 over thirteen, top 5 step 1/2 gives 5/2 over eleven.

The reason is that a coupon stack is nothing but a set of switches with distinct temperatures, played hottest first — precisely the situation the orthodox endgame account is exact on.

Written as a sum rather than as a stack, the five coupons above are four independent fights and a worthless one: {4 | −4}, {3 | −3}, {2 | −2}, {1 | −1}, each worth nothing on average and each with a different amount at stake. The endgame account adds the means, then the largest stake, minus the next, and so on, which here is 0 + 4 − 3 + 2 − 1 and comes to 2. That is the number the full recursion returns. The account is exact on a board of this shape because every region is a plain fight between two numbers with nothing hidden inside either option — there is no follow-up anywhere for it to be wrong about, and no two regions with the same amount at stake to be taken in the wrong order.

So the environment is the one kind of board the account never gets wrong. That is the whole design: an instrument with no surprises in it, so that any surprise in a reading belongs to the thing being measured.

Measuring a game against it #

With the stack’s own score known, the position’s contribution is a subtraction:

contribution = score(position + stack) − score(stack), both from the same first player, both a complete minimax.

For {4 | 0} beside the five-coupon stack that is 4 − 2 = 2. Its mean value is 2. The two agree exactly, and they agree again when the stack is refined to nine coupons a half apart.

This is the same quantity eight copies of one fight measures by a different route, and the two routes share no arithmetic. There the mean is pinned down by piling the position up and watching the error refuse to grow: six piles of {4 | 0}, each one copy larger, with the value of each set against that many means, and the widest the value ever strays from a whole number of means is 33/16 — reached at one copy and never exceeded. That is one grid step above the temperature 2, and a bound that does not grow with the pile is what makes 2 a mean rather than an average of something.

Here the same 2 arrives as a subtraction between two complete solves, from a construction that never adds a second copy of anything. One route measures how badly a sum of copies can behave; the other measures what a single copy is worth to a board it is sitting on. They agree, and neither was derived from the other.

Fifteen runs of the coupon measurement are on record, across plain switches, positions with fights inside their options, and plain numbers. Nine of the fifteen returned the mean exactly. In the other six the answer was off, and never by more than the coupon step.

What the solver computed, and how #

Everything above is a minimax over the disjunctive sum of the position and the entire stack, played to the end, with no evaluation function anywhere. Three details decide the answers and are worth stating.

The scoring convention. Play is normal play and continues until every component is a number, and the score is the sum of those numbers. That is the same convention the sente sweep uses, and every “takes the coupon” and “plays in the game” in these figures is the move that optimises it.

The tie. When taking the top coupon and moving in the game come out equal, the search takes the first component in its list, and the game is listed before the stack — so a tie reads as playing. That boundary case is not cosmetic: it is exactly why the coupons for a plain switch stop at the temperature rather than one step below it.

The cost. The search is exponential in the height of the stack, so the stack is capped at eighteen coupons and the generator refuses to draw above that. Seventeen coupons take about six seconds on their own and twenty-five exhaust the heap. A top of 4 with a step of 1/8 would be thirty-three coupons and is simply out of reach — which is the practical ceiling on how fine an environment any figure here can use.

The assertion that makes the whole construction a test rather than a demonstration is in the runner: it throws if the contribution ever differs from the mean by more than the coupon step. It is armed on every placement in this essay, and it has never fired.

The grain of the environment #

The coupon step is the one place the model is genuinely approximate, and it is approximate in a way with a stated bound: the error is at most the step.

The bound is honest and it is not the same as a promise of improvement. Halving the step halves what the error may be; it does not halve the error.

Both columns show it. {3 | 0} is out by a half at a step of 1 and out by a half again at a step of a half, before falling to nothing at a quarter. { {5 | {3 | 1}} | 0} is out by a quarter at a step of a half and still out by a quarter at a step of a quarter, where the error has gone from half the bound to the whole of it. So a finer environment is a better guarantee and not reliably a better answer, and the generator enforces the distinction: given a column in which no error ever changed, it refuses to draw.

The coupon they stopped at #

The second measurement is the more interesting one, because it is read off the transcript rather than off a subtraction: at which coupon did the players stop taking coupons and turn to the game?

For a plain switch the answer is the temperature, exactly, at every grain tried. {4 | 0} has temperature 2 and the coupons stop at 2, both with a step of 1 and with a step of a half. {6 | 2}, also temperature 2, stops at 2. {2 | 0}, temperature 1, stops at 1. {3 | 0}, temperature 3/2, stops at 3/2 once the grain is fine enough to have a coupon there. Five runs, five exact agreements, and in each of them the player who broke off to play in the game was Left.

That is the equivalence in its clean form. The temperature is defined by cooling — the tax at which the two walls of the thermograph meet — and it is measured as the size of the alternative a player will finally give up in order to take the fight instead. Nothing in the second description mentions a wall.

The fights that stop too high #

{5 | {4 | 0}} has a temperature of 1. Placed in a stack of nine coupons, the players leave the coupons at 3/2 — and the reason is visible in the line of play.

Two consecutive moves in the same component, in a line where every move is optimal over the whole board, is what “must be answered” looks like when it is played rather than named. The follow-up {4 | 0} has temperature 2, and the exchange was made as soon as the environment fell below 2 — with 3/2 on top of the stack, which is the largest coupon below 2 that this grain has.

Refining the grain confirms it rather than changing it. At a step of 1 the coupons are left at 1; at a half, at 3/2; at a quarter, at 7/4. The number being approached from below is 2, the follow-up’s temperature, and it is a number the thermograph above does not contain.

Over the twelve runs recorded, the rule the stopping coupon obeys is this: it tracks the hottest temperature anywhere in the position’s tree, not the position’s own temperature. Where the position is a plain switch the two coincide, which is why the switch case looks like a clean equivalence; where the position has a follow-up hotter than itself they come apart, and they can come apart very far.

The furthest apart they get here is worth drawing, because at that distance no reader would guess the two numbers belonged to the same position.

The follow-up {9 | 1} has temperature 4, and 7/2 is the largest coupon this grain has below it. So the gap between what the thermograph calls this position and what the environment measures is not a rounding difference: it is the whole distance from 1 to 4, and everything in between is a coupon the players were willing to leave on the table.

That is the surprising part, and it is worth being precise about why. Nothing in this construction mentions sente. There is no local fight and no rest of the board, no classification of moves into forced and optional, and no ambient temperature named anywhere — only a stack of numbers and a minimax. Yet the play produces the sente crossover as an observable: the exchange is held back while the ambient temperature is high and made the moment it drops below the follow-up’s own temperature, which is exactly the crossover the sente sweep measures by sweeping an artificial ambient temperature past a local fight. Two constructions with no vocabulary in common land on the same number.

It also means the slate’s tidy sentence — the coupon they stop at is the temperature — is false as stated, and the true statement is the better one. A single position’s temperature is a fact about that position alone; what an environment measures is what the position and everything reachable inside it are worth interrupting the environment for. Double sente is not a property of the position reaches the same conclusion from the sente side, on the same position { {5 | 3} | {2 | −4}}.

Where the model stops #

The top has to be high enough. Every run above uses a stack whose largest coupon exceeds the hottest temperature in the position. A stack topped below it would be measuring a truncated environment, and the transcript would look exactly as convincing.

The environment is a fiction, deliberately. Every coupon is a separate component of the disjunctive sum, so its moves are numbers, strictly decreasing by a fixed step, equally available to both players, and none of them has a follow-up. A real Go endgame has none of those properties: its moves come in lumps, several are the same size, some are available to one player only, and many carry threats of their own. That is what “idealised” is doing in the name.

The measurement is a check, not a proof. The mean value theorem is a theorem, and fifteen coupon runs are fifteen positions. What the runs do is make it fail-able: the assertion that the contribution is within a step of the mean is live on every figure here.

And the search is exponential. The eighteen-coupon cap means the finest environment reachable is a quarter-step under a top of 3 or 4. The limit that matters mathematically — the step going to zero — is not a row that can be computed, only one the rows point at.

Berlekamp’s environment #

The two quantities this essay measures were defined long before there was anything to measure them with. Milnor’s 1953 paper on sums of positional games and Hanner’s of 1959 established that a game has a mean and that the error in it stays bounded however many copies are added — a statement about limits, proved by an argument about limits, with no procedure in it a player could carry out.

Elwyn Berlekamp’s contribution, some forty years later, was to notice that the limit could be staged. Idealise the rest of the board into a stack of coupons of decreasing size, and the abstract quantity a mean is becomes an ordinary score while the abstract quantity a temperature is becomes a place in a transcript. He set it out in The Economist’s View of Combinatorial Games, in the 1996 collection Games of No Chance — the natural companion to the Go endgame work he and David Wolfe had published in Mathematical Go two years earlier.

Then he had it played. In the late 1990s a game of coupon Go was arranged between two professional nine-dan players, Jiang Zhujiu and Rui Naiwei, with a physical stack of coupons beside the board and the same rule as above: move, or take the top coupon. That is an unusual direction of travel for this subject. The theory normally arrives at a real game and simplifies it; here a simplification was built for a proof and then handed back to the players as something to play.

What the picture cannot show #

Every coupon-stack figure in this essay draws one line of play, and a line of play is the least informative part of a minimax.

The branches are missing. Each row is the move that optimises the final score over the whole board, and establishing that took a search over everything that was not played. The drawing shows what optimal play did; it cannot show that the play was optimal, because the evidence for that is the part of the tree nobody walked down.

The height of the stack is invisible as a condition. Nothing in a drawing of coupons from 4 down to 0 signals that 4 had to exceed the hottest temperature in the position for the reading to mean anything. A stack topped at 1 would draw just as neatly and report a different number.

And the limit is not a row. The grain figures print three steps and the claim they are evidence for is about the step going to zero. Three points do not draw a limit, which is why the honest statement here is the bound rather than a curve fitted through a column.

Where the ladder goes next #

The coupon stack is a new object on this site, and it has more rungs above it than this essay uses.

Coupon Go as it is actually played. The 1990s professional games record what strong human players do when the environment is made explicit: which exchanges they take early, where they part company with the theory’s ordering, and what the coupon values in their transcripts say about how they were counting.

The environmental temperature. The stack has a temperature of its own, and the question is what happens when several positions are placed in one environment at once — which is where the ordering of a whole endgame is decided, and where the construction meets playing the hottest.

The stack as a proof device. The bound this essay reports as a measurement is provable, and a coupon argument is one of the standard ways to prove it. A rung that runs the argument would connect the environment directly to the mean value theorem, replacing the many-copies route with a single copy in company.

And environments that are not idealised. Every property of the stack that makes it a clean instrument — equal steps, no follow-ups, symmetry between the players — is a property real boards lack. Relaxing them one at a time, and measuring what each relaxation costs the reading, is the rung where the model earns or loses its claim to describe an actual Go endgame.

The convention, named #

Normal play throughout, in the specific sense this subject’s endgame theory needs: play continues until every component is a number, and the score is the sum of those numbers. Whoever cannot move does not lose here — there is always a coupon — so the normal play convention enters through the values of the components rather than through the last move, and every position quoted was reduced to canonical form under it. Under misère play the components would have different values and every score above would be a different number.

Two further conventions decide particular numbers. A tie between taking the top coupon and moving in the game is resolved as moving, which is why a plain switch stops the coupons at its temperature exactly instead of one step below. And the stack bottoms out at zero, so the last coupon is worth nothing and taking it is a pass; an environment continuing into negative coupons would be one both players wanted to leave alone, which is a different construction with a different answer.