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.
# 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?
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
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.
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.