Combinatorial Game Theory
who wins, and by how much
Series

Alternation — the series

6 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    A puzzle asks once, a game asks alternately

    Quantifier alternation is the whole difference between a puzzle and a game. One chooser is an existential and its answer is a witness somebody can check; two choosers taking turns is a prefix of alternating quantifiers, and the witness stops being an assignment and becomes a strategy.

    part 1 · complexity
  2. 6 turns in strict alternation, priced. One quantifier prefix taken apart into its blocks, with the size of a winning strategy computed a term at a time. A choice made after k of the opponent's turns has to be written down once for each of the 2^k lines the opponent can produce, so the total depends on where the opponent's turns sit and not merely on how many there are.

    Twelve turns, and three different prices

    The earlier essay prices a universal quantifier at a doubling and leaves it there. Twelve turns with six of them the opponent's cost 6, 63 or 384 decisions to write down, depending on nothing but the order the turns come in — and the cheap arrangements are cheap for only one of the two players. What a claim costs is the number of times the choosing changes hands.

    part 2 · complexity
  3. How many turns are choices. Every position of each game with both sides to move, classified by whether the turn is a choice at all: no move, exactly one move, several moves that all lead to the same verdict, and several that do not. Only the last is a turn at which the alternation is doing any work.

    Eleven moves and one decision

    A prefix has one quantifier a turn, so a game of eleven moves is eleven alternations. Counted on the boards themselves, a Toads and Frogs strip of eleven moves has twenty-six turns with exactly one move available and one turn anywhere at which the choice changes the answer; a Clobber board has a hundred and fourteen turns and none. Nim, the game everybody calls solved, decides at four turns in five.

    part 3 · complexity
  4. A win is proved by one move and a loss by all of them. The smallest proof of each position's verdict, averaged by verdict. At a node the mover wins the proof takes the cheapest single option; at a node the mover loses it has to answer every option, which is the existential and universal quantifiers of the prefix showing up as two different objects.

    Proving a loss means answering everything

    A win is established by one move and a loss by every move, so the two verdicts are certified by objects of different shapes. Measured over every position of four games, a loss costs between 1.07 and 2.31 times a win — a small constant, never an exponential. The obvious explanation is the branching and it is wrong: Nim answers six options at a losing turn and pays 2.18, not six.

    part 4 · complexity
  5. What the opponent's choosing is worth. Every position answered twice: against an opponent who searches, and against one following a fixed rule with no search in it. Only a loss can change, so the share is taken over the losses. The spread between games is the measurement — in one of them nearly every loss is recovered and in another none is.

    The opponent stops choosing

    Replace one player by a rule with no search in it and the question has one chooser left, which is a puzzle rather than a game. Nim recovers five of its six lost positions that way, and six of seven on three heaps of five. Domineering recovers six of a hundred and twenty-two while the fixed rule throws away a winning move eighty-eight times, and one Clobber board recovers none at all — because on that board no rule can misplay.

    part 5 · complexity
  6. A turn is not a bit. The number of turns a game lasts, beside the number of quantified bits those turns amount to. Each ply is measured over the positions actually reachable at it rather than along one line, and the bits are the logarithm of the branching, which is what a quantifier prefix would need one of.

    A turn is not a bit

    The prefix a game is read as gives each player one quantifier a turn, and a turn on a board is a choice among however many moves there are. Nim on heaps of 3, 4 and 5 lasts twelve moves and carries 23.6 bits of choice; a Toads and Frogs strip lasts eleven and carries two. Corrected for that, the model predicts a strategy 539 times too large on one board and 67 times too small on another, and the two failures have different causes.

    part 6 · complexity

All series