Game complexity

Combinatorial game theory measures game complexity in several ways:

State-space complexity
Game tree size
Decision complexity
Game-tree complexity
Computational complexity

These measures involve understanding the game positions, possible outcomes, and computational complexity of various game scenarios.

Measures of game complexity

State-space complexity

The state-space complexity of a game is the number of legal game positions reachable from the initial position of the game.
When this is too hard to calculate, an upper bound can often be computed by also counting illegal positions.

Game tree size

The game tree size is the total number of possible games that can be played. This is the number of leaf nodes in the game tree rooted at the game's initial position.
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. 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 until it becomes tractable.
For games where the number of moves is not limited the game tree is generally infinite.

Decision trees

A decision tree is a subtree of the game tree, with each position labelled "player A wins", "player B wins", or "draw" if that position can be proved to have that value by examining only other positions in the graph. Terminal positions can be labelled directly—with player A to move, a position can be labelled "player A wins" if any successor position is a win for A; "player B wins" if all successor positions are wins for B; or "draw" if all successor positions are either drawn or wins for B.
The following two methods of measuring game complexity use decision trees:

Decision complexity

Decision complexity of a game is the number of leaf nodes in the smallest decision tree that establishes the value of the initial position.

Game-tree complexity

Game-tree complexity of a game is the number of leaf nodes in the smallest full-width decision tree that establishes the value of the initial position. A full-width tree includes all nodes at each depth. This is an estimate of the number of positions one would have to evaluate in a minimax search to determine the value of the initial position.
It is hard even to estimate the game-tree complexity, but for some games an approximation can be given by, where is the game's average branching factor and is the number of plies in an average game.

Computational complexity

The [Computational complexity theory|computational complexity] of a game 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.
The asymptotic complexity is defined by the most efficient algorithm for solving the game. The most common complexity measure, computation time, is always lower-bounded by the logarithm of the asymptotic state-space complexity, since a solution algorithm must work for every possible state of the game. It will be upper-bounded by the complexity of any particular algorithm that works for the family of games. Similar remarks apply to the second-most commonly used complexity measure, the amount of space or computer memory used by the computation. It is not obvious that there is any lower bound on the space complexity for a typical game, because the algorithm need not store game states; however many games of interest are known to be PSPACE-hard, and it follows that their space complexity will be lower-bounded by the logarithm of the asymptotic state-space complexity as well.

The depth-first minimax strategy will use computation time proportional to the game's tree-complexity, and an amount of memory polynomial in the logarithm of the tree-complexity.
Backward induction will use both memory and time proportional to the state-space complexity, as it must compute and record the correct move for each possible position.

Example: tic-tac-toe (noughts and crosses)

For tic-tac-toe, a simple upper bound for the size of the state space is 3⁹ = 19,683. 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, removing these illegal positions, gives 5,478. And when rotations and reflections of positions are considered identical, there are only 765 essentially different positions.
To bound the game tree, there are 9 possible initial moves, 8 possible responses, and so on, so that there are at most 9! or 362,880 total games. However, games may take less than 9 moves to resolve, and an exact enumeration 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. This game can be solved in DSPACE by searching the entire game tree. This places it in the important complexity class PSPACE; with more work, it can be shown to be PSPACE-complete.

Complexities of some well-known games

Due to the large size of game complexities, this table gives the ceiling of their logarithm 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 by tremendous factors, which might easily be much greater than the numbers shown.

Game	Board size	State-space complexity	Game-tree complexity	Average game length	Branching factor	Ref	Complexity class of suitable generalized game
Tic-tac-toe	9	3	5	9	4		PSPACE-complete
Sim	15	3	8	14	3.7		PSPACE-complete
Pentominoes	64	12	18	10	75		, but in PSPACE
Connect Four	42	12	21	36	4		, but in PSPACE
Kalah	14	13	18		50		Generalization is unclear
Domineering	64	15	27	30	8		, but in PSPACE; in P for certain dimensions
Congkak	14	15	33
English draughts (8x8) (checkers)	32	20 or 18	40	70	2.8		EXPTIME-complete
Awari	12	12	32	60	3.5		Generalization is unclear
Qubic	64	30	34	20	54.2		PSPACE-complete
Double dummy bridge		<17	<40	52	5.6		PSPACE-complete
Fanorona	45	21	46	44	11		, but in EXPTIME
Nine men's morris	24	10	50	50	10		, but in EXPTIME
Tablut	81	27
International draughts (10x10)	50	30	54	90	4		EXPTIME-complete
Chinese checkers	121	23			180		EXPTIME-complete
Chinese checkers	121	78			600		EXPTIME-complete
Reversi	64	28	58	58	10		PSPACE-complete
OnTop	72	88	62	31	23.77
Lines of Action	64	23	64	44	29		, but in EXPTIME
Gomoku	225	105	70	30	210		PSPACE-complete
Hex (11x11)	121	57	98	50	96		PSPACE-complete
Chess	64	44	123	70	35		EXPTIME-complete
Bejeweled and Candy Crush	64	<50			70		NP-hard
GIPF	37	25	132	90	29.3
Connect6	361	172	140	30	46000		PSPACE-complete
Backgammon	28	20	144	55	250		EXPTIME-Hard
Xiangqi	90	40	150	95	38		, believed to be EXPTIME-complete
Abalone	61	25	154	87	60		PSPACE-hard, and in EXPTIME
Havannah	271	127	157	66	240		PSPACE-complete
Twixt	572	140	159	60	452
Janggi	90	44	160	100	40		, believed to be EXPTIME-complete
Quoridor	81	42	162	91	60		, but in PSPACE
Carcassonne	72	>40	195	71	55		Generalization is unclear
Amazons (10x10)	100	40	212	84	374 or 299		PSPACE-complete
Shogi	81	71	226	115	92		EXPTIME-complete
Thurn and Taxis	33	66	240	56	879
Go (19x19)	361	170	505	211	250		EXPTIME-complete
Arimaa	64	43	402	92	17281		, but in EXPTIME
Stratego	92	115	535	381	21.739
Infinite chess	infinite	infinite	infinite	infinite	infinite		, but mate-in-n is decidable
Magic: The Gathering		at least		infinite	at least		AH-hard
Wordle	5	4.113		6			NP-hard, unknown if PSPACE-complete with parametization