Bot Version Overview
Overkill Bot (v1):
I spent almost a week trying to get overkill bot to work and have it function properly. Well, I started with the tutorial that @nmalgauti put together and then from there took a look at @erdman’s python starter bot and then tried to rewrite overkill bot from that. My first submission put me into 136/828, which I believe was good enough for a silver bot. Yay me! Maybe I can actually get a gold level bot. That would be amazing.
Single File:
I kept modifying the contents of the hlt file so I decided to import them into a single file for easy use. This also made it easy for me to just load a bot and not have separate files for each version. I guess I could have made a new folder for each version, but since I was making rapid changes at this point, it was easier for me to just have everything be self-contained.
Improving Overkill (v2-v6):
Building off the base, I started to experiment with looking beyond the immediate border. I played with giving a small bonus to border cells based on the value of the adjacent cells. I also play around with my strength consolidation function which while not identical, is actually decently close to what I use in my final version. This is what I use to coordinate multi-piece attacks.
Goldbot (v7-v26):
My first of many major rewrite of the codebase. I had hacked the prior starter code and just dumped everything into a single file.
I started utilizing numpy in this bot since dexgroves said he liked it and I had never used it before. I mainly use it to simplify manipulation of matrices and to broadcast matrices across dimensions. But that’s all boring stuff. What did this bot do?
Influence Maps
After breaking away from the starter packages, I decided to try to tackle the problem of movement and heuristics with a bunch of influence maps. I also have separate Square and Game class functions, which remained in my final version.
The main gist of GoldBot was that I calculate a bunch of influence maps related to production of the site, production / strength of the site. Strength of enemy pieces up to 3 squares away and having all that vary by whether it was owned by myself, neutral, or enemies. I then take all of those, apply various weights to the maps then add them all together to create a single unified view of the world that the bot could use to make its moves. Later versions of GoldBot split up the heuristics between early and late game.
Decentralizing Moves:
The original version of the bots, based off the starter bots, had each piece decide where it wants to move and then move it independently. I decided to change that up with this. Instead, I get a list of border cells and then decide if I want to capture it. If so, I then call pieces to move towards it to capture! Pieces that are then unassigned move towards the closest available border.
Coordinating Attacks:
I’ll explain in my final version of the bot below when I go into the mechanics of the bot, but the function that I use to coordinate multi-turn/cell attacks has gone relatively unchanged since GoldBot.
Moving to target:
The basis of my moving to target functions (which then eventually mostly get replaced) started here. I would give a target to a square and it would then try to find the up to 2 directions that would allow it to move closer and then pick the one with lower production. I also put in an option to move through friendly targets only. However, a major bug which I didn’t resolve until much later occurs when the following happens:
X X X X X X X
X O O O O O X
X S X X X O X
X O X X X O X
X X X X X T X
X X X X X X X
If O is squares that I own, S is source, T is target, S would always try to move south. I left it as is for now, but this was a source of frustration for a while.
The start of Globalization:
I knew certain squares or regions were more valuable than others, but I didn’t have a good way to get to them. I used the influence map concept to create what I called a recover_map. I basically take each cell, then look X squares out and weight them to each cell. A simple decay function was used. This then gave additional information to the border cells to try to move towards areas of higher value, which I defined as “turns to recover”, or Strength / Production.
All of these changes and complete rewrite was enough to jump me up to gold! I hit a peak of 20 with this bot. Not quite enough for front page, but I was ecstatic. Could I actually manage front page??
Diamond Bot (v27-37):
Trying to take a lesson from erdman, I decided sparsity was the way to go. I rewrote from scratch again because I was tired of trying to tweak my parameters for the 20+ influence maps I had with no way to know if I was affecting any change. This bot is essentially the structure I kept from now until the final with things being tacked on. In general I follow the following process:
Attack --> Expand --> Move to Border
Attack:
All cells within a combat radius of X cells are used to attack the enemy. Straightforward and simple.
Expand:
All non-combat cells are then used to capture the most valuable border cells.
Move to Border:
Instead of moving to the nearest border. I wanted to move to where it would be the most valuable. I used the turns to recover metric and determined that if there were two cells I could capture. One that would take 6 turns to recover, and another that would take 10, as long as it takes 4 turns or less to go to the one that takes 6 turns to recover rather than the one that takes 10, I should move to the 6, even if it’s further away. I prioritize combat cells a bit here by giving them a recover cost of 0. I also penalize far movements a bit since traveling incurs a cost.
Basically, what each cell starts off with is the value of each border & combat cell, then adds the transformed distance cost it takes to get to each of these cells, then picks the best cell and moves to it.
All of the above was sufficient to get me to diamond, and even into the top 5 here and there. It was amazing! Keeping it really simple worked. I got rid of all the influence maps and focused only on how valuable a cell was to capture.
Globalization (v38-v47):
At this point, I feel that the meta was starting to develop. Or at least I started caring about it. I think @acouette was the first to really exploit it with @nmalgauti following close after. Instead of looking and taking at the immediate borders, they used some way to find where the best spot on the map was and then start tunneling towards it. While I was already considering that to an extent, I didn’t explicitly target certain areas of the map to expand to, and not only that, my maps were fairly blurred, meaning that it would head in that direction, but wouldn’t try to tunnel to that area. I decided to try the same.
I used my recovery map for the most part and then did a global search for the max. To keep it within my bot, I actually gave it a massive bonus if that square was on the way to the global max. This way, the bot would always prioritize attacking a cell if it would get it closer and I could simulate the tunneling effect.
To my amazement, making a “simple” change actually worked fairly well. It was then at this time I could see myself in the top 5-10 fairly consistently. My big issue now was that I was often doing very well on the production score, but considerably poorly on the strength side of things. Not only that, I was getting significant timeouts on very large maps from the Dijkstra code. I was running two Dijkstras at this point and on super large maps it just times out during the init time.
Development Time (after v47 – before v48):
At this time, I was getting very frustrated with the timeout issues I was having. Both at the init phase and also during large map games. While some of it is Python, a lot of it is my inefficient coding skills. The two combined means that I have a lot of issues with time. I decided to switch to a compiled language to see if I could speed up my code. Having never learned golang, I decided to try that out.
I spent a couple of weeks learning it and porting the bot over. There were three things that pretty much killed the experiment:
- I couldn’t code a Dijkstra’s Algorithm faster in GoLang than what SciPy has implemented
- I never got around to figuring out the bug that was in my code that didn’t cause cells to attack properly.
- Halite raised the init timeout to 30 seconds.
While it was a failed experiment, it wasn’t a total waste of time as I was able to mull on things a bit and see how rewriting certain things could help.
Final Bots (v48-v80):
I’m lumping everything into the final bots. It was at this time I settled pretty much into my new structure. The biggest paradigm shift for me came with the following change in my code.
Emergent Global Searching:
Up to now, I had been explicitly searching for the most valuable area(s) of the map and artificially providing a bonus to move to those areas. Now, I had a different approach.
One of the Dijkstra’s map that I calculate is the “recovery cost” or Strength / Production, to get to a cell from every other cell. What I do then is I get a list of border cells, and then go through every neutral cell and assign that neutral cell to a border cell. Basically, every border cell gets a bonus to its value if it is the shortest path to another neutral cell. The bonus decreases based off the recovery distance from the Dijkstra’s algorithm. Instead of explicitly tunneling, now cells will tunnel if it means it’ll reach other high value cells as well.
Searching for Production:
I altered how I was trying to determine what cells to capture for production. I combined turns to capture and turns to recover to prioritize which cell to attack. I also look up out to 12-15 turns/squares away, and I only take cells that are > production * 5, instead of all production cells. This solved my issue of having too little strength at the cost of slightly lower production.
Also, I cleaned up my Move to Border phase. I basically said that any cell that isn’t currently being used for production should just move since now if I’m looking out 15 squares and it’s not used for production, it should just move to an enemy border. If it then gets picked up in a subsequent turn by a production call, that’s perfectly fine.
Parity, and Non Parity:
Checkerboard movement was a staple for a while. I’m not sure who popularized it. I think it may have been erdman. I put it in there and then when @mzotkiew came in and was the first top bot to not adhere to it. I got destroyed. I spent a good week trying to revise the combat code and while I’m not happy with it, it does what I programmed it to do. It heavily tries to avoid overkill damage, which it does successfully, but it also does not push through and capture territory very well. I never did solve this problem and it exists in my final bot unfortunately.
Non-Aggression Pact (NAP) (v81-85):
I think this was interesting. I’ll get more into this in my mini history, but the way that this developed and exploded overnight caused what I think are some crazy last minute shifts in the rankings. The last several versions dealt with the rapidly changing shifts. Last turn captures to a few turns before. Attacking when lowest strength. Who knows if any of this actually helped. The biggest change here was that I actively avoided opening up an accidental hole. That is:
A -> B – C <- D
There were many situations in which A would go to B, D would go to C, and then an open border would form. I tried to avoid this situation by not taking C if B could be captured this turn. This gives an advantage to the other player, but, if I can maintain the NAP longer, then hopefully that would outweigh the lost production. I left this on for 1v1 maps, but I’m not sure what the best way to handle it was.