I finished 17th Legend. I didn’t have as much time/energy as I did with previous contests, so I am very pleased with this result. I only made it into legend on the last night, after midnight. I never cut it this close before. The gold boss was so hard that I went all the way to the top half of legend as soon as I got in.
My code is even worse of a mess than it normally is, because of the time pressure. But amidst the 2.4k lines of duplicate code, bad naming and bugs, there were some good ideas:
I used the first 1000 ms to run a beamsearch for the first 12 turns (or less, it ends after half the map is taken). This beamsearch maximizes tiles owned and minimizes the distance to enemy HQ. This sort of has the effect of the bot trying to get as far out as possible. This gave me a very effective early game in terms of income. I always got the maximum income possible I believe (with a beamwidth of 5000 states), but it sometimes gave me a messy, hard to defend territory. If I had done it on a turn-by-turn basis instead of all in the first turn, I would have been able to respond to the opponent decisions and try to use voronoi to better control the map.
I calculate the finish using a kind of Dijkstra (I think?). I start at enemy HQ and I move outward like a BFS and add up the required costs to get to each square. Every time I hit a square that has been visited at an equal or lower cost already, I break off that part of the search. At some point I hit my own territory and I record the cost to get there. I will keep expanding and hit other parts of my territory until it is no longer possible to get a lower “best” cost. Then I will have found one possible best path. The tricky part is taking into account enemy towers. Because I move in reverse I will not incur the 30 gold cost for a level 3 unit if I go onto an enemy tower, because that would mean I destroyed it already when reversing the path and it would not have the movement penalty after passing the tower. This is not true when multiple towers are near, so each tile also keeps track of the number of tower effects on it. You also need to be careful when hitting your own territory. I calculate 0 cost if there is a unit on there with sufficient level (so the first action would be a 0-cost move when reversing the path). It is a bit complicated but super efficient.
This was hard for me to come up with. In the end I think I found a nice balance between computation and effectiveness. My code was unoptimized and uses a 2D array of Tile objects, so keep this in mind. The steps are as follows:
I make a list of all my tiles that border neutral or enemy territory. I don’t consider walls here.
I make a list of all opponent tiles that border any territory that is not owned by the opponent, including walls. In this case “border” also means diagonally, because cuts can work over diagonals.
I use a very similar algorithm as I explained above for the chain finish, except now it is from every start tile as described in (1) to every end tile as described in (2), so something like 15 times 30 start/end combo’s. Also, I don’t just get a cheapest path. I get ALL cheapest paths. So I allow two different paths with the same cost from A to B, but not a more expensive path from A to B if there is a cheaper one available. There are many instances where the long cuts are the best, but few where a more expensive cut from A to B is better than a cheap cut from A to B. I felt this was a good way to remove a ton of branching.
This gave me an opportunity to make extremely long cuts if I wanted to. I had no “depth” limit. Well… in fact I limited it to 200 gold because in rare instances, gold boss would save 300g and time me out while trying to calculate his cuts. I did this, of course, to be able to put towers in the paths of these cuts. To calculate the worth of the cut I did floodfills for both sides to see what the change in value is for the connected territory. This scorefunction was very rudimentary and could have been much improved.
Limits of this cutting strategy:
a more expensive path between A and B may cause more damage. I don’t consider this. This strategy could be made to take these paths better into account by also allowing an extra 10 cost to get to an already visited tile (or 20 or more). The larger this number is, the more you will branch. There are probably many possible tricks to use to make this better.
I didn’t have time to check for the cost reduction you can use when moving from your own territory to your own territory. You can take out a corner of the path and “move diagonally” in this case. This can lower the cut-cost by 10,20 or even 30g.
When you move from your own territory to your own territory, you can use a wall-connected area as a cutconnection between the two parts of the path that connect to your territory. There are some instances where this would work (with holes in the map). You cut from two places at once, ending on the wall area, potentially doing more damage at a lower cost. I didn’t have time to try something with this.
I did many other things in my code, but I don’t think any of them are worth mentioning. Most of it is common sense and a lot of it required more refinement.
Thanks to the creators for another fine CG contest. I had fun!