Combinatorial Game Theory
who wins, and by how much
Generator

Every quantifier is a move

Every quantifier is a move
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 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.

7 essays call quantifier-ladder. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

The positions it draws

6 distinct positions, harvested by running this generator again at the options each essay passed it.

PositionWorth OutcomeDrawn in
14-node reduction of a 3-variable formula — N A puzzle asks once, a game asks alternately
16-node reduction of a 3-variable formula — N A puzzle asks once, a game asks alternately · It ends, and nothing says when
17-node reduction of a 3-variable formula — P A puzzle asks once, a game asks alternately
26-node reduction of a 5-variable formula — N A puzzle asks once, a game asks alternately
6-node reduction of a 1-variable formula — N A puzzle asks once, a game asks alternately
7-node reduction of a 1-variable formula — P A puzzle asks once, a game asks alternately

Where it is called

Changing this generator changes every one of these figures.

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. What it costs

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.

 Hydras, and how long each takes to kill. Six small hydras with the ordinal the termination proof assigns to each and the exact number of chops it takes to finish it. Two of them are not finished here: the fight is guaranteed to end and the machine runs out of memory long before it does, which is the gap between a termination proof and a bound. Where it stops

It ends, and nothing says when

The recursion this site runs needs every line of play to reach a position with no moves, and the condition is usually met by an obvious decreasing quantity. The hydra meets it with no such quantity anywhere: the tree grows at nearly every step and the fight ends regardless, because the only thing that decreases is an ordinal. A four-node hydra dies in twenty chops; one level deeper and 279 chops reach forty thousand nodes with no end in sight.

 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. What it costs

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.

 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. What it costs

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.

 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. What it costs

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.

 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. What it costs

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.

 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. What it costs

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.

The whole library · The position index · The figures that play back