State-space complexity: Difference between revisions

Revision as of 05:46, 15 March 2004

Revision as of 09:50, 8 July 2004

Line 1:

#REDIRECT [[Game complexity]]

In [[game theory]], '''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.