εpsilon talk

Musings on math and education. Made with love by the Washington Student Math Association.

Bayesian Search: A Twist on Pacman

Pacman is a timeless arcade game.

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.

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

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

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

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

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.”

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.

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.

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

You can find the game here: http://www.wastudentmath.org/pages/resources/pacman.aspx 

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!