Combinatorial Game Theory
who wins, and by how much
Ladder

Complexity — the ladder

2 distinct arguments against one idea, from the one that introduces it to the one that assumes the rest.
  1. the value of a Nim positioninstantthe Grundy value of a small subtraction gamelinearthe canonical form of a moderate positionexponential in theorywho wins a general Domineering boardno efficient methodwho wins a generalised board gamePSPACE-completecostthe definitions are constructive, so everything here is computable in principleand the practical range of an exact evaluator is a few dozen moves, which is the working constraint

    How hard is it

    Every theorem on this site stays true at any size. The answers stop being reachable long before the games get interesting — deciding the winner of a generalised board game is PSPACE-complete, and an exact evaluator gives out after a few dozen moves.

    rung 1 · limits
  2. t1x1¬x1b1t2x2¬x2b2t3x3¬x3b3cC1C2the player to move winsthe ringed vertex is where the token startsblue vertices are the existential player's choices, red the universal player's

    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.

    rung 2 · limits

All ladders