{"id":108,"date":"2016-07-10T18:29:32","date_gmt":"2016-07-11T01:29:32","guid":{"rendered":"http:\/\/blog.wastudentmath.org\/?p=108"},"modified":"2016-07-10T18:29:32","modified_gmt":"2016-07-11T01:29:32","slug":"bayesian-search-a-twist-on-pacman","status":"publish","type":"post","link":"https:\/\/blog.wastudentmath.org\/index.php\/bayesian-search-a-twist-on-pacman\/","title":{"rendered":"Bayesian Search: A Twist on Pacman"},"content":{"rendered":"<p>Pacman is a timeless arcade game.<\/p>\n<div id=\"attachment_109\" style=\"width: 310px\" class=\"wp-caption aligncenter\"><a href=\"http:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/video-game-1332694_960_720.png\" rel=\"attachment wp-att-109\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-109\" class=\"size-medium wp-image-109\" src=\"http:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/video-game-1332694_960_720-300x112.png\" alt=\"Feed the hunger.\" width=\"300\" height=\"112\" srcset=\"https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/video-game-1332694_960_720-300x112.png 300w, https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/video-game-1332694_960_720-768x286.png 768w, https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/video-game-1332694_960_720.png 960w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><p id=\"caption-attachment-109\" class=\"wp-caption-text\">Feed the hunger.<\/p><\/div>\n<p>But have you ever heard of the Bayesian search theorem?<\/p>\n<p>Bayesian search utilizes <a href=\"https:\/\/en.wikipedia.org\/wiki\/Bayesian_statistics\">Bayesian statistics<\/a>\u00a0to search for lost objects. For example, it&#8217;s used in finding sunken ships and lost airplanes. Bayesian search theory has been used to successfully find the USS\u00a0<em>Scorpion<\/em>, a lost hydrogen bomb in 1966 Spain, and the crashed Air France Flight 447.<\/p>\n<div id=\"attachment_111\" style=\"width: 310px\" class=\"wp-caption aligncenter\"><a href=\"http:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/airplane-crash-569351_960_720.jpg\" rel=\"attachment wp-att-111\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-111\" class=\"size-medium wp-image-111\" src=\"http:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/airplane-crash-569351_960_720-300x225.jpg\" alt=\"Bayesian search theorem can locate this wreckage. \" width=\"300\" height=\"225\" srcset=\"https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/airplane-crash-569351_960_720-300x225.jpg 300w, https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/airplane-crash-569351_960_720-768x576.jpg 768w, https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/airplane-crash-569351_960_720.jpg 960w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><p id=\"caption-attachment-111\" class=\"wp-caption-text\">Bayesian search theorem can locate this wreckage.<\/p><\/div>\n<p>While we won&#8217;t\u00a0go into detail about how Bayesian statistics here, you can read some in depth papers <a href=\"http:\/\/www.math.washington.edu\/~morrow\/mcm\/mcm15\/38721paper.pdf\">here <\/a>and <a href=\"http:\/\/bayes.wustl.edu\/etj\/articles\/search.pdf\">here<\/a>\u00a0as well as an intelligible article by <a href=\"http:\/\/fivethirtyeight.com\/features\/how-statisticians-could-help-find-flight-370\/\">FiveThirtyEight<\/a>\u00a0examining case studies that utilize\u00a0Bayesian search theorem.<\/p>\n<p>Basically, the principle of Bayesian search is that probabilities can be re-assessed with new information. This can factor in\u00a0the error of the\u00a0measuring 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.<\/p>\n<p>Here&#8217;s a curt explanation of how the revision process works, according to Wikipedia (for more detailed, scholarly readings, check out the links above):<\/p>\n<blockquote><p>Suppose a grid square has a probability <i>p<\/i> of containing the wreck and that the probability of successfully detecting the wreck if it is there is <i>q<\/i>. If the square is searched and no wreck is found, then, by Bayes&#8217; theorem, the revised probability of the wreck being in the square is given by<\/p>\n<dl>\n<dd><img decoding=\"async\" class=\"mwe-math-fallback-image-inline\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/d695b0a12547d5bc8a6baf69344abf8147209e1a\" alt=\"p'={\\frac {p(1-q)}{(1-p)+p(1-q)}}=p{\\frac {1-q}{1-pq}}&lt;p.\" \/><\/dd>\n<\/dl>\n<p>For each other grid square, if its prior probability is <i>r<\/i>, its posterior probability is given by<\/p>\n<dl>\n<dd><img decoding=\"async\" class=\"mwe-math-fallback-image-inline\" style=\"border: none; vertical-align: -2.338ex; display: inline-block; width: 17.864ex; height: 5.676ex;\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/6d458bdeb787dfc59cc7626a2cf0387c39f75215\" alt=\"r'=r{\\frac {1}{1-pq}}&gt;r.\" \/><\/dd>\n<\/dl>\n<\/blockquote>\n<p>Well, you ask, what do I do with this information?<\/p>\n<p>In a fun twist, WSMA has integrated Bayesian theorem into a <a href=\"http:\/\/www.wastudentmath.org\/pages\/resources\/pacman.aspx\">Bayesian Pacman Game<\/a>.<\/p>\n<div id=\"attachment_121\" style=\"width: 310px\" class=\"wp-caption alignnone\"><a href=\"http:\/\/www.wastudentmath.org\/pages\/resources\/pacman.aspx\" rel=\"attachment wp-att-121\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-121\" class=\"size-medium wp-image-121\" src=\"http:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/Capture-300x206.png\" alt=\"Checkout the Bayesian Search Game on WSMA's website!\" width=\"300\" height=\"206\" srcset=\"https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/Capture-300x206.png 300w, https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/Capture-768x526.png 768w, https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/Capture.png 972w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><p id=\"caption-attachment-121\" class=\"wp-caption-text\">Checkout the Bayesian Search Game on WSMA&#8217;s website!<\/p><\/div>\n<p>Here are the instructions, according to our <a href=\"http:\/\/www.wastudentmath.org\/pages\/resources\/pacman.aspx\">website<\/a>:<\/p>\n<blockquote><p>Use the arrow keys to move. An object is hidden behind a wall; hit &#8220;g&#8221; 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&#8217;t get eaten!<\/p><\/blockquote>\n<p>First, start the game by pressing &#8220;n.&#8221;<\/p>\n<div id=\"attachment_123\" style=\"width: 251px\" class=\"wp-caption alignnone\"><a href=\"http:\/\/www.wastudentmath.org\/pages\/resources\/pacman.aspx\" rel=\"attachment wp-att-123\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-123\" class=\"size-medium wp-image-123\" src=\"http:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/step1-241x300.png\" alt=\"Seems like your run-of-the-mill Pacman game.\" width=\"241\" height=\"300\" srcset=\"https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/step1-241x300.png 241w, https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/step1.png 348w\" sizes=\"auto, (max-width: 241px) 100vw, 241px\" \/><\/a><p id=\"caption-attachment-123\" class=\"wp-caption-text\">Seems like your run-of-the-mill Pacman game.<\/p><\/div>\n<p>While this seems like a regular Pacman game, there&#8217;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.<\/p>\n<div id=\"attachment_124\" style=\"width: 253px\" class=\"wp-caption alignnone\"><a href=\"http:\/\/www.wastudentmath.org\/pages\/resources\/pacman.aspx\" rel=\"attachment wp-att-124\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-124\" class=\"size-medium wp-image-124\" src=\"http:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/step2-243x300.png\" alt=\"Avoid the ghosts!\" width=\"243\" height=\"300\" srcset=\"https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/step2-243x300.png 243w, https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/step2.png 349w\" sizes=\"auto, (max-width: 243px) 100vw, 243px\" \/><\/a><p id=\"caption-attachment-124\" class=\"wp-caption-text\">Avoid the ghosts!<\/p><\/div>\n<p>Press &#8220;g&#8221; 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.<\/p>\n<div id=\"attachment_125\" style=\"width: 254px\" class=\"wp-caption alignnone\"><a href=\"http:\/\/www.wastudentmath.org\/pages\/resources\/pacman.aspx\" rel=\"attachment wp-att-125\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-125\" class=\"size-medium wp-image-125\" src=\"http:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/step3-244x300.png\" alt=\"Scare away the ghosts.\" width=\"244\" height=\"300\" srcset=\"https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/step3-244x300.png 244w, https:\/\/blog.wastudentmath.org\/wp-content\/uploads\/2016\/07\/step3.png 347w\" sizes=\"auto, (max-width: 244px) 100vw, 244px\" \/><\/a><p id=\"caption-attachment-125\" class=\"wp-caption-text\">Scare away the ghosts.<\/p><\/div>\n<p>Continue in the Bayesian search procedure, and you&#8217;ll eventually succeed in the search and win the game.<\/p>\n<p>You can find the game here:\u00a0<a href=\"http:\/\/www.wastudentmath.org\/pages\/resources\/pacman.aspx\" target=\"_blank\">http:\/\/www.wastudentmath.org\/pages\/resources\/pacman.aspx\u00a0<\/a><\/p>\n<p>Give it a shot! The point of the game isn&#8217;t just to randomly press &#8220;g&#8221; in front of light-colored walls; that procedure illustrates the logic of Bayesian search.<\/p>\n<p>Let us know how you like the game, as well as any questions or comments. Hope you have fun playing!<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Pacman is a timeless arcade game. But have you ever heard of the Bayesian search theorem? Bayesian search utilizes Bayesian statistics\u00a0to search for lost objects. For example, it&#8217;s used in finding sunken ships and lost airplanes. Bayesian search theory has been used to successfully find the USS\u00a0Scorpion, a lost hydrogen bomb in 1966 Spain, and [&hellip;]<\/p>\n","protected":false},"author":21,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-108","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blog.wastudentmath.org\/index.php\/wp-json\/wp\/v2\/posts\/108","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.wastudentmath.org\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.wastudentmath.org\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.wastudentmath.org\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.wastudentmath.org\/index.php\/wp-json\/wp\/v2\/comments?post=108"}],"version-history":[{"count":10,"href":"https:\/\/blog.wastudentmath.org\/index.php\/wp-json\/wp\/v2\/posts\/108\/revisions"}],"predecessor-version":[{"id":133,"href":"https:\/\/blog.wastudentmath.org\/index.php\/wp-json\/wp\/v2\/posts\/108\/revisions\/133"}],"wp:attachment":[{"href":"https:\/\/blog.wastudentmath.org\/index.php\/wp-json\/wp\/v2\/media?parent=108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.wastudentmath.org\/index.php\/wp-json\/wp\/v2\/categories?post=108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.wastudentmath.org\/index.php\/wp-json\/wp\/v2\/tags?post=108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}