I made it to the top Legendary League in a bot programming contest. This is the first such competition I've done, with a language, Rust, which I barely know, and all while streaming the entire thing. Here I'll look back at what I did, the good and the bad, and plan for improvements the next time around.
I'm using the profile EveningRust on the CodinGame site, which coincides my stream on Twitch. My final rank was 68th, out of 1713, coming in 2nd place for Rust.
I go into more details about the code, and Rust language, in a followup article.
The Game
The game is a player versus player superhero battle. Each side chooses two heroes; I ended up with Ironman and Doctor Strange in the end -- this was the most popular combination. They fight on a field that contains several bushes to hide in, a few Groots, and one home tower each. The goal is to either kill the other heroes or destroy their tower.
Characters are controlled entirely by code. They are provided with the initial setup conditions via stdin. Each turn we're provided with status updates and expected to print our desired action.
To my disadvantage, but sensibly, the rules of the game are released in stages over several "Wood Leagues". Staggering allows players to start with a more relaxed rule set, encouraging people to play without being overwhelmed by initial complexity.
Given my intent to progress through all leagues, these progressive rules are a bit of hindrance. I was unable to see what was required for the full game and had to guess at code structuring. Fortunately, the viewers of my stream, who were already in further leagues, could fill in missing details. Even without, it wouldn't have been tragic; the initial rules hint at what's to come, and the changes wouldn't be a massive burden. Still, I'd prefer to just have the full details all at once.
Strategy and Tactics
Here I'll speak from a high-level about what I did. Look at "Code Structure" to get an impression about how the code was structured.
For each hero, I created an overall strategy. Most of the behaviour was the same for each hero -- recall we control two of them. I created a series of "tactic" functions. The strategy combined these tactics into a somewhat cohesive whole.
For example, part of my Ironman strategy would consider these tactics, in this order:
- run_away: get me out of a dangerous place on the map
- near_groot: attack a Groot who is attacking me
- attack_hero_range: if the fireball can hit the enemy hero then cast it
- find_deny: kill my units which are about to die to deny the enemy the gold for it
- find_last_hit: look for an enemy unit that I can kill
- buy_item: check the item list and buy something useful
It is a heuristical approach to AI: I'm using my knowledge and the game state to try and make a reasonable judgement. It's a massive set of if-else branching code. It's not an optimizing strategy: it doesn't do any score evaluation or lookahead. Given the openness of the game, and the lack of local opponents, heuristics seemed like a reasonable way to go.
Though a decent approach to creating a bot it suffers a fatal flaw: it's fundamentally limited to my creativity and understanding of the tactics. Like any expert system, it cannot surpass my abilities at the game. There is no automated training. The bot cannot improve on its own. There is no way it can derive new tactics.
The setup of the contest would make machine learning quite tricky here. You don't have access to opponents for local execution, thus nothing to train against. You can't get feedback from a submitted bot other than looking at individual games. You could build all of this locally, but that's a lot of effort. And you'd still have to create a learning model suitable for the game.
Coming up with tactics was the most creative part of this endeavour. It involves watching the game and thinking about some particular action that would be beneficial to my side. Watching the enemy players could also reveal new tactics.
Tweaking and Tuning
The tactics provided a lot of avenues for tuning. Tuning didn't change what happened, only under what circumstances it happened. For example, I had a low health check which made me hide. Does this trigger at 100 health, 150, 10%, or perhaps the total of the opponents attack damage?
This type of tuning made a substantial difference in my rank, but it was hard to do. Each change required submitting and then waiting for the battles to occur -- about 15-20 minutes, but sometimes longer. Beyond that, the rank could continue to change after the set battles. As other people submitted new code, my bots would fight against them and go up or down. The selection of opponents had a significant random element, and the order in which you fought could affect your rank. All of this made it hard to know if a minor tweak actually had an impact or not.
The alternative is to play against a specific enemy. I'd go through my battle list, select a loss and copy it into the testing area. I could replay the battle in the same conditions (all random setup elements were the same). I'd then tweak my code until I beat this situation. Then play against this opponent a few more times, ensuring I have a good win ratio. Then I'd submit it again...
...and often end up lower in the ranks. What worked well against one opponent worker poorly against the other. The trick was either to find a suitable balance or to find the inputs that distinguished between the good and bad situations.
Turn Limitation
My basic approach started showing another limitation as the tournament progressed. I theorized tactics that would be helpful, but I couldn't implement in the code.
My approach was entirely turn-based: each turn I'd read the state and make decisions solely based on that state. There was no way to encode a tactic that would take multiple turns to execute.
For example, Ironman could launch a fireball. It does the most damage when my mana is full, so I wouldn't fire unless that was the case. But, it also did more damage with distance: being further away from the target was better. Planning to move over several turns and then fire just didn't fit into my code!
All of my tactics had to be reduced to turn-based decisions. My superheroes often did back and forth dances or made terrible decisions.
No Strategy
Though I organized my code into "strategies" I didn't have an overall strategy. I just applied my tactics each turn and hoped for the best. I recognized numerous scenarios where this was a failure.
One clear case was an opponent that would slowly wear down my heroes until they died but never bothered attacking neutral units. Had I become more conservative as my score increased I would have won more battles -- having a higher score wins if at least one hero and the tower survives 500 rounds.
I also had a hard time against melee opponents. These typically involved Hulk -- and due to a defect ended up against two Hulks later in the competition. When facing melee, my entire strategy should have changed. I needed to do something entirely different. Instead, I just tweaked parameters and tried to survive the barrage. The melee opponents held me back. It would have been better to recognize the opponents and use a whole new set of tactics.
In the above game, the opponent would also hide in the bushes, waiting to ambush me. I did a simple change to my run_away strategy that detected hiding opponents and prevented walking too far into their side. Ideally, once I recognized hiding I would adopt a whole new plan: I could have just walked along the bottom and attacked their tower, or I could have gone defensive and shot at the bushes they were in (fireball can still hit them even if they are hiding).
Alas, I had no mechanism by which to make global decisions and multi-turn tactics.
The Meta-Game
The contest is broken into leagues, from the training Wood Leagues to Bronze, Silver, Gold, then Legendary. Each time you submit new code you reset your position in the league, fighting at first random opponents, then ladder relative ones. Not only does that make it hard to test minor changes, it also creates segments.
The leagues, past Wood, are opened every couple of days. They have a boss that must be beaten to get to the next one. This boss is a "stable" AI selected from one of the submitted bots. One of the our regular viewers created the gold league boss.
Each league had different types of strategies that worked. The top of the league differed from the bottom half. The bottom was filled with a lot of random stuff, people testing new ideas, and some degenerate strategies. They didn't get high in the rank, but they did successfully interfere with other bots. Thus I needed something that survived the initial class and performed well in the top.
Complicating this even more, the boss of the league also had to be beat. On Day 5 I had the issue of creating a bot that performed good enough against player bots but failed terribly against the boss. I thus couldn't make it out of the Gold league.
The boss was also just part of the leaderboard, any loss against it pushed it's rank score higher. The higher the boss, the harder it is for other bots to get out of the league -- I don't think I was popular that Saturday since I was doing quite good at pushing up the boss. This same problem hit me of course, having a bot that was good enough, but with enough people fighting the boss I couldn't quite get a high enough score.
This boss contention had the effect that, the later you made it to a higher league the better your bot did without tweaks. It got progressively harder to get by the bosses as the contest progressed.
This lack of appreciation for the meta-game caused me grief. I'd often quit streaming when I was at rank 3-5 instead of pushing myself that extra little bit. The next day I'd have dropped down to 40 and needed to do a lot of work to make it up again. I should have kept going whenever I was near the next league. Of course, as I usually stopped because I was exhausted, that may not have been an option.
Patience also plays a role. When you submit a bot, you play a fixed number of battles and get a score from those. Even if the bot is good enough, it may not play enough battles to get a good enough score*. But you continue to be scored as others submit bots.
Ultimately I achieved legendary by merely sitting and watching the leaderboard. By letting enough people fail against me, and avoiding to push up other players near me, I managed to advance. As a testament to all the tweaking, I went up to the 50% point in the next ladder without changes!
*Obviously if the bot is significantly better than the others it doesn't have this problem. If I'd found ways to be great, rather than just acceptable, I could progress a lot faster. Alas, unlike my computer generated bots, I'm not a superhero.
I made one more minor change and then left my bot to its own devices. I was done. I reached legendary, and that was enough.
Conclusion
This contest was both a lot of fun and quite stressful. I learned some new things about Rust, about AI, and about competitions. The stream added to the stress but lent a novel aspect to my programming. I think I streamed too much on the first weekend. It'd be wiser to do some more work offline and just stream a couple of hours at a time.
Read my followup article if you want more details about the code.
A big thank you to all my viewers. They were supportive, helping me out and cheering me on. You made it very rewarding for me!
I'll continue doing non-contest bots now, watch me on my stream. When the next context comes along, I'll sign up and do this all again! Hopefully, I can use this knowledge to better my performance.
If you enjoy my writing then follow me on Twitter or Facebook, or to keep me going, become a patron. Thank you for reading.
Top comments (2)
How come you didn’t implement strategies across turns? Was it a problem with Rust or something else?
It was late in the contest when I started seeing the possibilities for this and I didn't feel like restructuring my code at that point. It would have required significant changes to the structure, and the signature of basically all startegy functions.