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.
The thermograph of {5 | 1}. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake.

Temperature

  1. 1 What is at stake
  2. 2 Cooling
  3. 3 Playing the hottest
  4. 4 The same fight, eight times over
  5. 5 The first time it told somebody something
  6. +3 more
8 essays · temperature The thermograph of {5 | 1}. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake.

Thermograph

  1. 1 Reading a thermograph
  2. 2 The endgame, accounted for
  3. 3 Two hot fights that add to a cold number
  4. 4 A thermograph is built from its options'
  5. 5 A thermograph with two bends
  6. +3 more
8 essays · temperature 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 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. +2 more
7 essays · sums 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 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. +2 more
7 essays · history 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 Four rows of lamps and three winning cuts. A Nim board of four rows of up to seven lamps, lit 7, 5, 3 and 2, with each row's binary beside it. The columns add without carrying to 011, a nim-sum of 3; the three rows carrying the middle bit each have a winning cut, to 4, to 0 and to 1, and the lamps each cut would put out are shaded.

Machines

  1. 1 A machine that knew one theorem
  2. 2 A current through the board
  3. 3 A circuit asked once
  4. 4 A pairing is checked, not measured
  5. 5 The weights were not the argument
  6. +2 more
7 essays · history 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 Hex on 3 × 3, with every winning opening found. A rhombic Hex board with each cell marked according to whether taking it first wins. Left joins the top edge to the bottom and Right joins left to right; a filled board is always a win for exactly one of them, so the search needs no draw test. Strategy stealing proves that a winning opening exists without exhibiting one — these are the ones exhaustive search finds, on a board small enough for exhaustive search to finish.

Strategy stealing

  1. 1 The theorem that names a winner and no move
  2. 2 Where the needle has a sentence
  3. 3 A board one column wider
  4. 4 A potential that names every move
  5. 5 The winning reply is the fourth choice
  6. +2 more
7 essays · applied 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 the temperature that bounds the loss. Temperature runs up the page and value across it. Each wall is where a player is willing to move once a tax of that much is charged per move; above the temperature at which they meet, neither wants to move and the position is worth its mean value. The height of the meeting point is what is at stake.

Approximation

  1. 1 A rule that is never right and cannot be far wrong
  2. 2 The bound names the hottest part and the cost does not
  3. 3 The cheap fights make the rule cheaper
  4. 4 The cheapest fight is not the yardstick
  5. 5 The price of a tie
  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

All essays