Cet article est basé sur la conférence intitulée « De bronze à légendaire, comment réussir vos IA de bot » présentée par Grégory Ribéron (alias Manwe) au cours de la 6ème édition de Devoxx France.
J’ai pu par la suite mettre en pratique les conseils prodigués lors des 2 challenges Codingame suivants (« Coders of the Caribbean » et « Code4Life »).
Principe des concours Codingame
Codingame organise plusieurs fois par an des concours de programmation au cours desquels plusieurs milliers de développeurs du monde entier s’affrontent. Chaque participant dispose de 10 jours pour mettre au point une IA qui devra affronter celles des autres développeurs au cours de matchs rapides. Toute IA doit être écrite dans un seul fichier sans utiliser de bibliothèques extérieures, le langage de programmation est libre. Chacun des concours a ses propres règles mais en général le jeu se joue en un nombre limité de tours durant lesquels le joueur reçoit un certain nombre de paramètres et doit répondre en 50 ms par une liste d’instructions à effectuer. Si une IA ne répond pas dans le temps imparti ou si elle fait une action incorrecte, la partie est immédiatement perdue.
Les joueurs sont répartis dans un ensemble de ligues (d’où est issu le titre de la conférence Devoxx). Chaque joueur doit pour passer d’une ligue à une autre mettre au point une IA plus performante que celle de référence codée par les organisateurs.
La ligue de bois est celle de départ, elle permet de se familiariser avec les règles du jeu. En général, le jeu commence avec des règles simplifiées et c’est seulement à partir de la ligue de Bronze que le joueur dispose de l’ensemble des règles.
Les IA à battre pour atteindre la ligue de bronze utilisent essentiellement des coups aléatoires et il faut donc quelques dizaines de minutes pour atteindre la ligue de bronze où les choses sérieuses commencent.
Pour atteindre la ligue suivante, il faudra compter quelques heures supplémentaires. Enfin pour atteindre la ligue légende, un joueur entrainé comme Manwe met une quinzaine d’heures.
L’interface de l’IDE de Codingame se présente sous la forme suivante :
La partie en haut à gauche permet de visualiser les parties. Celle du milieu à gauche détaille les règles du jeu. La partie en bas à gauche permet d’accéder à la console,
alors que celle en haut à droite permet d’éditer le code de son IA (ici en langage Java). En bas à droite, il est possible de choisir les IA qui vont participer aux prochains matchs (Ici Manwe le présentateur de la conférence et Agade un joueur gagnant régulièrement les concours)
Les différentes sortes de jeu
Chaque concours présente un jeu différent des précédents, néanmoins ceux-ci peuvent être classés en trois catégories.
1. Les jeux arborescents
Ce sont des jeux comme « Hypersonic » ou « Code4Life » où le nombre d’actions et de possibilités sont faibles chaque tour. Les meilleurs algorithmes pour ces jeux sont le Minimax et le MaxNTree. Le principe est de parcourir toutes les possibilités d’actions de chaque joueur pendant le plus grand nombre de tours possible (en général compte tenu du temps très limité, 4 ou 5 tours). Une fonction d’évaluation permet de donner un score à chaque position. On choisit alors l’action qui donne le meilleur score pour nous même si l’adversaire fait le meilleur coup pour lui.
2. La gestion de ressources
Ce sont des jeux comme « Plantinum Rift » ou « Starcraft » où le nombre d’actions et de possibilités sont élevés chaque tour. Il n’est donc pas possible d’explorer l’ensemble des possibilités sur plusieurs tours. Le meilleur algorithme dans ce cas est la diffusion. Il consiste à attribuer un score à chaque type d’unité/d’usines puis à faire diffuser ce score aux cases adjacentes avec un facteur légèrement inférieur à 1 (0.9 par exemple). Ensuite, chaque unité peut être facilement dirigée ou placée juste en regardant les scores des différentes cases. Il devient alors possible de diriger convenablement une centaine d’unités en quelques millisecondes.
3. Les simulations
Il peut s’agir par exemple d’un jeu de voiture où chaque tour il faut choisir une accélération entre -100 et 100 plus une direction comprise entre -50 et 50. Le nombre d’actions est faible mais le nombre de possibilités est très élevé. Pour ce type de problèmes, les algorithmes génétiques sont particulièrement bien adaptés. Il faut néanmoins faire attention à ne pas générer des coups parfaitement distribués. Dans l’exemple ci-dessus, il est judicieux de choisir une accélération maximale 60% du temps, un freinage maximum 10% du temps et une accélération aléatoire 30% du temps.
Conseils
1. S’entrainer avec les concours précédent
Sur Codingame, les anciens concours sont accessibles quelques jours après la fin du challenge. Vous ne pourrez plus gagner de lots même si vous développez une IA de génie mais cela vous permet de vous entraîner sans limite de temps.
2. Commencer par coder une version simple pour atteindre rapidement la ligue de bronze.
Ensuite, cette version pourra être réutilisée pour simuler rapidement un adversaire.
3. Mettre au point des tests unitaires pour s’assurer que les différentes parties de son code fonctionnent correctement en toutes situations.
Cela permet d’éviter de passer des heures à trouver la cause d’un bug ou de perdre bêtement une partie car une exception a été lancée.
4. Utiliser les logs dans la console pour récupérer les paramètres reçus en entrée.
Il suffit d’envoyer dans la sortie d’erreur (System.err.println en Java) les données dont on a besoin et elle s’affiche alors dans la console de l’IDE Codingame. Cela permet de rejouer une partie en debug dans son IDE (comme Eclipse).
5. Regarder les parties faites par son robot
Surtout celles que l’on perd pour comprendre ce que l’on fait de moins bien que les autres et voir si des bugs sont présents.
6. Faire des parties contre les meilleurs joueurs et récupérer leurs bonnes idées.
7. Bien gérer son temps :
a. Dans les premières heures, se contenter de lire le sujet et d’implémenter de simples stratégies.
b. Evaluer le rapport gain escompté/temps à développer de chaque amélioration pour ne pas perdre son temps sur des développements trop coûteux.
c. Ne pas changer son code au dernier moment.
8. Lire les explications des précédents gagnants pour comprendre quelles stratégies ils ont adoptées.
Par exemple pour le dernier challenge: https://github.com/Agade09/Agade-Code-4-Life-Postmortem/blob/master/Agade_C4L_Postmortem.md
9. Utiliser un gestionnaire de sources pour pouvoir revenir en arrière si une amélioration n’apporte aucun gain ou met trop de temps à développer.
10. Utiliser les ressources mises à disposition sur github :
a. Un outil pour regrouper un ensemble de fichiers Java/C++ en un seul fichier : GitHub
b. Un programme pour faire des parties en local entre plusieurs robots : GitHub
c. Un ensemble d’implémentation de divers algorithmes : GitHub
Conclusion
Même si les challenges Codingame ne sont pas tout à fait représentatifs du travail que vous effectuez au quotidien, ils permettent d’améliorer vos capacités algorithmiques d’un côté et votre connaissance du langage de l’autre. Ils contribuent également à optimiser la gestion de votre temps en vue des entretiens de recrutement car, comme vous le savez peut-être, ils sont de plus en plus utilisés dans les entreprises pour évaluer les candidats.
