movegraphs

Movegraphs are graphs in which the vertices represent configurations or states of a system, and directed edges connect states that can be reached from one another by a legal move. They provide a mathematical model of state spaces for puzzles, games, and planning problems, and can be unlabeled or labeled according to the move that induces the transition.

Construction and variants: To construct a movegraph for a given game or puzzle, one typically identifies all reachable states from a starting configuration, creates a vertex for each state, and adds a directed edge from a state to the state that results from applying each legal move. If moves are reversible, the resulting graph is undirected; if not, it remains directed. Edges may be weighted or labeled to reflect move types, costs, or constraints. Some movegraphs are finite, while others are infinite or have finite representations through symmetry reduction.

Properties and analyses: Movegraphs enable analysis of reachability, shortest-sequence problems, and planning. The diameter, degree distribution, and the structure of connected components or strongly connected components influence search difficulty. In impartial games, movegraphs underpin computation of winning positions and Sprague-Grundy numbers. Algorithms such as breadth-first search, depth-first search, and Dijkstra’s algorithm are commonly applied to movegraphs.

Applications and examples: Classic examples include the state-transition graphs of sliding-tile puzzles like the 8-puzzle and the 15-puzzle, and larger strategy games. In automated planning, movegraphs model possible action sequences. In verification and model checking, they serve as abstractions of system behaviors.

See also: state graph, state-transition diagram, state space search, graph theory.