An environment instead of a stack

A schedule instead of a number took the guarantee behind play in the hottest component — that a player following it scores at least the mean of the board less its largest temperature — and asked how far down the sorted list of temperatures the guarantee reaches. The answer was one step: the second-largest temperature is never breached either, and the third is breached on 120 sums of 1,734.

It closed by naming the continuous version and predicting it:

A coupon stack supplies a temperature at every level rather than at four, and the guarantee against it is the integral the rung below asked for … The prediction this page suggests is that the answer will again be one step, because the argument is about a reply and a reply is one move.

The prediction is wrong. Against an environment there is no depth to measure, because there is no shortfall to bound.

The rule stops being approximate #

The pool on this ladder was built for one purpose: to make play the hottest lose. Its positions have large follow-ups on the far side of their hot options, so a player who takes the hottest fight hands the opponent something bigger. On the thirty-five three-component sums from it, the greedy rule plays exactly on thirty and loses five points on the worst.

Put the same three components in a coupon environment topped at six — the temperature of the hottest component in the pool — and the rule plays optimally on all thirty-five. Not within a bound. Exactly.

It is worth being clear about what is being compared, since the two boards are not the same board. Adding a coupon stack changes the game: there are more moves, the score includes what the coupons banked, and the optimal score is a different number. What is held fixed is the rule and the components, and what is measured on each board is the gap between the rule and optimal play on that same board. So the claim is not that the environment makes the players better off; it is that on a board with an environment the rule is not making mistakes, and on the same components without one it is.

So the schedule question does not have the answer the rung below predicted; it does not have an answer, because every level of the schedule is satisfied trivially by a rule that never falls short of anything.

That is worth dwelling on rather than passing over, because a negative answer to a well-posed question usually means the question was badly posed and here it does not. The rung below’s question was exactly right — how far down the temperatures does the guarantee reach — and it has a finite answer on bare boards and no answer here for the best possible reason. A schedule is a way of grading how wrong something is, and there is nothing to grade.

The prediction that failed is worth keeping too. One step, because the argument is about a reply and a reply is one move is a good piece of reasoning about a bare board, and it is the correct account of why the discrete answer is one rather than two. What it does not anticipate is that an environment changes what a player is replying to.

Why the trap stops working #

The mechanism is worth stating because it is the thing the ladder has been circling from the other side.

A greedy rule is trapped when it has to choose. The board offers a hot component and a colder one; the hot one’s follow-up is worse than the cold one’s; and a player who must move somewhere, and moves where it is hottest, walks into it. Every position in the trap pool is built to present exactly that choice.

An environment removes the choice. A coupon at the same temperature as the hot component is available, and taking it is a move — so a player is never forced to enter a fight in order to have something to do. The hot component sits there, the coupons come off the top one at a time, and by the time the coupons are exhausted the fight is being entered at the right moment rather than at the only moment.

There is a second thing the environment does and it matters as much. Coupons are taken strictly top down and they are worth the same to either player, so the order in which the temperature falls is fixed by the stack rather than negotiated between the components. On a bare board the players are simultaneously deciding which fight to have and when to have it; with a stack the when is settled by the coupons and only the which is left, and the which is what the rule is a rule about.

That also explains why the ladder’s traps are traps. Each of them works by making the when matter — a fight that is worth taking later and disastrous to take now — and the trap needs a board on which later does not exist.

That is why a rule with a guarantee has the guarantee it has. The bound mean minus the largest temperature is exactly the cost of being forced to move first in the hottest fight, and an environment is the thing that removes the forcing.

How hot an environment has to be #

Warming the stack from nothing produces a clean, graded transition. With no stack the worst loss is five points; a stack topped at a half brings it to four; at one, three; at two, three; at four, one; and at six — the hottest component’s own temperature — nought.

The transition is at the board’s temperature and not at a fraction of it. That is the sharpest form the answer could have taken and it is worth saying why it is not obvious: an environment topped at four already supplies moves at every temperature up to four, which covers most of the board, and it still leaves the rule losing a point. What is needed is a coupon at least as hot as the hottest component, because that is the fight the rule is going to be forced into.

The count of boards played exactly moves more coarsely — thirty of thirty-five up to a top of two, thirty-three at four, thirty-five at six — which is the usual relationship between a worst case and an average. The worst case improves smoothly; the count improves in jumps, as boards cross over one at a time.

The same board is the witness at every stage, which is worth recording: two copies of $\{6 \mid \{1 \mid -16\}\}$ beside $\{\{16 \mid -1\} \mid -6\}$ is the worst sum with no stack and the worst at every partial stack, and it is the last to be fixed. A single hard board being hard all the way up is what a graded transition ought to look like, and a sweep where the witness kept changing would be measuring noise rather than a threshold.

What this says about the bound #

Three statements, and the third is the one worth carrying.

The bound is not wrong. Mean minus the largest temperature is a true lower bound on a bare board and this page does not touch it. What the environment shows is that the bound is measuring the cost of a constraint rather than a defect in the rule.

The schedule refinement was measuring the same thing. The rung below found the guarantee reaching one step down the sorted temperatures, and one step is exactly the room a player has when the board offers no alternative to moving: they may decline the hottest fight for the second-hottest and no further. In an environment they may decline everything, and the schedule collapses.

And the rule was never really greedy. Play in the hottest component is a rule about where to move given that a move must be made; it was measured on boards where a player must, and it was found wanting. In the setting the theory was built for — a game with an environment, which is what Berlekamp’s coupon stack is a model of — it is not a heuristic at all. It is correct play.

The word greedy has been doing quiet damage throughout, and it is worth retiring. A greedy rule is one that takes the largest immediate gain and is expected to be beaten by one that looks further ahead. What this rule takes is the largest temperature, which is not a gain but a measure of what is at stake, and temperature is already a lookahead — it is computed from the whole thermograph, which is the whole recursion. So the rule was never short-sighted; it was reading the right quantity and being asked the wrong question.

That reframes the whole ladder. The four rungs below measured a rule’s error, and the error is an artefact of measuring it on bare sums of components. Bare sums are what this site can enumerate; boards with environments are what the theory is about; and the two disagree about whether the rule is any good.

It is worth being careful not to overstate that. A bare sum of components is a real position — a Go endgame with no ko and no large remaining moves is one, and so is any board whose easy points have all been taken — so the ladder’s numbers describe something a player can meet. What they do not describe is the general case, and the general case is the one the guarantee was proved for. Both readings are true and they answer different questions.

The practical version, for anybody using the rule: it is exact while there is anything easy left on the board, and it becomes a heuristic with a known error when there is not. Which is roughly the advice a strong player would give without any of this, and is the reason the theory was built the way it was.

What the ladder was measuring #

It is worth going back through the four rungs below with this in hand, because each of them reads differently.

A rule with a guarantee established the bound and measured how often the rule is exact on ordinary sums. A rule with no promise at all found a rule that beats it in practice and promises nothing. A pool built to punish greed built the adversarial positions that separate them. A schedule instead of a number asked how deep the guarantee runs.

Every one of those is a measurement on a bare sum of components, and every one of them is therefore measuring the cost of the missing environment rather than a property of the rule. That is not a complaint about the rungs — a bare sum is what an exhaustive sweep can enumerate, and the ladder says so at each step — but it is a different account of what the numbers mean than the one the ladder has been giving.

The rule that beats it, in particular, deserves re-measuring. If play the hottest is exact in an environment, then a rule that beats it on bare boards is beating it at a task neither of them is for, and whether it also plays exactly in an environment is a question with a definite answer that nobody has asked.

What is measured and what is not #

Thirty-five boards from one pool. The pool is small and it was designed to be adversarial, which cuts the right way here — a rule that is exact on the boards built to break it is a strong result — and it is still thirty-five boards.

The size is set by what the sweep costs rather than by choice. Each board is three components plus a stack of up to nine coupons, and both the optimal score and the rule’s line have to be computed on the whole thing; the seven stack settings together are a minute of work on a warm cache and considerably more on a cold one. Four-component boards with stacks are out of reach for the same reason the schedule sweep stopped at three.

One family of environment. A coupon stack with equal steps is one model of an environment, and the model in which the classical theory is stated. An environment with unevenly spaced coupons, or one that runs out early, is a different object and this page has not asked about either.

And the transition point is measured, not derived. That the nought arrives exactly at the hottest component’s temperature is what the sweep shows on this pool. An argument that it must — that a coupon hotter than every component removes every forcing — is available in outline and is not made here, because the outline does not obviously survive a board whose components’ follow-ups are hotter than the stack.

The stacks are coarse. A coupon every whole point up to six is seven coupons, which is a rough approximation to a continuous environment; the rung below’s word for what it wanted was continuous, and this is a discretisation of it. Finer stacks were run at the top of the range and behave identically, so the coarseness is not hiding anything at the transition — but a stack with a step of one cannot see a threshold that falls between five and six, and this page cannot rule out that the true threshold is somewhere in there rather than exactly at six.

That last one is the real open question and it is sharper than the rung below’s. The trap positions have follow-ups of temperature much larger than the positions themselves: $\{6 \mid \{1 \mid -16\}\}$ has temperature six and a follow-up worth a great deal more. A stack topped at six is not hotter than everything on the board; it is hotter than every component’s temperature. That it suffices is the surprising half of the measurement.

Approximate against exact #

The rule does not get better against an environment; it changes category.

Against a board, playing in the hottest component is a heuristic — a claim about which of several fights to enter, with a bound on how much the claim can cost. Against an environment as hot as the board, there is nothing to choose between: the environment is always available and always priced, and the rule reduces to taking the best-priced move there is. A rule with no alternative to weigh cannot be approximate.

Where the ladder goes next #

The strategy anchor has five rungs: a rule with a guarantee, a rule with none that beats it, the pool built to separate them, how far down the stack of temperatures the guarantee reaches, and now what an environment does to the question.

The rung above is the follow-up. The measurement here says a stack as hot as the hottest component makes the rule exact, on a pool whose follow-ups are far hotter than that. Whether the threshold is the components’ temperatures or something about their follow-ups is decidable by construction: build positions whose temperatures are equal and whose follow-ups differ, and warm a stack against both. If the threshold moves with the follow-up, the right statement of the bound is about the second level of the position and not the first — which would be the same finding the bend that governs reached on the neighbouring anchor, arriving from the other side.

Two neighbours are worth the trip. An environment made of coupons is where the stack is introduced and what it is a model of, and it is the page this one turns from a setting into an instrument. And a rule with no promise at all is the rule that beats this one on bare boards while promising nothing, and it is worth asking of it what this page asked here.