> 1 -------------------------------------------------------------------------------- 1 Team: 2 Team: 2 Dark Integers 3 Dark Integers > 4 3 Member: 5 Member: 4 Kazuhiro Inaba (www.kmonos.net / kiki@kmonos.net) 6 Kazuhiro Inaba (www.kmonos.net / kiki@kmonos.net) > 7 5 Language: | 8 Programming Language: 6 D Programming Language (dlang.org) 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 7 43 8 This submission for lightning division is not particulary interseting. | 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 :(. 9 46 10 - Robot rushes to the nearest lambda (or the open lift) by breadth first search. | 47 Flood: 11 - Not at all taking into account the dynamics (falling rocks, floods). | 48 Almost nothing is done for it. The "fire" solver locally takes care 12 - To mitigate the staticness, the robot avoids the '.' below '*' as much as | 49 of it, and it is inclided to use "U" during perturbation. Also, "wind" 13 possible, so that it won't fall new rocks. | 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. 14 58 15 - Output routine is 'guarded' by a 'sudden death' or 'stray sheep' detector. < 16 That is, if the above search routine was hit by a rock or a water, or it < 17 couldn't find a way to the next target and walked in vain, the output guards < 18 trims the command history and inserts the 'A'bort at the optimal timing. < 19 This is also used for SIGINT handling. < > 59 20 60 21 - gui.d is a windows GUI for the game, using DFL (http://github.com/Rayerd/dfl) | 61 Thanks for organizing the contest! I've enjoyed! 22 it is not compiled into the submitted routine. This is just a helper. < 23 < 24 Stay tuned for the full submission, judges! <