<body><script type="text/javascript"> function setAttributeOnload(object, attribute, val) { if(window.addEventListener) { window.addEventListener('load', function(){ object[attribute] = val; }, false); } else { window.attachEvent('onload', function(){ object[attribute] = val; }); } } </script> <div id="navbar-iframe-container"></div> <script type="text/javascript" src="https://apis.google.com/js/plusone.js"></script> <script type="text/javascript"> gapi.load("gapi.iframes:gapi.iframes.style.bubble", function() { if (gapi.iframes && gapi.iframes.getContext) { gapi.iframes.getContext().openChild({ url: 'https://www.blogger.com/navbar.g?targetBlogID\x3d10192368\x26blogName\x3dChrno\x26publishMode\x3dPUBLISH_MODE_BLOGSPOT\x26navbarType\x3dBLUE\x26layoutType\x3dCLASSIC\x26searchRoot\x3dhttp://mckev.blogspot.com/search\x26blogLocale\x3den_US\x26v\x3d2\x26homepageUrl\x3dhttp://mckev.blogspot.com/\x26vt\x3d7389753422818032331', where: document.getElementById("navbar-iframe-container"), id: "navbar-iframe" }); } }); </script>

Friday, June 27, 2008

Playing Worms

About three weeks ago, I found a website from my friend http://www.hacker.org/. It has many logic games, and one of its games is bot competition game, where we can program a bot in Java language, and watch our bot competes against other bots. See Wormageddon: http://www.hacker.org/worm/. I find it really really interesting :).


I designed my worm as follows:
1. First run BFS algorithm to find out the minimum path to the enemy. This will make our worm "chasing" the enemy.
2. If you stumble upon a wall, then you must turn away from the enemy.
3. If possible, you should evaluate the next step so you won't enter into a closed space. I used DFS algorithm to get "spaciousness" information of a coordinate. Because we are limited to 500,000 instructions per move so we have to be careful not to pass this limit.
4. I also added a recipe so that we won't be trapped by the enemy on his next move (look ahead one ply).
5. If you can't find a way to your enemy, means there is no path between you and the enemy, so now we have to stop chasing and use "fill" strategy to take as much space as possible.

The result... I got 2nd place worldwide yayyyyy... I'm so proud! I named my worm "SWorm", initially a smart worm but sometimes could be a stupid worm as well (especially when playing against "Turtle"), so I just named it SWorm haha..