Game complexity

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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.

Example: tic-tac-toe (noughts and crosses)

For tic-tac-toe, a simple upper bound for the size of the state space is 3 9 = 19,683. (There are three states for each of the 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, removing these illegal positions, gives 5,478. 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.

Complexities of some well-known games

Due to the large size of game complexities, this table gives the ceiling of their logarithm to base 10. (In other words, the number of digits). All of the following numbers should be considered with caution: seemingly minor changes to 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.

See also

Go and mathematics Solved game Solving chess Shannon number list of NP-complete games and puzzles list of PSPACE-complete games and puzzles

David Eppstein's Computational Complexity of Games and Puzzles

Text derived from https://en.wikipedia.org/w/index.php?oldid=1377305033 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

32 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.