Game complexity

Combinatorial game theory measures game complexity in several ways:

1. State-space complexity (the number of legal game positions from the initial position),
2. Game tree size (total number of possible games),
3. Decision complexity (number of leaf nodes in the smallest decision tree for initial position),
4. Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position),
5. Computational 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.