Halite Home

How your starting position impacts your bot's performance


#1

Note: there are many more effective ways to improve your bot than focusing on how the way you iterate over the map impacts how you compare game positions. This is just something I worked on recently that I wanted to share.

Iterating over the map

How do you iterate over the map each turn? If you're like me, you start in the top left and work row by row from left to right, top to bottom. It's how all the bots in my tutorial iterate.

It has served me well and I've been able to reach rank 1 without ever giving it much thought. But as I was working on my latest iteration, I was comparing how my new bot compared to my previous bot and was switching their positions in matches to make sure the results were the same.

Example:

# Run a game against some bots

$ ./halite -d "35 35" \
    "old bot" \
    "older bot 1" \
    "older bot 2" \
    "new bot" \
...
Player #1, OldBot, came in rank #1 and was last alive on frame #329!
Player #2, OlderBot1, came in rank #3 and was last alive on frame #305!
Player #3, OlderBot2, came in rank #2 and was last alive on frame #329!
Player #4, NewBot, came in rank #4 and was last alive on frame #168!

# repeat with old and new bot swapped

$ ./halite -d "35 35" \
    "new bot" \
    "older bot 1" \
    "older bot 2" \
    "old bot" \
...
Player #1, NewBot, came in rank #1 and was last alive on frame #329!
Player #2, OlderBot1, came in rank #3 and was last alive on frame #305!
Player #3, OlderBot2, came in rank #2 and was last alive on frame #329!
Player #4, OldBot, came in rank #4 and was last alive on frame #168!

Generally I would expect that my NewBot would do no worse than my OldBot when their positions were switched, and might even hope that it does better.

However, what I found was that if I did a complete rotation of bots (so everything was the same except that everyone was "upside down") I didn't get the same results.

$ ./halite -d "35 35" \
    "new bot" \
    "older bot 2" \
    "older bot 1" \
    "old bot" \

I had noticed this in the past and dismissed it with a shrug, but I was curious to see what the cause might be. So after I "rotated" the map, I also told my bots to iterate over the map in reverse.

While things weren't identical, they looked a lot more familiar. I decided to dig in further.

So should I start iterating in reverse?

No :stuck_out_tongue:.

The fact that my bots sometimes performed better depending on how they were oriented to the map meant that the order in which I let cells pick their moves mattered. I was deciding based on how I iterated over the map rather than the state of the map.

I played around with some different orderings to get a sense of how it impacted performance. I started simple by just reversing or shuffling the order each turn, but eventually I started sorting the cells based on different criteria. I'll leave the criteria as an exercise to the reader, but I used intuition and trial and error to find something that worked reliably in every orientation.

There were a lot of places in my code where the iteration order mattered (and I even uncovered some bugs). If you go down this path, think critically about how different parts of your program interact.

What about iterating over directions?

Thinking about how I iterated over the map also made me think about how I iterated over the neighbors of cells. I always iterated in the order of the CARDINALS: NESW.

I would evaluate and pick my "targets" based on the order that I iterated over them. Using a stable sort to order my targets, if 2 targets had the same heuristic value the first one I visited would be the one chosen.

It turns out (surprise!) that I was having more "ties" from my heuristic than I was expecting and the tie breaker happened to be the iteration order. Again, I iterated using intution and trial and error to find more ways to settle ties that improved performance.

I added logging to detect ties so I could examine the board state and see what additional information I might use to make a better decision. I found this to be pretty overwhelming and I spent a lot of time feeling around in the dark trying to understand why some moves that seemed equivalent were better than others.

I still haven't gotten to the point where no ties are decided by iteration order. However, I did feel like I was reaching diminishing returns and that larger macro changes to my heuristic would provide a bigger impact.

Big picture

The biggest takeway from this should be thinking critically about how your bot behaves.

  • Why are things different?
  • What changed?
  • Is that a bug?

Add good logging, watch replays closely, and always be curious.


#2

Good article. My internal simulator plays a game of Halite in about 2-4 seconds. You'd expect that if you run the same bot against another instance of itself (with a balanced map ofcourse), both would perform the same but this is not the case as Nmalaguti correctly stated when it has to prioritize a wind direction.

Even if you sort your list of possible expansions then the order in which they were added to the list matters a little bit. I think there should never be a case where changing the cardinal order is something your bot should do, rather, it should more closely sort the value of each tile, after all, choosing one over the other has lead to one of your bots losing to the other...

Ideally you can predict correctly which tile to pick that leads to that one bot picked luckily because of its rotation.

Examples could include : A tile closer to an enemy in multiplayer is worth slightly less or a tile closer to a "production gold mine" is worth more.


#3

Also, a roundabout solution is to center the map on top of the bot's starting location before sending that map to the bot. Unfortunately, I'm quite certain this is not something Halite does currently.

Multiplayer games are never truly equal without centralized maps for each player because most people prefer to expand "north" when the two values are the same. I have watched games where my bot would get "ganged up" on because of how their bots favoured attacking my cardinal direction first : enemy 3 tiles north and enemy 3 tiles east and the tiles in the center would go north.

EDIT : I forgot to mention that some maps are mirrored instead of normal copy for each player in which case centring the map does not give exactly equal results (although I'd argue it still helps a lot). From my research this specific part depends entirely on the player count. For example 2 horizontally aligned players next to each other results in a mirrored map.