Pebble game
From Wikipedia, the free encyclopedia
For the board game, see Go (game).
In mathematics and computer science, a pebble game is a type of mathematical game played by placing "pebbles" or "markers" on a directed acyclic graph according to certain rules:
- A given step of the game consists of either placing a pebble on an empty vertex or removing a pebble from a previously pebbled vertex.
- A vertex may be pebbled only if all its predecessors have pebbles.
- The objective of the game is to successively pebble each vertex of G (in any order) while minimizing the number of pebbles that are ever on the graph simultaneously.