{"id":1722,"date":"2012-11-04T09:15:11","date_gmt":"2012-11-04T13:15:11","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1722"},"modified":"2012-11-04T09:15:11","modified_gmt":"2012-11-04T13:15:11","slug":"optimizing-angry-birds","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2012\/11\/04\/optimizing-angry-birds\/","title":{"rendered":"Optimizing Angry Birds"},"content":{"rendered":"

Most operations research competitions look at problems that are, frankly, dull. \u00a0At least to the non-OR-connoisseur. \u00a0 Whether it is optimizing computer usage<\/a>, nurse scheduling<\/a>, \u00a0financial portfolio creation<\/a>, or rescheduling airplanes<\/a>, there is a certain utilitarianism about operations research competitions. \u00a0There are some competitions that have some level of charm (predicting murders in Philadelphia<\/a> perhaps). \u00a0But, to the outsider, most of competitions sound as exciting as eating one’s\u00a0vegetables. \u00a0 Good to do, but rarely filled with anticipation.<\/p>\n

I note that our colleagues in artificial intelligence and planning have addressed this issue straight on by developing the Angry Birds Challenge<\/a>. \u00a0If you do not know the Angry Birds<\/a> game, get yourself down to the airport, sit next to any waiting business \"\"person with a tablet, and watch what they are doing: \u00a0chances are they are playing Angry Birds. Or ask any eight year old.<\/p>\n

With more than a billion downloads<\/a>, Angry Birds is one of the world’s leading wasters of computer cycles. \u00a0The game is popular enough that my wife and I went as game characters last Halloween, as you can see.<\/p>\n

To summarize, your goal in Angry Birds is to slingshot birds towards various structures in an attempt to kill pigs lurking within (really!). \u00a0Your birds have different capabilities (some might drop bombs, others can split into multiple birds), and it is necessary to use those capabilities to get to all the pigs.<\/p>\n

\"\"<\/a>The game is not as mindless as it might appear. \u00a0The underlying physics engine is very good, so the collapse of the structures when hit by the birds generally feels right. \u00a0Killing the pigs takes foresight, planning, creativity (of a\u00a0very<\/em> specialized kind), and sometimes a little luck. \u00a0So, a natural question is: can you create a computer system to play angry birds?<\/p>\n

For some human time-wasters, computer systems are very easy to create. \u00a0 It is straightforward to create a sudoku-solver far better than any human<\/a>. \u00a0For Angry Birds, it is not so clear. \u00a0There is no obvious brute-force search that has a hope of leading to a solution. \u00a0Even the problem representation seems to be a difficult issue. \u00a0This looks to be quite a challenging problem!<\/p>\n

I don’t see how to use traditional operations research methods for this problem. \u00a0But it would be great if we could show that operations research is awesome enough to solve the big problem of our time: \u00a0how to get three stars on level 4-14<\/a>!<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

Most operations research competitions look at problems that are, frankly, dull. \u00a0At least to the non-OR-connoisseur. \u00a0 Whether it is optimizing computer usage, nurse scheduling, \u00a0financial portfolio creation, or rescheduling airplanes, there is a certain utilitarianism about operations research competitions. \u00a0There are some competitions that have some level of charm (predicting murders in Philadelphia perhaps). … Continue reading “Optimizing Angry Birds”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"class_list":["post-1722","post","type-post","status-publish","format-standard","hentry","category-challenges"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1722","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1722"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1722\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1722"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1722"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1722"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}