…Or how I became a Legend in 40 days.
I first heard about Codingame only 2 months ago, when my co-worker challenged fellow colleagues: “Who can write better bot for the Legends of Code & Magic multiplayer bot game (LoC&M)?” I work as a sales manager at a local IT company. While I have formal education in information technology, I never worked as a software developer, so coding has always been just a hobby.
Anyhow, I gave Codingame a try and – as some “new age” books would put it – it changed my life forever. ☺️
Week 1 – Choosing a Language
I deliberately avoided the LoC&M game, spending time getting familiar with the site and focusing on the easy practice puzzles instead. I really needed to bring my quite rusty programming skills up to par before trying anything complex.
In my high school and university years, I programmed in Pascal quite a lot (Turbo Pascal 5.5 – anybody remember that one?), but that was 25+ years ago…I have a basic understanding of C, C++, Java and Javascript, but with no real experience I knew I would just struggle with the syntax. So I chose PHP, which I learned a few years ago when I created a dynamic hobby website. I knew right from the beginning that choosing a loosely typed and interpreted language might not be the best choice when it comes to speed or ease of debugging, but I wanted to focus on the algorithms and not on the language syntax.
Week 2 – Gearing Up
I read the rules of LoC&M for the first time.
Oh man, it’s quite complex! I didn’t have the slightest idea how I should draft or play as a human! I never played Hearthstone or any other card game (okay, Rummy and Uno do not count…).
So I decided to skip this for another week, and go back to the easy and medium puzzles; those gave me a more immediate feeling of success. I realized how good CodinGame’s progress system was – you constantly get rewards: XPs, levels, achievements. I quickly became an addict.
As a sidetrack, I wondered at how many diverse programming languages exist; some I had never even heard of. I solved the simplest The Descent and Mars Lander Episode 1 puzzles in 20 languages by googling up the language syntax. It is clear that functional programming languages are still not my thing…
Week 3 – Taking a Leap of Faith
After solving around 20 puzzles, I felt confident enough for the bot arena. I made a short detour with Coders Strike Back by reaching a low Bronze level just to get a grasp of how multiplayer games work.
LoC&M, here I come!
Getting up in the Wood leagues was much easier than I expected. I just implemented the rules and made sure that the action I generated was at least valid – I used the items I had; I attacked the guards or the opponent if there was no guard. To select a target, I simply assumed that a card with a higher ID was stronger.
Soon I found myself in the bottom part of the Bronze League with a very dumb bot that at least always played valid actions. Although I never won against the boss, I could beat some even dumber bots. I thought “Now the real work begins!”
I moved up to the upper half of the league by improving both the drafting and the action selection in the battle phase. However, I was quite sure that simply using better heuristics would not get me too far. I was so far from understanding the real game strategy, that several times, I “improved” my heuristics just to see my bot fall back in the ranking…
I knew I needed to search the list of possible actions for the best ones, and for this I needed an evaluation function of the game state and a working simulation of the different actions. In theory, I knew about MiniMax and alpha-beta pruning and Monte Carlo tree search, even about genetic algorithms, but I never ever implemented one of these complex algorithms.
Week 4 – Refactoring…Twice
I refactored my code to a (what I thought at the time) better game state representation: instead of multiple global variables, a single associative array which can be copied instantly – important for simulation. I also decided it was not cheating to learn from others, so I read through the forum for some helpful and time-saving ideas. (LoC&M was a contest in 2018, so after it ended, lots of people shared how they tackled the problem.) I realized I should not spend any more time on drafting methods, as contest winner ClosetAI had published a fixed card order which worked much better than any ordering or mana curve I had tried before. By far, the biggest help was the 2*4 hours of stream by the Legend league leader reCurse, in which he created a bot from scratch. Man, this guy can write code faster than I can blink. ☺️
It was time to refactor or, more precisely, time to rewrite from scratch, and introduce a much clearer data and code structure, very similar to what reCurse used in the first stream, with separate classes (no C++ struct in PHP) for Card, Player, Action, Turn, GameState, BotAgent, etc. I also started to write the simulator, similar to the one presented in the second stream of reCurse. I learned once again to hate the loose-typedness of PHP wholeheartedly. When you mistype a variable name, most often you don’t get any error messages; the interpreter just creates a new variable and you wonder why the code does not work as intended…I lost several hours debugging silly typos.
My bot in action
Week 5 – Ranking Up
One month after signing up for CodinGame, my simulator was ready and (supposedly) bug free. Even my heuristics-based bot improved to top 40 of Bronze, because when selecting an action as part of the turn with the simulator, I could take into account the effect of the actions already chosen but not yet played. But there was no point in stopping here, so a single-step Monte Carlo search was the next step: The bot kept randomly generating a valid list of actions and evaluated the resulting game state using a simple function. When the 100 ms response time limit was near, it cut off the search and played the best solution found so far. I could beat the boss in the IDE all the time, so it was time to re-submit. Seeing my bot promote to Silver league was great; it ended up with a decent rank even within Silver.
To celebrate, I went back to some easy and medium puzzles, where I found almost everything much easier than 3-4 weeks ago – this was the reward of practicing and competence building. However, the Mars Lander Episode 2 puzzle tricked me beyond frustration despite spending many hours on it. The best I could get was making it through the first test and failing all the others.
Week 6 – Legendary!
Luckily, it was very easy and straightforward to modify my LoC&M code to do a depth 2 random search. The think time budget was usually enough for me to simulate 3-5000 iterations. I suppose it is much less than a good C++ coder would achieve for the same problem, but it seemed to be enough, so I did not bother trying to optimize my code further. For each randomly generated turn, I generated 30 random versions of a response turn and selected the minimum value (because the opponent would choose what was best for him, not what was good for me). This left enough time to simulate 100-200 different random lists of actions for my turn, from which I selected the best score in a minimax fashion.
The moment of truth came after the next submit: my bot promoted to Gold and jumped up directly to the 11th place within that league. The only idea I had left was to try to fine-tune the evaluation function by changing the weights I applied to card attack, defense, and other properties. It was purely trial and error, and the highest I ranked was 2nd place, just below the boss. It was very embarrassing to be so close but still unable to promote.
In the IDE, I could beat the boss many times but it was still not good enough within the league. Every new attempt required submitting again and waiting several minutes for the 100+ games to finish, so I felt it was not efficient at all. Earlier I had read in the forum that the best players used massive local self-play to improve their bot, so after some searching I found CGBrutalTester and the LoC&M referee by counterbalance (for some reason the original ones by the contest authors did not work for me). I created 20 different versions of my bot (differing only in weights in the evaluation function) and ran around 10,000 games locally against each other.
The funny thing is that this self-play did not really work as planned: it came out from the logs that for some reason beyond my understanding, my bots timed out many times (but not always) when playing locally (but never on the Codingame site). So the winner bot was not necessarily playing better than the others – it just timed out less. Nevertheless, when I submitted it in the arena, it improved just enough to overtake the Gold boss and promote to Legend league.
“I became a Legend” 40 days after I signed up. I felt proud, even though I knew there were still 60 bots out there better than mine. I have to admit I could not have gotten this far without the collected wisdom in the forum posts and the coding streams I saw. But still, what is more important, I enjoyed the whole process and learned quite a lot during these 40 days. I spent much more time with Codingame, both on weekday evenings and on weekends, than I originally thought I would.
Codingame IS fun, even if you are not a professional software developer – you just need to like problem solving.