"Introduction to State Spaces"
The Painted Squares Puzzle
Towers of Hanoi
8 Puzzle
Finding a proof as a puzzle
Pentominos
States, Spaces, Goals, Moves, and Operators
State: a configuration, "snapshot' or details of a situation at a given time or point in a sequence of moves.
Space: set of all possible states for a given puzzle, problem, or game or task.
Goals: particular states that satisfy some given criteria.
Move: A single transition from one state to another that is allowed by the puzzle or problem.
Operator: A partial function on
the state space that maps each state in its domain to another state, corresponding
to some legal move. For example, in the game of chess, one operator
is "Move your leftmost pawn forward a square." Given a particular
state, this operator may cause a move or it may be inapplicable.
An Overview of the Standard Search Algorithms
Random search: at each state, determine the possible moves and select one of them at random. Continue the search from the new state.
Depth-first search: Systematically search the entire space by "walking" from the start state, backtracking only when no new states can otherwise be reached.
Breadth-first search: Systematically examining all the states at distance 0, 1, 2.... moves from the start state, in that order.
Best-first search: Among all the open states (unvisited successors of visited states) process next that state with the lowest associated heuristically evaluated cost.
Uniform-cost search: process states in order of their increasing distance (cost) from the start state -- a generalization of breadth-first search.
A* search: a variation of best-first search in which the cost function combines the distance from the start state with an estimate of the distance to the nearest goal state.
Genetic search: search in which
a "population" of states is gradually changed according to "mutation" and
"crossover" transformations with some combination of directed (by a fitness
function) and random guidance.
Designing State Representations
The data structure used to store state descriptions can greatly influence the efficiency of search.
E.g., in chess, one representation is a "board map" using a 2-d array. It's easy to compute the moves corresponding to various pieces this way.
But another representation is to
keep a list of all the pieces and what squares they're on.
When the problem doesn't have very
clear rules, the specification of the state space is a greater challenge.
Last modified: October 21, 1998
Steve Tanimoto