About Pebble It and Graph Pebbling


What is Pebble It?
Pebble It is a human computing game based on graph pebbling.


What is Graph Pebbling?

Graph pebbling can be viewed as a resource distribution and allocation problem. A graph consists of a set of vertices which are connected by edges. Each vertex has a certain number of "pebbles" placed on it. In the graph to the right, the vertices are represented by circles, diamonds, triangles, and rectangles. The numbers represent the number of pebbles on each vertex. The lines between the vertices are the edges.

Pebbles can be moved from a vertex to any vertex that is connected by an edge, but there is a catch: moving one pebble costs an additional pebble. So moving a pebble from a vertex with two pebbles to an adjacent vertex with zero pebbles would result in the first vertex having zero pebbles and the second vertex having one.


Moving one pebble costs one pebble.
Given a graph with pebbles, an important question is whether or not the graph is solvable. To be solvable, one has to be able to move at least one pebble on to any vertex on the graph. Is the graph above solvable? (Hint: The triangle vertex is the one to focus on.)
This can be viewed as an adversarial process: You are given a graph and a set of pebbles to place wherever you wish on the graph. Your adversary will choose any vertex on the graph he wishes. You then have to move a pebble onto that chosen vertex. You will win if you can place the pebbles such that it is possible to reach every vertex.

Graph pebbling problems are computationally complex mathematical problems. Essentially, computers can only solve graph pebbling puzzles by using brute force methods, looking at every possible configuration. Graph pebbling problems belong to a large class of problems called NP-Complete. Put simply, these are problems whose best known algorithms require an exponential amount of time. This means that, for instance, adding one vertex to a graph may mean an algorithm takes twice as long to solve the problem, adding two means it takes 4 times as long, adding three means it takes 8 times as long, etc.

If you are interesting in learning more about Graph Pebbling, here are some excellent web sites that we suggest.


What is Human Computing?
Human computing is using the computational power of an individual to help solve a problem. In other words, human computation involves the use of neurons, not CPUs. Human computing is employed when computers cannot solve problems efficiently. Human computing is exciting because it uses the power of the mind and the intelligent decision-making power humans possess to solve problems more efficiently than computers can.

Human computation is an emerging area of study in Computer Science, and there are already several interesting projects underway. These are not limited to the mathematical problems discussed above. There are many different things that volunteers can contribute to if they wish. To see a list of various human computing projects visit DistributedComputing.info.

Some interesting projects are:

Explain Pebble It some more.
As we already stated, Pebble It is a human computing game based on graph pebbling. Hopefully that sentence makes more sense to you now. Our overall goal is to harness the intelligent, decision-making power of the human brain to solve graph pebbling problems. We hope to benefit from the players in two ways.

First, we wish to (eventually) present large graph pebbling problems to a large number of players in the hopes that there are graph pebbling savants out there who can just "see" the solutions. Thus, we hope that some humans can contribute in a way that, at least currently, computers cannot.

Second, we wish to see what we can learn from how people play the game. As you play Pebble It, your moves are recorded. We are hoping that by observing the moves of the best players, we can discover the heuristics (the way in which people solve problems) they use and in turn use those heuristics to improve graph pebbling algorithms.

Tell me more about Human Computing Games
Several researchers have realized that one great way to get people to volunteer their brain power is to make it fun. Since men and women of all ages play games, it seems like a logical choice for recruiting participants from a wide variety of demographics. The more players that are attracted to a game--and who continue to play--the more benefit for the research project. Not many people want to help proofread books, but most people will play a game if it is fun. Some people will be even more interested in human computing games since there is a tangible outcome of their gameplay--they are helping solve real problems. If you are interested in other human computing games, we suggest:
  • Fold It is a game that lets players help predict protein structures, and will eventually let users try their hand at designing proteins. This is an important area of biology that may lead to the cure for various diseases.
  • GWAP has several different games to choose from, most of which have to do with labeling images or sounds on the web, which is a task that is difficult for computers, but for humans is quite easy.