ICFP Programming Challenge

First I would like to say that the choice of a killer robot theme is quite appropriate.  My organization concurs with the ICFP on the promotion and developement of killer robot technollogy.  The TSCBS is already working on Killer Robot Technollogy as a means to take over the world.  

Dominator was my entry for the ICFP programming challenge.  I saw the announcement for the ICFP on Slashdot Friday afternoon while at work.  By Friday night I had talked myself into making an entry.  So I headed for the grocery store to stock up on all-nighter food:  Botteld water, potato chips, coke, root beer, nutter-butters, Keebler fudge cookies, etc..  I was at my keyboard by about 11:00pm Friday night.

As I program in C++ at work, I felt that I would be most efficient programming in that language.  I had considered using python, but chose against it 1) I am not as fluent in Python and didn't want to spend time on a language learning curve and 2) as the problem could potentially be search intensive the speed of C++ would help out.  I already had a machine with a freshly installed Redhat 7.3 I would use that machine for development.

I prioritized my goals as follows:

read a map

route search

process robot movement

pick up and deliver packages

add huristics to improve above

    The map was the easyest to do.  I picked AStar for the path finding as it is pretty simple, and works well on big maps--there are descriptions for it on any self respecting game developement site. The network stuff was real easy--I just hooked the socket  up to a file descripter and used <stdio.h> style input and output.  I think the most important part of the design is in the huristics implemented in the robot--Anyone can do a path search.

Here are some of my huristics:

1) robot is hydrophobic:  movement cost for water tiles at risk (not all water tiles are dangerous) is tripple.  This keeps the robot away from tiles at risk.  This is only turned on when there is more than one robot in the game.

2) Movement cost for bases is zero -- this encourages the robot to move through bases and collect data on packages.  I kept a list of global packages available.  

3)  Deathbot move:  If we pass by another robot next to the water--spend 20 units to push him in.  If you push someone in, the will be unable to score any more points.

4)  Escape move:  If we get pushed to a water square AND another robot is positioned to push us in, use 3% of our energy to push back.  If you get pushed in the water you cannot score any more points so it is foolish not to spend some points trying to stay dry.  Further, if we do more than 3 escape moves in a row, try to side step.

5)  Evade move:  if we stay in the same area for more than 7 turns, give up on current path and move random for a while.

Bidding:  Except mentioned above I would bid 1 unless the square I was moving to contained another robot in which case I bid 2.   You can't score any points if you've used all your energy killing other robots.

Package selection:  I maintained a global list of packages on the map.  If the list was empty I would select a random base and move to it.  If the list was not empty, I would either a) (80% chance) move to the best valued package (value is weight of package / (distance from current location to package + distance from package to destination)) then the next best package to the same location.  Then any other package.  Packages detected on the way were also picked up.  

What I did wrong:  I used distance formula instead of manhattan distance (better) or AStar distance(best)--duh!  My package tracking wasn't perfect.  If I was pushed and dropped all my packages it was not detected, I would continue to the destination and drop packages I didn't have.  I should have kept track of bases.

What I didn right:  Using C++, I was able to work effectively since I was very familiar with the language;  the program was blindingly fast, I had to put some delay loops in so I could actually see the robot move.  I spent some time with the bidding.  I noticed may entries "always bid 1" which will really hurt them when they go against someone who had a more sophisticated bidding strategy.

The robot seemed to do well on the test servers even with the bug.  I expect my bot to do well in solo and non crowded maps.  On maps with many robots I think my robot will deliver to many dropped packages.

That's it.  I'll put my code here a little later on, when I have more time.

If you have any comments, you can contact me here.