Editing Game complexity (section)

=== Game tree size ===
The ''game tree size'' is the total number of possible games that can be played. This is the number of [[Leaf nodes#Terminology|leaf nodes]] in the [[game tree]] rooted at the game's initial position.

The game tree is typically vastly larger than the state-space because the same positions can occur in many games by making moves in a different order (for example, in a [[tic-tac-toe]] game with two X and one O on the board, this position could have been reached in two different ways depending on where the first X was placed). An upper bound for the size of the game tree can sometimes be computed by simplifying the game in a way that only increases the size of the game tree (for example, by allowing illegal moves) until it becomes tractable.

For games where the number of moves is not limited (for example by the size of the board, or by a rule about repetition of position) the game tree is generally infinite.