Combinatorial Game Theory
who wins, and by how much
Generator

Every formula, played both ways

Every formula, played both ways
Every formula, played both ways. One mark per quantified formula over three variables. For each one the truth value was computed directly and the geography game on the reduced graph was solved separately, and the mark is filled only where the two agree. A reduction is an argument that these two questions are the same question, and this is that argument being made to fail if it can.

One mark per quantified formula over three variables. For each one the truth value was computed directly and the geography game on the reduced graph was solved separately, and the mark is filled only where the two agree. A reduction is an argument that these two questions are the same question, and this is that argument being made to fail if it can.

2 essays call reduction-check. 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.

Where it is called

Changing this generator changes every one of these figures.

A formula, drawn as a game. 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. What it costs

Hard, proved

A game is as hard as a logical formula when the formula can be drawn as the game. Here is the drawing — a quantified formula turned into a graph with a token on it — with every formula over three variables played both ways and required to agree.

 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.

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