среда, 1 августа 2012 г.

ICFPC 2012: Report

What's ICFPC? See wikipedia.

TL;DR: https://bitbucket.org/xa4a/icfpc12/src (python)

This year's annual functional programming celebration took place in July. Following few previous years tradition I was looking forward to following the contest and was actually preparing by looking for the team and drafting some code.

As it usually happens organizers started giving some cues (as it turned out) before the contest actually started: they mentioned breast-shaped hills with mines in them, pouring rains and flying trampolines.



Day 1: Friday the 13th


~13:00: After filling myself with lunch and logging in to #icfp-contest at irc.freenode.net and icfpc@conference.jabber.ru, expecting the task. 
13:00 It took few seconds for the task to become available throughout the world.

This year the task starts with story of overwhelmed scottish miners, diligently working at the mines under aforementioned hills to satisfy the world demand in lambas (λ). Despite all the efforts, we are expected to run out of lambdas by October this year, which means functional programming is in danger!
The participants are requested to replace underperforming and inefficient human miners with real metal robots, and specifically – write software for navigating these robots in the mines.
After the second look it turns out that what they want from us is a bot for the game similar to Boulderdash. Doh! Another Google AI Challenge. Also the task promised four extensions, which would be revelaed during the contest. The fact that this year's task was quite precise and contained just a single error (order of processing the game-end conditions) is noteworthy.


13:20 Looks like 20 minutes were enough to look through the task. First commit – 10 suggested maps from the task specification. Every map is (usually) a rectangular field containing letters and punctuation representing walls, rocks, target lambdas and other landscape elements, e.g:


#######
#..***#
#..\\\#
#...**#
#.*.*\#
LR....#
#######

where # - walls, \ - lambdas, R - controlled robot, L - closed exit, which opens as soon as all lambdas are collected, * - pushable/falling/smashing rocks. Robot's aim is to collect all the lambdas and escape through the opened lift door and not get smashed in the meantime. Participant's aim: for the given map generate a command sequence (Up/Right/Left/Down) to solve the map. The task is processed and the first thought is that some kind of game engine simulator will be absolutely required for testing and scoring the generated solutions.

16:04 The first working simulator version is commited, it can run given command sequences on the map and draw the result, and at 16:34 simulator is quite correct and can compute the score.

16:59 Commited simulator can execute commands step-by-step.

With a working simulator it was possible to start implementing a bunch of accumulated thoughts. The first iteration was a simple A* search, looking for lambdas, or if there are no more left – for the exit, and using all the walkable cells. Since from the beginning I didn't aim at uberoptimized solver + taking map changes into account while performing A* seemed to be difficult, the way it worked was: A* was executed at every step, looking for path to the closest target, the first step of this path simulated and the new path to the closest target was searched again. This was repeating until the robot reached dead-end. Also, avoiding falling rocks turned out to be rather easy by just scoring the affected cells as walls.

19:34 Simple solver, that works – the solver solves and even completes some maps!

19:44 The first task extension announced: pouring showers flood the mines and the robot is not too waterproof – it can only stay underwater for limited period of time. 
At this point, after fixing few bugs, the first day was over for me, so processing water was postponed to Saturday.

Day 2: Saturday

By 13:15 a commit saying "lala" was ready, which added processing water in the simulator and the solver improvement of "if we've drowned, undo last move and return result". I believe this code has made it into the lightning round submission and hopefully it won't be a shame.
water level is on the right here
14:39 A* improvements, in particular when scoring cell transitions instead of static target cell scores uses transition directions, so from some directions rocks can't be pushed -> scored as a wall, and from others can – entering them is cheaper.
At about the same time the first idea of avoiding dead-ends is implemented: if there are no reachable lambdas – go and dig rocks.
One more idea: sometimes you can get faster to the lift, if instead of collecting lambdas closer to the robot, you go for the farthest from the lift. In this case the last lambda would be the closest to the exit lift, so you can get there fast. One of the two approaches was chosen on every step based on the estimated total distance.
Watching the bot at this point has shown that following A* it often blocks itself with the falling rocks and gives up. The important part is that it blocks itself during just few last steps. Solution? If blocked, backtrack few steps and try to replace the "optimal" A* with random possible outcomes and see, if any of them avoids blocking itself. The idea worked quite well, though was only polished at the end of day three.

17:33 Second task amendment announced: maps may contain trampolines-teleports.



Saturday ends.
No, it doesn't: at 22:47 new task extension is announced: the mines may contain growing beard (W), which is to be shaved with razors (!). Expecting imminent beard nightmares going to sleep.

Day 3: Sunday

11:01 Simple change in A* scoring: paths including razors cost 1, earth – 3 and the robot involuntary collects razors on its way.
11:49 If beard blocks the path – shave!
12:30 New task extension: in addition to the regular rocks and regular lambas we now have higher-order rocks (@), which are rocks until they fall, when they become lambdas, which also have to be collected.
Now the rocks should've been pushed more aggressively and thus finding the directions for this ot happen would be nice. It became clear that the used method for looking for the A* targets and describing them became too verbose and something more concise was required.

At 14:05 the answer to this is searching for the targets on the map using pattern-matching, e.g:
targets = find_cells(map, '\\')

# break horocks
# dig under
pattern = ["@",
           "."][::-1]
targets += find_pattern(pattern, [0,0], map)

# dig to the down-right
pattern = ["@ ",
           "r."][::-1]
mapping = {'r': 'R*@\\'}
targets += find_pattern(pattern, [0,1], map, mapping)
That is targets are given by a 2D pattern which is located on the map and coordinates inside this pattern. This reduced tons of code for describing possible scenarios and actually write down even more of them. A bit more refactoring and at 14:33:
if there are no more lambdas left, come to the pushable rocks:
if not targets:
    pattern = [" @e",
               "-w-"][::-1]
    mapping = {'w': '#W',
               'e': ' .'}
targets += find_pattern(pattern, [1,2], map, mapping)
and push them: 
pattern = [" @R",
           "-w-"][::-1]
mapping = {'w': '#W'}
targets += find_pattern(pattern, [1,1], map, mapping)

14:57 Targets were assigned priorities so the robot got down digging rocks only if there was nothing else left to do.

19:55 Committed the last significant code change: path-tail bruteforcer started actually giving some usable results + added resulting path optimizer to strip unneeded moves from middle and end of the path.

21:18 Fixed small bugs + speed increased ~twice by just:
- #!/usr/bin/env python
+ #!/usr/bin/env pypy
Tried packing the solution few times and went to bed.

Day last: Monday

Had no more energy to write anything else, and had work to do, so all I did on Monday was trying out the solutions on the judges' virtual machine and submitting it.

What went good:
  1. As always, it was entertaining!
  2. Organizers made a good job with the task, description and organizing in general: asnwered questions in a timely manner, didn't have their servers down.
  3. It was really fun to spend three days, and hopefully I'll get some satisfying result.
What could be better:
  1. The more people you have to contribute in the solution, the better.
  2. Some kind of online scoreboard was really missing. That'd be more spirit of contest.
That's it.

The results for the first round of testing are actually already available with my team "A" doing well so far:

1 комментарий:

  1. Nice job, great results so far!

    P.S. I missed the context this time. Feeling sad while reading all the reports

    ОтветитьУдалить