Combinatorial Game Theory
who wins, and by how much
Theme

The thread: The theory runs out — page 4

Misère play, scoring, three players and computational hardness each break something essential. Knowing which of them is biting is most of knowing where a game stands.
One misère outcome, searched. The number of positions a misère search visits to decide the outcome of a sum of k heaps of Dawson's chess, each heap at most 9, on a logarithmic scale: the average over the sums and the worst single sum, for k from one to eight. Normal play decides the same sums from 20 stored values. What it costs

A misère sum is searched, not added

Under normal play the outcome of a sum of heaps is a nim-sum of numbers already known: twenty stored values decide every sum of Dawson's chess with heaps up to nine, however many heaps it has. Under misère play each sum is a new position to search. One outcome costs six positions for a single heap, two hundred for four heaps and over five thousand for eight, and a table of every eight-heap outcome costs a hundred thousand. The misère quotient is the only thing that brings the price back down.

 A staircase, not a slope. The number of misère classes of Dawson's chess positions as the largest heap allowed rises from three to 16, computed with positions of at most three heaps and tests of at most two. The count stays flat for several heaps at a time and then jumps. What it costs

A staircase, not a slope

With the misère closure cut forty-fold, Dawson's chess can be classified at heaps far beyond nine. The count of classes is a staircase: six from heap three to eight, twelve from nine to twelve, seventeen from thirteen to sixteen. Normal play steps once in that range, from four to eight at heap thirteen, where a Grundy value of four first appears. Misère play steps there too, and once more at heap nine, where normal play does not move at all — the first wild heap. Heaps eleven, fifteen and sixteen are also wild and move nothing.

 Four positions, sampled. Three samples of three thousand loopy regions on four positions, drawn with each possible move present at a chance of one half, about a third and a quarter. For each: how many regions have both sides named by the thirty-five names two-position regions use, by those together with the thirteen invented for three positions, and how many need a new name. How it was found

Four positions, sampled

Ten names write both sides of every loopy region of two positions, and forty-eight every region of three. Four positions are over four billion graphs and cannot be counted, but they can be drawn. Three thousand regions at each of three densities: the forty-eight names cover between 95.9 and 99.5 per cent, the thirteen names invented for three positions come back at four almost all of them, and the sparsest sample meets thirty-five sides nothing earlier reproduces — a floor of eighty-three names, and a curve that grows by accretion rather than collapse.

 A rare class that thins. The number of heaps of ·354 with an odd Grundy value in each block of two thousand, through twenty thousand heaps: 288, 22, 3, 1, 0, 0, 0, 4, 1, 2. The odd values fall away after the first block and keep turning up rarely to the end. Impartial games

A rare class exclusive-or respects

The rare values of ·007 were measured by rank — everything outside the twenty-two commonest — and found getting commoner. A sparse-space argument needs a different split: a rare class closed under nothing and a common class closed under exclusive-or, which is to say a parity of bits. Over every parity of every bit, ·007 and ·6 have no class that thins. Across the 79 growing octal codes of up to three digits, one does: ·354, whose odd values fall from 288 in its first two thousand heaps to seven in its last ten thousand.

 What each assumption buys back. Forty-five positions of up to two heaps of up to eight, sorted into classes that no test position of up to three heaps can tell apart, under four rules. Two-player Nim has sixteen classes, both three-player conventions have forty-five, and one player against a coalition of two has six. Where it stops

What survives a coalition

Three-player Nim has no winner without a convention and no sum theory at all. Fix one player against the other two and both come back: every position has a winner, the winner is read off the number of heaps of one modulo three and the number of larger heaps, and forty-five positions fall into six interchangeable classes — fewer than Nim's sixteen. Fix a scoring rule instead and the winner comes back, identical to one of the conventions, and nothing else does: no two positions are interchangeable.

 Half the new sides are sums. The 50 sides of four-position loopy regions that no earlier name reproduces, tested against every sum of two games from the day-two values, the stoppers and the thirteen three-position names. 23 are such sums, 15 of them using a three-position name; 27 are not. How it was found

Each size is built from the last

At three positions the sides that needed new names were sums of nothing older: no pair of stoppers, and no two-position stopper with a small game beside it, wrote any of them. At four positions the thirteen names three positions forced are available as parts, and they change the answer. Of the fifty sides the samples met that nothing earlier names, twenty-three are sums of two earlier games — fifteen of them using a three-position name — and twenty-seven are not.

 Six rulesets, and the heaps that stop mattering. Single heaps of six impartial rulesets classified under three-player play with one player against a coalition of two. Nim's heaps fall into three classes; subtraction {1, 2} keeps five, Kayles six, subtraction {1, 3} ten, subtraction {2, 3} twelve and Dawson's Kayles ten before every larger heap is interchangeable, and three rulesets have a smaller heap that joins the large class early. Where it stops

A coalition counts to three

Three-player Nim with one player against two collapses to six classes, because every heap of two or more is a store of tempo either side can draw on. Put the same coalition on games whose heaps are not all stores and it does not collapse: subtraction {1, 2} keeps five kinds of heap, Kayles six, subtraction {1, 3} ten and {2, 3} twelve, each count settling as the range grows. Past a threshold the large heaps are interchangeable again — and in every one of the five, unlike Nim, a single large heap hands the game to the coalition. The classes neither refine the two-player values nor coarsen them: {1, 3} has two Grundy values and ten coalition classes.

 Two even rows, and the incentive to move. Every sum of two coin rows of two or four coins under four coin sets, 4,095 sums each. The first player is never behind; the margin is never below the difference of the two rows' own margins, equals it on 3,147 sums, and exceeds it on the other 948. Out in the world

Two rows still reward the move

A single coin row with an even number of coins always rewards the player to move, because the first player can take a whole parity class. Two such rows side by side break that argument, and the conclusion survives anyway: on every one of 16,380 sums of two rows the first player is never behind, and there is a proof — open the row worth more, then answer in whichever row the opponent moves in — that guarantees the difference of the two rows' margins, which is what two switches would give. The sum meets that floor on three pairs in four and beats it on the rest, once by both margins together. At three rows the switch arithmetic stops being a floor. The incentive does not.

 The odd values do not stop. The odd Grundy values of the octal game ·354 counted in blocks of ten thousand heaps to 100,000. The first block holds 314; every later block holds between three and eleven, and the last odd value in range is at heap 99,600. Impartial games

The odd values keep coming

·354 is the one growing octal code of up to three digits whose values have a class that thins: 288 odd values in the first two thousand heaps, seven between ten and twenty thousand, the last of those at 18,908. A sparse-space argument needs that class to stop. Taken to a hundred thousand heaps it does not: 48 more odd values arrive after twenty thousand, every block of ten thousand holds some, and the last in range is at 99,600. They keep no schedule a remainder can see, their gaps are spread like arrivals, and most of them are one number, 37 — each one a heap where every split that could have reached 37 misses it.

 Heights from ω² down to nought. Thirteen Sylver Coinage positions with the gcd of the named numbers, its prime factors counted with repeats, the gaps of the semigroup scaled by the gcd, and the ordinal height those give: ω² for the empty position, ω·4 for {16}, ω for {2}, 3 for {3, 5} and 0 for {2, 3}. Where it stops

No number bounds it

Sylver Coinage cannot be given a termination measure in the natural numbers: from {2} the game can last one move, two, or any number the second player chooses. The measure proposed for it — the gap count beside the number of distinct primes the named numbers share — rises on {4} + 6. Count the primes with their repeats and it falls on every one of 42,519 moves checked, and it is exact: the game tree is ω squared tall, and the height of a position is ω times the prime factors of its gcd plus the gaps that are left.

 Ten classes, and a rule to name them. The classes of subtraction {1, 2} with one player against two: a grid of heaps of one counted modulo three against no other heap, a heap of two or a heap of three, each cell giving the lone player's result with each player to move, and a tenth class — anything with a heap of four or more, or two heaps from two and three — won by the coalition. Where it stops

Units modulo three, and one choice

Nim's rule for one player against two has a shape: count the heaps that always last one move, modulo three, allow one heap that offers a choice, and give any second choice to the coalition. Subtraction {1, 2} has exactly that table — ten classes, nine of them a count of ones against nothing, a two or a three — and so do Kayles, where a heap of three is a heap of two with a unit beside it, and Dawson's Kayles. Subtraction {1, 3} and {2, 3} do not: a board with two choices on it can still be the lone player's, and the short key fails. And {2, 3} and Dawson's Kayles give every heap to ten exactly the same menu of game lengths, so what a coalition reads is not how long a heap can last.

 A star with one empty place. The Mū tōrere board at the start: eight points on a circle joined to their neighbours and to an empty centre, Black's four counters on neighbouring points and White's on the other four. Black's two end counters, each beside a White counter, may move into the centre; the two middle counters may not. The start is a draw with best play. Out in the world

The same rule on a star

Kōnane turned out to hold the theory's whole vocabulary, and one old game is an anecdote. Mū tōrere, a Māori game on an eight-pointed star, has the same rule for losing — a player who cannot move loses — and is small enough to solve whole. Of its 630 arrangements, not one is a win for whoever moves first or a loss for whoever must move, sixteen go to each side whoever starts, and most are drawn. A random player still loses it every time. The vocabulary was never in the rule for losing; it was in the captures.

 Right for five hundred heaps before it can be known. The Grundy sequence of the octal game ·45 read one heap at a time, with the period a sweep would report at each depth. False readings of period 1 and period 20 come and go until depth 538, after which the reading is period 20 from heap 498 for good; the periodicity theorem's window does not close until depth 1038. What it costs

A repetition is a guess

Read an octal game's values one heap at a time and report the first pattern that fits, and the report is a guess that changes. Over the 291 short octal codes whose period can be proved, the guess is wrong 4,684 times before it settles; on ·45 it changes 181 times, is right from heap 538 and cannot be proved until heap 1,038. No false guess ever reaches the window that would certify it — the furthest gets 74 per cent of the way — and no fixed number of repetitions is a safe substitute, because the window asks for as many as the period's late start requires: two on some codes, twenty-seven on ·45.

 A win with no pairing. A graph of ten points, each with three neighbours, in which Short claiming points and Cut deleting them, Short wins moving second. No pairing of the eight contested points puts a whole pair inside all 10 minimal separating sets; the closest misses {e, f, h}, the three neighbours of A. Out in the world

Two neighbours keep a pairing, three lose it

In the switching game on points, Short wins moving second by a pairing when every smallest set of points that cuts A from B holds both points of some pair. On every graph of seven points — 971,104 of them — every Short win has one, at every degree. In random link games, where each contested point has two neighbours, every win has one too, although the winning strategy follows trees that change as the game goes. The first wins with no pairing appear at nine points with four neighbours and at ten points with three: a cubic graph Short wins whoever moves, which no fixed set of answers explains.

 A pairing that changes once. The ten-point cubic graph that no pairing certifies, drawn four times, once for each plan of a one-change certificate: after Cut's first deletion Short claims one point and then answers by a fixed pairing. Deleting c: claim d, pair e–f, g–i, h–j. Deleting d, e, g, i, j: claim c, pair f–h. Deleting e, f, g, i, j: claim h, pair c–d. Deleting h: claim f, pair c–g, d–i, e–j. Out in the world

A pairing that changes once

The cubic ten-point graph is a win for Short that no fixed pairing explains, and the full strategy that does explain it is a tree of 68 decisions. One change is enough: after Cut's first deletion Short claims a stated point, and from then on a fixed pairing of what is left holds every cutting set. Four such plans, eight pairs between them, answer every opening. Of the 23 pairless wins in the samples, 21 need one change and two need a second, and in both the second is a forced claim. Unless the hard problems collapse, no fixed number of changes can be enough for every graph.

 A staircase, not a slope. The number of misère classes of Dawson's chess positions as the largest heap allowed rises from three to 20, computed with positions of at most three heaps and tests of at most two. The count stays flat for several heaps at a time and then jumps. What it costs

A heap that loses under both endings

The misère classes of Dawson's chess climb in steps, and the two steps to heap sixteen landed on first appearances: the first wild heap and the first Grundy value of four. Run on to twenty, the count sits at seventeen through heap nineteen and then jumps to twenty-four, on a heap worth nought whose genus is tame. Heap twenty is the first heap that loses for the mover under both endings, it behaves like two Nim heaps of two, and most of what it adds is a new way of telling old positions apart. What every step to twenty shares is a genus no smaller heap has. The search that finds this stops at twenty-one, when the positions it remembers outgrow the table that holds them.

 A saltus found, and none on offer. Two Grundy sequences read heap by heap for an arithmetic period. The hexadecimal code ·28 is read 71 wrong ways and then, from depth 107, as period 53 with saltus 16 for good. The octal code ·6, whose values also grow, is read 1128 ways in 1,200 heaps and every reading breaks within a few periods. What it costs

Growing is not climbing

The octal codes whose values grow were expected to be arithmetically periodic — repeating with a constant added each period — and to fool a reader with false climbs. Read for that pattern, the 220 octal codes of up to three digits with no certified period produce 246,048 readings in 1,200 heaps and not one holds for more than six periods. The false climbs are exactly as short as on the hexadecimal codes where the climb is real; the difference is that no right reading ever arrives, and the largest values grow more slowly than any constant climb allows.

 Every game on three positions. All sixteen directed graphs on three vertices up to relabelling, each with one of its stable sets filled and the count written beneath. Nine have one, six have several and the 3-cycle has none. How it was found

The solution that was a losing set

In 1944 von Neumann and Morgenstern defined the solution of a game by two conditions on a set of outcomes: none overrules another, and each outcome outside is overruled by one inside. They were writing about coalitions. The same two conditions, read with a move in place of an overruling, describe exactly the lost positions of a game that must end. Where play can loop, the same definition gives several answers or none, and three positions are enough to show both.

 Parity on a cycle. Single directed cycles of two to seven positions. Even cycles have two stable sets, the alternating halves, one of which is filled; odd cycles have none. How it was found

An odd cycle is the only way to have none

A cycle of two positions has two stable sets and a cycle of three has none. Moses Richardson proved in 1953 that this is the whole story of absence: a graph with no odd cycle always has a stable set. Run over all 9,608 games on five positions, the theorem holds without exception, sits inside a chain of five nested families, and leaves open the larger question its converse invites, since 7,452 of those games have an odd cycle and a stable set anyway.

 A mirror where there was no solution. The sum of two cycles of 3 positions, drawn as a grid of pairs, with a diagonal filled. It is a stable set of the sum, although a cycle of 3 alone has none. Moves that wrap around are left out of the drawing. How it was found

What a stable set knows about a draw

On a graph with cycles, outcome labelling calls a position lost, won or drawn, and stops. The stable sets go further in exactly one place. On every game of up to five positions they hold every lost position, no won one, and among the drawn positions are exactly the stable sets of the drawn part taken alone. So a stable set is a certificate that the player who keeps returning to it never gets stuck. It can distinguish draws that labelling cannot, and two parts with no stable set can have one between them.

 A stable marriage is a stable set. A three-by-three preference table with the pairs ranked by each side, shown three times. Each filled set of cells is a stable matching and also a stable set of the graph whose moves go from a pair to a pair one of its members prefers. How it was found

A stable marriage is a stable set

Draw a graph whose positions are pairs of people, with a move from a pair to any pair one of its members prefers. Its stable sets are exactly the stable marriages, on all 46,656 profiles of three men and three women. So Gale and Shapley's theorem of 1962 is an existence theorem of the kind Richardson's was, on graphs where 49 per cent have odd cycles and his hypothesis is useless. The reason it holds is that every clique in the graph is one person's list, and four roommates show what happens when it is not.

 Peeling a square by stable sets. A three-by-three square with lists of three colours per cell, coloured one colour at a time. In each panel the uncoloured cells wanting the colour are shaded and the stable set among them is filled and takes it. How it was found

The list that cannot run out

Give each cell of an n × n square its own list of n colours, and ask for a colouring from the lists with no repeat in any row or column. Dinitz asked in 1979 whether that is always possible, and reading the cells in order fails about four times in ten. Galvin's proof of 1994 needs one page. Use an ordinary Latin square to turn each row and column into a preference, so that every cell has exactly n − 1 moves, and peel off a stable set for one colour at a time. A list of n cannot run out against n − 1 moves.

 A formula drawn as a game. Chvátal's construction on two clauses over three variables: each variable a pair of positions moving to each other, each clause a triangle whose corners each have a move to one literal. A stable set is filled, and it names a satisfying assignment. What it costs

A formula drawn as a game

Backward labelling answers who wins on any finite graph in time proportional to the arcs. Whether the same graph has a stable set is another matter: Chvátal showed in 1973 that it is NP-complete, by drawing a formula as a game whose variables are two-way pairs and whose clauses are triangles. On every one of the 255 formulas of this form on three variables the graph has a stable set exactly when the formula is satisfiable, and every position is drawn. The hard question lies entirely where the easy one says nothing.

 Recording the turn doubles an odd cycle. On the left a cycle of three positions, which has no stable set. On the right the same game with the player to move recorded in each position, a cycle of six, with two stable sets, each consisting of all the positions with one player to move. How it was found

Taking turns removes the hard part

Whether a graph has a stable set is NP-complete, and every hard instance depends on odd cycles. A real game's position graph has none. A position records whose turn it is and every move changes that, so all cycles are even, Richardson's theorem applies, and the set of all drawn positions with one player to move is a stable set of the drawn part, always. Mū tōrere and Three Men's Morris both confirm it. The hard question never reaches a game with turns, and the sets it hands over carry no information at all.

All themes