Legend #14
My bronze bot started by identifying the cells where I want my robots; there are 3 types of these “targets”:
- attack target: a cell owned by the opponent next to one of my cells
- defense target: my cell next to one of the opponent’s cells
- exploration target: an unowned cell that is either closer to me than to the opponent, or equally distant from both players, but has a neighbour that’s closer to the opponent
I continue by running the Hungarian algorithm to assign my robots to these targets, with priority exploration > defense > attack; only one bot can be assigned to each of the attack/exploration targets; defense targets can be assigned to multiple bots (as many as there are enemy robots on the neighbouring cells). Attack and defense targets can be assigned only to the bots in the neighbouring cells, exploration targets can be assigned to any bot, but closer bots are preferred.
After that, I run the Hungarian algorithm once more, this time to assign to every robot the cell it will move to - there are multiple “tasks” corresponding for every cell, so I allow multiple robots to move to the same cell, but the reward the next robots going to the same cell is a bit lower; also, only the 1st robot receives a bonus for moving to an unowned cell.
Spawning is handled as moving from a special cell that has all my owned cells as neighbours; I placed 0 or 1 recycler per turn - the cell where I placed the recycler was the one with the highest [profit/my cells destroyed] ratio out of my cells that no robot wanted to move to. Whether or not I would place the recycler depended on owning a cell that would give enough scrap, results of Voronoi and the number of targets of each type(attack/defense/exploration).
This simple bot (occasionally with some extra heuristics that didn’t seem to have any impact on its winrate) was good enough to get to top 2-5 at the time, then I started to look for improvements, but I mostly ran into things that didn’t work:
- beam search the early game: I usually managed to get to depth 6-8, it was better that what I had at that point, but I discarded it when I improved my recycler placement
- any sort of search that takes opponent’s moves into consideration - nothing seemed to work, I think it’s because a lot of rock/paper/scissors in this game
- tuning the edge weights for the Hungarian algorithm - the algorithm (at least the way I used it) is just not good enough for the game and I decided to completely replace it
One thing that actually worked was using simulated annealing for recycler placement - I estimated the number of cells I can safely lose to recyclers, and I used simulated annealing to pick the best (still using the same formula as described above) recycler positions among the cells I owned, or those that were on a shortest path to one of the exploration targets assigned to my bots (then I rewarded moving towards those in the 2nd run of the Hungarian algorithm that I described above). I used 500ms in the first turn to calculate my plan for recyclers, then I spent a bit of time to update my solution every turn. The algorithm worked well in theory, but not in practice, because all the exploration targets had the same weight, so my Hungarian algorithm kept picking different ones every turn and the recycler plan kept changing all the time.
Hungarian algorithm had to go - it was simply not viable to evaluate the “importance” of targets in a vacuum and get better than mediocre results, and picking the target and the next move separately is bad, and moving towards one exploration target is the same as moving towards another (which this algorithm completely ignores), and sometimes I want more to move than 1 robot towards attack/exploration target (actually spawn stuff to get control of cells that are equally distant to both players instead instead of giving it to the opponent after we trade 1 bot each there - this is probably the biggest problem of my bot), and sometimes defending is more important than exploring, and the distance malus for exploration targets is a pain (e.g. d=1 and d=3 vs d=2 and d=2), and …
My intention was to replace it with another simulated annealing that would assign both one of the targets and a neighbouring cell (in the direction of the target) to each of my bots. A neighbour (next iteration of SA) of one such assignment would be found by changing the target of one of the robots, and if there’s already another robot targetting the same cell, with some probability change that one’s target as well… and repeat - inspired by looking for an augmenting flow/path. This seemed to virtually always find global maximum of simple evals I wrote for testing, and it was already much better in the early game because the recycler SA actually worked; then it was time to actually write a good eval taking into consideration everything that I had in my bot… and then I found that I had no time for CG in the last week, so the Hungarian algorithm stayed.
Considering that I also never implemented any sort of reasonable decision making of building a recycler vs spawning, or breaking deadlocks in the late game situations without recyclers, I’m surprised that I ranked this high - maybe placing recyclers somewhat efficiently, and planning them for future turns is something only very few people did and it actually does something, unlike most of the thing I tried.