Game complexity
Game complexity
combinatorial-game-theory measures game complexity in several ways:
State-space complexity (the number of legal game positions from the initial position) #Game tree size (total number of possible games) #Decision complexity (number of leaf nodes in the smallest decision tree for initial position) #Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position) #Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large)
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. 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(mn) 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.