r15 - 08 May 2007 - 02:50:29 - Anton OrlovYou are here: TWiki >  Refaldevel Web > WebHomeEn > IcfpContest2005En

Team R+ entry to the ICFP 2005 Programming Contest

Team R+ (consisting of one member: Anton Orlov) participated in the eighth annual ICFP programming contest.

This year contest consisted of two stages. In the first one participants had three days to program a given task. Then after two weeks there was a second stage in which a set of changes to the task were announced and participants had one day to adapt their programs to the new requirements.

In both stages the task was to program two robots -- a cop and a robber. Both move in turn on a given map (directed graph). The target of the robber is to rob banks. The target of the cop is to cooperate with four his colleagues from other participants and to catch the robber. The main change in the second stage was the ability for cops to join the robber and for a reward allow him to rob banks safely. But betrayed cop should behave in such a way that honest ones can't guess his dirty plan and don't accuse him.

My robber and cop are named correspondingly Fox and Gleb Zheglov after the heroes of "The Age of Charity", the novel by Vainer brothers on which very popular in Russia "The Meeting Place is Impossible to Change" TV series are based.

Download

Each robot is just a program that communicates with the game server (can be downloaded from http://icfpc.plt-scheme.org/) through stdin and stdout.

Download source code (in Refal Plus) of my bots: icfpc2005-R.zip (29.1 Kb).

Two versions for each robot are provided:

  • fox and zheglov are precisely the bots from my second stage submission.
  • fox2 and zheglov2 were prepared shortly after the time ran out. They are supplied with rather extensive comments.

Also you can download the same archive with statically linked Linux binaries for all robots included: icfpc2005-Rbin.tar.bz2 (2.5 Mb).

Readme file from the archive: readme.

Short essay (also included in the archive) that briefly describes ideas behind the bots behavior and my handling of the rules twist in the second round: essay.txt.

Timeline

First round

Although I started to read problem spec soon after it was announced the whole one day passed until I at last determined to take part in the contest and started to think on possible solutions and try to implement something.

I decided to use our Refal+ system. The problem could be a good test for its maturity. And participating in the ICFPC using Refal+ could help on promoting Refal in general and our system in particular.

To the end of the first round I had working finding of the shortest paths and the boundary of a set of nodes reachable by cops before the robber. The robber somehow tried to escape through the nodes of that boundary not protected by cops and rob banks inside it. For the first round he wasn't bad I think (but maybe buggy).

But the cop was written last and I had finished the simplest version just before the deadline. He should send his colleagues to the boundary nodes in order to encircle the robber. But unfortunately I misread the spec and my cop generated plans for the worlds numbered less to one then he should. So even fully obedient colleagues (McGruffs) just stand still and can't catch a robber.

I didn't have time to find that bug and due to that my first submission don't pass the regular season (see http://icfpc.plt-scheme.org/spec.html#tournament).

Second round

Right after the end of the first round I fixed bugs in all my code and refactored it a bit. It took about three hours at the same evening (the deadline was 18:00 at my timezone). My bots worked somehow but I hadn't any idea about how good they are. Probably not pretty. They didn't take into account smells and evidences. Cop didn't maintain a map of possible robber locations, didn't listen to other cops information, and always voted for his own plans. None of bots tried to precompute some game positions in advance or evaluate some moves from the long run point of view.

Initially I planned to implement a part of that features before the second round. But making something advanced was too much work and my motivation vanished eventually. In the end I didn't touch the code until the twisted spec was announced.

Just to adapt robots for the new game protocol was easy. But a good strategy for the bots wasn't clear. And it isn't clear for me even now, after I saw several robots from other teams.

The robber was simpler. First of all I added a search of routes in bypass of given nodes. It allowed the robber to find more safe paths to banks. When he founds himself in a perilous closeness from a cop he tries bribing or pushing. When cooperating with cops he tries to listen their advices. If several of them suggest a particular move and that move is on a safe path to some bank then the robber can change his former mind. He follows the winning plan if it suggests a step on a safe path to some bank.

After the robber was done very little time was left for the cop again. So he was just minimally changed to conform to the spec. He always remain straightforward. Before the deadline I tried to add some dubious accusation heuristics based on a correlation between the number of times one follows the winning plan and the number of times one don't. But I failed to do it in time.

Afterwork

After the deadline I proceeded with the work on the cop. I added the notion of a target for a cop. If the robber wasn't caught after encircling his supposed location then each cop gets a target and is suggested to move towards it. The targets at first are chosen to follow possible ways of escape for robber, then randomly.

Then I implemented my accusation heuristics and found silly bug in the robber. As the spec says, the robber should push a cop when he tries bribing, but there is no offers and no cop was ever bribed. When implementing this condition I forgot that all bribed cops can eventually be accused and controlled by clean cop-brains. So I just checked there is no bribed cops. The fix was just adding few words -- a check on there is no any controlled cops:

        ..., <? &Slaves> : /*empty*/ ...

It's a pity that silly thing will probably cause disqualification of my submission. During the tournament there most likely will be situation when all bribed cops are accused and the robber will try to push somebody.

All meaningful code changes took about two additional hours. After that I only added comments to the last versions of the robots.

Surprisingly it turns out that my final cop can catch my final robber (by managing McGruffs) with a lot of combinations of turn numbers when some cops offer themselves for bribing.

Conclusion

Refal+

There were almost no problems with the implementation. The system is fairly stable and it's time to make official release.

There were three small obstacles:

  • StdIO is buffered and there isn't Flush function. I just added fflush(stdout) call to the Print implementation. Should be fixed by adding Flush! to StdIO library.

  • Randomize function isn't implemented in C++ (just forgotten). I used uninitialized Random. It wasn't important for me.

  • Due to a bug in the converter to C++ it's sometimes not possible to use reference to a function from another module. I fixed it by writing stub function. Converter to C++ should be fixed -- it sometimes puts function in a wrong namespace.

I hadn't any problems with the speed or memory resources for my bots. The 5 seconds were more than enough to precompute the shortest paths, and find the boundary nodes at each step, and find safe paths to all banks for the robber. Much more computations could be done in the given limits.

The language features I starved for most were closures and formats checking for the values in boxes and tables. One of the nastier bugs evolved from not syntactically distinguishing between repeated use of a variable and its initialization.

Impression

I'd like to thank the contest organizers for the interesting task and all their work. Thanks for the game server and visualizer. It was fun just to hack the core problem and not supporting tools.

The task was really hard. Maybe too hard. Especially for one-man team. I think if I had a companion then we'd manage to complete some working solution for the first stage (even in two days), and there would be more motivation to work on the problem between the rounds and finally there hopefully wouldn't be that silly bug in the robber.

On the other hand trying to solve that hard task by oneself was really interesting and cognitive. Probably the main effect the contest has on myself is in my feeling more respect to static type systems. But on that in another topic? some time (and probably in Russian, sorry).

In expectation of the contest results and the ICFPC-2006 ;-).

-- Anton Orlov - 23 Aug 2005

Update (Results are unveiled!)

Results are published at the contest home page.

The most unexpected fact about it is that from about 160 teams participated in the contest only 13 took part in the final playoffs.

About half of the teams just didn't submit a solution for the twisted task. And most of submissions failed to beat judges' bots (or was disqualified due to some erroneous behavior during the regular season). So there are only 13 entries in the results table and no way to compare all the rest submissions.

As the majority of others my submission have lost to judges' bots: http://icfpc.cs.uchicago.edu/teams/118.html. Most of the time I spent on the robber and was pretty sure of him. But I didn't provide for a cops strategy consisting in standing by the banks and not hunting the robber. Judges' cops did exactly that. And as a lot of other teams' robbers in that situation my one just buzz at some place in hesitation instead of searching for unguarded bank.

As for my cop he also performed poorly. The biggest mistake was the following. After encircling a location where the robber was last seen the cops stayed there in a rather tight group, thus allowing the robber to safely pass around.

In the slightly improved cop version that I wrote soon after the contest this behavior was changed (see #Afterwork). So it was interesting to see how good against the judges' robber would the last version of my cop.

I ran the regular season games with my final bots instead of the submitted ones. All other parameters are the same as were in the tournament. The table summarizes the results.

  abBennie_ cdBennie_ efBennie_ ghBennie_ ihBennie_ R+
robber round 61 37 12 12 72 0
cop1 round 121 893 833 893 0 893
cop2 round 121 1000 1000 0 1120 1060
cop3 round 31 90 0 953 833 893
cop4 round 509 2721 60 0 0 60
cop5 round 0 132 754 694 754 377
total 843 4873 2659 2552 2779 3283

In each row the robber's score is emphasized. As can be seen there is only one round (cop4) which ends by the win of the robber. And due to that win cdBennie_ gains more points then my bots. So, unfortunately I can't even say that I needed just two additional hours and my submission would reach the playoffs. It wouldn't. But it would be pretty close to it ;-).

I think my final result isn't bad after all. And really it's rather surprising that one could advance thus far without considering smells and information from other bots.

-- Anton Orlov - 14 Oct 2005

Show attachmentsHide attachments
Topic attachments
I Attachment Action Size Date Who Comment
txttxt essay.txt manage 2.8 K 22 Aug 2005 - 16:40 OrloV Short essay describing the submission
zipzip icfpc2005-R.zip manage 29.1 K 20 Aug 2005 - 18:19 OrloV Robots source codes
elsebz2 icfpc2005-Rbin.tar.bz2 manage 2526.7 K 20 Aug 2005 - 18:21 OrloV Robots source codes and statically linked Linux binaries
elseEXT readme manage 3.4 K 22 Aug 2005 - 16:38 OrloV Readme file from the archives
Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r15 < r14 < r13 < r12 < r11 | More topic actions
Refaldevel.IcfpContest2005En moved from Refaldevel.IcfpContest2005 on 07 May 2007 - 22:50 by Anton Orlov - put it back
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback