Bayesian Search: A Twist on Pacman

Pacman is a timeless arcade game.

Feed the hunger.

Feed the hunger.

But have you ever heard of the Bayesian search theorem?

Bayesian search utilizes Bayesian statistics to search for lost objects. For example, it’s used in finding sunken ships and lost airplanes. Bayesian search theory has been used to successfully find the USS Scorpion, a lost hydrogen bomb in 1966 Spain, and the crashed Air France Flight 447.

Bayesian search theorem can locate this wreckage.

Bayesian search theorem can locate this wreckage.

While we won’t go into detail about how Bayesian statistics here, you can read some in depth papers here and here as well as an intelligible article by FiveThirtyEight examining case studies that utilize Bayesian search theorem.

Basically, the principle of Bayesian search is that probabilities can be re-assessed with new information. This can factor in the error of the measuring device used in searching for an object. The procedure of Bayesian search involves searching areas from high to low probability, and then constantly revising probabilities based on search results and new occurrences.

Here’s a curt explanation of how the revision process works, according to Wikipedia (for more detailed, scholarly readings, check out the links above):

Suppose a grid square has a probability p of containing the wreck and that the probability of successfully detecting the wreck if it is there is q. If the square is searched and no wreck is found, then, by Bayes’ theorem, the revised probability of the wreck being in the square is given by

p'={\frac {p(1-q)}{(1-p)+p(1-q)}}=p{\frac {1-q}{1-pq}}<p.

For each other grid square, if its prior probability is r, its posterior probability is given by

r'=r{\frac {1}{1-pq}}>r.

Well, you ask, what do I do with this information?

In a fun twist, WSMA has integrated Bayesian theorem into a Bayesian Pacman Game.

Checkout the Bayesian Search Game on WSMA's website!

Checkout the Bayesian Search Game on WSMA’s website!

Here are the instructions, according to our website:

Use the arrow keys to move. An object is hidden behind a wall; hit “g” to guess a wall. The lighter the wall color, the more likely the object is behind that wall, but your measuring tool is inaccurate. Good luck, and don’t get eaten!

First, start the game by pressing “n.”

Seems like your run-of-the-mill Pacman game.

Seems like your run-of-the-mill Pacman game.

While this seems like a regular Pacman game, there’s a twist: the walls are different colors. They represent the different probability areas in Bayesian search. The lighter the color, the higher the probability of the object being there.

Avoid the ghosts!

Avoid the ghosts!

Press “g” in front of the lighter color walls to search there! After you search, the colors of the walls will change to reflect a revision in probabilities.

Scare away the ghosts.

Scare away the ghosts.

Continue in the Bayesian search procedure, and you’ll eventually succeed in the search and win the game.

You can find the game here: 

Give it a shot! The point of the game isn’t just to randomly press “g” in front of light-colored walls; that procedure illustrates the logic of Bayesian search.

Let us know how you like the game, as well as any questions or comments. Hope you have fun playing!


| July 10th, 2016 | Posted in Uncategorized |

Leave a Reply