Definition
Plain language
A map where every dot is one possible situation and every line is a single legal move between them.
As stated in the literature
The graph whose vertices are reachable configurations and whose edges are single legal transitions; shortest-path length in this graph defines optimal solutions and gives a ground-truth distance metric for probing representations.
Also called: state graphs
Why it matters: It provides an exact, checkable answer for how far any situation is from the goal, giving researchers ground truth to test whether a model's internal sense of progress is real.
For example, in a sliding-tile puzzle each dot is one arrangement of the tiles and each line connects two arrangements that differ by sliding a single tile.
Heard on the show
“The state graph of the Tower of Hanoi literally is that fractal.”Episode 237 — The Model Built a Perfect Map of the Puzzle, Then Lost It