state space is the system in which divergent trees of possible outcomes are plotted. in a state space, there is an object and any number of operators that modify the state of the object. for example, a
chess board might be the object and the possible moves would be the operators. consider a more simple example: the object is a number and the operators either add 1 or subtract 2 from the number. if the number began at 4, then the begginning of a state space tree for it might look like this:
4
5 2
6 3 3 0
7 4 4 1 4 1 1 -2
and so on...
state space trees are often used as tool in artificial intelligence for finding the solutions to problems ranging from making a robot move across a room to playing a game of chess or checkers.
if you know the starting state of something and everything that could happen too it, it is possible to determine what it could be like at some time in the future. with this knowledge, it is possible to search for desired outcomes. the problem is that the farther down things get in a state space tree, the more pronounced the effects of a phenomenon known as combinatorial explosion are. this makes blindly stumbling through state space very innefficient. for example, by the 40th move in a game of chess, there are 10 to the 120th power different moves that could have taken place! to compensate for this, many search algorithms have evolved which try to explore only promising nodes in the search space such as bi-directional and A*. still, there are many tasks that are well beyond the range of state space, for example, an average game of go has 10 to the 800th possible outcomes, meaning that if every molecule in the universe where calculating possibilities at a rate of one hundred billion every seccond since the beginning of time, it wouldnt even be close to done and the tasks that we face in our every day life are often much more complex than a game. nonethe less, state space is a valuable tool in ai research.