Halite Home

Perimeter Optimization during Expansion


#1

I've often mentioned in discussions of strategy with players that optimizing perimeter is really important in Halite (at least from a theoretical standpoint). I never really got around to proving it, though... until now! (specifically I now have time to do so because of winter holidays :slight_smile:)

Here's what I've done:
I wrote up a fairly simple and mediocre bot (on par with those introduced in @nmalaguti's wonderful tutorial), which uses a few BFS searches to route pieces to sites and borders. Here's the key, though: One specifies in the code a grid that the bot must stay on, originating at the site the bot starts on, and the code is written such that I can easily switch the grid dimensions. Once the bot has conquered 99% of the map contained in that grid, the grid restriction becomes disabled and the bot runs just like any other. Here are my results on the single player mini-competition posted by @erdman:

(x_grid, y_grid) -> turns_to_disable -> turns_to_total
(1, 1) -> n/a -> 198
(2, 2) -> 182 -> 192
(2, 3) -> 181 -> 197
(3, 2) -> 179 -> 195
(3, 3) -> 174 -> 199
(3, 4) -> 173 -> 203
(4, 3) -> 172 -> 202
(4, 4) -> 174 -> 209
(6, 6) -> 166 -> 213
(9, 9) -> 159 -> 229
(12, 12) -> 174 -> 241

It’s pretty clear that this bot is nowhere near winning the single player mini-competition -- it has no traffic control, makes bad choices in expansion, could route its pieces more efficiently, etc. However, the thing I want to call attention to is that the bot was able to achieve a 6 frame improvement by following a 2x2 grid and then taking the rest.

What’s going on?

The answer, I think, has to do with how distances work in Halite. In Halite, strength on a border is far more valuable than strength in the middle of one’s territory. The reason for this is that in order to make any use of the strength in the middle of one’s territory, one must first move it a bunch of times, and every time a piece is moved that’s production being lost. One way of thinking about the single-player challenge is that the map has a total of some number of strength, and your bot just has to generate that much strength in as few frames as possible. Moving pieces over long distances is bad for that.

Consequently, we want to try to move less! How do we do so? We do so by ensuring that newly produced strength always has short paths to unowned sites. In other words, we’re deliberately leaving gaps in our territory that we’ll fill in later.

My bot did the best on the smallest possible grid (2x2) -- the results do clearly show that following too large a grid all the way through is bad. In fact, the benefit disappears at a 3x3 grid and then it’s all up from there. However, the time that it takes for the tentacles to cover the whole map decreases for longer, reaching just 159 frames at 9x9, whereas a 2x2 takes 182. Once one heads past 9x9, it rises again, since strength has to travel quite far before being used during the grid-based expansion.

I found that a grid is a convenient way to organize the gaps and demonstrate my point, but there are almost certainly better ways of doing it dynamically that take into account things like the strength and production of unowned sites and the locations of strength within your bot. As a simple example, it would probably be better to follow a larger (i.e. 3x3 grid) at the start, switch to a 2x2 grid during later expansion, and have the grid disabled while conquering the last pieces of territory.

I predict that the best-expanding bots (calling out @cdurbin and @pepijno) could do 5-10 frames better if they left gaps in their initial expansion and filled them in later.

Here's the code.

I hope this was useful, and good luck!
-Sydriax


Deciding where to move your pieces
#2

I like the idea, but there are also advantages to taking a site earlier in the interior depending on the strength to production ratio.

I have seen times on certain maps where my bot will hollow out interiors like this and then the cells behind fill in these interiors. At first I tried to "fix" this behavior in my expansion, but then I saw that it was actually working out well so you could be on to something.