The sequence of states formed by possible moves is called a
* search tree*. Each level of the tree is called a * ply *.

Since the same state may be reachable by different sequences of moves, the state space may in general be a graph. It may be treated as a tree for simplicity, at the cost of duplicating states.