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).

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.

This is far smaller than the set of positions that can be achieved by placing combinations of the available chess pieces directly on the board.