|
[[Combinatorial game theory]] [[Computational complexity theory|measures]] '''game complexity''' in several ways:
#stateState-space complexity (the number of legal game positions from the initial position),
#gameGame tree size (total number of possible games),
#decisionDecision complexity (number of leaf nodes in the smallest decision tree for initial position),
#gameGame-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position),
#computationalComputational complexity (asymptotic difficulty of a game as it grows arbitrarily large).
These measures involve understanding game positions, possible outcomes, and computation required for various game scenarios.
The complexity of [[tic-tac-toe]] involves an upper bound of 19,683 states including illegal positions, refined to 5,478 legal ones, and 765 when considering rotational and reflective duplicates. There are up to 362,880 total games, but only 255,168 practical games, and 26,830 when accounting for duplicates. Its computational complexity is PSPACE-complete when generalizing it to m,n,k-games on an m by n board.
==Measures of game complexity==
| 