HomepageTeaching PageResearch PageResources Page

Combinatorial Game Rulesets

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.

Rulesets

Ruleset Image and Variants Partiality Length Initial Position Outcome Classes Computational Complexity Other Properties
Arimaa

-- link here --

Strictly partisanLoopy?In EXPTIME
Amazons
(blog post)

-- link here --

Strictly partisanShort? (I don't know what is considered an Initial Position.)PSPACE-complete even with only one amazon apiece
Atropos
Play it: HTML

-- link here --

ImpartialShortOpen! Conjecture: N ("fuzzy") iff there are an even number of open circles.PSPACE-complete
Unrestricted Atropos

-- link here --

ImpartialShortOpen! Conjecture: N ("fuzzy") iff there are an even number of open circles.Open; in PSPACE
Chess

-- link here --

Strictly partisanLoopyOpenEXPTIME-complete
Chomp
Play it: Java

-- link here --

ImpartialShortFirst PlayerIn PSPACE
Clobber
Play it: HTML, Java

-- link here --

Strictly partisanShort?
NP-hard
In PSPACE
All-Small
Anti-Clobber

-- link here --

Strictly partisanShort?In PSPACEAll-Small
Clobbineering
Play it: HTML
(blog post)

-- link here --

Strictly partisanShort???
Col
Play it: Java

-- link here --

Strictly partisanShortNo common initial position.PSPACE-complete on both uncolored non-planar graphs and partially-colored planar graphsEach value is a number or a number plus *
Proper-k-Coloring

-- link here --

ImpartialShortNo common initial position.PSPACE-complete
Oriented-k-Coloring

-- link here --

ImpartialShortNo common initial position.PSPACE-complete
Oriented-Blue-Red-Coloring

-- link here --

ImpartialShortNo common initial position.PSPACE-complete
Weak-2-Coloring

-- link here --

ImpartialShortNo common initial position.open
Distance-Coloring

-- link here --

ImpartialShortNo common initial position.PSPACE-complete for distance 2, open for higher distance
Sequential/Online Coloring

-- link here --

ImpartialShortNo common initial position.PSPACE-complete for 3+ colors, open for 2 colors
Collatz Game
(blog post)

-- link here --

ImpartialUnknown??
Connect Four

-- link here --

Strictly partisanShortFirst PlayerIn PSPACEDraws possible
Constraint Logic (Bounded)
(blog post)

-- link here --

Strictly partisanShort?PSPACE-complete, even for planar graphs with five specific vertex types
Unbounded Constraint Logic
(blog post)

-- link here --

Strictly partisanLoopy?EXPTIME-complete even for planar graphs with six specific vertex types
Cutthroat
(blog post)

-- link here --

Strictly partisanShortNo standard Starting configuration
Domineering
Play it: HTML
(blog post)

AKA: Crosscram

-- link here --

Strictly partisanShortVariesIn PSPACE
Cram

-- link here --

ImpartialShortOdd-by-Even: First Player
Even-by-Even: Second Player
Odd-by-Odd: Varies
In PSPACE
NoCanDo
(blog post)

-- link here --

Strictly partisanShortunknownIn PSPACE
Dots-and-Boxes
Play it: JavaScript

-- link here --

Strictly partisanShort?In PSPACEScoring play game
Draughts

AKA: Checkers

-- link here --

Strictly partisanLoopy?EXPTIME-complete
Fjords
(blog post)

-- link here --

Strictly partisanShortNo standard starting configuration.PSPACE-complete, even on planar graphsOnly the second phase of the commercial game is strictly combinatorial.
Flag Coloring
Play it: JavaScript

-- link here --

ImpartialShortNo standard starting configurationPSPACE-complete
Flume
(blog post)

-- link here --

Strictly partisanShort?In PSPACE
Geography

AKA: Directed-Vertex Geography, Generalized Geography

-- link here --

ImpartialShortVariesNormal play: PSPACE-complete, even on planar graphs; Misère play: PSPACE-complete
Undirected-Vertex Geography

-- link here --

ImpartialShortVariesNormal Play: in P, Misère play: PSPACE-complete
Edge Geography

AKA: Directed Edge Geography

-- link here --

ImpartialShortVariesPSPACE-complete
Undirected Edge Geography

-- link here --

ImpartialShortVariesPSPACE-complete
Partizan Geography

-- link here --

Strictly partisanShortVariesPSPACE-complete
Edge NimG

-- link here --

ImpartialShortVariesIn EXPTIME
Vertex NimG

AKA: NimG-RM

-- link here --

ImpartialShortVariesNormal 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 --

ImpartialShortVariesIn EXPTIME, Normal play: PSPACE-hard with loops, Misère play: PSPACE-hard
(Directed) VertexNim

-- link here --

ImpartialShortVariesNormal play: in P with self-loops everywhere, in EXPTIME otherwise. Misère play: in P
Undirected VertexNim

-- link here --

ImpartialShortVariesNormal and Misère play: in P
Go

-- link here --

Strictly partisanLoopyFirst PlayerEXPTIME-complete
with Superko

-- link here --

Strictly partisanLoopy?PSPACE-hard; In EXPSPACE
Godomachi

AKA: Congruence Matching Game

-- link here --

ImpartialShortNo standard startIn PSPACE
Gomoku

AKA: Go-bang, Omok, 5-in-a-row

-- link here --

Strictly partisanShortFirst playerPSPACE-complete
Renju

-- link here --

Strictly partisanLoopy??
Pente

-- link here --

Strictly partisanLoopy??
Grundy's Game

-- link here --

ImpartialShortvaries?
Hackenbush

-- link here --

Strictly partisanShort?NP-hardHard even without green edges.
Hanoi Stick-Up
(blog post)

-- link here --

Strictly partisanShort?In PSPACE
Hex
Play it: Java

-- link here --

Strictly partisanShortNo Pie Rule: First Player; With Pie Rule: Previous PlayerPSPACE-completeThis version is Dicotic.
Rex (Misère Hex)

-- link here --

Strictly partisanShortEven-sized board: first player; Odd-size: previous playerIn PSPACE
Winner-Take-All Hex

-- link here --

Strictly partisanShortSame as Hex: the first player in the absence of the pie rule.In PSPACE
Adjex (Adjacent Hex)
(blog post)

-- link here --

Strictly partisanShort?In PSPACE. PSPACE-complete? (I believe the original reduction by Reisch still applies)
Whex (Weak Hex)
(blog post)

-- link here --

Strictly partisanShortNo Pie Rule: First PlayerGeneral graphs: PSPACE-complete
Hex board: in PSPACE.
Flex (Follow-the-Leader Hex)
(blog post)

-- link here --

Strictly partisanShortNo Pie Rule: First PlayerIn PSPACE
Only-Red Impartial Hex

-- link here --

ImpartialShortunknownIn PSPACE
Either-Color Hex

-- link here --

ImpartialShortunknownIn PSPACE
Hey That's My Fish

-- link here --

Strictly partisanShortRandom Starting Positions?Scoring Game. Has every value born by day 2.
Kayles (Node Kayles)

-- link here --

ImpartialShortNo standard starting positions.PSPACE-complete
Bowling Kayles
Play it: Java

-- link here --

ImpartialShortFirst player (more than zero pins).In P
Popping Balloons
Play it: HTML

-- link here --

ImpartialShortFirst player from full grid.unknown
Dawson's Kayles
Play it: Java

-- link here --

ImpartialShort?In PSPACE
Bigraph Node Kayles

-- link here --

Strictly partisanShortdependsPSPACE-complete
Arc Kayles

-- link here --

ImpartialShort?In PSPACE
Impartial Cutthroat
(blog post)

-- link here --

ImpartialShortNo standard starting positions.In PSPACE
Konane
Play it: Java

-- link here --

Strictly partisanShort?PSPACE-completeContains all short game values.
Mad Rooks
(blog post)

-- link here --

Strictly partisanShort?In PSPACE
Manalath
(blog post)

-- link here --

Strictly partisanShort?In PSPACE
Martian Chess
(blog post)

-- link here --

Strictly partisanLoopy??
Nim
Play it: JavaScript

AKA: Sticks (misere)

-- link here --

ImpartialShortBy XOR-rule.In P
Antonim

-- link here --

ImpartialShort?In EXPTIME
Circular Nim

-- link here --

ImpartialShort?In EXPTIME
Gale's Nim

-- link here --

ImpartialShort?In EXPTIME
Penultimate Nim

-- link here --

ImpartialShort??
Supernim

-- link here --

ImpartialShort?In PSPACEExtendable to n degrees.
NoGo
(blog post)

AKA: Anti-Atari Go, NoCaptureGo

-- link here --

Strictly partisanShort?PSPACE-complete
Othello
Play it: JavaScript

AKA: Reversi

-- link here --

Strictly partisanShort?PSPACE complete
The Parity Game

-- link here --

Strictly partisan???
Pentalath

AKA: Ndengrod

-- link here --

Strictly partisan???
Phutball
Play it: Java
(blog post)

-- link here --

Strictly partisanLoopy?PSPACE-hardDetermining whether you can win this turn is NP-hard.
Quantified Boolean Formula
(blog post)

AKA: Formula Game

-- link here --

Strictly partisanShortdependsPSPACE-complete on 3-CNF, but easy on 2-CNF
Unrestricted QBF

-- link here --

Strictly partisanShortdependsPSPACE-complete on positive 11-CNF and positive 11-DNF
Positive QBF

-- link here --

Strictly partisanShortdependsPSPACE-complete on 11-CNF and 11-DNF
Partitioned Variables QBF

-- link here --

Strictly partisanShortdependsPSPACE-complete on CNF
Positive Avoid-True

-- link here --

ImpartialShortdependsPSPACE-complete on CNF and 2-DNF
Partitioned Positive Avoid-True

-- link here --

Strictly partisanShortdependsPSPACE-complete on CNF and 2-DNF
Positive Seek-True

-- link here --

ImpartialShortdependsPSPACE-complete on CNF, 3-DNF
Partitioned Positive Seek-True

-- link here --

Strictly partisanShortdependsPSPACE-complete on CNF, 3-DNF
Partisan Lazy Avoid-False

-- link here --

Strictly partisanShortdependsPSPACE-complete on 2-CNF
Lazy Avoid-False

-- link here --

ImpartialShortdependsPSPACE-complete on 2-CNF
Restricted Lazy Avoid-False

-- link here --

ImpartialShortdependsPSPACE-complete on 4-CNF
Sift

-- link here --

Strictly partisanShortdependsPSPACE-complete
Six

-- link here --

Strictly partisanLoopy?In EXPTIME
Slimetrail
Play it: JavaScript
(blog post)

-- link here --

Strictly partisanShortunknownPSPACE-complete on planar graphs
Slipe

-- link here --

Strictly partisanLoopyunknownIn EXPTIME
Snort

AKA: Cats and Dogs

-- link here --

Strictly partisanShortdependsPSPACE-complete
Either-Color Snort

-- link here --

ImpartialShort?In PSPACE
Sprouts
Play it: Java
(blog post)

-- link here --

ImpartialShortConjecture: (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 --

ImpartialShortOdd crosses: First Player
Even crosses: Second Player
In PValue is always either 0 or *.
Subtraction (Game)

AKA: Take Away, Nim (one pile)

-- link here --

ImpartialShortEither playerSingle 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 --

ImpartialShortDepends 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 partisanShortVariesNP-hard
Subtract a Square

-- link here --

ImpartialShortVaries
Toads and Frogs
(blog post)

-- link here --

Strictly partisanShortNo standard starting positions.NP-hard
Elephants and Rhinos

-- link here --

Strictly partisanShort?In P
Toppling Dominoes
(blog post)

-- link here --

Strictly partisanShort?In PSPACE
Voronoi Game
Play it: Java

-- link here --

Strictly partisanNeither short nor loopy.??
Welter's Game

-- link here --

ImpartialShort??
Wythoff's Nim
Play it: Java
(blog post)

AKA: Wythoff's Game, Corner the Queen, Puppies and Kittens

-- link here --

ImpartialShort?In P
Xiangqi

AKA: Chinese Chess

-- link here --

Strictly partisanLoopy???
Yavalath
(blog post)

-- link here --

Strictly partisanShort?In PSPACE
Yodd

-- link here --

Strictly partisanShort?In PSPACE

†unpublished or not-yet-published. (Please challenge these!)

Acknowledgements

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.