Team Name: TAPLAS
"O'Caml is the programming tool of choice for discriminating hackers."
Members: Yutaka Oiwa, Eijiro Sumii, Tatsurou Sekiguchi
Program Name: Rog-O-Matic III (written in Objective Caml)
We were really glad when we heard we won the contest this year, especially because we had never felt confident - the task involved much "uncertainty" in the sense that finding an optimal solution was almost impossible (the task subsumed many NP-hard problems) and speculating the behavior of other robots (or, actually, the strategy of their programmers) was also difficult. So, we were always anxious however hard we were tuning up our robot. We could say our victory is a result of luck rather than the ability of programming, either of which is enough to make us happy anyway. ;-)
The goal of this year's ICFP Programming Contest is to implement tactics which conducts a robot to win a package-delivery game. The complete task description is published in the Programming Contest Homepage.
Tar archive of our entry is located here. You can browse and download indivisual source files here.
The core of our strategy is common to both single-robot game and multi-robot game, although various additional factors are considered if there is other robots in the game. We describe the strategy in single-player mode first.
At first the robot makes a plan. After that, it goes to its destination along the route which was set at the time of planning. unless other robots are very close to it. The plan is determined as follows.
Of course, the distance of a target is also taken into account. The planning algorithm is actually implemented by Dijkstra's shortest path finding algorithm.
When our robot reaches a location on which packages are put, the packages are divided into groups according to their mutual distances. Near packages are grouped provided that their total weight is more than the limit of a robot. Then, those groups are sorted with respect to both the sum of their weights, and their distances from the robot. The robot takes packages as many as possible according to the ordering.
When the robot reaches one of the destinations of carried packages, it attempts to drop them.
If there are multiple robots in the game, the strategy is slightly modified to avoid interference from other robots. Firstly, our path determination algorithm attempts to make a route that does not contain cells neighboring water or narrow passage as far as possible. We put additional cost to such dangerous cells when the robot calculates path distances using Dijkstra's algorithms. Figure 1 is an example of the cell costs. Figure 2 shows two different paths which are treated as 'the shortest' in single-player and multi-player games (detail...).
| Figure 1. example cell costs | |
|---|---|
| map | costs |
###################### #....................# #....................# #....................# #..################..# #..~~~~~~~~~~~~~~~~..# #....................# #S.~~~~~~~~~~~~~~~~.G# ###################### START GOAL |
1 2 3 4 5 6 7 - 0-9 A-E F-J K-O P-T U-Y Z ###################### #6------------------6# #--------------------# #--------------------# #--################--# #-K~~~~~~~~~~~~~~~~K-# #-1CFFFFFFFFFFFFFFC1-# #6K~~~~~~~~~~~~~~~~K6# ###################### |
|
The cells marked "K" is highly dangerous, because enemies may push the robot to water from side. "The bridge" is not dangerous for water hazard (there is no space to push!), but is too narrow and may be blocked by enemies. | |
| Figure 2. The preferred paths (marked *) | |
|---|---|
| single player | multi player |
###################### # # # # # # # ################ # # ~~~~~~~~~~~~~~~~ # # ****************** # #**~~~~~~~~~~~~~~~~**# ###################### |
###################### # # # # # ****************** # #**################**# #* ~~~~~~~~~~~~~~~~ *# #* *# #* ~~~~~~~~~~~~~~~~ *# ###################### |
When other robots are very close to our robot, it predicts all possibilities in a near future (3 turns) of movement of relevant robots and itself based on a min-max search algorithm. We, however, ignore any "chain-of-effect" caused by several enemies and tactics of enemies: we simply assume that if some location is a 2-step-walk from some enemy, that enemy may not be there at the next turn, but at the 2 turns (or more) after now. If the plan produced by the strategy is determined to be dangerous, It chooses an alternative plan (including "STAY - don't move") which makes the possibility of death minimum.
The bid is established as follows: When other robots are neighbor, the robot spends up to 1% of the total money as a bid. When there is a possibility that another robot kills our robot, it spends up to 2.5% of the total money. The sign of the bid is decided by comparing the dangerousness of two possible move orders (me first / enemies first).If the robot is intercepted by another robot repeatedly, it gives up the current destination, and goes to the next important target. (The robot remembers the set of "difficult-to-deliver" targets.) Also, if the robot is repeatedly held up when avoiding dangerous position, the robot dare to go through the possibly dangerous route. (This is implemented by adding negative score to consecutive STAY decisions.)
| Figure 3. possible deadlock situation |
|---|
~~~~~~~~~
A
B
~~~~~~~~~
Assume that robot A wants to go EAST, and B wants to go WEST.
Both movements are dangerous because they may be
pushed into water in the 2nd next turn.
Our robots choose STAY tactics in this situation.
However, if both robots choose to STAY, they deadlock.
|
There is a special tactics for the first move of the game. If many robots are overlaped in the start location, the normal tactics guesses that negative bet is better (because there is no possibility to be pushed.) Actually, the best tactics depends on map. Our robot handles this case specially: It checks the space in front of the robot, and if the wall appears before water, the bid is changed to positive, expecting preferable chain-of-push action. If a water can been seen from the current location, the bid will be negative, to prevent "pushed-pushed-pushed-pushed-then-drown :-(" action. (see the Figure below.) The robot bids 5% of the current money.
| Figure 4: The tactics for the first bid |
|---|
The current position is &.
bids POSITIVE bids NEGATIVE ################### ################### #&---------------># #&-------------->~# # # # # # # # ~# # # # # # # # ~# ######## ########## ######## ########## # # # # |
We wrote the program sitting around a table on which we put our laptop computers. So we don't use CVS nor modern software developing methodology. We directly modified the same source programs taking a RCS lock by putting it in a word. The program itself is very small (about 1500 lines of code), so much time was spent for designing the robot movement strategy. Yutaka implemented a client program for a human, and we repeatedly tuned the strategy by fighting between a computer and a human, or between humans.
We would like to point out that the source code is very small, about 1500 lines of code. (It even contains dead code!) The program of the second winner (written in C) consists of about 3000 lines of code. It seems that Ocaml allows the programmer to write much more compact code than C without losing quality of code.
Rog-O-Matic was an expert system developed about twenty years ago whose aim is to solve Rogue automatically. Rogue is a text-based game, followed by Hack and Nethack. The task in Rogue was to pick up the amulet of Yendor in a deep dungeon where lots of monsters reside in, and to go out of the dungeon. Students used to play Rogue instead of 3D graphical action games. Strategy and prediction were quite important in solving Rogue.