Computational Complexity of Games and Puzzles

Many of the games and puzzles people play are interesting because of their difficulty: it requires cleverness to solve them. Often this difficulty can be shown mathematically, in the form of computational intractibility results: every NP-complete problem is in some sense a puzzle, and conversely many puzzles are NP-complete. Two-player games often have higher complexities such as being PSPACE-complete.

WW (pp. 218-219; see references below) is disparaging of this sort of result, writing that "this asymptotic result says little about the difficulties of calculating good strategies", describing NP-hard game positions as "degenerate" and "relatively dull", and advocating (as a response to hardness proofs) looking for additional rules and conditions that would make the game easier. But to me NP-completeness is not the end but the beginning of the study of a game: it shows that the game is complex enough that we can encode interesting computational problems within it. If a game is in P, it becomes no fun once you learn "the trick" to perfect play, but hardness results imply that there is no such trick to learn: the game is inexhaustible. And of course NP-completeness or PSPACE-completeness doesn't even rule out the possibility of computing game values exactly; true, it seems to imply that worst-case-exponential algorithms are required, but there is still plenty of interesting work in designing, analyzing, and implementing such algorithms.

There is a curious relationship between computational difficulty and puzzle quality. To me, the best puzzles are NP-complete (although some good puzzles are in P, relying on gaps in human intuition rather than on computational complexity for their difficulty). Some puzzles are even harder than NP (for instance, sliding block puzzles and Sokoban are PSPACE-complete) but to me this means only that the problem can have an annoyingly long sequence of manipulations in its solution. For two-player games, one encounters a similar phenomenon at a higher level of complexity. The tree of potential interactions in a game typically gives rise to PSPACE-completeness results of a sort I find more interesting than PSPACE-completeness in puzzles. However some games are harder, EXPTIME-complete, which to me means that it may sometimes be necessary for a well-played game to go on for a tediously long sequence of moves. Perhaps some games or puzzles in which the players start with incomplete knowledge of the game or puzzle configuration might lead to other types of completeness (e.g. MA-completeness or #P-completeness) for finding the starting move most likely to succeed, but I know of no such results.

I primarily list here real games and puzzles, games that were invented to be played, rather than to be analyzed. So I'm not including some of the more artificial entries in e.g. WW or GJ, such as "sequential truth assignment". If someone can point me to a tournament for these games, a copy of the game sold in stores, or a program for people to play them against their computers, I'll consider adding them.

One caveat: NP-completeness is not a concept that applies to a single puzzle or game position, or even a finite collection of positions. It only makes sense to talk about an infinite family of problems as being NP-complete. For this reason games like chess cannot themselves be NP-complete, as they only have a finite (albeit unthinkably large) number of possible positions. In many cases however there is a natural generalization from some finite game or puzzle to an infinite family of game positions on arbitrarily large game boards, in which it makes sense to talk about NP-completeness. The fact that these infinite generalizations are computationally hard gives us some justification for believing that the original finite games are also hard in some less well-defined sense.

Index:

Puzzles and solitaire games: Alphametics; Clickomania; Cryptarithms; Cubic; 15-puzzle; Instant Insanity; KPlumber; Mah Jongg; Pearl puzzles; Rush Hour; Shanghai; Sokoban

Two-player games: Amazons; Bridge-It; Checkers; Chess; Dots and boxes; Draughts; Go; Hex; Mastermind; Othello; Phutball; Reversi; Shannon switching game; Twixt

Some useful general references:

Amazons
Description: Players move queens on an n*n board, as part of each move shooting an arrow from the moved piece. Arrows move like a chess queen when shot but are immovable afterwards. The arrows eventually block the movement of the queens; the last player to complete a move wins. Game-play combines go-like goals of surrounding territory with chess-like tactics of blocking opposing pieces' lines of play. The most commonly used starting configuration involves four queens of each color placed around the edges of a 10*10 board.

Status: PSPACE-complete. Endgames in which pieces of opposing colors are separated from each other are NP-hard.

References:

Checkers and Draughts
Description: Players move pieces diagonally forward one square at a time on alternating squares of an n*n board, removing the other players' pieces by jumping diagonally over them. Object is to leave opponent with no move by blocking or jumping all pieces. The 8*8 version is called checkers, but on larger boards it is called draughts.

Status: EXPTIME-complete.

References:

Chess
Description: This game is both too complicated and too well-known to describe here in detail, but the basic idea is to move pieces around an 8*8 board, capturing one's opponents' pieces, until the game is ended either by checkmate (one player winning by forcing the capture of the opposing player's king) or by various kinds of draws.

Status: This is a finite game, but generalizations to n*n boards are EXPTIME-complete.

References:

Cryptarithms
Description: In these puzzles, also known as alphametics, a sequence of letters is arranged in the form of an arithmetic problem, a famous example being 
    SEND
   +MORE
   -----
   MONEY
The problem is to construct a 1-1 mapping from letters to digits that makes the arithmetic work out correctly.

Status: This is a finite problem, but generalizations to bases other than decimal are NP-complete.

References:

Dots and boxes
Description: This childhood game is played with pencil and paper, starting from a drawing of a rectangular lattice of dots. The players alternately connect adjacent dots with line segments; if a player forms a four-segment square he or she scores a point and gets another move.

Status: WW describes a generalized version of the game that is NP-hard, by a reduction from finding many vertex-disjoint cycles in graphs. The same result would seem to apply as well to positions from the actual game, by specializing their reduction to trivalent planar graphs. (This is very closely related to, but not quite the same as, maximum independent sets in maximal planar graphs.)

References:

Cubic
Description: Something of a cross between Sokoban and Same Game, this puzzle involves pushing blocks left or right in a polygonal region, where they are subject to a gravity that pulls them downward whenever possible. Blocks have colors, and when multiple blocks of the same color become adjacent, they vanish. The goal is to eliminate all blocks.

Status: Friedman claims to prove that Cubic is NP-complete. His reduction clearly shows that it is NP-hard, but it is less obvious to me that it is in NP.

References:

15-puzzle
Description: 15 of the 16 positions in a 4*4 matrix are filled by tiles, leaving one unfilled hole. Tiles adjoining the hole can be shifted into the hole, the object being to form some particular permutation of the tiles (typically forming a picture out of fragments printed on the tiles).

Status: this is a finite problem, but can easily be generalized to n*n matrices. Testing whether a solution exists is in P but finding the solution with the fewest moves is NP-complete.

References:

Go
Description: This ancient game is played by placing stones on a 19*19 board. When a group of stones of one color is completely surrounded by stones of the other color, the surrounded group is removed from the board. The object is to control empty squares by surrounding them; after both players are unwilling to continue play, these squares are counted and the scores adjusted by the numbers of stones that had been removed.

Status: This is a finite game, but can be generalized to n*n boards. Even without ko (special rules related to repetition of positions) the game is PSPACE-hard; with ko (Japanese rules) it is EXPTIME-complete. It is apparently still open whether Chinese or US rules Go is EXPTIME-complete. Even certain "simple" endgames in which the go board has been decomposed into many small independent regions of play are PSPACE-hard.

References:

Hex
Description: players take turns placing pieces on a diamond-shaped board composed of hexagonal tiles. Each player owns two opposite sides of the board, and aims to connect those sides by a contiguous path of pieces.

Status: First player wins by a strategy-stealing argument but PSPACE-complete in general. The "Shannon switching game" in which pieces are placed on edges (known on the square grid as "Gale"; a related game has been sold as "Bridge-It") is in P.

References:

Instant Insanity*
Description: four multicolored cubes are to be stacked so that no color appears twice on a single side of the resulting column.

Status: This is a finite problem, but a generalized version with n cubes and n colors is NP-complete.

References:

* Trademark of Parker Brothers, Inc.

KPlumber
Description: rotate tiles containing drawings of pipes, to make the pipes form a connected network.

Status: NP-complete.

References:

Mastermind
Description: One player sets up a secret configuration of colored pins, and the other player makes a sequence of guesses about the configuration. After each guess, the player with the secret tells the other player how many many pins are correct and how many are the correct color but in the incorrect position. The object is to make as few guesses as possible.

Status: Since this game relies on secret information, it can be treated using classical game theory, but the relevant payoff matrices are so large as to make computation with them intractible. Finding a solution compatible with the guesses made so far is NP-complete; the complexity of determining whether such a solution is unique, or of playing either side of the game optimally, remain open.

References:

Othello
Description: This game (also known as Reversi) is played with reversible pieces on a square board. Players alternate placing pieces on the board, placed with the player's color up; when a piece is placed, the player also reverses lines of pieces of the opposite color sandwiched between the new piece and old pieces of the same color, so that those lines also become pieces of the player's color. The object is to have the most pieces when the board becomes filled.

Status: PSPACE-complete.

References:

Phutball
Description: Played on a Go board, with one black stone and many white stones. Players on each turn either place a single white stone on any vacant position, or make a sequence of jumps of the black stone over contiguous groups of white stones, removing the jumped stones. The object is to move the black stone to the edge of the board nearest the opponent.

Status: Testing for the existance of a winning move is NP-complete. The complexity of determining the correct outcome of a game position is PSPACE-hard.

References:

Pearl Puzzles
Description: A Japanese pencil and paper puzzle in which black and white "pearls" are placed in a square grid. The object is to draw a polygon with edges parallel to the grid lines, through all the pearls, with vertices at each black pearl and adjacent to each white pearl, but no vertices adjacent to any black pearl or at any white pearl.

Status: NP-complete.

References:

Rush Hour*
Description: This is a commercial sliding block puzzle in which pieces representing cars are placed on a 6x6 grid, with walls surrounding its perimeter except for one exit edge. The cars take up two or three adjacent grid cells, and can only move forwards or backwards. The goal is to move a specially marked target car out through the exit. Similar Java applets are available at PuzzleWorld and RhymeZone.

Status: This is a finite puzzle, but generalizations to arbitrarily large rectangles are PSPACE-complete.

References:

* Trademark of Binary Arts, Inc.

Same Game
Description: This is a computer puzzle, also known as Clickomania, in which a grid is filled with colored tiles. Contiguous groups of two or more tiles of the same color can be removed, causing the tiles above them to drop down. The goal is to remove all tiles.

Status: Solvable in polynomial time for one column of tiles. NP-complete for two or more columns and five or more colors of tiles, or five or more columns and three or more colors of tiles.

References:

Shanghai
Description: This solitaire game is played with Mah-Jongg tiles, which (like playing cards) can be arranged in groups of four similar or identical tiles. The tiles are placed randomly face-up into stacks, forming some particular shape (most computer solitaire implementations include several shapes of varying difficulty). Only the top tile of a stack is visible, although some shapes involve tiles partially covered by other tiles which can be seen but not removed. The object is to remove matching pairs of uncovered tiles until all tiles have been removed.

Status: NP-complete even if all tile positions are known. PSPACE-hard even to approximate the strategy with maximum probability of success when some tiles are covered and unknown. #P-complete to count solutions (personal communication from Michiel de Bondt).

Proof (of NP-completeness): reduction from 3-SAT. (Joint with Michiel de Bondt; an earlier reduction listed here until early 2016 was not valid.) We have a different type of tile for each variable, clause, and term (appearance of a variable in a clause) of the 3-SAT instance, with four copies of each type of tile. We arrange these into stacks of the following types:

The variable tiles can only be matched by pairing one tile from the big stack with one tile from one of the two term stacks. If this pairing is done according to a satisfying assignment, it will then be possible to match the term tiles from all of the chosen variable stacks, freeing at least one copy of each clause tile. The freed clause tiles can then be used to complete the pairing of the big stack, which in turn allows the remaining variable, term, and clause tiles to be paired. On the other hand, if there is no satisfying assignment, then there is no way of freeing one copy of each clause gadget, and the problem cannot be solved.

References:

Sokoban
Description: A warehouseman moves around a rectilinear maze, pushing pallets one at a time from initial locations scattered throughout the maze until they are all placed in a designated loading dock.

Status: PSPACE-complete.

References:

Twixt
Description: Players alternate placing vertices on a square grid. Each player's vertices may be connected with edges connecting pairs of vertices a knight's move apart. After placing a vertex, the player may remove some of his own edges or add more of them. No two edges may cross. The object is (like Hex) to connect opposite sides of the board by a path.

Status: NP-complete to determine whether a single set of vertices can support a connecting path. PSPACE-complete to determine the game value, by a reduction from Hex.

References:

Combinatorial Games, David Eppstein, ICS, UC Irvine.