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.
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
  4. 4 The plays do not say who chose them
4 essays · impartial Which of the two operators distributes over a sum. Cooling and heating, each asked whether applying it to a sum is the same as applying it to the parts and adding. The pools are the values born by day two and a set of deliberately hot positions; the counts are of ordered pairs.

Heating

  1. 1 Cooling adds and heating does not
  2. 2 Why cooling has to add
  3. 3 The bonus an integer is owed
  4. 4 An exemption that costs nothing below one
4 essays · temperature 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
  4. 4 The same rule on a star
4 essays · applied Three take-and-break games, three kinds of answer. The Grundy sequences of Nim, Lasker's Nim and Kayles over the first heaps. Adding a move that removes nothing takes Nim's sequence from the identity to a four-line formula; bounding how much may be taken instead takes it somewhere with no formula at all.

Lasker

  1. 1 Splitting is a move
  2. 2 The proof is sixteen cells
  3. 3 One split is enough
  4. 4 The formula is a limit
4 essays · impartial The 22 values born by day two, and the order they form. Each value sits above everything it is greater than, joined to what it covers. The order has 36 covering relations and is nine levels deep, and 52 of its 253 pairs are incomparable — and it is still a lattice: every pair has a least upper bound and a greatest lower bound among the same 22 values. Two values are marked, together with their join and their meet.

Lattice

  1. 1 The simplest game above both
  2. 2 Where the order and the sum disagree
  3. 3 Fifty-two errors and seven sizes
  4. 4 One of four questions
4 essays · values The same position, two conventions, two winners. Three-player Nim with the last counter winning. The two columns differ only in what a player does when they cannot win themselves, which is a question the rules do not answer — and the answer decides who wins.

Multiplayer

  1. 1 Three players and no answer
  2. 2 What survives a coalition
  3. 3 A coalition counts to three
  4. 4 Units modulo three, and one choice
4 essays · limits Every empty NoGo board a build can solve. The empty boards, with the value the recursion returns and the outcome that follows from it. The one-row boards run 0, star, switch and repeat, which is a pattern with no reason behind it that survives past six squares.

Nogo

  1. 1 Every group must keep breathing
  2. 2 When the regions add
  3. 3 How thick a wall has to be
  4. 4 A wall that bends
4 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
  4. 4 The table closes, until heaps of four
4 essays · limits Every impartial position is a Nim heap. A heap in a subtraction game, its Grundy value, and the Nim heap it is equivalent to. The equivalence is exact: the two positions have the same options up to value, so they behave identically in any sum, which is the Sprague–Grundy theorem.

Sprague–Grundy

  1. 1 Every impartial game is a Nim heap
  2. 2 A row of coins is already a sum
  3. 3 Two people, four years apart, one theorem
  4. 4 Where the impartial theory stops
4 essays · impartial 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. The two marks on the base line are the stops — what each player gets by moving first and playing the fight out with no tax charged at all.

Stops

  1. 1 Where the fight stops
  2. 2 The fight never runs backwards
  3. 3 The numbers it is confused with
  4. 4 Which end of the interval is open
4 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
  3. 3 Two takes, one line
  4. 4 The third take is the other two
4 essays · impartial Welter positions and what they are worth. Coins on a strip, with the Grundy value the recursion returns and the nim-sum the squares would have if they were independent heaps. The two columns are the essay: they hardly ever agree.

Welter

  1. 1 No two heaps alike
  2. 2 The pairing the formula hides
  3. 3 The pairs are read from the bottom bits
  4. 4 One square for every coin
4 essays · impartial 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 Knowing who wins is not enough. Three pairs of positions, every one of which is in outcome class N on its own. Their sums are not all the same, and not all in the same outcome class — so the outcome of a sum cannot be worked out from the outcomes of its parts, and that is why the theory needs values.

Additivity

  1. 1 Outcomes do not add
  2. 2 What a part would have to report
  3. 3 A foot is a menu, not a number
3 essays · sums 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 A hot position, split into its mean and what is left. Each row is a position cooled by exactly its own temperature — the tax at which it stops being worth moving in. The result is the mean value with something small still attached, and the last column is that something, obtained by subtracting the mean from the cooled game rather than by inspection.

Dissociation

  1. 1 A number and a fight
  2. 2 The hotter residue survives
  3. 3 Colder exactly when the residues cancel
3 essays · temperature Top Entails, one heap at a time. Each heap with the outcome of playing it alone, the Grundy value an ordinary solver would give it, and the moves that win from it. Taking the top coin of a heap forces the opponent to answer in that heap, which is a kind of move an ordinary sum of games has no room for.

Entailing

  1. 1 A move that must be answered
  2. 2 One value more than Nim
  3. 3 A compulsion that points elsewhere
3 essays · limits

All essays