Combinatorial Game Theory
who wins, and by how much
Depth

Series — page 4

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.
Wythoff's game, and the line the losing squares lie on. A queen moves left, down, or diagonally down-left any distance, and whoever cannot move loses. Every square carries the Grundy value the mex rule gives it. The squares worth nothing — the ones a player wants to hand over — lie along two lines whose slopes are the golden ratio and its reciprocal, in a game with no geometry and no continuous quantity in its rules.

Wythoff's game

  1. 1 Wythoff's game, and the ratio nobody put there
  2. 2 A golden ratio thirty years early
  3. 3 The digits say which move wins
  4. 4 A set with three descriptions, and a function with none
4 essays · impartial 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
3 essays · complexity The same game, written twice. A position as it arises and the same position reduced. Left would never move to −1 when 0 is available, so that option is dominated and can go. The two games are equal — checked, not assumed — and the second is the canonical form.

Canonical form

  1. 1 Canonical form
  2. 2 Two hundred and fifty-six ways to write twenty-two things
  3. 3 A factor, and not an overhead
3 essays · values Cooling by 1, and heating back. Each row is a position, its temperature, what it becomes when every move is taxed, and what comes back when the tax is refunded. The refund is not an inverse: a position whose temperature was below the tax has already frozen into a number, and heating a number does nothing at all.

Chilling

  1. 1 Cooling by exactly one
  2. 2 The operator chosen for one game
  3. 3 The operator that puts the star back
3 essays · temperature Clobber: every value smaller than every number. Blue and red stones on a small board. A move takes one of your own stones onto an orthogonally adjacent enemy stone, which is removed. Because adjacency is symmetric, a player has a move exactly when the opponent does — so no position can ever be worth a whole move to anybody, and every value that comes out is an infinitesimal.

Clobber

  1. 1 A game where nobody can be ahead in moves
  2. 2 One row of Clobber
  3. 3 When the bracket decides
3 essays · positions Mock Turtles on 8 coins: every lost position. The rows a player to move has already lost, drawn in full. A filled disc is a coin showing heads. The set is closed under turning over every coin two of its members disagree about, which is what makes it a linear code, and the count of heads in the sparsest of them is the fewest coin turns that separate two lost positions.

Codes

  1. 1 The losing positions are a code
  2. 2 The code names the move
  3. 3 The dual was the value table
3 essays · impartial Generalized Geography. A token on a directed graph. A move slides it along an edge to a vertex not yet visited, and a player who cannot move loses. That is the whole game, and deciding who wins it is as hard as anything decidable in polynomial space — which is the strongest hardness claim anybody makes about a combinatorial game.

Geography

  1. 1 A token on a graph
  2. 2 Using up the edges instead
  3. 3 Two graphs a rule cannot tell apart
3 essays · impartial 1 ko point, no ko rule. A ko fight drawn as a position graph and labelled by retrograde analysis: blue edges are Black's captures, red are White's, and each position carries the verdict for whichever side is to move. Positions the propagation never reaches are drawn — neither player can force a win and the game does not end — and they appear only where the rules permit a repetition.

Go

  1. 1 The rule that makes Go a finite game
  2. 2 A ko is won somewhere else
  3. 3 Two ways to count a finished board
3 essays · applied Every row of 8 squares, and the 36 values they hold. A census of Kōnane rows: how many arrangements of a row of squares carry each value, with the shortest row carrying that value printed beside it. Most arrangements are worth nothing at all; the rest spread over numbers, halves and quarters, stars, switches and infinitesimals — the whole vocabulary of the theory, from a game that predates it.

Kōnane

  1. 1 A game older than the theory
  2. 2 The second dimension is not the deep end
  3. 3 The two moves that are not captures
3 essays · applied What a component has to carry. Four impartial games, one of which is Nim. In the other three a component cannot say what its own legal moves are without knowing something about the past or about the rest of the board, so the Sprague–Grundy recipe does not apply — and the table says by how much. Every outcome was obtained by solving the sum outright rather than by any formula.

Memory

  1. 1 What a component has to carry
  2. 2 What restores the theorem
  3. 3 Two clauses and a third question
3 essays · limits What each heap is worth. The value of a single heap of each size. Nothing here repeats: the forms grow deeper as the heap grows, which is what stops the impartial theory's periodic table from having an analogue.

Partizan subtraction

  1. 1 Two players, two lists
  2. 2 A sequence with a rule and no period
  3. 3 The condition that survived the wider sweep
3 essays · positions A pass that may not end the game is not a component at all. The same grouping with the pass forbidden as the final move. Each group now holds several values, and a group with several values is a proof that the parts do not determine the whole.

Pass

  1. 1 A pass is not a move
  2. 2 Three heaps and a pass
  3. 3 What a component would have to carry
3 essays · limits Subtraction of 1, 3, 4 — and the window that proves the period. The Grundy values of a subtraction game, with the window that certifies the period marked. Everything after the window follows from it by induction, because a value is a mex over values at most one move back — so a finite check settles the whole infinite sequence, and the thousands of further values computed here agree with a claim that was already proved.

Periodicity

  1. 1 Four values, and the sequence is settled for ever
  2. 2 The sequence nobody has settled
  3. 3 Three bits of rule
3 essays · complexity Two numbers from the same tree. Four subtraction games, each with its Grundy sequence and its remoteness sequence. The Grundy value decides a disjunctive sum and the remoteness decides a conjunctive one; the only thing they always agree about is which heaps are losses for the player to move.

Remoteness

  1. 1 How long it lasts
  2. 2 The number nobody needs
  3. 3 A compound of two different games
3 essays · sums One of these is a game. Every length that came out of 40 random games from each starting position. Brussels Sprouts always ends after exactly five crosses less two moves, so whoever is to move at that point was decided before the first curve was drawn. Sprouts ends at different lengths depending on how it is played, which is what makes it worth playing.

Sprouts

  1. 1 Sprouts, and the game that is not one
  2. 2 A conjecture from hand play
  3. 3 What computing further has bought
3 essays · positions The same row, cut and toppled. Rows of blue and red drawn once and evaluated twice: as a Hackenbush string, where a player cuts an edge of their own colour and everything above it falls, and as Toppling Dominoes, where a player knocks one over and everything on the chosen side falls. Both values are computed by the same recursion from the two rulesets.

Toppling dominoes

  1. 1 Topple it from either end
  2. 2 How long a row a value needs
  3. 3 A recipe instead of a census
3 essays · positions Col and Snort on a path of four. One graph, two games, and one word of difference between the rules. Col forbids painting next to your own colour, which makes every move a small self-harm and drives the values towards numbers. Snort forbids painting next to your opponent's, which makes every move a land grab and drives them towards fights. Both values are computed from the same recursion.

Colouring

  1. 1 One board, two rules
  2. 2 One rule makes it cold, the other hot
2 essays · positions Grundy values for subtraction of 1, 2, 3. The Grundy value of every heap size for a take-away game, computed by the mex rule. A period, if the figure marks one, was found by searching the computed sequence rather than assumed — and where no period is marked, none was found in the range drawn, which is not the same as there being none.

Grundy sequences

  1. 2 Grundy sequences, and where they stop being predictable
  2. 3 Naming a game with a number
2 essays · impartial Comparing two positions means playing a third. Pairs of positions with the relation between them, and the game whose solution decided it. There is no way to compare two games by looking at them: the question “is G at least H?” is answered by playing G − H and asking who wins, which is a search, and its cost is counted here beside each answer.

Incentives

  1. 1 What a move is worth to the player making it
  2. 2 Nobody wants to move here
2 essays · values Grundy values for subtraction of 1, 3, 4. The Grundy value of every heap size for a take-away game, computed by the mex rule. A period, if the figure marks one, was found by searching the computed sequence rather than assumed — and where no period is marked, none was found in the range drawn, which is not the same as there being none.

Subtraction

  1. 1 Take one, three or four
  2. 2 The period is small and the proof does not say so
2 essays · impartial

All essays