6th Legend and 1st with no simulation at all.
At the beginning, I thought simulations wouldn't perfom well in this game, so I decided to go with Python, which I find easier to read and to use for heuristics.
How I managed my time: I mostly coded the first Saturday to get #3, and 30 minutes the next morning to secure #1 with a 4-point lead. I then refactored my code to make it more flexible and I used it to try new strats (giant rush, double giants late game, archer-based defense, etc.) on Monday and Tuesday. None of them made it in the end. Seeing how good RoboStac was with his sim, I decided to code my engine in Python on Wednesday, but it was horribly slow. I profiled it, made my own local referee to test it, search for some hacks to make it faster, but I couldn't make it usable. God I missed some -O2 / inline pragmas. I started translating my code to C++, but that wasn't fun at all and I was not here to do that, so I gave up and decided to do it without sim at all, even if that meant losing some ranks. When Legend opened, I barely made it with the exact same AI I had on Monday but had one of the worst AI there. It was time to react. I was wondering why so many people copied some top AIs ideas (like Nagatwin's anti-collision system or Xyze's defense), but no-one cared copying my swarm strat. I benchmarked it, and realized it was awful. Removing it made me caught up with the top10 again. I then used cgstats to look at my worst match-up and fix them. At the end of the day, I could just go to any defeat I had in my last battles, jump to frame 60, and say "Yup, I've already lost this one." After a really lazy Saturday spent testing some magic numbers, I used the final rush of Sunday to reimplement my build opening (that made me go back in the top5), then study match-ups against the top3, without being able to find a way to beat them. Eventually, I ended #6.
About movement in this game, eulerscheZahl already explained how to find the best path and MSmits how to visit intermediary sites. Personally I copy-pasted a function I made in the BotG contest that was slightly sub-optimal (losing 1 or 2 turns per really annoying site on my way), but earned an hour, used to implement something that may have been more useful. Roughly, I computed the two intersections between the circle representing the movements possibilities of my queen and the circle representing where she could be around a site without colliding with it, going straight forward if I wasn't colliding this turn.
My queen has three states:
- "I'm a new queen but I see big: Let's create a empire"
- "Ok I'm safe, let's expand"
- "Oh God, I'm under attack, what do I do?"
Each state has its own ramifications that I will skim through.
The "I'm a new queen but I see big: Let's create a empire" state
A good starter is really important because in most games, the only damages dealt are in the first two waves sent. After 30 turns, you can almost always know who will win this game. A bad start and you would either have taken way more damage than your opponent (which is instant defeat against defensive sim like Xyze or Agade), lost ground or been cornered.
My build opening is the following: mine, mine, barracks, tower, tower (after benchmarking different combinations, that's the one that worked best for me).
- I want my two mines to be where I will not go anymore, ideally in the top band if I'm red, bottom band if I'm blue
- I want my barracks to be near the opponent side. It has to have easy access to the other side: no site to collide against when units spawn.
- My towers have to be near each other so I can defend easily in the beginning. Furthermore, I need to first build the furthest one, to hide in my side when the first enemy waves spawn.
- If I can, I want a third site to be near my towers to build a tower on it and be safe.
So in this example, I took more damage than my opponent, but my placement already ensures my win. My mines are safe for the rest of the game, I will never go there again and no enemy can come here. My barracks can easily attack the enemy side, top and bottom. Finally I have a third tower easily accessible. On the contrary, see how the blue player is hiding near their mines and how their only tower is not covering their queen. They will eventually lose a mine to protect themselves. 10 turns later, I will have more income, more towers, more health, and a better placed barrack to attack them.
- The "Ok I'm safe, let's expand" state
This state occurs when I believe no one can hurt me (I will define how I computed this in the next state).
If this is the case, then I need to develop my "empire". This is done with a serie of priority:
- If I have a low income (4 or less if I'm ahead to defend, 7 or less if I'm behind to attack), then I try to find a site where I can build a mine safely, even if it is my own tower. To know if a mine is a good idea, I have a rough estimation that computes the number of towers protecting it from any enemy barracks (protecting = on the path). I'd usually ask for 3/4 towers if the enemy has one barracks, 6 if s/he has severals, and 2/0 if I'm confident I am playing against a camper that will not attack me.
- If there are sites where my queen would be useful, I go there. Are considered as such neutral sites (where my queen can build something new), enemy barracks / mines (that she can destroy and build upon) and tower with low health (to repair)
- Else, I don't need anything, I go and hide near my furthest tower from enemy barracks. (very rare case)
For each site I check, I make sure that if I went there, both my next position and my last position would be safe, safe meaning "I won't get hit by a tower there". If I am behind, I consider my knights are covering me, so I can expand, but if I'm ahead, I often disable this because against Agade who had tons of towers I often had the case where my knights died and left my queen alone in dangerous zones, taking free damage.
The site I find is my goal. The goal is where my queen should go, and why, may it take 10 turns to do so. However, there were often multiple towers on the way, that cost nothing to improve on the way. My queen could then stop and repair it, before going to her goal (or change her mind and go elsewhere). I relied a lot on the dense map to modify sites on the way and had no actual pathfinding algorithm to do so.
- The "Oh God, I'm under attack, what do I do?" state
Last, but probably most important. Since I had no simulations at all and since most games ended at the 401st turn, I had to be extra cautious to not take any undesired damage.
At the beginning of each turn, I computed the number of knights really closed to my queen, those near and those far away.
I_m_under_attack = numb_knights_close > 0 or numb_knights_near > 2 or numb_knights_far > 4
With 200 / 500 / 1200 as ranges to computes the numbers. The idea here is to detect really close knights to not get immediately hit, not so far single wave and far double or more waves.
This boolean also takes into account my number of towers to protect myself. I'm not that in danger if three knights are coming but I'm already hiding between six towers. Also, if I was ahead in life, I'd sometimes start the "ultrasafe" mode (or camping mode) where I'd double those range values to be extra extra safe.
Then if I think I am in danger, I have several reactions depending on what is the danger:
- If I am under an enemy tower, I just run in the opposite direction
- If the danger is not immediate (numb_knights_close == 0), I first try to run to a site I can improve. For this, I compute the angle danger-queen-site and consider it possible if it is greater than a certain value (for example 120° or 80° if the enemy are still far away). I'll then validate this candidate by making sure it's not in the middle of nowhere, but comfortably between several towers I own.
- If I haven't found anything before, I run to the most protected tower (often the furthest tower, that has the most towers in the way of the enemy to protect it).
- If I'm already there, I hug around the tower, using it as an obstacle for the knights (with their pathfinding, it really bought time) and then just running around it to limit the number of knights able to hit me.Jeu de survie
Once again, on my way to my goal, I might touch some site that I could improve before resuming my journey. I had no problem destroying a mine to build a tower instead to protect me.
A good example to show it: https://www.codingame.com/replay/307872437
You can see how I used towers to make the knights collide then after some time go in a ultrasafe mode.
When to train
Until Friday evening, I had a swarm strategy where I'd save up during turns 100 to 150 before lauching a huge wave in the last 50 turns. It lead to beautiful replays with 50, 100 zerglings massing and overwhelming the enemy side and sometimes even the CG engine itself. However after some benchmarking, I realised I had a 20% better winrate without it (going to 60% to 71% on 200 games against top15). I was surprised because I saw many blatant wins thanks to this technique. In fact, by saving money for 50 turns, I drastically reduced pression and territory control. Watching some replays against Agade who had a territorially agressiv AI really made it clear.
The metagame is not to kill your opponent, but to deal more damage in early game, then defend. To defend you need to have territory and to constrain the enemy to theirs. And to do it, you need to attack as much as you can. For this reason, I'd attack any time I had enough money to train in all my barracks. I'd build a second barracks (or a third) only if I had a great income, like 6 for the second and 10 for the third. Being honest, that was only the case if I had already won.
I really liked this contest. It had a nice balance between simulation and heuristics and a clear viewer. Thanks CG and the team behind it (csj, harshch000, Netbattler11). The stream about the evolution of the game between the first alpha and the final release was also very interesting, thanks again csj.
For the multiplayer, I'd like the max_mine_rate in the viewer as well. AIdevOOPS made a pull request to fix the asymetry which was blatant against top sim. I think the collisions of the queen should be calculated after the knights's, making everyone "blue side". (A queen taking 1 damage per turn while being circled by 7 knights doesn't seem fair to me).
Lastly, gratz RoboStac for winning this contest. Your AI really was amazing, it is more than deserved.