Comment j’ai terminé dans le TOP 6% du CodinGame Fall Challenge 2020

Accès au challenge

Cette année, Esker a participé au Fall Challenge organisé par CodinGame. Ce rendez-vous met en combat des IA de programmeurs autour d’un jeu dévoilé pour l’occasion. Nous avons eu 10 jours pour obtenir les meilleurs résultats ! J’ai obtenu la 408 ème place sur plus de 7000 participants. Je vous propose dans cet article de détailler mon cheminement de pensée.

L’objectif du jeu était de réaliser une IA qui obtienne le plus de points possible. J’ai choisi de programmer mon IA en C++, également utilisé au quotidien chez Esker.
Pour marquer des points, il fallait réaliser des potions. Toutes les potions n’avaient pas la même récompense (dépendant des ingrédients nécessaires à leur brassage). Nous avions donc un inventaire contenant des ingrédients et des sorts permettant de transformer certains ingrédients. Par exemple un sort transformant 2 unités d’ingrédient bleu en 1 unité d’ingrédient orange.

À chaque tour, nous devions choisir une action parmi les suivantes :
✨ Lancer un sort pour créer des ingrédients,
🧪 Brasser une potion,
😴 Régénérer nos sorts en se reposant,
🎓 Apprendre de nouveaux sorts.

Sachant que quelques règles supplémentaires venaient pimenter le jeu :

• Une potion brassée par l’adversaire ne pouvais plus être brassée,
• Les potions des clients les plus pressés avaient des bonus,
• Plus un sort à apprendre était loin dans le livre des sorts, plus il fallait dépenser pour l’apprendre,
• Certains sorts pouvaient être lancés plusieurs fois par tour (sorts répétables).

La partie prenait fin après 100 tours, ou quand une IA a réalisé 6 potions. Celle ayant le plus de points gagnait alors la partie. Pour déterminer le classement, notre IA combattait automatiquement contre des centaines d’autres concurrents.

Le début de la compétition a été particulièrement lent pour moi. J’ai vite fait le parallèle avec le jeu de société Century qui a les mêmes règles de jeu, mais un contexte différent. L’analogie m’a rapidement permis d’avoir des premières idées. Au total j’ai réalisé 3 versions de mon IA, une version algorithmique, une version utilisant un BFS (arbre de recherche en largeur) et une version plus optimisée.

VERSION Algorithmique

La première version de mon bot est celle qui m’a pris le plus de temps à développer. Beaucoup de gribouillages sur des feuilles, à construire des arbres avec des chiffres dans tous les sens. Mon algo était alors découpé en 3 étapes :

• Chercher une potion réalisable avec l’inventaire actuel,
• Sinon, construire un enchainement de sorts à lancer pour obtenir les ingrédients nécessaires, et ce pour chaque potion visible :
• Pour chaque ingrédient, je teste toutes les combinaisons de sorts me permettant d’obtenir la quantité recherchée puis j’appelle le code récursivement pour trouver comment produire les ingrédients nécessaires à cette combinaison. Cela me permet de construire un arbre de profondeur 4 (1 par ingrédient) pour une recette donnée, avec pour chaque nœud la liste de sorts à lancer pour obtenir la quantité voulue. A partir de cet arbre, je peux ainsi construire la plus petite liste possible pour compléter la recette. Pour accélérer le processus, un cache garde en mémoire la meilleure liste de sorts pour une recette donnée.
• De ces listes de sorts pour brasser les potions, je ne garde que celle qui a le moins d’étapes (en comptant les repos), sans dépasser 5. Si ça dépasse ce maximum, c’est qu’il est plus intéressant d’apprendre un nouveau sort pour aller plus vite.
• Si aucun enchainement satisfaisant n’a été trouvé, je regarde alors le livre de sorts pour en apprendre de nouveaux :
• Pour chaque sort que je peux apprendre avec mon inventaire, je calcule l’enchainement de sorts à lancer pour produire la même chose avec ceux déjà appris, et l’enchainement pour produire les ingrédients nécessaires pour lancer le nouveau sort. S’il faut moins d’étapes pour produire les ingrédients nécessaires et lancer le sort que pour produire l’équivalent avec mes sorts actuels, alors je considère qu’il est intéressant à apprendre.
• Parmi les sorts retenus, je sélectionne celui qui m’apporte le plus de valeur, en fonction des ingrédients dépensés et produits.
• Si aucun sort du livre n’est assez intéressant, je me rabats alors sur la production de l’ingrédient bleu pour avoir plus de choix sur l’apprentissage de sorts.
• Enfin, si aucune des précédentes actions n’aboutit, je me repose.

Cette première version a une logique assez complexe et m’a demandé presque 4 jours pour aboutir à un résultat satisfaisant. Pendant ce temps, je voyais mes collègues monter en ligue Argent alors que j’étais coincé dans le fond de la ligue Bronze. Je me suis plusieurs fois demandé si j’allais vers une solution utilisable. Mais finalement j’ai commencé à battre facilement le Boss de la ligue Bronze. J’ai ainsi pu monter en ligue Argent et me positionner vers le milieu du classement.

VERSION Simulation

Il me fallait de nouvelles idées. En regardant le chat, et en discutant avec mes collègues participants, j’ai décidé de changer complètement de cap pour mon bot : simuler plusieurs tours de jeu avec un BFS pour analyser le plus d’options possibles. C’était l’objectif de ma deuxième version.

J’ai pris beaucoup de plaisir à la développer parce que, même si j’avais déjà l’habitude de faire des arbres de décision pour choisir le meilleur chemin, je n’avais jamais vraiment implémenté de BFS à proprement parler. J’ai donc commencé à réfléchir à la façon de représenter l’état du jeu pour un nœud de l’arbre. La construction de ce dernier s’est avérée assez simple, et c’est aussi pour cette raison que j’aime bien cette version. En deux jours, j’ai réussi à reprendre tous les éléments qui faisaient la force de la première version pour les intégrer dans la deuxième.
Ma logique de construction des nœuds enfants était la suivante :

• Je commence par parcourir les potions réalisables. Si je me rends compte que l’adversaire peut faire la même potion que moi, alors je force celle-ci pour ne pas me faire avoir, et j’arrête mon BFS. De même, si l’adversaire peut finir la partie en brassant sa 6è potion, et que je peux moi même en brasser une, même si ça n’est pas l’option la plus intéressante dans le temps, je force le brassage de cette potion parce que je ne pourrais pas faire mieux. C’est le seul moment où je me soucie de ce que peut faire l’adversaire. Pour chaque potion retenue, je crée un enfant BREW.
• Si je ne force pas le brassage, je parcours alors les sorts que je n’ai pas encore appris à une étape précédente de la simulation. Si j’ai assez d’ingrédients pour l’apprendre, je crée un enfant LEARN uniquement si le nouveau sort ne déséquilibre pas ma production globale. Pour chaque ingrédient, je refuse que la somme dépense + gain soit inférieure à -1 et supérieure à 5. Ca permet à mon bot d’équilibrer la production de chaque ingrédient pour un brassage optimal. Je limite mon nombre de sorts total à 10, ce qui me semblait un nombre correct pour brasser les potions rapidement sans perdre trop de temps à apprendre des sorts. Toutes ces valeurs ont été trouvées expérimentalement et en étudiant les IA adverses.
• Si j’ai dépassé la limite de sorts ou que je n’ai pas trouvé de sort suffisamment intéressant à apprendre, je parcours l’ensemble de mes sorts connus et que je peux lancer avec mon inventaire courant. Pour gérer les sorts répétables, je calcule le maximum de répétitions possibles avec mes ingrédients, et je crée un enfant CAST pour chaque répétition de 1 à max possibles. Ça permet à mon bot de ne pas forcément transformer tous les ingrédients possibles mais juste ce qu’il faut pour avancer vers le brassage d’une potion.
• Enfin, j’ajoute un enfant REST pour récupérer l’usage de l’ensemble de mes sorts.

Pour éviter de parcourir des nœuds dans un état déjà observé auparavant, et ainsi faire des calculs inutiles, je me servais du hash de cet état pour éliminer la redondance.
Avec tout ça, mon BFS n’était pas très performant mais me permettait de descendre jusqu’à une profondeur de 6–7 dans une limite de 40ms.
A partir de l’arbre généré, je récupère la feuille la plus intéressante avec une fonction d’évaluation prenant en compte la valeur de la potion, le nombre d’actions pour la brasser, la valeur intrinsèque des ingrédients dans l’inventaire, et surtout ne pas déséquilibrer la production.

Une fois la meilleure feuille de l’arbre identifiée, je remontais jusqu’au parent de profondeur 1, correspondant à la prochaine action à exécuter. Cette nouvelle version a fait des merveilles puisqu’elle m’a propulsé dans le top 600 en ligue Argent.

VERSION optimisée

J’ai malgré tout assez vite stagné. J’ai alors commencé à réfléchir à une troisième version. Le problème principal de mon bot était le nombre de nœuds explorés, vraiment faible par rapport à ce que d’autres arrivaient à obtenir. Je me suis donc mis pour objectif d’optimiser mon BFS avec un état plus léger et donc un hashing plus performant. J’ai aussi beaucoup aimé cette phase qui m’a poussé à jouer avec les bitset mais malheureusement le temps m’a manqué pour arriver à un résultat satisfaisant.
J’ai tout de même réussi à faire rentrer toutes les informations dont j’avais besoin dans :

• Un premier uint64: état (castable) de chaque sort pour moi et mon adversaire avec prise en compte des sorts appris pendant la simulation.
• Un deuxième uint64 plus fourre-tout:
• Les 10 premiers bits pour les potions : 2 bits par potion pour stocker qui l’a brassée. 0 = personne, 1 = moi, 2 = l’adversaire, 3 = les deux,
• Les 36 bits suivants pour le livre de sorts: 6 bits par sort visible pour stocker la taxe (4 bits) et qui l’a appris (2 bits, comme pour les potions),
• Les 18 derniers bits sont pour mon action : 2 bits pour le type d’action. 0 = BREW, 1 = CAST, 2 = LEARN, 3 = REST, je ne me sers pas de WAIT. 8 bits pour l’ID de la cible (0xFFFFFFFF = pas utilisé). 8 bits pour la répétition (0xFFFFFFFF = pas utilisé).
• Un uint32 pour mon inventaire et celui de l’adversaire: 16 bits par inventaire, avec 4 bits par ingrédient.

Ce changement principal m’a permis de générer bien plus de nœuds et donc d’atteindre une profondeur 11 par moment. Ça m’a aussi poussé à rafraichir mes compétences en manipulation de bits et je m’en resservirai probablement pour les prochains défis, voir pour ceux déjà passés !

La bonne surprise a été mon passage en ligue Or. Alors que de plus en plus de monde passait dans cette ligue, j’ai fini par me rapprocher du Boss de la ligue Argent, et il s’est avéré que mon bot était meilleur. Une fois en ligue Or, il a continué à grimper dans le classement pour se stabiliser autour de 400. Un classement dont je suis assez fier après avoir passé la moitié du temps total à galérer sur la première version, à me demander si j’arriverais à avoir un bot suffisamment bon pour monter en ligue Argent.

En conclusion, j’ai pris encore une fois beaucoup de plaisir (et beaucoup de temps :P) avec ce défi CodinGame. Cette fois j’ai eu l’occasion d’échanger avec mes collègues de travail sur les bonnes idées ou les choses à éviter. J’ai aussi appris à mieux implémenter un BFS, comment compresser un état de jeu dans un minimum d’espace, et de nouvelles idées de stratégie pour le jeu de société Century !
J’ai hâte de voir ce qu’ils vont nous concocter pour la prochaine session au printemps 2021, pour pouvoir mettre à profit ce que j’ai appris avec celui-ci.