#7 Legend
I started by messing around with deep searches, trying to figure out how deep could I go if I got creative with pruning. The result of that was a beam search that could on the first turn easily get to depth 20 with width ~3000 on maps with a lot of walls (often under 200ms), and at least figured out where I should start putting my roots on the more open maps (~depth 8). The heuristics I used to prune were:
- limit to 4 organisms; after growing the 4th one, the bot stops following the beam
- every sporer has to make a root immediately
- limit sporer and root options to 2-3 most promising ones per organism
- after growing a basic organ, the organism has to build something on the newly-neighbouring squares next turn
- use only basic organs to move, and retroactivaly change them to other organs if I run out of A
- prune non-optimal sequences with harvesters (that lose resources compared to options that build harvesters sooner)
The nodes were evaluated based on the resources, the distances between the roots, and their position relative to the opponent’s first root.
The bot follows the results of the beam search until it meets with the opponent, possibly inserting other moves found by my other algorithm if they don’t interfere with the beam.
I wanted to keep looking at deep searches for 2 players with similar (or even more aggressive) pruning, but unfortunately I got sick a couple of days into the contest, so I gave up on time-consuming apporaches and switched to a “simple” depth 1 bot. I chose to use genetic algorithm with 2 populations - 1 population per player, 1 gene per organism, evaluation by simulating them against each other and rewarding destroying/threatening organs and quantity of resources (and distance to the ones not being harvested). I thought this algorithm was just a meme (I saw it in another postmortem), but surprisingly it could have worked somewhat well. Its biggest problem was that in rock-paper-scissors situations, which were rather common, it kept switching between the options every couple of generations and often chose some of the weirder ones - which I fixed by having one last “generation” of all the unique winners of the previous previous generations.
The vast majority of my bot’s losses were due to the beam search coming up with a specific solution, which the genetic algorithm forgot as soon as it took over, not grabbing space early on (because I would need to tune my beam search’s eval based on the characteristics of the map), and my genetic search’s eval being quite bad at evaluating fights taking more than 1 turn.