My biggest struggle, as always, was the multi-agent aspect of this challenge. Preventing the workers from getting in each other's way was a problem I struggled throughout.
My bot is mere 2k lines, you can check it out on github.
Plans as 1st class concepts
Using plain commands array and then puts commands.join("; ") may work for a while, but it becomes unworkable once multiple agents are in play and you need introspection like "is this agent doing anything this turn?" or "is any other agent already going here?".
Do yourself a favour and introduce a Plan concept like
Plan = Struct.new(:name, :worker_id, :type, :node, :weight)
Furthermore, distinguish "ultimate goal" from "command to result for this turn". This can help further improve plan collision (there's an interesting 2x2 possibility matrix here:
- ultimate goals and turn command match, very bad
- ultimate goals match, but turn commands differ (workers on different squares, no surprise), still bad.
- ultimate goals differ, but turn commands match, uhg, gotta look for pathing alternatives or somesuch
- ultimate goal and commands differ, yay
)
Timing tracking
Save turn start time at the very beginning of turn.
Be able to tell how long you've taken so far. This allows early-termination in case of deep prediction or, inversely, using leftover time in simpler turns to do some pre-crunching for next turns.
In this challenge I used this technique to lazily pre-fill pathing to trees, since their positions only become available on 1st turn.
# @return Numeric # in ms
def turn_time_taken
t1 = Process.clock_gettime(Process::CLOCK_MONOTONIC)
elapsed_ms = ((t1 - t0) * 1000.0).round
end
# using a value somewhat lower than 50ms stated in rules for safety
# @return Numeric # in ms
TURN_TIME = 45
def turn_time_remaining
45 - turn_time_taken
end
State VS de-novo
Say I see an opponent does something the bot should take note of and remember, to then use in later turns. This complexes spec setup and testing, necessitates an easy way to feed the internal state in initializer, which can get cumbersome.
Strongly prefer deciding on best move solely based on info given that turn, but sometimes memory is really helpful, YMMV.
Override #inspect
Does your main object vomit out hundreds of lines of irrelevant ivar data when inspected in console? Override its def inspect for what you need!
def inspect
ivars = instance_variables - [:@row] # or whatever you want to hide
attrs = ivars.map do |ivar|
"#{ivar}=#{instance_variable_get(ivar).inspect}"
end.join(", ")
"#<#{self.class}#{attrs}>"
end
In Rails systems you can try the more targeted override for #pretty_print_instance_variables
def pretty_print_instance_variables
instance_variables - [:@file]
end
Subpath memoization
This is big. Say you run your shortest path algo and it gives you a four-node long path [1, 2, 3, 4]. What you've actually gotten is all shortest subpaths - [1, 2], [2, 3], [3, 4], [1, 2, 3], and [2, 3, 4]. Memoize these alongside the main path!
Short-circuiting sorting
Consider sorting optimization that uses short-circuiting - if there is just one element in a collection, sorting it can be skipped altogether. This is useful if the sorting block does expensive things like pathing calculations:
def quick_max_by(&block)
if one?
first
else
max_by(&block)
end
end