This is meant to be a table of games and facts known about them. Please let me know if you can help me fill in any un-completed blocks, or if I should add a new game or a new property! I would especially like to replace question marks with "Open" for problems that are known to be open. Also, if you have any complaints about anything here (perhaps I've linked to a paper you don't agree with, etc) please let me know. My email address is located off of my home page. Thanks!
HUGE THANKS to everyone who has helped out with this, both by suggesting additions and alerting me to errors!
| Game Rules | Variant(s) | Impartial? | Short? |
Who Wins? (From Start) |
Complexity: Who can Win? |
Other Properties |
| Amazons (Play it!) (post) |
No | Yes | ? | PSPACE-complete | ||
| Atropos (Play it!) |
Yes | Yes |
Open Conjecture: First player iff even open circles. |
PSPACE-complete | ||
| Unrestricted | Yes | Yes |
Open Conjecture: First player iff even open circles. |
? | ||
| Chess | No | No | ? | EXPTIME-complete | ||
| Chomp (Play it!) |
Yes | Yes | First Player | Open | ||
| Clobber (Play it!) |
No | Yes | ? | NP-hard | Always All-Small | |
| Anti-Clobber | No | Yes | ? | ? | Always All-Small | |
| Col (Play it!) |
No | Yes | ? | ? | ||
| Snort | No | Yes | ? | ? | ||
| Collatz Game (post) |
Yes |
Open; depends partly on Collatz Conjecture |
No standard starting configuration. | Open | ||
| Connect Four* (Play it!) |
No | Yes | ? | In PSPACE | Cookie Cutter (post) |
Yes | Yes | ? | ? |
| Domineering (post) |
No | Yes | ? | ? | ||
| Cram | Yes | Yes |
Odd-by-Even board: First player Even-by-Even board: Second player Odd-by-Odd board: ? |
? | ||
| Dots and Boxes* (Play it!) |
No | Yes | ? | ? | ||
| Flume (post) |
No | Yes |
|
? | ||
| Geography | (Directed, Vertex) | Yes | Yes | No standard starting configuration. | PSPACE-complete | |
| (Undirected, Vertex) | Yes | Yes | No standard starting configuration. | In P | ||
| (Directed, Edge) | Yes | Yes | No standard starting configuration. | PSPACE-complete | ||
| (Undirected, Edge) | Yes | Yes | No standard starting configuration. | PSPACE-complete | ||
| Go | Japanese | No | No | ? | EXPTIME-complete | |
| with superko | No | No | ? |
PSPACE-hard In EXPSPACE |
||
| Hanoi Stick-Up (post) |
Yes | Yes | ? | ? | ||
| Hex (Play it!) |
No | Yes | First Player | PSPACE-complete | ||
| Rex (Misere Hex) | No | Yes |
Even-by-Even board: First player Odd-by-Odd board: Second player |
? | ||
| Adjex (Adjacent Hex) (post) |
No | Yes | ? |
In PSPACE PSPACE-complete? (I believe the original reduction by Reisch still applies) |
||
| Whex (Weak Hex) (post) |
No | Yes | First Player | PSPACE-complete on general graphs. Hex board case in PSPACE. | ||
| FLex (Follow-the-Leader Hex) (post) |
No | Yes | First Player | PSPACE-complete (same reduction as Hex). | ||
| Kayles | Dawson's (Graph) |
Yes | Yes | No standard starting configuration. | PSPACE-complete | |
| Bowling (Play it!) |
Yes | Yes | First player, if the row has more than zero pins. | In P | ||
| Konane (Play it!) |
No | Yes | ? | PSPACE-complete | ||
| Mad Rooks (post) |
No | Yes | ? | ? | ||
| Martian Chess (post) |
No | Yes | ? | ? | ||
| Nim (Play it!) |
Yes | Yes | No standard starting configuration. | In P | ||
| NoGo (post) |
No | Yes | ? | ? | ||
| Othello (Play it!) |
No | Yes | ? | ? | ||
| Phutball (post) |
No | No | ? | PSPACE-hard | NP-hard to determine whether you can win this turn. | |
| Sprouts (Play it!) (post) |
Yes | Yes |
Open Conjecture: First player when n mod 6 = 3, 4, 5. Second player when n mod 6 = 0, 1, 2. Calculated up to n = 32. |
Open | ||
| Brussels Sprouts | Yes | Yes |
Odd Crosses: first player wins Even Crosses: second player wins. |
In P | ||
| Toads and Frogs (Play it!) (post) |
No | Yes | No Standard starting configuration. | ? | ||
| Elephants and Rhinos | No | Yes | No Standard starting configuration. | ? | ||
| Toppling Dominoes (post) |
No | Yes | No Standard starting configuration. | ? | ||
| Voronoi Game (Play it!) |
No | Yes | ? | ? | ||
| Wythoff's Game (Play it!) (post) |
Yes | Yes | Known | In P |
Please visit my combinatorial game blog!
... or my homepage!