A search space is the set or domain through which an algorithm searches. In computer science, the space may be a well-defined and finite data structure. Or, as in decision theory, it may be a vast and possibly infinite set whose elements need to be individually generated during the search.

A decision tree. Each layer shows the search space for that iteration.

For example, in the game Guess Who, the players each begin with a set of character cards from which to choose. They then take turns asking yes-or-no questions about the other player's choice. The set of cards is the search space for this game. This set is finite and known ahead of time.

In chess, the search space is much more complicated. The search space is the set of all possible valid moves. For a given turn the space is finite, but the set of all possible games is infinite. Since the player is trying to maximize the probability of winning, they must search through many turns. These possibilities must be generated during the search.

In the context of AI, the search space is used to define the optimization power of the AI. Eliezer Yudkowsky defines optimization power as follows. If S is the search space and S₊ is the set of options better or equal to the chosen one, the the optimization power is

Blog posts

Measuring Optimization Power
Decision Theories: A Less Wrong Primer
Backward Reasoning Over Decision Trees

See also

Decision theory
Optimization process