Where the needle has a sentence

The theorem that names a winner and no move sets strategy stealing beside the moves a search finds, on Hex and on Chomp, and ends on the question it cannot answer: an existence proof and a construction are sometimes both available for the same game, and nobody has measured what lies between. It found one striking regularity on the way. Every Chomp bar up to 6 × 6 has exactly one winning opening, which it called the needle, and for square bars the needle is known — take everything except the bottom row and the left column.

That is two separate claims about Chomp, and both are worth pushing on. One is that some needles can be said, as opposed to found. The other is that there is only ever one.

Ninety-five bars, and the one that breaks the count #

Start with the count, because it is the cheaper of the two to test and the result changes how the rest reads.

The search is the plain one: a position is a staircase of column heights, a move picks a square and eats everything above and to the right of it, and a position is won when some move leaves a lost one. Labelling every position reachable from the 12 × 8 bar labels every position of every smaller bar as well, since a smaller bar is a position of the larger one, so one pass answers all ninety-five.

Ninety-four bars have one winning opening and the 10 × 8 bar has two. The earlier essay’s thirty-five had one each; fifty-nine more beyond 6 × 6 have one each; and then a bar of eighty squares, with seventy-nine opening moves, has two moves that both leave the other player lost.

That is exactly the kind of result an observation over small cases is exposed to, and it is worth being plain about what it does and does not overturn. It does not touch the stealing argument, which never said anything about how many needles there are — only that there is at least one. It overturns a pattern, and a pattern read off thirty-five bars was always a statement about thirty-five bars. A pattern that has not started yet is the same trap from the other side: there a regularity begins past where anybody looked, and here one ends there.

The square: two heaps of Nim #

Now the needles that can be said. The earlier essay gives the square’s in a clause, and the clause turns out to contain a whole game.

Take the square one up and one right of the poison. What is left is the poison with an arm of n − 1 squares above it and an arm of n − 1 squares to its right. That L is two heaps of Nim. A move in the vertical arm picks a square and eats it and everything above, which shortens that arm by any amount and leaves the other alone; a move in the horizontal arm does the same to the other. The poison is taken only when both arms are gone and there is nothing else to take — which makes the player left with the bare poison the player unable to move, and that is ordinary Nim with two heaps.

Two-heap Nim is lost exactly when the heaps are equal, which is the nim-sum at its simplest, and the table checks it on every L with arms up to nine. Ninety-nine L-positions, and the lost ones are precisely the nine on the diagonal.

So the square’s sentence is not a lucky shortcut. The first move converts Chomp into a game with a complete theory, and the theory is the oldest one in the subject. The strategy after it is the strategy that is a symmetry: whatever one arm loses, take the same from the other. The corner square is the mirror.

That is also why this needle names more than a move. A sentence that says take this square would still leave the rest of the game to be found by search. This one says make the two arms equal, and keep them equal, and that is a strategy for every position that follows.

Two rows: keep the bottom row one longer #

The second family is the bars two rows deep, and it is even shorter to say.

On a bar two rows deep the needle is the top-right square, and what it leaves is a bottom row of n and a top row of n − 1. A two-row position is lost exactly when the bottom row is one longer than the top, and the table checks it on all ninety positions with rows up to twelve.

The strategy is not a mirror this time, but it is the same kind of object, and the case analysis is short enough to give in full.

Write a two-row position as a top row of t squares and a bottom row of b, with b at least t. From a position obeying the rule, every move breaks it. A square taken from the top row shortens only the top, leaving the bottom two or more longer. A square taken from the bottom row at column c shortens the bottom to c and the top to whichever is smaller of t and c — and since c is at most t on a bottom row one longer than the top, the two rows come out equal. Either way the bottom is no longer exactly one longer.

From a position breaking the rule, some move restores it. If the bottom is two or more longer than the top, take the bottom-row square at column t + 1, which cuts the bottom to t + 1 and leaves the top alone. If the rows are equal, take the top-row square at column b − 1, which cuts the top to one short of the bottom. That exhausts the cases, and it is a complete proof for every length — the table is a check on the search rather than the evidence.

The rule names the reply from every position, which is what a pairing does.

It would be tempting to look for Nim here too, and the temptation is instructive. A two-row position does not split into two independent heaps, because eating from the bottom row can shorten the top row as well — the rows are not independent, and no sum of two games describes them. The rule is simpler than Nim and it is not Nim. What the two families share is not a game underneath but the shape of their strategies: a relation between two lengths that every move breaks and a reply can mend.

Three rows: one needle, and no sentence #

Add a third row and the regularity of the count survives — every three-row bar in range has one winning opening — while the regularity of the answer does not.

The needle is always a cut across one of the two upper rows: a square on the second row, which leaves a block of full columns followed by a strip of single squares, or a square on the top row, which leaves full columns followed by columns of two. From six columns to eleven it looks almost settled — second row, top row, second, top, second, second — and then the top row returns at twelve and fourteen, and the column of the winning square jumps from six at ten columns to nine at twelve and back to eight at thirteen.

No rule of the two-row kind fits the table, and it is worth saying what kind of statement that is. It is not a proof that no sentence exists; sentences can be long, and a rule with a dozen cases is still a rule. It is the observation that the relation which settles two rows — a single fixed offset between two lengths — has no three-row analogue visible here, and that the positions a three-row needle leaves behind are themselves positions whose losing set has to be looked up rather than stated. Three rows is where the needle becomes a table.

That is the exact point the earlier essay’s question turns on. The stealing argument delivers one bit for every bar. The two-row rule and the square’s Nim deliver a strategy for their families at no cost. For three rows the search delivers the needle at the cost of labelling every position, and nothing cheaper is on offer.

The bar with two needles #

The two needles of the 10 × 8 bar are nothing alike. One takes the square in column six, row five, and eats a block of twenty squares from the upper right. The other takes column nine, row four, and eats a narrow block of ten. Both leave positions the opponent loses, and neither position is a reflection or a rearrangement of the other.

It is worth being careful about how surprising this should be. In most games a won position has many winning moves; the earlier essay notes that roughly half the openings of a random game would win. What was strange about Chomp was the opposite — a haystack growing quadratically with exactly one needle in it every time — and the sparseness of Chomp’s lost positions was the explanation offered. The 10 × 8 bar does not refute the sparseness. It says the sparseness is not so extreme that a lost position can never be reached two ways from the same bar, and that the count of one was a property of small bars rather than a law.

Three prices for the same bit #

A search labels every position a bar can reach, and a position is a staircase inside the bar that still contains the poison. That count is a binomial coefficient — choosing where the staircase steps — and it is checked here by walking two bars position by position. The 12 × 8 bar has 125,969 positions; a 12 × 2 bar has 90.

The sentence costs nothing to apply on the families that have one, and it is not cheap on the families that do not; it is absent. The stealing argument costs two lines on every bar and names no square on any of them. So the same fact — the first player wins this bar — comes at three prices, and the prices are not ordered the way the certainty is. The two-line argument is the most certain of the three and the least useful; the search is the most useful and the most expensive; and the sentence, where it exists, is both cheap and useful, because it is a strategy rather than an answer.

The difference is sharpest when it is put in terms of what a player would have to be handed. On a square bar the whole winning strategy is a sentence — take the corner square, then keep the arms equal — and anyone can check it against any line of play. On the 12 × 8 bar the only thing that settles every position is the labelling itself, a table of 125,969 wins and losses, and checking a single entry means checking the entries it depends on. That is the distinction a strategy is not a certificate draws in general, arriving inside one game: the square’s certificate is shorter than the question, and the rectangle’s is the size of the game.

What solved means has a word for each end. The square bars are solved in the strongest sense, with a rule naming the move from any position at any size. The general rectangle is solved in the weakest useful sense for the bars in range, by a database, and in the stealing sense for every bar, by an argument that names nothing. Chomp is one game carrying all three at once, sorted by the shape of the bar.

Nor is the expensive end likely to get cheaper by cleverness alone. Chomp is a game on a partially ordered set — a square may be taken whenever nothing below and to the left of it has gone — and deciding the winner of an arbitrary finite game of that kind was shown PSPACE-complete in 2013, which puts it with the hardest games in the classification. The rectangles are a very special family of such sets and their complexity is not known. What the classification says is that no method fast on every such game is expected, and the rectangles have not been shown to be an exception.

This is the spectrum the earlier essay asked about, measured on one game. A winning strategy that is a spanning tree sits at the cheap end for a whole game at once, since Lehman’s trees exist on every switching graph; Chomp has that end only on two thin families, and the rest of its bars sit at the expensive end, beside the rectangles nobody has a description for.

What a pairing buys, and where it comes from #

Both sentences found here are pairings, and it is not an accident that the constructive end of this spectrum keeps being occupied by them.

A pairing strategy answers every move with a move fixed in advance — the other arm, the other row, the partner link in the other tree. It needs a structure in the position that every move damages and that a single reply repairs, and it needs no search at all once the structure is found. Every game has a negative is the general form of the mirror, and the square’s L is that mirror with the poison as its axis.

The stealing argument is the other end, and the comparison between them is sharper here than anywhere. Stealing uses a symmetry of the rules — an extra square taken can only help — and delivers one bit. A pairing uses a symmetry of the position — two equal arms, two rows one apart — and delivers every move. A bar that is not a square and is more than two rows deep has the first symmetry and not the second, and that is the whole reason its needle has to be searched for.

What the survey cannot say #

Twelve columns and eight rows is a small window. The 10 × 8 bar is the only bar in it with two needles, and nothing here says how common such bars become, whether a bar ever has three, or whether the count grows with the bar at all.

The sentences are checked, not proved, beyond what their pairings prove. The L rule is Nim and is proved by the nim-sum for every arm length; the two-row rule’s pairing proves it for every length too, and the tables are checks on the search. But these are the only families with a sentence is not claimed and is not true in any provable sense: a single row has one, trivially — take everything but the poison — and nothing here rules out a family with a long rule that no table of this size exhibits.

Nor does the three-row table establish that three rows have no rule. It establishes that the offset rule of two rows does not extend, and that the needle’s position does not follow a pattern visible in fifteen bars.

The rule the game is played under #

Chomp is played under a rule that looks like misère and is not. Whoever eats the poison loses, so nobody eats it voluntarily, and the player left with nothing but the poison has no move they want to make — which is the normal-play convention with the last move made unattractive rather than impossible.

The square’s reduction to Nim depends on reading it that way. Two empty arms and a poison is the position with no move in it, the player facing it loses, and that is the base case of normal-play Nim.

Change the rule to make it the other convention — the player who takes the last square beside the poison loses, rather than the player left facing it — and the L becomes two heaps of misère Nim. Misère Nim agrees with ordinary Nim on two equal heaps of two or more, and disagrees on two heaps of one: there, the player to move takes one, and the opponent is forced to take the last. So under the changed rule the square’s needle still wins every square bar from 3 × 3 upward and loses on the 2 × 2 bar, where it leaves exactly two heaps of one. The sentence survives the change of convention except at its smallest case — which is the usual shape of what a convention costs Nim, and the reason the one-line misère rule has a clause about heaps of one.

Still open: the bars that are not squares #

The earlier essay noted that Hex’s winning openings follow a geometric rule on two of three board sizes and fail on the third. Chomp’s needles follow a sentence on two families and no visible rule elsewhere. In both games the stealing argument covers every board and the moves come from somewhere else.

Hex has one more family worth asking about, because it breaks the argument itself rather than its silence. Stealing needs the rules to treat the two players alike, and on a square Hex board they do. Take one row off one side, so that one player’s edges are nearer together than the other’s, and the symmetry of the rules is gone. What happens to who wins, and whether the player the argument can no longer help acquires a strategy of their own, is a question about what the stealing argument was protecting.