J’ai récemment découvert un site génial pour tous les développeurs qui souhaitent s’amuser et coder en même temps : CodinGame.
D’après Wikipédia : CodinGame est un site dédié à la programmation informatique ludique, proposant d’un côté des casse-têtes de difficulté croissante à résoudre dans l’un des vingt-cinq langages de programmation disponibles, et de l’autre des jeux d’intelligence artificielle multijoueurs, ou des défis de résolution de problèmes en temps limité, ou de code golf.
Je voulais redécouvrir le langage Python, mais également me challenger. Particulièrement friand d’algorithmique et d’intelligence artificielle, c’est tout naturellement que je me suis dirigé vers les combats de bots. Dans les combats de bots, chacun peut coder son intelligence artificielle pour se mesurer à celle des autres.
Je me suis alors inscrit au challenge de combat de bots à venir : Legends of Code and Magic. Dans la suite de cet article, je vais vous présenter mon parcours, semé d’embûches. Le but de cet article n’est pas de présenter l’algorithme final mis en place, mais l’approche que j’ai eue pour permettre à cet algorithme de naître et de terminer 12ème mondial sur 2173 participants et 1er en Python.
Découverte du Challenge
Ce challenge était décomposé en deux phases : une première phase « Sprint » de 4 heures suivi d’une phase « Marathon » de 4 semaines.
Dès les premières minutes après l’ouverture du challenge, je m’empresse d’ouvrir le challenge et de lire le sujet ! J’aurais dû m’en douter… Au vu du titre et de l’image du challenge, ça allait tourner autour des jeux de cartes !
Qu’à cela ne tienne, ce sujet ne pouvait pas mieux tomber. En effet, le jeu sur lequel nous allions devoir coder était extrêmement proche du célèbre jeu de carte à collectionner Hearthstone. Etant donné que j’ai joué de manière semi-professionnelle à Hearthstone il y a de cela quelques années, ce challenge était fait pour moi. J’étais impatient de pouvoir mettre à profit mes connaissances du jeu et mes compétences de développeur.
Les règles du jeu
Pour des raisons de simplicité, certaines subtilités ont été omises volontairement.
Le jeu est un jeu de cartes à 2 joueurs. Après que chacun ait construit son paquet de cartes, le but est d’utiliser les cartes pour réduire les points de vie du joueur adverse de 30 à 0.
Vous l’aurez compris, le jeu est divisé en deux phases : la phase de construction du paquet, et la phase de combat.
Pendant la phase de construction, chaque joueur doit choisir 30 fois de suite une carte parmi 3 proposées pour construire un paquet de 30 cartes. Une carte peut être une créature ou un objet. A la suite de la phase de construction, chaque joueur pioche 4 cartes.
Pendant la phase de combat, le joueur pioche une carte. Chaque carte à un coût. Au début de son tour, le joueur possède un certain nombre de ressources, appelé mana. Pour pouvoir jouer une carte, le joueur doit dépenser autant de mana que le coût de la carte.
- Il peut décider de jouer des cartes « créatures ». Dans ce cas, elles sont invoquées sur le champ de bataille. Chaque créature a une attaque et une défense, et certaines ont des capacités spéciales.
- Il peut décider de jouer des cartes « objets », utiles par exemple pour améliorer ses créatures ou détériorer les créatures de l’adversaire.
- Il peut utiliser ses créatures déjà présentes sur le champ de bataille pour attaquer des créatures adverses, ou directement les points de vie de l’adversaire. Lorsqu’une créature en attaque une autre, elles s’infligent des dégâts mutuellement égaux à leur attaque sur leur défense. Lorsque la défense d’une créature tombe à 0, elle meurt et est retirée du champ de bataille.
Pour ceux qui sont intéressés, vous pouvez trouver les règles complètes du challenge sur le site de Codingame ici : https://www.codingame.com/ide/puzzle/legends-of-code-magic
La phase de « Sprint » : l’échec total
C’est parti pour 4 heures de développement intense. La première idée qu’il m’est venu était de faire une simulation. Qu’est-ce qu’une simulation ? C’est une méthode algorithmique d’optimisation consistant à faire l’inventaire d’un grand nombre de combinaisons d’actions possibles puis retenir la combinaison qui donnait le meilleur résultat.
Sur le papier, c’est un concept qui semble beaucoup plus simple que dans la pratique, d’autant que c’était ma première expérience de ce genre et ma première simulation.
Autant vous dire que finalement les 4 heures sont passées beaucoup trop vite et que mon code était trop bogué pour retourner quoi que ce soit de viable. Ce fût l’échec total. Après ça, j’étais d’autant plus déterminé à réussir le Marathon.
La phase de « Marathon »
Déroulement de la phase de développement
Ayant 4 semaines de développement devant moi, la pression était retombée et j’avais enfin le temps de m’essayer à toutes les stratégies que je voulais.
Dans un premier temps, j’ai repris mon code de Sprint. Pour rappel, c’était une tentative (ratée) de simulation. Ma simulation consistait à tester toutes les combinaisons possibles et de regarder à la fin de mon tour, l’état du jeu.
Après avoir revu mon code, j’ai découvert mon premier problème majeur, le problème récurrent de toutes simulations : ça prend beaucoup trop de temps !!!
A ce moment-là, j’ai procédé de la manière suivante et ça m’a permis d’écrire le cœur de mon algorithme dès les premiers jours du challenge, que j’ai gardé tout au long du challenge.
- J’ai pris une feuille et un stylo.
- J’ai simulé aléatoirement un terrain rempli de créatures chez l’adversaire comme du mien.
- J’ai établi selon moi le meilleur coup à faire.
- J’ai rationalisé toutes les étapes qui m’ont amené à trouver ce coup.
- A partir de cette rationalisation, j’ai écrit un algorithme.
- J’ai codé mon algorithme.
Cela a réduit le nombre de combinaisons dans ma simulation de manière drastique.
Après cela, le plus dur pour moi n’était pas de coder les améliorations, mais de trouver les améliorations. Pour cela, j’ai dépensé un temps considérable à regarder et analyser scrupuleusement tous les matchs que j’avais perdu, comprendre pourquoi et comment j’aurais joué en tant qu’humain pour gagner. Et ce qui était horrible dans tout ça, c’était la démotivation que ça amène. Voir son algo perdre sans arrêt fait très mal à son égo, mais c’est la meilleure manière de s’améliorer. Alors oui, de temps en temps, je regardais des matchs que je gagnais, car même si algorithmiquement ça ne m’avançait à rien, psychologiquement, ça m’aider à rester motiver et à tenir le choc !
Regarder les matchs perdus est le moyen qui m’a permis de trouver des idées et des améliorations.
Pour déterminer si une modification dans mon code était une amélioration ou pas, il y avait la phase de test, ou phase passive de « Je reste bloqué sur le déroulement de mes tests pour espérer un miracle sur sa réussite » !
Au final, le développement s’est résumé à boucler sur ça :
- Trouver des idées
- Coder les idées
- Tester
En ayant l’idée de cet article, je pensais concentrer mes efforts sur la présentation de l’algorithme que j’ai finalement mis en place pour ce challenge. Toutefois, je me rends compte que pour des personnes n’ayant pas eu l’occasion de réfléchir sur le challenge, je ne pense finalement pas que ce soit très digeste. J’ai cependant rédigé un article concernant ma solution pour ceux qui voudraient la lire ici : https://www.codingame.com/forum/t/legends-of-code-magic-cc05-feedback-strategies/50996/32
Problèmes majeurs rencontrés
Le problème principal que j’ai rencontré dans l’élaboration de ma solution est l’utilisation d’outils, de logiciels extérieurs à CodinGame pour analyser, récupérer des donner et simuler localement des matchs. La plupart des développeurs expérimentés utilisaient de tels outils qui les aidaient sans nul doute dans leur phase de développement. Plus précisément, le point crucial de beaucoup de personnes dans la dernière semaine du concours était d’optimiser la phase de construction de paquet. Pour cela, quoi de plus simple que d’analyser la construction de paquet du meilleur joueur, et de copier ses choix à l’aide d’un algorithme de tri topologique. Le problème était qu’il fallait pouvoir récupérer beaucoup de données sur les parties, et je ne savais pas comment faire.
Un des autres problèmes était celui de la motivation : quand ton algo ne s’améliore plus ou très peu et que tout le monde passe devant dans le classement vers la fin du challenge, tu ne te sens pas bien !
Conclusion
Au terme de ces 4 semaines, j’ai énormément appris, en algorithmique, en développement Python, mais également en communication.
La motivation d’abord, puis la détermination est essentielle pour y arriver. Ma plus grande source de motivation était de pouvoir rendre Meritis fier de moi, et pour cela Mathias puis Gaëtan m’ont beaucoup soutenu durant le challenge et je les remercie particulièrement. Combiné à mon fâcheux esprit de compétition et ma volonté de toujours donner le meilleur de moi-même, c’était le mélange parfait !
Pour tous ceux qui souhaitent découvrir ou raviver une passion pour le développement, peu importe le niveau avec lequel vous partez, je vous conseille de venir essayer CodinGame. Je serais heureux de vous y trouver et d’échanger avec vous , sous le pseudo d’Aeneas !
