Artifact 145a0b89a717cc17f81f3f80006e8c1bbe00a456
1 --------------------------------------------------------------------------------
2 Team:
3 Dark Integers
4
5 Member:
6 Kazuhiro Inaba (www.kmonos.net / kiki@kmonos.net)
7
8 Programming Language:
9 D Programming Language (dlang.org)
10 --------------------------------------------------------------------------------
11
12 Three types of solvers are combined.
13
14 1. Solver "Forest"
15 It does breadth first search every turn for taking the game's dynamism
16 into account. Basically it tries to rush to the nearest lambda or open
17 lift, but if there is no route found, it tries other various options.
18 Pushing rocks, digging earth around rocks, wait a while...
19 It is slow, but relatively more clever.
20
21 2. Solver "Wind"
22 It does breadth first search and memorize the computed path. As far as
23 possible, it tries to follow the precomputed route. If some obstacle is
24 found, it redoes the BFS. It is dumb but fast. So it is used for large
25 maps.
26
27 3. Solver "Fire"
28 It is a kind of "higher-order" solver, that takes another solver and
29 creep into it to make it more careful. Precisely speaking, this higher
30 order solver runs the subsolver as a 10-20 step lookahead. While no
31 problem is found in the lookahed, it behaves exactly as same as the
32 sub solver. If there was a problem (i.e., subsolver dead or stuck),
33 it tries all the possible perturbations to the lookahead window, and
34 re-runs subsolvers many times and chooses the best one.
35
36 Fire<Forest> is used for W*H<=1600 instances. Fire<Wind> is used for any
37 instances. For smaller maps, the better result of the two is used as the
38 final output. In addition, all these outputs are guarded by a sentinel
39 who aborts by force the output sequence at the best score position (so
40 that left-over run does not make the score worse).
41
42
43
44 For the added features, not quite much effort is paid. So if there came a
45 map that fully exploits the characteristics of the gadgets, I'll lose :(.
46
47 Flood:
48 Almost nothing is done for it. The "fire" solver locally takes care
49 of it, and it is inclided to use "U" during perturbation. Also, "wind"
50 solver's BFS is made to like "U" direction in larger maps.
51 Trampoline:
52 Just treated as one BFS edge.
53 Beard:
54 No clue. If there is nothing else to do, goes to the place where many
55 Wadler's are around, and uses the shaver.
56 Higher-order Rocks:
57 Tries to push them somehow randomly.
58
59
60
61 Thanks for organizing the contest! I've enjoyed!