Combinatorial Game Theory
who wins, and by how much
Depth

Series — page 3

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.
A board in pieces costs the sum, not the product. A Domineering board with squares blocked out, so that it falls into regions no domino can span. The number of positions in the whole board is exactly the product of the numbers in its regions — which is why evaluating the regions separately, and adding the values, is an exponential saving rather than a tidier way of writing the same search.

Decomposition

  1. 1 The board falls apart, and the arithmetic changes
  2. 2 Finding the parts
  3. 3 How often a board falls apart
  4. 4 A wall an amazon can walk through
  5. 5 Pieces that can only come apart
  6. +1 more
6 essays · complexity 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 Classes needed, as the heaps get bigger — Dawson's chess ·137. How many kinds of position there are, against how large a heap the universe allows. Under normal play the answer stops growing as soon as the Grundy values stop growing. Under misère play it does not stop, and every new class is a pair of positions that behave identically under normal play and differently under misère.

Misere cost

  1. 1 The cost is in the closure, not in the positions
  2. 2 A misère sum is searched, not added
  3. 3 Two heaps of testing are enough
  4. 4 Twelve classes, seven questions
  5. 5 A staircase, not a slope
  6. +1 more
6 essays · complexity One node per route, one node per position. For each board, the number of nodes in the recursion tree a solver with no memo table would walk, beside the number of distinct positions that tree contains, beside the longest run of moves in it. The first number is the cost of forgetting; the second is the size of the table that avoids it; the third is the stack, and it stays small however the other two grow.

Search

  1. 1 A position reached eleven ways is one position
  2. 2 The order a solver tries the moves in
  3. 3 A verdict that changes with the depth
  4. 4 Where a search may stop
  5. 5 Search on in pairs of moves
  6. +1 more
6 essays · complexity a path with every link doubled: the criterion and the game. A Shannon switching graph with the two marked vertices in gold. Short secures links and Cut deletes them; Short wins by joining the two marks. Lehman's criterion says Short wins moving second exactly when some subgraph holding both marks splits into two edge-disjoint spanning trees — drawn here in blue and red where one exists. The verdicts beside the graph come from playing the game out, and the criterion is computed without looking at the game at all.

Switching

  1. 1 A winning strategy that is a spanning tree
  2. 2 The first move is a link that is not there
  3. 3 Cut is Short on another graph
  4. 4 A point with three neighbours
  5. 5 Two neighbours keep a pairing, three lose it
  6. +1 more
6 essays · applied A blocked file, and the tempo it holds. Files of a blocked pawn ending: a White pawn below, a Black pawn above, and a gap between them that either side may close one square at a time. Each file carries the value the game recursion gives it. With only single steps available a file is worth a star or nothing, by the parity of the gap, so the whole position is tempo and no material at all — which is what a chess player means by mutual zugzwang.

Chess

  1. 1 A pawn ending is a sum
  2. 2 What has to break before a pawn is worth a number
  3. 3 One king, and two files to be in
  4. 4 A position with no value, and the rule that gives it one
  5. 5 A win is not a way of winning
5 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 Folding a 4×4 board by its symmetries. The size of a Domineering solver's table when positions related by a board symmetry are stored once. The saving rises toward the size of the symmetry group and stops there — it is a constant factor by construction, and no board is large enough to make it anything else.

Identification

  1. 1 What counts as the same position, and what that is worth
  2. 2 What it costs to notice a repetition
  3. 3 A key shorter than the position
  4. 4 A check bit halves the average and not the key
  5. 5 A key is a code, and two squares come free
5 essays · complexity Smaller than every positive number, and not zero. Values that sit between zero and every positive number, each compared with zero and with 1/1024. Every relation drawn was computed by playing the difference, and one of them is confusion — neither greater, smaller nor equal. None of these is a number, and in a close game they are the entire margin.

Infinitesimals

  1. 1 Infinitesimals
  2. 2 How many ups
  3. 3 Tiny, miny, and the sizes below every size
  4. 4 The class where nobody runs out first
  5. 6 When the ups add
5 essays · values Nim with heaps of 3, 5, 7. Heaps of counters; a move takes any number from one heap. The position is a loss for the player to move exactly when the binary digits of the heap sizes cancel in every column — the nim-sum — and that is the whole of the theory of Nim.

Nim

  1. 1 Nim, and the nim-sum
  2. 2 The move that gives counters back
  3. 3 The nimbers multiply
  4. 4 The tartan theorem
  5. 5 Four hundred and seventy steps
5 essays · impartial 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
  4. 4 A repetition is a guess
  5. 5 Growing is not climbing
5 essays · complexity How the word is made. The Prouhet–Thue–Morse word built by doubling. Each row of one, two, four up to thirty-two letters is the row above followed by its swap, which is the same word obtained by replacing A with AB and B with BA.

Repetition

  1. 1 A rule that let the game run for ever
  2. 2 How strict a rule can be
  3. 3 The opponent makes it repeat
  4. 4 What counting positions buys
  5. 5 The number in the rule
5 essays · history The reduction that puts options back. How the two reductions change the width of a form. Domination only ever removes an option. Bypassing a reversible option substitutes the answer's whole option list, so it can leave the form wider than it started — and the finished canonical form can be wider than the form it came from.

Reversibility

  1. 1 The reduction that puts options back
  2. 2 How wide a form can get
  3. 3 What a value costs to write down
  4. 4 The same position, written once
  5. 5 A reduction that reads a graph
5 essays · values What the rule costs. Every sum of three components from a fixed pool, played out twice: once with one side following the rule "move where the stake is largest" and once with both sides evaluating exactly. The rule is not optimal, the gap is bounded, and the bound is the largest temperature on the board.

Strategy

  1. 1 A rule with a guarantee
  2. 2 A rule with no promise at all
  3. 3 A pool built to punish greed
  4. 4 A schedule instead of a number
  5. 5 An environment instead of a stack
5 essays · temperature Poker Nim from 3, 5, 7, with reserves of 4 and 4. Nim with one extra kind of move: a player may put any number of counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. They cannot, and the winner is decided by exactly the same nim-sum as ordinary Nim — checked here over every position within a stated range rather than argued.

Termination

  1. 1 The condition the recursion rests on
  2. 2 It ends, and nothing says when
  3. 3 Two ways to end with no bound
  4. 4 Which games end at which level
  5. 5 No number bounds it
5 essays · limits Toads and frogs. Toads move right and frogs move left, one square into a gap or hopping over exactly one opponent. A player unable to move loses. It can be played on squared paper by anybody, and its values are immediately stranger than the game looks.

Toads and Frogs

  1. 1 Toads and Frogs
  2. 2 The strip nobody has a formula for
  3. 3 The same strip without the jump
  4. 4 The strip where every number is a whole one
  5. 5 The square that cannot be halved
5 essays · positions End-Nim: a player at each end of the row. Rows of heaps in which Left may take from the leftmost heap and Right from the rightmost. The value beside each row was computed by the game recursion and reduced to canonical form; the outcome beside it says who wins. A single heap is a Nim heap, because both players may take from it — and that is the last thing about this game that looks like Nim.

End-Nim

  1. 1 Taking from the ends
  2. 2 Where the nimbers run out
  3. 3 The rows that are their own mirror
  4. 4 A game with nothing at stake
4 essays · positions Every heap up to 40, won or lost. Heap sizes with the outcome for the player who moves first. The lost ones are shaded; they are exactly the Fibonacci numbers, which is a fact about a game with one heap, no board and no geometry in it anywhere.

Fibonacci nim

  1. 1 The heap is not the position
  2. 2 The family the Fibonacci numbers belong to
  3. 3 What the numerals knew
  4. 4 One proof, and one wrong lemma
4 essays · impartial

All essays