Game complexity

In combinatorial game theory, game complexity is, quite simply, a measure of the complexity of a game. This article covers three measures of complexity: state-space complexity, game-tree complexity, and computational complexity.

Measures of game complexity

State-space complexity is the number of different possible positions that may arise in the game.

When this is too hard to calculate, an upper bound can often be computed by including illegal positions or positions that can never arise in the course of a game.

Game-tree complexity is the size of the game tree: that is, the total number of possible games that can be played. The game tree is typically vastly larger than the state space because the same positions can occur in many games by making moves in a different order (for example, in a tic-tac-toe game with two X and one O on the board, this position could have been reached in two different ways depending on where the first X was placed).

It is usually impossible to work out the size of the game tree exactly, but in some games a reasonable estimate can be made by raising the game's average branching factor to the power of the number of plies in an average game. An upper bound for the size of the game tree can sometimes be computed by simplifying the game in a way that only increases the size of the game tree (for example, by allowing illegal moves) until it becomes tractable.

Computational complexity describes the asymptotic difficulty of a game as it grows arbitrarily large, expressed in big O notation or as membership in a complexity class. This concept doesn't apply to particular games, but rather to games that have been generalized so they can be made arbitrarily large, typically by playing them on an n-by-n board. (From the point of view of computational complexity a game on a fixed size of board is a finite problem that can be solved in O(1), for example by a look-up table from positions to the best move in each position.)

Example: tic-tac-toe

For tic-tac-toe, a simple upper bound for the size of the state space is 3⁹ = 19,683. (There are three states for each cell and nine cells.) This count includes many illegal positions, such as a position with five crosses and no noughts, or a position in which both players have a row of three. A more careful count gives 5,478. When rotations and reflections of positions are considered the same, there are only 765 essentially different positions.

A simple upper bound for the size of the game tree is 9! = 362,880. (There are nine positions for the first move, eight for the second, and so on.) This includes illegal games that continue after one side has won. A more careful count gives 255,168 possible games. When rotations and reflections of positions are considered the same, there are only 26,830 possible games.

The computational complexity of tic-tac-toe depends on how it is generalized. A natural generalization is to m,n,k-games: played on an m by n board with winner being the first player to get k in a row. It is immediately clear that this game can be solved in DSPACE(mn) by searching the entire game tree. This places it in the important complexity class PSPACE. With some more work it can be shown to be PSPACE-complete.

Complexities of various games

Due to the large size of game complexities, this table gives the ceiling of their logarithms (to base 10). All of the following numbers should be considered with caution: seemingly-minor changes to the rules of a game can change the numbers (which are often rough estimates anyway) by tremendous factors, which might easily be much greater than the numbers shown.

Game	Board size (in cells)	log(State space)	log(Game tree)	Average game length (# of moves)	Complexity class of suitable generalized game
Tic-tac-toe	9	3	5	9	PSPACE-complete
Magic Fingers					PSPACE-complete
Nine Men's Morris	24	10	50	?	?, but in EXPTIME
Awari/Oware	12	16	32	?	? Generalization is not clear
Pentominoes	64	12	18	10	?, but in PSPACE
Connect Four	42	14	21	42	?, but in PSPACE
American checkers	32	21	31	?	EXPTIME-complete
International checkers	50	33	50?	?	EXPTIME-complete?
Chinese checkers (2 sets)	121	27	?	?	?, but in EXPTIME
Chinese checkers (6 sets)	121	77	?	?	?, but in EXPTIME
Lines of Action	64	24	56	?	?, but in EXPTIME
Othello	64	28	58	55	PSPACE-complete
Hex 11x11 grid	121	?	56	40	PSPACE-complete
Draw Poker* (4 players)	-	36	?	?	? Generalization is not clear
Texas hold 'em (5 players)	-	38	?	?	? Generalization is not clear
Omaha hold 'em (4 players)	-	40	?	?	? Generalization is not clear
Seven-card stud (4 players)	-	?	?	?	? Generalization is not clear
Contract bridge	-	?	?	?	? Generalization is not clear
Mahjong	-	?	?	?	? Generalization is not clear
Backgammon	28	20	144	?	? Generalization is not clear
Chess	64	46	123	40	EXPTIME-complete
Chess960	64	46	123	40?	EXPTIME-complete
Xiangqi	90	39	150	40?	EXPTIME-complete
Arimaa	64	42	190	35	?, but in EXPTIME
Shogi	81	71	226	80?	EXPTIME-complete
Connect6	361	172	140	200	PSPACE-complete?; in PSPACE
Go	361	172	360	200	EXPTIME-complete

*The Poker figures assume no jokers; table stakes, with total stakes of 1000 units per player, and no other restrictions on betting.

See also

• Solved board games
• Shannon number
• list of NP-complete games and puzzles

References

• Stefan Reisch, Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete). Acta Informatica, 13:5966, 1980.

External links

• David Eppstein's Computational Complexity of Games and Puzzles