Game complexity
|
|
In game theory, game complexity is a measure of the complexity of a game. This article covers three measures of complexity: state-space complexity, game-tree complexity, and computational complexity.
| Contents |
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 (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 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
A simple upper bound for the size of the state space is 39 = 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 well-known 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 |
|---|---|---|---|
| Tic-tac-toe | 3 | 5 | PSPACE-complete |
| Nine Men's Morris | 10 | 50 | ? |
| Awari | 12 | 32 | ? |
| Pentominoes | 12 | 18 | ? |
| Connect Four | 14 | 21 | ? |
| Backgammon | 20 | 144 | ? |
| Checkers | 21 | 31 | EXPTIME-complete |
| Lines of Action | 24 | 56 | ? |
| Othello | 28 | 58 | PSPACE-complete |
| Chess | 46 | 123 | EXPTIME-complete |
| Xiangqi | 75 | 150 | probably EXPTIME-complete |
| Shogi | 71 | 226 | EXPTIME-complete |
| Go | 172 | 360 | EXPTIME-complete |
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 PSPACE-vollstandig (Gomoku is PSPACE-complete). Acta Informatica, 13:5966, 1980.