Combinatorial Game Theory
who wins, and by how much
Concept

Quantified Boolean formula — where it appears

A logical formula with alternating quantifiers, whose evaluation is the standard hard problem a game reduction targets. The alternating quantifiers are what a game's alternating moves encode, which is why games and this problem sit at the same level.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

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.

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.

complexity · Complexity 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.

complexity · Alternation 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.

complexity · Alternation 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.

complexity · Alternation

Named alongside it

The objects these essays reach for when they reach for this one.

AlternationCertificateComplexityExhaustive searchPSPACEStrategyCountingGeneralized GeographyIntractableReductionDecisionDraw

All concepts