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