Halite Home

A top 20 bot in twenty lines code - an illustrated guide


Here you go:



Awesome. Of all the published bots, this is my favourite so far for elegance. Nice one @DanielVF


This is fantastic. Now you have me curious about what kind of improvement you might see from using a score that looks ahead a couple of tiles beyond each border to help pull you towards the best sites even more.


This is pretty much what I did with my bot.

The basic idea is to partition the whole exterior region into separate parts, one connected to each border site. This then makes it possible to assign a score to each border site as the sum of a reward function over its share of the exterior.

One way to partition the exterior is to use Dijkstra's algorithm over the lattice of sites with vertex weight = site strength.
If you introduce a fictitious node "interior" and connect it to all border sites, and disconnect any edge between two border sites, then the minimum distance path from "interior" to any exterior site (as found by Dijkstra) passes through a single border site. Importantly, these paths define a partition of the exterior based on the proximity to border sites. Note that this partition can be computed in O(n log n) time through a single Dijkstra pass, regardless of the number of border sites.

Now the problem is reduced to assigning a score to each exterior site based on production, strength, BFS distance, "strength distance", and perhaps some other features. Basically you need to define a multivariate reward function that works on all maps (and regrettably this is where I should've spent more time..).
Once you have that, the Dijkstra-based partition gives you a score for each border site, and you can use this score to pull units outward.


How did you generate those diagrams?


I wrote a little bit of ruby that lets me spit out html page with notes, diagrams, and running code. Sort of like iPython. The arrows are just unicode.

So this:


I also wrote a python version for use with Jupyter Notebook. That's public and up on github here Halite Notebook