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 nodes which are connected by edges.
Each node has a certain number of "pebbles" placed on it. The graph to the right
is an example of a simple graph which has 16 nodes, 4 of which have 2 pebbles each.
Pebbles can be moved from a node to any node that is connected by an edge,
but there is a catch: moving one pebble costs an additional pebble.
So moving a pebble from a node with two pebbles to an adjacent node with zero pebbles would
result in the first node having zero pebbles and the second node having one.
(See diagram below)
|
|
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 node on the graph.
Is the graph above solvable? (Hint: Can you get one on the bottom most node?)
|
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 node on the
graph he wishes. You then have to move a pebble onto that chosen node.
You will win if you can place the pebbles such that it is possible to reach every node.
Graph pebbling problems are computationally complex mathematical problems.
Oversimplifying things a bit, 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
to solve.
This means that, for instance, adding one node 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 that by presenting puzzles to a large number of people
we will increase the chance of finding solutions. In particular, we hope that there are graph
pebbling savants out there who can just "see" the solutions.
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.
There are dozens of other human computing games, but these are the most successful so far (that we know of).
|
|
