Game complexity
From Academic Kids

In game theory, game complexity is a measure of the complexity of a game. This article covers three measures of complexity: statespace complexity, gametree complexity, and computational complexity.
Contents 
Measures of game complexity
Statespace 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.
Gametree 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 (for example, the initial position appears in all games).
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 nbyn 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 lookup table from positions to the best move in each position.)
Example: tictactoe
A simple upper bound for the size of the state space is 3^{9} = 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 tictactoe depends on how it is generalized. A natural generalization is to m,n,kgames: 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 PSPACEcomplete.
Complexities of wellknown 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 great care. Tiny changes on 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  log(State space)  log(Game tree)  Complexity class of suitable generalized game 

Tictactoe  3  5  PSPACEcomplete 
Nine Men's Morris  10  50  ? 
Awari  12  32  ? 
Pentominoes  12  18  ? 
Connect Four  14  21  ? 
Backgammon  20  144  ? 
Checkers  21  31  EXPTIMEcomplete 
Lines of Action  24  56  ? 
Othello  28  58  PSPACEcomplete 
Chess  46  123  EXPTIMEcomplete 
Xiangqi  75  150  probably EXPTIMEcomplete 
Shogi  71  226  EXPTIMEcomplete 
Go  172  360  EXPTIMEcomplete 
See also
External links
 David Eppstein's Computational Complexity of Games and Puzzles (http://www.ics.uci.edu/~eppstein/cgt/hard.html)
References
 Stefan Reisch, Gobang ist PSPACEvollstandig (Gomoku is PSPACEcomplete). Acta Informatica, 13:5966, 1980.