Content deleted Content added
→Computational complexity: added "the" |
|||
Line 45:
The asymptotic complexity is defined by the most efficient (in terms of whatever [[computational resource]] one is considering) 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 [[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.
| |||