Combinatorial Game Theory
who wins, and by how much
Theme

The thread: The theory runs out — page 3

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.
Every domino Left can topple in LRRL. A row of dominoes, blue for Left and red for Right, and each of the mover's options below it. Toppling a domino leftward removes it and everything to its left; rightward removes it and everything to its right. The value under each option is what the game recursion returns for the row that survives. Particular games

A recipe instead of a census

Counting a thousand values in seven dominoes suggests Toppling Dominoes reaches every short game, and a count is not a construction. The obvious construction — lay the two options either side of a Left domino and a Right one — is exact on day one, right on a third of day three, and cannot be applied to nine in ten values at all.

 What a designed pool can say. Six statements about the coefficient, with which pool each rests on. Temperature

A second pool, designed differently

One designed pool put the rule's best coefficient between a quarter and a third, and all three board sizes agreed. A second pool, built by the identical greedy criterion from different material, has no cell that is best at every size — so the coefficient is a property of the pool and there is no number to find.

 The genus of Kayles ·77, heap by heap. One row per heap: the genus symbol, the misère outcome it implies, and whether the symbol is one a Nim heap has. A game all of whose positions are tame is played in a misère sum exactly as Nim is; a single wild heap ends that, and the normal-play Grundy value gives no warning of which heaps those will be. Where it stops

Closing the wild side

The twenty-two wild genus symbols are not closed under addition, and the rung below offered two answers: a monoid nobody had guessed, or no algebra at any size. Neither. Five of the six games with wild heaps close at three or four heaps, with closures of two to five symbols, and the sixth is still growing.

 on: which positions play can return to. A position graph with the moves of both players drawn, and beside it the shortest sequence of moves that gets back to each position. A position play can return to is a position whose value is defined in terms of itself, so the recursion every value in this subject is built from has no base case there. A position with no way back is one the ordinary recursion terminates on. Where it stops

A stopper and how to find one

The class a value theory for loopy games would need is the ones with no infinite alternating run, and the qualifier does the work: seventy-nine of the two hundred and fifty-six two-node loopy games qualify and seventy-two of them have a cycle. Every one has a decided outcome, and under eight tests the seventy-nine collapse to six.

 Two ways to be certain and ignorant at once. Ten positions from two games that both terminate for reasons no bound comes out of. Sylver Coinage's proof counts something that goes down and can be counted; the hydra's counts an ordinal, which cannot, and the last column shows what that difference is worth. Where it stops

Which games end at which level

Between a game that ends within a computable bound and one that ends with no bound at all there are levels, each corresponding to a strength of induction. This site's games sit at three of them, and which level a game is at is decided by exhibiting its termination measure and checking that every move lowers it.

 Where the two conventions come apart, counted. Every small Go endgame solved under both scoring conventions. The scores agree exactly when the number of neutral points is even and never when it is odd, which is the parity of the stones each side ends up placing. A counted fraction name different winners. And a smaller fraction are played differently, which is the half of the finding a rules argument does not predict: a neutral point is a one-point play under one convention and worth nothing under the other, so the two rule sets disagree about the order of the endgame and not only about its total. Out in the world

Two ways to count a finished board

Territory scoring and area scoring are both in daily use and they are not variants of one rule. Over seventy-nine small endgames they agree exactly on the thirty-nine with an even number of neutral points and on none of the forty with an odd number — sixteen name a different winner, and twelve are played differently, which is not something a convention is supposed to do.

 The only two moves in Kōnane that are not captures. A filled Kōnane board with every opening Black may play marked on it, and the value of the position White's best reply leaves. The opening is the one place in the game where a player removes a stone rather than capturing with one, so it is played under a different rule from everything after it — and the choice is worth a computed amount rather than nothing. Out in the world

The two moves that are not captures

Kōnane begins from a full board and the first two moves lift stones rather than take them, which is the only time in the whole game anybody does. Nothing on this site applies to them, and the choice is not free — on a 3 × 5 board two of Black's eight openings leave a position a whole move worse than the other six, and on a 3 × 3 board none of the five does.

 What a pass buys, and what it costs. Rows of coins solved with and without a pass. Milnor's mean-value theory needs a non-negative incentive to move, and rows containing a coin nobody wants break that condition — a player forced to take is a player who would rather have passed. Allow a pass and the condition is not merely satisfied but unbreakable, on every row in range. The price is that a player who may pass is never stuck, so the last-move convention has nothing to attach to and the game needs a separate rule to end at all. Out in the world

What a pass is worth to a theory

The rung below finds fifteen of twenty-seven coin rows where having the move is a disadvantage, and those are exactly the rows Milnor's mean-value theory has to assume away. Allow a pass and the hypothesis stops being a hypothesis — nought violations, on every row in range. What it costs is the convention the rest of this site is built on.

 A game beside its own mirror, and what is left over. Every coin row added to its own negative, played out exactly, with the resulting scores counted. Under the last-move convention every such sum is worth nothing, because the mirroring strategy guarantees the second player the last move. Here the same strategy is available and the score it produces is not nothing: the mirror of a coin conceded is another coin conceded. Gold is the sums that do come to nothing, which are a minority. Out in the world

Nothing to subtract with

Comparison is defined by contexts and computed by subtraction, and the equivalence between the two is a theorem about groups. A scoring game is not one — sixty-six of eighty-one coin rows do not cancel against their own negatives — and the difference test then fails on a row compared with itself, which every context accepts and nothing certifies.

 A game every play of which ends, and no round settles. A game whose first move chooses how long the game will be, cut off at several sizes. Every play of it is finite and no position is drawn, so the fourth outcome class has nothing to do with what goes wrong. What goes wrong is the round counter: the opening is a loss, a loss settles only when the last of its options is known, and there is no last option. Cut the game off larger and the round grows, so no number in the column is the answer for the untruncated game — and the induction that labels it has to run past every finite stage. How it was found

Every play ends and no round settles

Take the finiteness hypothesis away carefully — not by adding a cycle, which has already been priced twice, but by adding infinitely many positions to a game every play of which still ends. Nothing is drawn, every line finishes, and the round the opening settles in grows with every cut: two, four, six, eight, twelve, sixteen, and no number in the column is the answer.

 The same rules under the convention they were posed in. Dawson's chess under misère play, which is how Dawson posed it. Under normal play every position of the game collapses onto one of a handful of nimbers however large the heaps are allowed to get. Under misère play the positions that behave alike form classes whose number grows with the heap limit, and a heap carries a genus rather than a value. The first wild heap is where the two accounts stop resembling each other, and the classification doubles at exactly the limit that admits it. How it was found

The convention Dawson actually used

Dawson published his puzzle as a problem where running out of moves loses you the game, and every compact result about ·137 is about the other convention. Under his own, nine values become a classification that doubles the moment a wild heap enters the range, and a heap stops carrying a number at all.

 The misère sentence, asked of games it was not written for. Bouton's one-sentence solution of misère Nim put to four other impartial games and checked against a search on every position. It is exact on Nim, which is the game it is a theorem about, and wrong on all the others — and wrong in both directions, calling wins losses and losses wins, where the same paper's normal-play criterion errs only one way. The clause responsible is the one about heaps of size one, which is a statement about how many counters are left rather than about what a move can do with them. How it was found

The sentence that solved the other convention

Bouton's paper solves misère Nim too, in one line, and it is the only misère result in the subject that fits on one. Transplanted the way the normal criterion is, it fails differently — the normal one calls losses wins and never the reverse, and this one errs in both directions on every game tried, because the clause it adds is about counters rather than about moves.

 A shuttle and a loop, judged by what the play returns to. A three-node loopy game drawn as a graph, with Left's moves in blue, Right's in red and position a marked. Beside it, each position-and-mover pair under the backward labelling and under the rule that a never-ending play goes to Left when it returns to a infinitely often. Four pairs are drawn by the labelling; the new rule gives two to Left and two to Right and leaves the decided pairs as they were. How it was found

What the play keeps coming back to

A draw is what the backward labelling never reaches, and handing every never-ending play to one player turns the draws into wins wholesale. Judge an infinite play instead by what it keeps returning to, and every draw gets a winner of its own: over the 262,144 three-node games, 15,432 send some of their draws to one player and some to the other, which no wholesale rule can do. Finding those winners takes a fixed point inside a fixed point.

 One step and four captures. Dawson's pawns on a board three ranks deep and five files wide. A White pawn steps forward on the middle file, and because a capture must be made when one is available, four captures follow: Black takes, White retakes, Black takes, White retakes. Five moves later the three middle files are finished and the two outer files are untouched, which is the octal move taking three from a heap of five and leaving two heaps of one. How it was found

The capture that has to be made

Dawson's chess is quoted as the octal game ·137, and the step from a pawn diagram to a row of counters has been taken on trust. Searched as a chess position, the diagram agrees with ·137 on every board from one file to twelve, under both endings, and every exchange it can start is an odd number of moves that lands on one of ·137's options. The whole reduction rests on one rule of the diagram that the octal code never mentions: a capture, when one is available, must be made. Make it optional and the winner changes on two, three, six and seven files.

 Four restrictions, and what each one buys. Four candidate classes of scoring game — every row, the incentive condition at the top, the same condition at every subposition, and the rows that cancel against their own negatives — scored on two families of coin rows for the mean-value bound, for comparison by subtraction, and for cancellation. Out in the world

The restriction that buys the most

Four candidate classes of scoring game, scored on the same two families and the same three questions. The class everyone expects to be tiny — the rows that cancel against their own negatives — is empty on rows of three and the widest restriction on rows of four, where it holds fifteen rows against the hereditary class's twelve and gets all 225 of its comparisons right against 108 of 144. The trade everyone expected does not exist.

 The money played out, and it never mattered. The bidding rule played move by move with a countable pool of chips, at every way of splitting it. The verdict is constant across the splits and opposite under the two ways of resolving equal bids, so what settles these positions is the tie-break rather than the money. Where it stops

The auction never gets to the money

The critical fraction is computed and never played. Played out with a countable pool of chips — twelve positions, four pool sizes, every split of the chips, every bid answered — the verdict does not move with the money on a single one of the forty-eight sweeps, and the rule for equal bids settles all forty-eight. The reason is one line long: declining every auction wins, and bidding nothing declines.

 How much of a board the endgame theory reaches. Every subset of a board's strings, counted by whether the surviving coins fall into chains and loops. The share is taken over the positions with no free box on the table, since a position with a capture available is one a player takes rather than chooses from. Out in the world

The endgame theory arrives late

Every component the chain-and-loop theory names has coins of degree two, so a position it can read is one where every surviving coin holds exactly two strings. Over a six-box board that is 1,033 of the 28,028 positions with no free box on the table — 3.7 per cent — and more than half of them only after twelve of the board's seventeen strings have been cut.

 The components the theory does not name. Grundy values of strings-and-coins components with a branching coin, grouped by the value. A chain or a loop is worth nothing on its own whatever its size; a coin with three strings takes four different values depending on its arms, and a coin with four strings is back to nothing. Out in the world

A coin with three strings is worth something

Every chain and every loop is worth nought on its own, whatever its size, and that is exactly what makes their nim-sum useless. A coin with three strings on it is worth nought, one, two or three depending on its arms — 31 of the 35 measured are not nought, and the four that are are the ones whose arms are all long. A coin with four strings is back to nought every time.

 The fee the geometry charges. The same endgames solved with the cost of declining changed. Two boxes on a chain and four on a loop are what a single cut and a pair of cuts complete; altering them changes the winner of a large share of positions, which is what says the law depends on them. Out in the world

Two and four are not conventions

Declining costs two boxes on a chain and four on a loop, and those numbers are read off the geometry rather than chosen: one cut completes the last two boxes of a chain and two cuts complete the last four of a loop. Solved again with the fee changed, 418 endgames give a different winner on up to a third of themselves — so the endgame's law is a law about the fee as much as about the shapes, and the fee is not a free parameter.

 Every region of three positions, counted. The 262,144 graphs on three positions reduced to the regions that are genuinely three positions with a cycle in them, and then split by whether the two-position vocabulary has a name for both of their sides. How it was found

Four thousand nine hundred regions with no name

Two positions give 256 regions and ten names cover every side of all of them. Three positions give 262,144 graphs, 110,934 genuine loopy regions — and 4,931 of those have a side that no name in the two-position vocabulary reproduces, with 3,990 of them named on one side and blank on the other. The count the earlier essay left open comes back in the affirmative.

 The guess, and what it covered. Two attempts to name the leftover sides out of the old vocabulary: every pair of the six stoppers, and every two-position region that is a stopper, each with small finite games added. Both cover nothing, and the count of distinct leftovers is what remains. How it was found

The names are not built out of the old ones

The guess was that a three-position region's missing names would be sums of two loopy ones — on plus over, and that family. Built and tried, every pair of the six stoppers covers none of the 4,931 regions that need one, and so does every two-position stopper there is, all seventy-nine of them with small games added. Thirteen names have to be invented, and forty-eight cover the whole census against ten at two positions.

 Two heaps and a held pass. Every pair of heaps up to 16 with one pass available that may not be the last move. Filled cells are the pairs the player to move loses: the empty board and the pairs one and two, three and four, five and six, and so on. Outlined cells are the equal pairs Nim calls lost, all of which are wins once the pass is there. Where it stops

Three heaps and a pass

Nim with a single pass that may not end the game is easy on one heap and on two: a heap swaps each odd size with the even one above it, and two heaps lose exactly at (2k − 1, 2k). On three heaps the losses are known only as a list. Fix the smallest heap and each slice of the list settles into a pattern after an irregular start — period 4, 8, 10, then 160 at a smallest heap of ten, and nothing visible from eleven.

 Cancelling is not pairing. For three sets of coin values and rows of two to seven coins, how many rows cancel against their own negatives, how many pair off as nested equal pairs, how many do both, and how many do one without the other. Out in the world

Cancelling is not pairing

The coin rows that cancel against their own negatives looked like the rows whose coins pair off as nested equal pairs, and on rows of four they are exactly those. From six coins the description fails in both directions — twenty rows pair off perfectly and do not cancel, and one coin set has a hundred and thirty-six that cancel with no pairing at all — and a row of five coins cancels, though an odd row can never pair off. What does hold, on every row swept, is that the first player in a row plus its negative never finishes behind.

 Even rows always reward the move. For four coin sets and rows of one to seven coins, the number of rows in which the player to move does at least as well as when the opponent moves first. Every even column is full. Out in the world

Even rows always reward the move

Milnor's mean-value theory needs an incentive to move — the player to move must do at least as well as if the opponent moved first. On a coin row with an even number of coins that is not a hypothesis but a theorem: the first player can collect one whole parity class of coins, and one of the two classes holds at least half the total. So the condition excludes no even row whatever the coins, the class the earlier table called 'incentive at the top' was every row of four, and the hereditary condition is a condition on odd intervals alone.

All themes