1 +-------------------------------------------------------------------------------- 1 2 Team: 2 3 Dark Integers 4 + 3 5 Member: 4 6 Kazuhiro Inaba (www.kmonos.net / kiki@kmonos.net) 5 -Language: 7 + 8 +Programming Language: 6 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. 11 - - Not at all taking into account the dynamics (falling rocks, floods). 12 - - To mitigate the staticness, the robot avoids the '.' below '*' as much as 13 - possible, so that it won't fall new rocks. 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. 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) 22 - it is not compiled into the submitted routine. This is just a helper. 23 - 24 -Stay tuned for the full submission, judges! 61 +Thanks for organizing the contest! I've enjoyed!