C'est la première fois que je participe à un concours de ce type : programmer un robot pour jouer au jeu Tron Lightcycle, souvent appelé jeu du serpent. Codingame, entreprise qui organise des concours pours programmateurs, en a mis un en place depuis janvier 2014 (novembre 2013 pour la phase bêta), qui se terminait hier vendredi 28 février. Etant arrivé à la 5ème place (1er de la phase bêta), voici la stratégie que j'ai mise en place.

Considérations générales

Description du jeu 

Le jeu se déroule sur un plateau de 30x20 cases, chaque partie comprend entre 2 et 4 joueurs qui jouent à tour de rôle. Quand un serpend perd, les cases occupées par sa queue sont libérées.

Les programmes ont 100ms pour jouer chaque coup, et les codes ne doivent pas faire plus de 50ko. Une quinzaine de langages de programmation sont disponibles. 

Documentation

Avant de se lancer dans le codage intensif, il est très important de faire le tour des ressources disponibles sur le sujet.

Concernant le jeu Tron, Google en avait déjà fait un challenge en 2010, et voici l'article très intéressant de  a1k0n qui avait gagné le concours :

http://www.a1k0n.net/2010/03/04/google-ai-postmortem.html

 Pour la recherche en profondeur, lire les ressources concernant l'algo minimax :

 http://fr.wikipedia.org/wiki/Algorithme_minimax

Plus tard, j'ai fait des recherches sur les programmes qui jouaient notamment au Go, et je me suis intéressé aux arbres de recherche associés à l'évaluation par Monte Carlo

A Survey of Monte Carlo Tree Search Methods 

Modification of UCT with Patterns in Monte-Carlo Go - HAL - INRIA

 Pour la fin de jeu, je me suis penché sur les algos de circuits hamiltoniens, et notamment celui-ci :

 A Fast Algorithm For Finding Hamilton Cycles

Choix du langage de programmation

 Pour ce challenge, le temps de codage n'était pas limitée, le temps de calcul par coup, l'était. J'ai donc préféré un langage rapide et j'ai pensé que le C++ serait le meilleur compromis. Ces temps ci j'utilise aussi beaucoup le C++ pour mon algo d'itinéraires de transports en commun avec les données  GTFS, ca me permet de mieux faire le tour de ce langage.

Il s'est avéré en cours de route que les flags d'optimisation à la compilation n'était pas utilisés par le serveur de jeu, et que les robots en C et C++ étaient lancés par gdb. L'avantage de rapidité de calculs par rapport aux langages Go, Java et C# n'est certainement plus si évident ; pour le prochain défi d'AI ca vaudra le coup de faire des tests de rapidité avant. C'est vrai que quand on choisit C++ pour coder un algo calculatoire, dans la vraie vie on choisit aussi de compiler avec -O3 ou -O2

Chez moi, mon IA est 4 fois plus rapide compilée avec les optimisations -O3 que -O0. Malgré tout, je n'ai pas voulu supprimer des méthodes de classes ou inliner au dernier moment comme l'a suggéré Manwe. Je considère que c'est le boulot du compilateur et je ne voulais pas rendre mon code (encore plus) illisible au dernier moment. Malgré tout j'ai essayé d'optimiser les fonctions de base les plus employées durant le développement, avec gprof qui fait partie des outils présentés ci dessous. 

Le sketch des threads

 J'ai longtemps attendu avant de coder une version multi threadée comme d'autres participants. C'est intéressant mais difficile à construire sans bugs, et ca pourrit le code. Une fois les bugs éliminés, Codingame a changé son mode de jeu pour les classements et l'utilisation des threads devenait contre productive.

Environnement de test et de développement 

Outils 

Comme d'habitude, je code avec Vim en mode graphique, et en bépo depuis janvier. Je me suis fait aussi un Makefile pour compiler chez moi. J'utilise subversion comme gestionnaire de version, pour travailler sur plusieurs ordinateurs et sauvegarder toutes les versions du code.

Pour déboguer, j'utilise gdb et surtout valgrind que j'ai découvert à cette occasion ; ce programme génial permet de voir les mauvaises utilisations de la mémoire avant une corruption donnant des résultats incompréhensibles. J'ai aussi utilisé gprof pour voir sur quelles fonctions le programme passe le plus de temps.

Scripts persos 

Le premier système de classement de codingame étant peu fiable, je me suis fait mon propre système de scripts en python pour faire jouer des parties entre plusieurs versions de mon IA et avec moi. J'ai partagé ces scripts au début de la phase publique du jeu ; Yvesmocq et Manwe y ont un peu contribué. 

Dans la dernière version de mes scripts, que je n'ai pas partagé, j'ai la possibilité de passer une variable de réglage à mon IA et de le faire jouer en tournoi contre d'autres versions. La variable est tirée au hasard sur un intervalle, et après une centaine d'itérations on peut tracer une courbe du score en fonction du réglage et voir ainsi la meilleure valeur.

Situations de jeu prédéfinies

En mode debug, j'ai donné la possibilité à mes IA à prendre en compte une situation de jeu préréglée avec déjà des murs, et une taille de terrain paramétrable. J'ai ainsi dans plusieurs fichiers, des situations de jeu typiques avec lesquelles je vérifie le choix de mon IA à chaque changement. Ces situations peuvent être issues de combats perdus dans l'arène avec des mauvais choix de mon IA qu'il a fallu corriger. 

Interactions avec les autres joueurs

Le forum mis en place par Codingame était peu actif. J'y ai contribué en partageant mes scripts python et en y mettant des tests de classement avec des IA simplifiées utilisant un algorithme précis : Monte Carlo, Zones, hasard. Ca permettait de voir la montée du niveau général ; je suis conscient que j'ai pu donner des idées à d'autres joueurs.

Dans un échange de mail, Yves, qui a souvent été premier, m'a parlé de Monte Carlo et Minimax. Il nous a aussi fourni une double énigme (de mémoire) :

- Il faut profiter du cadavres des autres

- Le serpent vois mieux quand il ferme un œil

 La première phrase décrit quelque chose que je faisais déjà ; pour la seconde j'ai essayé de ne tenir compte que d'une direction dans le calcul des Zones : le résultat était intéressant, mais moins fort au classement que mon IA de base, et je n'en n'ai pas tenu compte.

Dans le jeu, ca manquait au moins d'un chat dans la console pour discuter pendant les mises en arène. 

Description de l'algorithme

L'algorithme comprend 3 modules principaux : une fonction d'évaluation de situation, la recherche en profondeur, et l'algorithme de fin de partie quand le serpent est isolé. 

Fonction d'évaluation

Le cœur de l'algorithme est une recherche des zones par ligne de partage des eaux : on trouve les cases que chaque joueur peut atteindre avant les autres et on compte la taille respective des zones.

J'ai codé plusieurs optimisations, que je n'ai pas toutes gardées.

• Score des cases en fonction des accès : en fonction du nombre de cases libres autour d'elle, une case accessible n'a pas le même poids, par exemple de 1 à 4 :  [0.3, 0.8, 1.2, 1.3]
  J'ai aussi essayé la méthode de a1k0n, avec moins de succés ici.
  Cette optimisation est restée assez tard, je l'ai laissée de côté avec la gestion des chambres.

• Parité des cases : sur un échiquier noir et blanc, un serpent ne pourrait pas parcourir plus de cases blanches que noires, seulement une noire de plus s'il est sur une case blanche et réciproquement.

• Bonus de futur cadavre : quand un serpent est en contact avec la queue d'un autre serpent qui a une moins bonne espérance que lui, il a un bonus de points basé sur le nombre de cases occupées par le futur cadavre partagé par les autres serpents en contact actuellement avec sa queue. Le facteur de prise en compte de ce bonus est assez faible : 0.1 dans la dernière version.
  J'ai lu que Manwe a implémenté une version plus précise de ce bonus.

• Chambres : comme a1k0n, je recherche les zones accessibles avec seulement une case : une porte. Quand on va dans une chambre on ne peut aller dans les autres accessibles de la même chambre d'origine. Les chambres sont définies sous forme d'arbre, avec comme racine la zone courante de la tête du serpent.
  Pour trouver les portes j'utilise des motifs de 3x3 cases que je compare avec les zones centrées sur les cases atteignables.
  
  J'ai aussi essayé de ne prendre en compte soit la distance à une chambre plus le score de cette chambre, soit uniquement la chambre d'origine, quand le serpent n'est pas le seul dans une de ces deux chambres. J'ai abandonné ce bout de code.

J'ai un peu essayé l'évaluation par Monte Carlo : jouer des parties au hasard à partir d'un premier déplacement donné. Même avec des optimisations comme choisir à chaque coup des déplacements qui laissent au moins n possibilités pour ne pas s'enfermer, cet algo n'a jamais été au niveau que celui avec les zones. Le seul moment où il est vraiment bon alors que l'autre donne parfois des bêtises, c'est quand le serpent a un choix décisif à faire entre prendre une porte ou une autre sans retour en arrière possible. 

Recherche en profondeur

 Au début, j'ai codé un algorithme Minimax. Je n'ai pas codé d'élagage alpha-bêta car il aurait fallu un calcul du score qui augmente pour un joueur quand il joue, et qui diminue celui des autres, ce qui n'était pas le cas du mien.

Ce qui me gênait dans cet algorithme, c'est que la plus grande part des calculs est perdu à chaque tour : quand l'horloge sonne quand on calcul la profondeur n, on ne tient compte que de n-1, or le nombre de calculs est multiplié par 1 à 3 entre chaque niveau. 

En me replongeant dans une recherche sur les IA de jeux sur le net, je suis tombé sur les méthodes employées pour le jeu de go, avec comme fonction d'évaluation Monte Carlo. Elles utilisent des arbres de recherche où on privilégie les branches qui ont le plus de chance d'être joué, tout en jouant les autres quand même de temps en temps.

J'ai donc implémenté la méthode UCT pour  Upper Confidence Tree Algorithm. Une fois compris, cet algo n'est pas plus difficile à implémenter que le minimax et tout se passe sous forme d'arbre, ce qui est adapté à une programmation objet. Tout réside dans le réglage de la variable k qui sert à choisir en fonction du score, la portion de l'arbre explorée : avec une valeur élevée, l'exploration sera plus en largeur. avec une valeur faible, en profondeur ce qui prend plus en compte les coups probables. Dans ma dernière version, je l'ai mise à 0.08 ; les valeurs de 0.2 et 0.7 fonctionnaient bien aussi.

Cet algorithme prend en compte tous les coups joués dans le calcul des scores et non seulement le meilleurs ou le pire, il est donc difficile à régler et il joue plutôt bien contre les IA moyennement classés et moins bien contre les bonnes, par rapport à minimax. Mais je le trouvais tellement plus beau que minimax que je n'ai pas réessayé cette première solution.

Pour choisir les coups préférés des serpents adverses, il vaut mieux prendre en compte les coups pire pour moi que les coups meilleurs pour l'adversaire (les 2 versions sont présentes dans le code).

Pour le calcul des scores avec UCT, je ne prends plus en compte le nombre de cases du calcul des zones, mais la proportion score serpent / score total. Chaque évaluation est ainsi ramenée entre 0 et 1, et ce qui est privilégié est la place pressentie sur le podium.

Pour terminer, à chaque coup le programme reprend le sous arbre calculé au coup d'avant qui correspond à la position courante ; on récupère donc un peu du calcul précédent. 

Une petite note sur la gestion du temps de calcul : le temps à partir duquel le calcul s'arrête est légèrement diminué par le nomble de nœuds dans l'abre, qu'il faudra nettoyer à coup de delete ce qui dans certains cas extrêmes peut être important.

Fin de jeu

Une fois le serpent sans contact avec la têtes des autres, il faut optimiser le nombre de cases qu'il traverse ; l'algo principal n'est pas assez bon à ce jeu là et quelques cases gagnées font monter de quelques points et beaucoup de places dans le classement.

Ce problème correspond à la recherche du circuit hamiltonien dans la théorie des graphes ; manque de bol c'est un problème NP complet. 

Je me suis inspiré du papier en lien dans la section documentation, et j'en ai tiré mon propre algorithme simplifié. J'ai réalisé ce code quasiment au début et il n'a pas bougé depuis, je vais essayer de m'en rappeler 

• A chaque coup on traite une case dans la liste (au début, la case de départ) et on la fixe avec le numéro n qu'elle porte alors (1 pour commencer)
• Chaque case atteignable non fixée à partir de cette case recoit comme numéro n+1 (même si un numéro lui a déjà été attribuée)
• Pour choisir la prochaine case à fixer on choisit dans la liste une des cases qui porte le plus grand numéro, et parmi celles là on prend celle qui a le moins de voisins. Si plusieurs sont à égalité on tire au sort.

Cet algo, tel quel, ne trouve pas la meilleure solution à chaque fois. Tant qu'on a pas un chemin considéré comme optimum, cad qui couvre autant de cases que lors du calcul des zones avec parité des cases et chambres, on recommence et on retient le plus grand.

Si un chemin correspond au maximum possible on le retient et aucun autre calcul n'est effectué jusqu'à la fin du jeu sauf si un serpent perd. 

Un peu plus tard j'ai implémenté un bonus des cadavres directement dans cet algo : si le serpent est en contact avec la queue d'un autre de moins bon score, le score d'un chemin est bonifié par le nombre de case du chemin qui touche le futur cadavre aprés qu'il soit mort seulement, et le plus proche possible du moment de sa mort. Dans ce cas, le calcul n'est pas mis en cache d'une fois sur l'autre et le résultat n'est jamais considéré comme optimal.

Améliorations possibles

• Malgré quelques essais, je n'ai pas réussi à corriger le défaut de la fonction d'évaluation quand le serpent est coincé entre deux autres,

• Chaque noeud du calcul en profondeur est une copie du jeu et le calcul des zones est recommencé à chaque fois. A la lecture de l'algorithme de certains, je me dis que le jeu au moins aurait pu ne pas être copié sauf à la mort d'un joueur. Le calcul des zones, lui, devrait être difficile à garder d'un coup sur l'autre, surtout avec le calcul des chambres et des portes.

 Liens finaux

Ci dessous, le lien vers mon code. Il contient beaucoup d'options à la compilation, et quelques bouts de code  obsolètes comme l'utilisation des threads. Il fait plus de 50ko ; pour le mettre dans l'arène je le compresse un peu (suppression des tabulations, commentaires, etc..)

Je remets aussi le lien vers mes scripts de test en python, et vers mon classement et celui des autres sur codingame.

La prochaine fois vous me retrouverez sûrement, fort de l'expérience acquise cette fois là..