Pebble game
Encyclopedia
In mathematics
and computer science
, a pebble game is a type of mathematical game
played by moving "pebbles" or "markers" on a directed graph
. A variety of different pebble games exist.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a pebble game is a type of mathematical game
Mathematical game
A mathematical game is a multiplayer game whose rules, strategies, and outcomes can be studied and explained by mathematics. Examples of such games are Tic-tac-toe and Dots and Boxes, to name a couple. On the surface, a game need not seem mathematical or complicated to still be a mathematical game...
played by moving "pebbles" or "markers" on a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
. A variety of different pebble games exist.
- Graph pebblingGraph pebblingGraph pebbling is a mathematical game and area of interest played on a graph with pebbles on the vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of taking two pebbles off one vertex and placing one on an adjacent vertex...
: A certain number of pebbles are distributed among the vertices of an undirected graph; the goal is to move at least one to a particular target vertex. But to move one pebble to an adjacent vertex, another pebble at the same vertex must be discarded.
- A game known as "Black Pebbling" was developed in 1970; in it a pebble may be placed at any vertex of an acyclic digraphDirected acyclic graphIn mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
, provided that all its immediate ancestor vertices are also pebbled. (So an initial vertex with no ancestor can always be pebbled.) Pebbles may also be removed from the graph at will; the goal is to put a pebble on the target vertex while minimizing the number of pebbles in use at any time. Note that it is permitted to place a pebble on one vertex while simultaneously removing one from a parent vertex, effectively sliding the pebble. HopcroftJohn HopcroftJohn Edward Hopcroft is an American theoretical computer scientist. His textbooks on theory of computation and data structures are regarded as standards in their fields. He is the IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University.He received his...
, Wolfgang J. Paul, and ValiantLeslie ValiantLeslie Gabriel Valiant is a British computer scientist and computational theorist.He was educated at King's College, Cambridge, Imperial College London, and University of Warwick where he received his Ph.D. in computer science in 1974. He started teaching at Harvard University in 1982 and is...
showed that the number of pebbles required never exceeds n/log n for n the number of vertices of the graph. This enabled them to prove that DTIMEDTIMEIn computational complexity theory, DTIME is the computational resource of computation time for a deterministic Turing machine. It represents the amount of time that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm...
(f(n)) is contained in DSPACEDSPACEIn computational complexity theory, DSPACE or SPACE is the computational resource describing the resource of memory space for a deterministic Turing machine. It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a...
(f(n)/log f(n)) for all time-constructible f.
- A extension of "Black Pebbling", known as "Black-White Pebbling" was developed by Stephen CookStephen CookStephen Arthur Cook is a renowned American-Canadian computer scientist and mathematician who has made major contributions to the fields of complexity theory and proof complexity...
and Ravi SethiRavi SethiRavi Sethi is an Indian computer scientist retired from Bell Labs and president of Avaya Labs Research. He is best known as one of three authors of the classic computer science textbook Compilers: Principles, Techniques, and Tools, also known as the Dragon Book.Sethi was born in 1947 in Murdana,...
in a 1976 paper. It also adds white pebbles, which may be placed at any vertex at will, but can only be removed if all the vertex's immediate descendant vertices are also pebbled. The goal remains to place a black pebble on the target vertex, but the pebbling of adjacent vertices may be done with pebbles of either color.
- Takumi Kasai et al. developed a game in which a pebble may be moved along an edge-arrow to an unoccupied vertex only if a second pebble is located at a third, control vertex; the goal is to move a pebble to a target vertex. They determined the computational complexityComputational ComplexityComputational Complexity may refer to:*Computational complexity theory*Computational Complexity...
of the one and two player versions of this game, and special cases thereof. In the two-player version, the players take turns moving pebbles. There may also be constraints on which pebbles a player can move.