State-space complexity

State-space complexity refers to the number of different game-positions that can exist in a game. Game-tree complexity is normally defined as the product of the games average branching factor and the number of plies (half-moves) in an average game. The game-tree complexity is normally higher than the state space complexity due to the fact that the same position can occur in multiple games.