State space (computer science)

The size of the state space for a given system is the number of possible configurations of the space.[3]

If the size of the state space is finite, calculating the size of the state space is a combinatorial problem.[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

${\displaystyle {\binom {64}{8}}=4,426,165,368}$

This is significantly greater than the number of legal configurations of the queens, 92. In many games the effective state space is small compared to all reachable/legal states. 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.

All continuous state spaces can be described by a corresponding continuous function and are therefore infinite.[3] Discrete state spaces can also have (countably) infinite size, such as the state space of the time-dependent "counter" system,[2] similar to the system in queueing theory defining the number of customers in a line, which would have state space {0, 1, 2, 3, ...}.

A search state is a compressed representation of a world state in a state space, and is used for exploration. Search states are used because a state space often encodes more information than is necessary to explore the space. Compressing each world state to only information needed for exploration improves efficiency by reducing the number of states in the search.[5] For example, a state in the Pacman space includes information about the direction Pacman is facing (up, down, left, or right). Since it does not cost anything to change directions in Pacman, search states for Pacman would not include this information and reduce the size of the search space by a factor of 4, one for each direction Pacman could be facing.

Standard search algorithms are effective in exploring discrete state spaces. The following algorithms exhibit both completeness and optimality in searching a state space.[5][6]

• Breadth-First Search
• A* Search
• Uniform Cost Search

These methods do not extend naturally to exploring continuous state spaces. Exploring a continuous state space in search of a given goal state is equivalent to optimizing an arbitrary continuous function which is not always possible, see mathematical optimization.