Combinatorial games are two-player, perfect-information games with no randomness. This table contains many rulesets and known properties. I update it as I learn new things.
New: Hover over the name cell of a ruleset to see a brief description. I don't have descriptions for all of them yet.
Ruleset | Image and Variants | Partiality | Length | Initial Position Outcome Classes | Computational Complexity | Other Properties |
---|---|---|---|---|---|---|
Arimaa -- link here -- | Strictly partisan | Loopy | ? | In EXPTIME | ||
Amazons -- link here -- | Strictly partisan | Short | ? (I don't know what is considered an Initial Position.) | PSPACE-complete even with only one amazon apiece | ||
Atropos Play it: HTML -- link here -- | Impartial | Short | Open! Conjecture: N ("fuzzy") iff there are an even number of open circles. | PSPACE-complete | ||
Unrestricted Atropos -- link here -- | Impartial | Short | Open! Conjecture: N ("fuzzy") iff there are an even number of open circles. | Open; in PSPACE | ||
Chess -- link here -- | Strictly partisan | Loopy | Open | EXPTIME-complete | ||
Chomp Play it: Java -- link here -- | Impartial | Short | First Player | In PSPACE | ||
Clobber -- link here -- | Strictly partisan | Short | ? | NP-hard In PSPACE | All-Small | |
Anti-Clobber -- link here -- | Strictly partisan | Short | ? | In PSPACE | All-Small | |
Clobbineering Play it: HTML -- link here -- | Strictly partisan | Short | ? | ? | ? | |
Col Play it: Java -- link here -- | Strictly partisan | Short | No common initial position. | PSPACE-complete on both uncolored non-planar graphs and partially-colored planar graphs | Each value is a number or a number plus * | |
Proper-k-Coloring -- link here -- | Impartial | Short | No common initial position. | PSPACE-complete | ||
Oriented-k-Coloring -- link here -- | Impartial | Short | No common initial position. | PSPACE-complete | ||
Oriented-Blue-Red-Coloring -- link here -- | Impartial | Short | No common initial position. | PSPACE-complete | ||
Weak-2-Coloring -- link here -- | Impartial | Short | No common initial position. | open | ||
Distance-Coloring -- link here -- | Impartial | Short | No common initial position. | PSPACE-complete for distance 2, open for higher distance | ||
Sequential/Online Coloring -- link here -- | Impartial | Short | No common initial position. | PSPACE-complete for 3+ colors, open for 2 colors | ||
Collatz Game -- link here -- | Impartial | Unknown | ? | ? | ||
Connect Four -- link here -- | Strictly partisan | Short | First Player | In PSPACE | Draws possible | |
Constraint Logic (Bounded) -- link here -- | Strictly partisan | Short | ? | PSPACE-complete, even for planar graphs with five specific vertex types | ||
Unbounded Constraint Logic -- link here -- | Strictly partisan | Loopy | ? | EXPTIME-complete even for planar graphs with six specific vertex types | ||
Cookie Cutter -- link here -- | Impartial | Short | ? | In PSPACE | ||
Cutthroat -- link here -- | Strictly partisan | Short | No standard Starting configuration | |||
Domineering Play it: HTML AKA: Crosscram -- link here -- | Strictly partisan | Short | Varies | In PSPACE | ||
Cram -- link here -- | Impartial | Short | Odd-by-Even: First Player Even-by-Even: Second Player Odd-by-Odd: Varies | In PSPACE | ||
NoCanDo -- link here -- | Strictly partisan | Short | unknown | In PSPACE | ||
Dots-and-Boxes Play it: JavaScript -- link here -- | Strictly partisan | Short | ? | In PSPACE | Scoring play game | |
Draughts AKA: Checkers -- link here -- | Strictly partisan | Loopy | ? | EXPTIME-complete | ||
Fjords -- link here -- | Strictly partisan | Short | No standard starting configuration. | PSPACE-complete, even on planar graphs | Only the second phase of the commercial game is strictly combinatorial. | |
Flag Coloring Play it: JavaScript -- link here -- | Impartial | Short | No standard starting configuration | PSPACE-complete | ||
Flume -- link here -- | Strictly partisan | Short | ? | In PSPACE | ||
Geography AKA: Directed-Vertex Geography, Generalized Geography -- link here -- | Impartial | Short | Varies | Normal play: PSPACE-complete, even on planar graphs; Misère play: PSPACE-complete | ||
Undirected-Vertex Geography -- link here -- | Impartial | Short | Varies | Normal Play: in P, Misère play: PSPACE-complete | ||
Edge Geography AKA: Directed Edge Geography -- link here -- | Impartial | Short | Varies | PSPACE-complete | ||
Undirected Edge Geography -- link here -- | Impartial | Short | Varies | PSPACE-complete | ||
Partizan Geography -- link here -- | Strictly partisan | Short | Varies | PSPACE-complete | ||
Edge NimG -- link here -- | Impartial | Short | Varies | In EXPTIME | ||
Vertex NimG AKA: NimG-RM -- link here -- | Impartial | Short | Varies | Normal play: in P (with and without loops), Misère play: in P when loops are everywhere, but otherwise PSPACE-hard (and in EXPTIME) | ||
NimG-MR AKA: Neighboring Nim (with loops everywhere) -- link here -- | Impartial | Short | Varies | In EXPTIME, Normal play: PSPACE-hard with loops, Misère play: PSPACE-hard | ||
(Directed) VertexNim -- link here -- | Impartial | Short | Varies | Normal play: in P with self-loops everywhere, in EXPTIME otherwise. Misère play: in P | ||
Undirected VertexNim -- link here -- | Impartial | Short | Varies | Normal and Misère play: in P | ||
Go -- link here -- | Strictly partisan | Loopy | First Player | EXPTIME-complete | ||
with Superko -- link here -- | Strictly partisan | Loopy | ? | PSPACE-hard; In EXPSPACE | ||
Godomachi AKA: Congruence Matching Game -- link here -- | Impartial | Short | No standard start | In PSPACE | ||
Gomoku AKA: Go-bang, Omok, 5-in-a-row -- link here -- | Strictly partisan | Short | First player | PSPACE-complete | ||
Renju -- link here -- | Strictly partisan | Loopy | ? | ? | ||
Pente -- link here -- | Strictly partisan | Loopy | ? | ? | ||
Grundy's Game -- link here -- | Impartial | Short | varies | ? | ||
Hackenbush -- link here -- | Strictly partisan | Short | ? | NP-hard† | Hard even without green edges. | |
Hanoi Stick-Up -- link here -- | Strictly partisan | Short | ? | In PSPACE | ||
Hex Play it: Java -- link here -- | Strictly partisan | Short | No Pie Rule: First Player; With Pie Rule: Previous Player | PSPACE-complete | This version is Dicotic. | |
Rex (Misère Hex) -- link here -- | Strictly partisan | Short | Even-sized board: first player; Odd-size: previous player | In PSPACE | ||
Winner-Take-All Hex -- link here -- | Strictly partisan | Short | Same as Hex: the first player in the absence of the pie rule. | In PSPACE | ||
Adjex (Adjacent Hex) -- link here -- | Strictly partisan | Short | ? | In PSPACE. PSPACE-complete? (I believe the original reduction by Reisch still applies) | ||
Whex (Weak Hex) -- link here -- | Strictly partisan | Short | No Pie Rule: First Player | General graphs: PSPACE-complete Hex board: in PSPACE. | ||
Flex (Follow-the-Leader Hex) -- link here -- | Strictly partisan | Short | No Pie Rule: First Player | In PSPACE | ||
Only-Red Impartial Hex -- link here -- | Impartial | Short | unknown | In PSPACE | ||
Either-Color Hex -- link here -- | Impartial | Short | unknown | In PSPACE | ||
Hey That's My Fish -- link here -- | Strictly partisan | Short | Random Starting Positions | ? | Scoring Game. Has every value born by day 2. | |
Kayles (Node Kayles) -- link here -- | Impartial | Short | No standard starting positions. | PSPACE-complete | ||
Bowling Kayles Play it: Java -- link here -- | Impartial | Short | First player (more than zero pins). | In P | ||
Popping Balloons Play it: HTML -- link here -- | Impartial | Short | First player from full grid. | unknown | ||
Dawson's Kayles Play it: Java -- link here -- | Impartial | Short | ? | In PSPACE | ||
Bigraph Node Kayles -- link here -- | Strictly partisan | Short | depends | PSPACE-complete | ||
Arc Kayles -- link here -- | Impartial | Short | ? | In PSPACE | ||
Impartial Cutthroat -- link here -- | Impartial | Short | No standard starting positions. | In PSPACE | ||
Konane Play it: Java -- link here -- | Strictly partisan | Short | ? | PSPACE-complete | Contains all short game values. | |
Mad Rooks -- link here -- | Strictly partisan | Short | ? | In PSPACE | ||
Manalath -- link here -- | Strictly partisan | Short | ? | In PSPACE | ||
Martian Chess -- link here -- | Strictly partisan | Loopy | ? | ? | ||
Nim Play it: JavaScript AKA: Sticks (misere) -- link here -- | Impartial | Short | By XOR-rule. | In P | ||
Antonim -- link here -- | Impartial | Short | ? | In EXPTIME | ||
Circular Nim -- link here -- | Impartial | Short | ? | In EXPTIME | ||
Gale's Nim -- link here -- | Impartial | Short | ? | In EXPTIME | ||
Penultimate Nim -- link here -- | Impartial | Short | ? | ? | ||
Supernim -- link here -- | Impartial | Short | ? | In PSPACE | Extendable to n degrees. | |
NoGo AKA: Anti-Atari Go, NoCaptureGo -- link here -- | Strictly partisan | Short | ? | PSPACE-complete | ||
Othello Play it: JavaScript AKA: Reversi -- link here -- | Strictly partisan | Short | ? | PSPACE complete | ||
The Parity Game -- link here -- | Strictly partisan | ? | ? | ? | ||
Pentalath AKA: Ndengrod -- link here -- | Strictly partisan | ? | ? | ? | ||
Phutball Play it: Java -- link here -- | Strictly partisan | Loopy | ? | PSPACE-hard | Determining whether you can win this turn is NP-hard. | |
Quantified Boolean Formula AKA: Formula Game -- link here -- | Strictly partisan | Short | depends | PSPACE-complete on 3-CNF, but easy on 2-CNF | ||
Unrestricted QBF -- link here -- | Strictly partisan | Short | depends | PSPACE-complete on positive 11-CNF and positive 11-DNF | ||
Positive QBF -- link here -- | Strictly partisan | Short | depends | PSPACE-complete on 11-CNF and 11-DNF | ||
Partitioned Variables QBF -- link here -- | Strictly partisan | Short | depends | PSPACE-complete on CNF | ||
Positive Avoid-True -- link here -- | Impartial | Short | depends | PSPACE-complete on CNF and 2-DNF | ||
Partitioned Positive Avoid-True -- link here -- | Strictly partisan | Short | depends | PSPACE-complete on CNF and 2-DNF | ||
Positive Seek-True -- link here -- | Impartial | Short | depends | PSPACE-complete on CNF, 3-DNF | ||
Partitioned Positive Seek-True -- link here -- | Strictly partisan | Short | depends | PSPACE-complete on CNF, 3-DNF | ||
Partisan Lazy Avoid-False -- link here -- | Strictly partisan | Short | depends | PSPACE-complete on 2-CNF | ||
Lazy Avoid-False -- link here -- | Impartial | Short | depends | PSPACE-complete on 2-CNF | ||
Restricted Lazy Avoid-False -- link here -- | Impartial | Short | depends | PSPACE-complete on 4-CNF | ||
Sift -- link here -- | Strictly partisan | Short | depends | PSPACE-complete | ||
Six -- link here -- | Strictly partisan | Loopy | ? | In EXPTIME | ||
Slimetrail Play it: JavaScript -- link here -- | Strictly partisan | Short | unknown | PSPACE-complete on planar graphs | ||
Slipe -- link here -- | Strictly partisan | Loopy | unknown | In EXPTIME | ||
Snort AKA: Cats and Dogs -- link here -- | Strictly partisan | Short | depends | PSPACE-complete | ||
Either-Color Snort -- link here -- | Impartial | Short | ? | In PSPACE | ||
Sprouts Play it: Java -- link here -- | Impartial | Short | Conjecture: (with n points) Previous Player: n mod 6 = 0, 1, or 2 First Player: n mod 6 = 3, 4, or 5 | In PSPACE | ||
Brussels Sprouts -- link here -- | Impartial | Short | Odd crosses: First Player Even crosses: Second Player | In P | Value is always either 0 or *. | |
Subtraction (Game) AKA: Take Away, Nim (one pile) -- link here -- | Impartial | Short | Either player | Single pile of n's outcome class is in O(n log^2(n), which is polynomial in n, and exponential in the bit-complexity. | ||
Fibonacci Nim -- link here -- | Impartial | Short | Depends on the Zeckendorf representation of the current number. Best move is to take the smallest number in the representation. (I don't recall exactly when you lose.) | ? How long does it take to find the Zeckendorf representation? | ||
Partisan Subtraction (Game) -- link here -- | Strictly partisan | Short | Varies | NP-hard | ||
Subtract a Square -- link here -- | Impartial | Short | Varies | |||
Toads and Frogs -- link here -- | Strictly partisan | Short | No standard starting positions. | NP-hard | ||
Elephants and Rhinos -- link here -- | Strictly partisan | Short | ? | In P† | ||
Toppling Dominoes -- link here -- | Strictly partisan | Short | ? | In PSPACE | ||
Voronoi Game Play it: Java -- link here -- | Strictly partisan | Neither short nor loopy. | ? | ? | ||
Welter's Game -- link here -- | Impartial | Short | ? | ? | ||
Wythoff's Nim Play it: Java AKA: Wythoff's Game, Corner the Queen, Puppies and Kittens -- link here -- | Impartial | Short | ? | In P | ||
Xiangqi AKA: Chinese Chess -- link here -- | Strictly partisan | Loopy | ? | ?? | ||
Yavalath -- link here -- | Strictly partisan | Short | ? | In PSPACE | ||
Yodd -- link here -- | Strictly partisan | Short | ? | In PSPACE |
†unpublished or not-yet-published. (Please challenge these!)
Thanks to these people for helping me put this together! (Did I forget you? Please email me: paithanq@gmail.com.)
Here is the GitHub Repo for the underlying javascript I use to put this all together.