Chip-firing game

Example graph with the state variables s(v) indicated
A possible finite firing sequence, with the vertex to be fired in red – the game ends as each vertex has s smaller than its degree

The chip-firing game is a one-player game on a graph which was invented around 1983 and since has become an important part of the study of structural combinatorics.

Each vertex has the number of "chips" indicated by its state variable. On each firing, a vertex is selected and one of its chips is transferred to each neighbour (vertex it shares an edge with). The number of chips on each vertex cannot be negative. The game ends when no firing is possible.