I finished on the 4th place
My bot is mostly heuristics, guided by some simulation to help making decisions.
I have the following functions, which I apply one after another:
Doing a lethal attack, then avoiding it, moving my units, handling cuts, building towers, spawning units, building mines, undoing moves.
Lethal attacks
You often see bots collecting a lot of gold and then building a long chain to the opponent headquarter. My bot does that as well, starting a Dijkstra search at the own headquarter, going towards the opponent. Here connections to my one cells as well as one movement are free. All other connections are equal to the spawn cost of the target cell (beware of towers getting destroyed, they no longer protect their neighbor cells).
If I can’t find a way to kill my opponent, I check if he can kill me - and bruteforce possible tower locations to stop him.
Moving units
Moving several units requires some coordination, to avoid them blocking each other. I have a score matrix, where the rows are the individual units and the columns are the cells of the board. An entry contains the score of a unit being on a given cell. Here I reward conquering new regions, cutting off some opponents with my move and also closeness to a target cell (which is the opponent base for my front line and the closest cell which isn’t mine for the units in the back).
As each unit can only move to one cell and each cell can only be occupied by one unit, there is an efficient way to find the maximum possible score: the Hungarian method.
Edit: you can find a more detailed explanation on this below.
The downside is, that it only optimizes for the current turn. Units can easily end up in a situation with no free cells to conquer next to them. The Hungarian method gives one optimal solution among many that exist. So I try to reassign the target of each unit - one after another - and ensure that the score stays the same. If that reduces the amount of stuck units for the next turn, I keep that solution.
Then I move the units one after another. The order matters, as some units have to move first, to create free spots for the others.
Cuts
Breaking the connection between the opponent headquarter and some cells of his is an effective way to kill his units and also reduce his income.
I do a full search of depth 5 as well as another search of depth 10 with only one corner along that path (that is forming an L-shape), starting from every cell next to my own territory. For each of those possible cuts I check the cells and units still active. I take the best cut possible, the scoring being:
regionScore = 2*tilesDeactivated + 3*unitLevel (of units killed/deactivated) + 2*towerInactive + 6*towerDestroyed
cutCost = sum of pow(spawnLevel, 1.3) for each spawn of the cut
cutScore = regionScore / cutCost
The exponent ensures that a level 3 unit is more expensive than 3 level 1 units, although they have the same spawn cost. This is to take the upkeep into account.
With my own cut applied I try to find an opponent counter attack. If the counter has a higher score than my cut, I try to block instead. I do so by placing a tower or a level 1 unit.
I repeat this as long as I find good cuts and have enough gold.
Other players like Magus or dbdr find more potential cuts. So I fail defending them some times, as I don’t see them coming.
Coward strategy
Some players tend not to attack, but collect gold for one single lethal attack. When the opponent gold is greater than the income + 20, I assume that my opponent is doing that. In this case I stop the turn here, not calling the functions listed below. I also do so, when I can collect the money for a lethal wave before my opponent (with 1 extra turn for a safety margin).
Building towers
I also build towers beside countering cuts. I place them next to the border or at a spot where they can protect my border level 1 units from hostile level 2 ones.
Spawning units
At the beginning I have an offensive spawn, trying to get as close as possible to the opponent base. When the opponent is close enough, I try to expand my own territory instead. I exclude cells as spawn candidates, which are going to be visited in my next 2 move turns (running the Hungarian method again to figure that out).
Building mines
If I have some gold remaining, I build mines as far away to the opponent as possible. I’m not sure if this is helpful in any way or not.
Undoing moves
As the bot just runs some functions in a certain order, without them knowing about each other, this can result in bad decisions: a unit moves away from a cell to capture another one - but leaves the previous cell unprotected. The tower building repairs this in most cases. However if the move endangers the previous tile of a level 1 unit, I undo the move not to give up my territory next to the border.
About the game
I liked the game for its simplistic rules. I didn’t even try pulling off a fully search based bot, as the branching factor is enormous.
The biggest issue, the advantage of the red player, was addressed at the opening of silver - thank you for that.
I’m still not sure how to use mines the right way. There are some games lasting over many turns, where they can help for sure. But in other cases you will be better off just saving the money for the next turn.
I had a lot of fun competing, despite my disappointing ending.