Editing Game complexity (section)

=== Computational complexity ===
The [[Computational complexity theory|''computational complexity'']] of a game describes the [[Asymptotic analysis|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 game|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.)

The asymptotic complexity is defined by the most efficient algorithm for solving the game (in terms of whatever [[computational resource]] one is considering). 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 [[DSPACE|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 (technically the bound is only a polynomial in this quantity; but it is usually known to be linear).
* The [[depth-first search|depth-first]] [[minimax strategy]] will use computation time proportional to the game's tree-complexity (since it must explore the whole tree), and an amount of memory polynomial in the logarithm of the tree-complexity (since the algorithm must always store one node of the tree at each possible move-depth, and the number of nodes at the highest move-depth is precisely 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.