Index: submission/README ================================================================== --- submission/README +++ submission/README @@ -1,24 +1,61 @@ +-------------------------------------------------------------------------------- Team: Dark Integers + Member: Kazuhiro Inaba (www.kmonos.net / kiki@kmonos.net) -Language: + +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 is used for W*H<=1600 instances. Fire 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). + + -This submission for lightning division is not particulary interseting. +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 :(. -- Robot rushes to the nearest lambda (or the open lift) by breadth first search. - - Not at all taking into account the dynamics (falling rocks, floods). - - To mitigate the staticness, the robot avoids the '.' below '*' as much as - possible, so that it won't fall new rocks. + 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. -- Output routine is 'guarded' by a 'sudden death' or 'stray sheep' detector. - That is, if the above search routine was hit by a rock or a water, or it - couldn't find a way to the next target and walked in vain, the output guards - trims the command history and inserts the 'A'bort at the optimal timing. - This is also used for SIGINT handling. + -- gui.d is a windows GUI for the game, using DFL (http://github.com/Rayerd/dfl) - it is not compiled into the submitted routine. This is just a helper. - -Stay tuned for the full submission, judges! +Thanks for organizing the contest! I've enjoyed!