Legends of Code and Magic is a game from CodinGame created by aCat and radekmie.
For the people who have not yet heard of CodinGame, it is a web platform that offers coding challenges and hosts artificial intelligence contest. I encourage anyone who wants to learn with fun about coding or AI to try out this website.
Legends of Code and Magic is a card game inspired by Hearthstone and The Elder Scrolls: Legends. It is a turn by turn zero-sum game without the possibility of a tie. The game is composed mainly of two phases, the draft phase, and the battle phase.
In the draft phase, each player needs to choose 30 cards among a random set. This latter is the same for the two players.
In the battle phase, in each turn, the player can execute multiple actions sequentially: summoning monsters, using spells and attacking.
For more information about the rules of the game, see here.
This is the first time that CodinGame introduces the new contest format Sprint. Its duration is only 4 hours. However, lots of participants, including me, think it is a good initiative and a refreshing format, but it has some points that can be improved.
The time between submitting the code and CodinGame ranking the AI can take many minutes or even hours. This is quite limiting in this format due to its length. Apparently, the backend had some problems.
On top of that, we needed the wait the end of the submission to continue the coding. Indeed, we begin only with partial rules of the game, and only when we advance in leagues that the rules become more complete.
However, for the more watchful, the complete rules were shared in the chat to let participant to code in prevision of league promotion. Personally, I used the high-level Python language for its rapid prototyping and ended 11 / 743 using simple heuristics. I take only monsters in the draft phase, and summon the biggest one each turn. For each monster on my board, check each possible trade and attack only when it brings card advantage. Prioritize guard monsters, and go full face if there is not.
The marathon format comes 1 week after the Sprint and lasts for 4 weeks. Its long duration is more suited to methods using simulation.
In the beginning, I made some improvements in my Python version such as handling spells. However, after watching the ReCurse stream (the replay can be found here), I decided to start from scratch and use C++ for its performance. My AI managed to finish 18 / 2174.
The following subsection will explain my final strategy for this contest.
The draft phase is the most important part of this game. The AI needs to choose 1 card among 3, and this 30 times to complete the deck. The cards that will be presented to the AI is picked uniform randomly in this card list.
At first, I tried to write a card evaluation function based on its features: mana cost, attack, defense, abilities. However, after a moment of stagnation, I decided to copy the draft of the top AI. I wrote a simple tool that uses the CodinGame private API to retrieve the games and parses the logs. It also provides simple visualisations such as mana curve:
Using enough games data, we can make a sorted list of cards. However, the draft is still static, a card is always better than another card regardless of the situation. To break this I created different lists based on the player position. Indeed, being player 1, you can try to take only low-cost creatures and rush the opponent. This will be harder to achieve when being player 2.
On top of that, I decided to constraint the deck to a minimal number of monsters. To do so, I created again two different set, one for monsters in priority, and one with all cards. When the deck does not contain enough creatures to satisfy the constraint, the AI will use the MonsterSet. At the end we get 4 sets: MonsterSetP1, AllSetP1 and MonsterSetP2, AllSetP2. These sets are obtained from the scraped games from CodinGame API.
Here is an example of an AllSet:
68, 7, 65, 49, 116, 69, 151, 48, 53, 51, 44, 67, 29, 139, 84, 18, 158, 28, 64, 80, 33, 85, 32, 147, 103, 37, 54, 52, 50, 99, 23, 87, 66, 81, 148, 88, 150, 121, 82, 95, 115, 133, 152, 19, 109, 157, 105, 3, 75, 96, 114, 9, 106, 144, 129, 17, 111, 128, 12, 11, 145, 15, 21, 8, 134, 155, 141, 70, 90, 135, 104, 41, 112, 61, 5, 97, 26, 34, 73, 6, 36, 86, 77, 83, 13, 89, 79, 93, 149, 59, 159, 74, 94, 38, 98, 126, 39, 30, 137, 100, 62, 122, 22, 72, 118, 1, 47, 71, 4, 91, 27, 56, 119, 101, 45, 16, 146, 58, 120, 142, 127, 25, 108, 132, 40, 14, 76, 125, 102, 131, 123, 2, 35, 130, 107, 43, 63, 31, 138, 124, 154, 78, 46, 24, 10, 136, 113, 60, 57, 92, 117, 42, 55, 153, 20, 156, 143, 110, 160, 140
Each number is an id card. For example, the best card to pick is “Giant Squid” and the worse one is “Grow Wings”.
For the search, since the high branching factor and the depth of the game, I ended up with a greedy selection of move. It based on a minimax at depth 2 with alpha pruning. This latter explores all the combinations of 3 AI actions, then all the combinations of 3 opponent actions. The resulting move is the first action from the best combinations of AI actions under the best enemy ones. It updates the local environment with this move, and then repeating the minimax algorithm until the end of turn.
This seems to be a very awkward and not efficient algorithm since we are calculating the same states multiple times between two minimaxes. However, in practice, based on experiments, it is better compared to a flat Monte-Carlo with random selection. The main reason behind this is the speed of the forward model and the number of possible combinations. Given the limited amount of time of 100 ms, we can evaluate only a little fraction of combinations. Using the greedy selection minimax, we ensure that the sequence of actions are coherent and give us the best board state at least for every action triplets.
The evaluation of the board uses handcrafted features and the weights were tuned using random search of self-play (thanks to cg-brutaltester). The following features were used:
- For each cards on the board:
Because of the randomness of the game, to compare if one set of weights is better than another, more than 1000 games are required to decide.
This solution is far from being perfect, there are lots of points that can be improved.