Combinatorial Game Theory
who wins, and by how much
Theme

The thread: A theorem that names no move — page 4

Knowing who wins and knowing what to play are different achievements, and the subject is full of results that supply the first and refuse the second. A bound is sometimes all there is.
The yield, four sizes further. Toppling Dominoes rows to twelve, with the count of values not seen at any smaller size and the share of rows that is. Values

The mirror was the floor

Toppling Dominoes' share of genuinely new values had fallen from one to a half over eight sizes, and the rung below could not tell a floor from a slow fall. Four more sizes settle it: the distance above a half halves every two sizes. And the half is not a shortage of values but a symmetry — a row played from the other end is the same game, and the ruleset is as injective as that allows.

 One board, all the way down. The mobility rule's failure rate on a three by five board at every depth, with the threshold each depth gives. Values

A heuristic that becomes a theorem

The mobility rule's failure rate had been measured at two depths on each of five boards and found to fall. Swept at every depth it does not merely fall — it accelerates, and it reaches exactly nought before the endgame. From four to eight empty squares onwards the rule has no exceptions at all, which turns a rule of thumb into a guarantee for the last few moves.

 Wrong by one, or by nothing. The seventy-two decisions the rules get wrong, by how many replies the named placement misses a best one. Values

The price of taking the maximum

The seventy-two decisions where a Domineering strategy's rules name the wrong placement are never wrong by more than one reply, and a third of them are the second rule's fault rather than the mobility count's. The repair that follows — keep every placement within one reply of the best — retains a best placement every time and costs thirty decisions for every one it saves.

 Four conditions. The four linear conditions whose kernels are the losing sets, with the cases each covers. Impartial games

The parameter was the difference

The losing words of bounded Moore's Nim form a linear subspace and no map was known whose kernel they are. The equations exist, four conditions cover all thirteen cases at three to six heaps, and they are indexed not by the heap count but by the heaps less the width of a move — which turns the failure at six heaps into a prediction about seven.

 The clause that was free. Five requirements on a pairing strategy, with which of them each map meets. Impartial games

A symmetry that is not a pairing

The quarter turn was the last symmetry a Cram pairing argument had not tried, and the one a square board seemed to offer. It fires on the empty four by four and it settles nothing the half turn misses — and the reason is a clause four rungs of this anchor never had to write down, because every map tried so far was its own inverse.

 Three orders, one of them right. The holder's rank above the crossover under three different orderings of the options. Temperature

Which top is the top

The crossover law's proof rests on the walls above the crossover being governed by the top two options, and the check was never run. Run on 23,586 heights it holds exactly — but only when the options are ranked by mean value. Ranked by the temperatures the law is stated in, it fails on a fifth of them.

 Three catalogues, ten entries each. The catalogue built from a sweep against two self-built ones, on reach and on content. What it costs

A catalogue that builds itself

A solver that stores every region it has to evaluate builds a catalogue out of its own games. After 650 games it holds 232 of the 1,042 shapes and is still growing — and the order things arrive in is nearly arbitrary while the order they are consulted in reproduces a census of a strong player's games almost exactly.

 Five rules over 120 sums built to punish greed. Each rule plays every sum against an opponent evaluating exactly, on a pool whose components are traps: a large immediate gain that hands the opponent a larger follow-up. The pool was built to punish the greedy rule and does not — that rule scores a move by the stop it leaves, and a stop already contains the follow-up. What the traps catch is the rule below it, which scores a move by the territory it takes and loses up to 16. Temperature

An environment instead of a stack

The guarantee behind playing the hottest component survives one step down a board's sorted temperatures and fails at two. Against a coupon environment as hot as the board it survives all of them — because the rule stops being approximate and starts being optimal, on every sum in the pool built to punish it.

 Two fibres and a tail. The values reached by the most antichains. Nought takes half of them and star fourteen more; twenty-three of the thirty values are reached by exactly one. Sums and comparison

Twenty-six other values

The mex rule accounts for sixty-six of the ninety-six antichains and is silent on the other thirty. Every one of those thirty is worth a self-negative value born by day three — and the same mex, run over that family instead of over the nimbers, is exact on all ninety-six. The nimber rule is this one cut short after its fourth member.

 How long a win takes, against how long the argument allows. Ordinary impartial games with the size of their position graphs, the number of rounds the backward labelling takes, and the number of moves the longest win actually lasts. The round a position settles in is the length of the play from it, which is computed here a second way so the two must agree. The rounds are a handful and the positions are many, which is the gap Zermelo's 1913 paper is about — his question was how many moves a forced win needs, and the answer he could prove was the size of the whole graph. How it was found

The paper was about how long

Zermelo's 1913 paper is remembered for a theorem it proves in passing. The question it actually asks is how many moves a forced win takes, the answer it can prove is the size of the whole position graph, and the round counter in the procedure is the real answer — a quantity nobody named for another forty years.

 A bridge circuit, with a link that is not there. The switching graph drawn as a bridge circuit, with an imaginary link from A to B dashed in gold. The graph alone does not split into two edge-disjoint spanning trees, so Short moving second loses; with the imaginary link it does, drawn in blue and red, so Short moving first wins. The green links are the links of the red tree that cross between the two halves the blue tree falls into without the imaginary link — the first moves the trees name. Out in the world

The first move is a link that is not there

Lehman's criterion answers one question about a switching game — who wins when Short moves second. The other question has the same answer asked of a different graph: add one link from A to B, and Cut is forced to spend its first move deleting it. The trees of that larger graph then name Short's opening, and on every subgraph of seven graphs they name a winner.

 The Bridg-It board of size 3, both players at once. A Bridg-It board of size 3: blue dots in 4 rows of 3, red dots in 3 rows of 4, interleaved. Every bridge blue can usefully build is drawn in blue and every bridge red can usefully build in red, and each blue bridge crosses exactly one red one. Blue's switching graph and its planar dual have the same numbers of points and links, because the dual is red's board turned a quarter. Out in the world

Cut is Short on another graph

Everything proved about the switching game is proved from Short's side, and Cut appears only as the player whose moves get enumerated. On a graph drawn without crossings Cut does not need a theory of its own: deleting a link is securing the link that crosses it in the dual, so Cut's game is Short's game on a different graph. Bridg-It is the board that is its own dual — one link short of two trees at every size, which is why its first player wins.

 Chomp to 12 × 8: one needle on every bar but one. Every Chomp rectangle up to 12 columns by 8 rows, with the number of winning opening moves in each cell, found by search. All but one have exactly one; the 10 × 8 bar has 2. Cells in blue belong to the families whose winning move can be stated in a sentence — a single row, two rows, or a square; cells in gold are found only by searching. Out in the world

Where the needle has a sentence

Strategy stealing proves the first player wins every Chomp bar and names no square to take. On two families the square can be said in a sentence — a square bar and a bar two rows deep — and in both the sentence is a pairing that names every later move too. Three rows deep the needle wanders, and the observation that every bar has exactly one needle survives ninety-four rectangles and fails on the ninety-fifth.

 Hex on 3 × 4: the nearer edges win whoever starts. Two copies of a Hex board of 3 rows and 4 columns. On the left each cell is coloured by whether Down, joining top to bottom, wins by taking it first: all 12 do. On the right each cell is coloured by whether Across, joining left to right, wins by taking it first: none do. Down's edges are one row nearer together than Across's, and Down wins whoever moves first. Out in the world

A board one column wider

Strategy stealing proves the first player wins Hex, and it needs three things: no draws, an extra stone never hurting, and rules that treat the two players alike. Add one column to the board and the third goes. The player whose edges are now nearer together wins whoever moves first — and does it with a table of pairs that names every reply, checked against every line to a board of twenty cells.

 The positions that pair their gaps off, and who loses them. Every Sylver Coinage position with at most sixteen unnameable numbers, counted by genus, split into the symmetric and pseudo-symmetric semigroups — the irreducible ones — and the rest, with the positions lost for the player to move in each. Of 584 irreducible positions exactly one is lost, the single position whose only gap is 1; the remaining 11,185 positions include 1,405 losses. Out in the world

Every move closes the largest gap

A census of Sylver Coinage by genus finds a parity that nearly decides the game and asks whether any known property of a numerical semigroup predicts the outcome. One does, completely: a semigroup whose gaps pair off around the largest one is never lost for the player to move — none of 583 up to genus sixteen. The reason is strategy stealing, and it is the same reason the top-right square decides Chomp: every move from such a position closes the largest gap.

 Two replies to the first stone. The 4 by 5 Hex board after Across's first stone in row 1, column 1, with every empty cell labelled by the weight of Across's unblocked chains through it. The potential answers in the heaviest cell, row 2, column 4; the pairing, which wins this board for Down, answers in row 1, column 2. Out in the world

A potential that names every move

Strategy stealing names no move, and the pairings that do name moves need a board with the right symmetry. The Erdős–Selfridge potential needs neither: Down, moving second in Hex, takes the empty cell through which Across's unfinished chains weigh most. Its guarantee reaches only boards two rows deep. It wins far past the guarantee — on every board of three rows that Down can win — and then, on a four-by-five board that a table of pairs wins for Down with certainty, it answers Across's first stone in a different cell and loses along the bottom edge.

 The gaps of ⟨5, 7, 9, 11⟩, and which of them the pairing removes. A Sylver Coinage position drawn as the numerical semigroup it is, with every legal move marked by what a single pass says about it. Gold squares are the numbers already named; plain squares are sums of them; magenta squares are the gaps, which are the legal moves. Under each gap is "struck" when the position that move reaches has its own gaps paired around its own largest gap — a position the opponent wins, so the move loses — and "wins" when the search says the move wins. Out in the world

The pairing removes moves it cannot name

Symmetric positions were settled by an argument that names a winner and no move. Turned on the moves instead, the same one-pass test strikes off 27,215 of the 159,728 moves in the census and not one of the 21,234 winning ones — a quarter of a full search — and still names nothing. On 583 paired positions nine arithmetic descriptions of the winning gap reach at most 123, and 367 of those positions have exactly one winning move.

 One cycle, and how much of it the criterion misses. The matching criterion for undirected geography put to the game where a move uses up the edge it crosses, on every connected graph up to 6 vertices with exactly one cycle. It is right at 77 of 114 starts, and at none of the six on the graph whose cycle has six vertices. What it costs

Two graphs a rule cannot tell apart

The repair proposed for the matching criterion was to read the cycle as well. Over every connected graph with exactly one cycle up to six vertices — 21 graphs, 114 starts — eleven such rules reach at most 91, and the winner is not a function of the matching, the cycle's length, the start's distance from it, its degree and the edge count together: six cells of that table hold both verdicts, the smallest a pair of five-edge graphs.

 An edge bonus, on every board it could help. The Erdős–Selfridge potential for Hex with the chains along the outer rows weighted more heavily, on six boards. No bonus wins the four-by-five board the plain potential loses, and the bonus costs Down 4 boards it was already holding. Out in the world

The winning reply is the fourth choice

The repair proposed for the potential was to weigh an edge chain more heavily. Fifty-five weightings later, none holds the four-by-five board, and an edge bonus costs Down four boards it was already holding. The reason is not the numbers: over 393,660 turns of the pairing that does hold that board, the potential would take the same cell 26.1% of the time, and the winning cell is its 3.7th choice on average and as low as its seventeenth.

 Seven orders, and none of them better than chance. Seven quantities a one-pass scan could compute about each move surviving the pairing test — the number itself, how many gaps it closes, what it leaves behind — each read as an order over the survivors and scored against the winning moves of 583 positions. The best puts a winner first on 24.9% of positions against 22.3% at random, and every one of the seven places the winner deeper in its order than chance would. Out in the world

A shortlist with nothing at the top

The one-pass test leaves 9.58 moves of 12.27 and names none of them. Seven quantities a scan could compute about the survivors were turned into orders and scored on 583 positions: the best puts a winning move first on 24.9% against 22.3% by chance, and every one of the seven places the winner deeper in its order than chance does. Read as sieves instead, the gentlest keeps half the list and throws the only winner away on 264 positions.

 A move that leaves no surviving reply. A Sylver Coinage position whose gaps are 1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 17, 18, 23, 28, with the number of the opponent's surviving replies under each move that survives the pairing test. Naming 4 leaves no surviving reply, which proves it wins; the other winner leaves as many replies as the losing moves. Out in the world

A move whose every reply is struck

Read two moves at a time, the Sylver Coinage shortlist is no better ordered than read one at a time: preferring the survivor that leaves the opponent the fewest surviving replies puts a winner first on 24.7% of 583 positions against 22.3% by chance, and places it deeper than chance does. Read as a proof, the same count does what no order could. On 57 positions a survivor leaves no surviving reply at all, and wins by a certificate a few lines long; searched deeper, the survivors prove every position by thirteen moves — at a price that is never below the search that simply finishes.

 6 turns in strict alternation, priced. One quantifier prefix taken apart into its blocks, with the size of a winning strategy computed a term at a time. A choice made after k of the opponent's turns has to be written down once for each of the 2^k lines the opponent can produce, so the total depends on where the opponent's turns sit and not merely on how many there are. What it costs

Twelve turns, and three different prices

The earlier essay prices a universal quantifier at a doubling and leaves it there. Twelve turns with six of them the opponent's cost 6, 63 or 384 decisions to write down, depending on nothing but the order the turns come in — and the cheap arrangements are cheap for only one of the two players. What a claim costs is the number of times the choosing changes hands.

 A win is proved by one move and a loss by all of them. The smallest proof of each position's verdict, averaged by verdict. At a node the mover wins the proof takes the cheapest single option; at a node the mover loses it has to answer every option, which is the existential and universal quantifiers of the prefix showing up as two different objects. What it costs

Proving a loss means answering everything

A win is established by one move and a loss by every move, so the two verdicts are certified by objects of different shapes. Measured over every position of four games, a loss costs between 1.07 and 2.31 times a win — a small constant, never an exponential. The obvious explanation is the branching and it is wrong: Nim answers six options at a losing turn and pays 2.18, not six.

 The same number, from a rule that needs no tie-break. The number computed twice: once as the critical share of a pot under the auction, and once as the probability that Left wins when a fair coin decides who moves at each turn. They agree on every position, and only the second derivation survives being played out. Where it stops

A coin needs no tie-break

The same recursion has a second derivation: a fair coin decides who moves at each turn, a player whose turn it is with no move has lost, and both play to win. Written from those rules it comes out identical on every position — and it needs no rule for equal bids, because there are no bids. The number is a probability, it belongs to Left rather than Right, and the empty position is the one where the coin decides everything.

All themes