Combinatorial Game Theory
who wins, and by how much
Depth

Series — page 2

A field says what an essay is about. A series follows one idea essay by essay — from the question that introduces it to the one that assumes all the others.
Every day-three value, moved by every quarter. Four claims counted over 3,000 translations — 120 values, each moved by every quarter from −3 to 3: that adding a number leaves the temperature alone, that it shifts both stops by exactly itself, that the interval between the negated stops is where the two players are confused, and that the only failures of the last are on its endpoints.

Translation

  1. 1 What a number does to a fight
  2. 2 What an infinitesimal does to a fight
  3. 3 What a fight does to a fight
  4. 4 A bound with one number too many
  5. 5 Which end a sum lands at
  6. +3 more
8 essays · sums How much company equality needs. Each row restricts the quantifier in the definition of equality to the games named, and counts how many of the 22 values born by day two survive as distinct. The bar is the same number drawn; the jump from nine numbers to four games is the whole argument.

Universes

  1. 1 Equal in this company
  2. 2 The company that is closed
  3. 3 The closure that picks the nimbers
  4. 4 A product against a sum
  5. 5 Half a licence is nearly all of it
  6. +3 more
8 essays · limits What the auction can and cannot see. Values under both conventions. The Richman value is the share of the money the second player needs; a half means the position itself decides nothing and whoever has more money wins. Every infinitesimal on the list, and zero with them, comes out at a half.

Bidding

  1. 1 Nobody has to move
  2. 2 The auction never gets to the money
  3. 3 A coin needs no tie-break
  4. 4 Left always wins, and loses more often than not
  5. 5 Every chance but a certainty
  6. +2 more
7 essays · limits Which questions are answerable. The theory is exact and much of it is expensive. Values are computable by definition; computing one for a position of any size is a different matter, and deciding the winner of a generalised board game is complete for PSPACE — as hard as anything solvable in polynomial space.

Complexity

  1. 1 How hard is it
  2. 2 Hard, proved
  3. 3 The game with the shortest rule is the hard one
  4. 4 Nim is easy, in binary
  5. 5 "Left wins" has no short proof
  6. +2 more
7 essays · complexity Cutcake: every value an integer. The value of an m by n cake, for every small m and n. Left cuts down, Right cuts across, and neither player ever gains by moving — so nothing is ever at stake, every value is a whole number, and the number says exactly how many spare moves one player has.

Cutcake

  1. 1 Cutcake, where every value is a whole number
  2. 2 Maundy Cake
  3. 3 The size of a cake
  4. 4 Cut small unless you are behind
  5. 5 The short side only says how many
  6. +2 more
7 essays · positions 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.

Genus

  1. 1 Tame and wild
  2. 2 What a tame heap may be replaced by
  3. 3 The genus of a sum
  4. 4 The rule the symbols follow
  5. 5 A function with no formula
  6. +2 more
7 essays · limits Twenty-two codes, swept to 600 heaps. Octal codes and hexadecimal ones under the same search, which looks for a period and for a period with a constant added. The second kind occurs only in the wider family here, and a search that looks only for plain repetition reports those sequences as unsettled.

Hexadecimal

  1. 1 A period with a constant added
  2. 2 A code that climbs by three
  3. 3 The third digit
  4. 4 The only way to split into three
  5. 5 Two counters, and one displaced term
  6. +2 more
7 essays · impartial A position that comes back. Three positions whose moves lead round in a circle. Every value in this subject is defined by recursion on the options, and that recursion assumes play ends — here it need not, so the definition has nothing to stand on and the outcome may be a draw, which normal-play theory has no name for.

Loopy

  1. 1 Loopy games
  2. 2 Start at the end and work backwards
  3. 3 An outcome with no value behind it
  4. 4 One part that never ends
  5. 5 When never ending is a win
  6. +2 more
7 essays · limits The picture is the numeral. Blue-red Hackenbush strings and their values. Left may cut a blue edge, Right a red one, and everything above the cut falls. The value of each string is a number, and reading the string from the ground upward gives the binary expansion of exactly that number.

Ordinal sum

  1. 1 The other sum, the one that nests
  2. 2 When the nested sum only sees the value
  3. 3 What the colon respects
  4. 4 No fifth value
  5. 5 The proof needs both reductions
  6. +2 more
7 essays · sums What the reduction collapses. Each reduced form with the values that reduce to it. The largest class is the one that reduces to zero and it holds every infinitesimal on the list, which is exactly what the reduction is for — against a hot background, none of them is distinguishable from nothing.

Reduced form

  1. 1 What is left when the small change is thrown away
  2. 2 How hot a background has to be
  3. 3 Add, then reduce again
  4. 4 The option nothing names
  5. 5 Not a domination, in that order
  6. +2 more
7 essays · sums 7 positions of the same value, and how long each of them lasts. Nim positions whose heap sizes all nim-sum to zero. As games they are the same object: each is worth zero, each is a loss for the player to move, and each may be substituted for any other inside any sum without changing a single outcome. The bars are how many moves each one takes, from the shortest legal play to the longest. The value determines everything about who wins and nothing at all about when.

Tempo

  1. 1 What a value leaves out
  2. 2 How many moves are worth making
  3. 3 What a strategy has to remember
  4. 4 Three rules and a tie-break
  5. 5 Seventy-two of them were not silence
  6. +2 more
7 essays · values Every quantifier is a move. A quantified boolean formula with its quantifiers drawn as turns: an existential is a choice by the player to move, a universal a choice by the opponent. The same formula is put through the reduction to Generalized Geography and the two answers are checked against each other, so the prefix of quantifiers and the game beside it are one claim.

Alternation

  1. 1 A puzzle asks once, a game asks alternately
  2. 2 Twelve turns, and three different prices
  3. 3 Eleven moves and one decision
  4. 4 Proving a loss means answering everything
  5. 5 The opponent stops choosing
  6. +1 more
6 essays · complexity Bouton's invariant, checked over 512 positions. Nim positions in binary, one column per bit. Bouton's 1901 argument is that a position is a loss for the mover exactly when every column holds an even number of marks — and that from such a position every move breaks a column, while from any other position some move repairs them all. Both halves are checked here over every position in the range rather than illustrated once, and the middle row shows the repairing move being made.

Bouton

  1. 1 The theorem that needed none of the theory
  2. 2 Three complete solutions in nine years
  3. 3 A set with a short description
  4. 4 The sentence that solved the other convention
  5. 5 The step nobody took for thirty-four years
  6. +1 more
6 essays · history Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does.

Comparison

  1. 1 Comparing positions
  2. 2 Comparing two positions means playing a third
  3. 3 Confused is not the same as unknown
  4. 4 How rare it is to be bigger
  5. 5 A floor, and not a decline
  6. +1 more
6 essays · sums The Grundy values of ·137, and the exceptions to its period. An octal game's Grundy sequence, with the periodic part in gold and the exceptions in magenta. The exceptions are the point: a sequence described as eventually periodic contains values that disagree with the value one period later and always will, so the period is a statement about a tail and not about the sequence. The rule used to identify an exception is printed, because published lists of them differ by which convention was used.

Dawson

  1. 1 A chess problem that turned out to be an octal game
  2. 2 What the arithmetic cost in 1956
  3. 3 The convention Dawson actually used
  4. 4 The capture that has to be made
  5. 5 A wall the pawns cannot cross and the rule can
  6. +1 more
6 essays · history A position is the sum of its parts. Four separate Hackenbush sprigs. A move is a move in one of them, so the position is their disjunctive sum, and its value is the sum of their values. Which part to play in is the entire decision, and the values are what makes it decidable.

Disjunctive sum

  1. 1 The sum is the object
  2. 2 Which part to move in
  3. 3 Three ways to add the same games
  4. 4 Independence is a claim
  5. 5 How wrong a nearly-independent split is
  6. +1 more
6 essays · sums What reversing the ending destroys. Everything that makes normal play tractable is a theorem about who moves last, and misère play contradicts every one of them. The positions are unchanged; the means of evaluating them is gone, and what replaces it is far heavier.

Misère play

  1. 1 Misère play
  2. 2 What survives misère play
  3. 3 "Hopeless" was a claim about a method
  4. 4 Misère play has no negatives
  5. 5 Two misère outcomes are not enough
  6. +1 more
6 essays · limits The gaps of ⟨5, 7⟩, which are the moves. A Sylver Coinage position drawn as the numerical semigroup it is. Gold squares are the numbers already named; plain squares are sums of them, and so cannot be named again; magenta squares are the gaps, which are exactly the legal moves. The largest gap is the Frobenius number, marked F — past it every integer is reachable, which is why the game has finitely many moves left and must end.

Sylver

  1. 1 The game that is a number system
  2. 2 A parity with a first exception
  3. 3 Every move closes the largest gap
  4. 4 The pairing removes moves it cannot name
  5. 5 A shortlist with nothing at the top
  6. +1 more
6 essays · applied Where running out of moves is permanent. Eleven rulesets, each walked position by position from three small boards, with every position at which a player has no move examined for whether any continuation gives them one back. Nothing here is evaluated: dead-ending is a property of the rules, and two boards worth the same value can differ on it. 9 of the 11 are dead-ending and 2 are not.

Dead-ending

  1. 1 Nobody comes back
  2. 2 What the class does not buy
  3. 3 Wrong in one direction only
  4. 4 The clause that turns the class off
  5. 5 A quotient that identifies nothing
5 essays · limits The picture is the numeral. Blue-red Hackenbush strings and their values. Left may cut a blue edge, Right a red one, and everything above the cut falls. The value of each string is a number, and reading the string from the ground upward gives the binary expansion of exactly that number.

Hackenbush

  1. 1 Hackenbush is a numeral
  2. 2 Squash every loop to a point
  3. 3 A green edge on a blue one
  4. 4 A tree is still a number
  5. 5 Where the numeral stops
5 essays · positions

All essays