State space (computer science)

[1] It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory.

Formally, a state space can be defined as a tuple [N, A, S, G] where: A state space has some common properties: For example, the Vacuum World has a branching factor of 4, as the vacuum cleaner can end up in 1 of 4 adjacent squares after moving (assuming it cannot stay in the same square nor move diagonally).

[4] For example, in the Eight queens puzzle, the state space can be calculated by counting all possible ways to place 8 pieces on an 8x8 chessboard.

This is the same as choosing 8 positions without replacement from a set of 64, or This is significantly greater than the number of legal configurations of the queens, 92.

This property is also observed in Chess, where the effective state space is the set of positions that can be reached by game-legal moves.