Après 10 jours seulement de combats acharnés avec des drones virtuels, me voici quand même premier de cette compétition d'intelligences artificielles sympa co-organisée par Parrot et Codingame, sur 621 participants.

Le jeu consiste à prendre le contrôle de zones avec des drones sur un terrain rectangulaire ; chaque zone rapporte 1 point par tour et peut être perdue à tout moment si le nombre de drones de l'adversaire est supérieur. Tous les drones d'un joueur sont pilotés par un seul programme, une intelligence artificelle qu'il fallait développer pour gagner (ou perdre) les batailles de drones. Tous les joueurs décident de leur mouvement en même temps et bougent simultanément à chaque tour.

Chaque jeu met en compétition entre 2 et 4 joueurs en même temps. Un grand nombre de batailles (au moins 100 par joueur) font le classement final.

Pour vous faire une idée plus précise du jeu, allez voir des matchs, par exemple :

 http://www.codingame.com/cg/#!viewgame:4573402

 http://www.codingame.com/cg/#!viewgame:4601859

 The Game of Drones Thrones

*merci à Manwe pour ce jeu de mot involontaire

Le déroulement de la compétition fut comparable à une série télévisée, avec son lot de rebondissements. Pendant une semaine entière j'ai été premier avec une avance confortable. Sur le chat anglophone, un participant m'a comparé à Sauron :

When Sauron grows up, he can't stop

Dimanche dernier, 48h avant la fin de la compétition, j'avais tellement d'avance sur les 2 et 3ème que j'ai regardé des vidéos d'utilisation des drones et discuté sur le chat en ligne plutôt que de continuer à faire progresser mon AI.

Buis patatra, lundi matin, Dieu (god) était venu d'orient (il comprendra) pour faire tomber Sauron : j'étais redescendu à la 2ème place, il était très fort et j'avais beaucoup moins de temps pour coder. Il y en même qui m'ont dit qu'ils étaient tout déboussolés ! Je me suis donc remis au travail.

Hier soir à la fin de la compétition nous étions au coude à coude ; après avoir passé l'après-midi devant moi et la soirée à un poil de cheveu, mon AI est remontée vers la fin pour finir première.

Langage et outils

Python

Comparé à tron, dans ce jeu il y avait moins de calculs à faire faire par le programme :  à priori pas de calcul en profondeur ou de grosse recherche. J'ai donc choisi de laisser le C++ de côté et de programmer en Python, quitte à revenir vers le C++ si en fin de compte j'avais besoin de puissance de calcul mais avec l'algorithme déjà expérimenté en Python ; je n'ai pas eu à le faire. Je voulais moins tenir à mon code déjà existant à un moment du jeu en cas de changement, ne pas hésiter à réécrire des portions entières et plus tenir compte du jeu et de la logique que du code lui même. En résumé, pour ce jeu, moins de programmation et plus de logique et de géométrie.

D'ailleurs, chaque coup était trouvé par mon AI en 1 à 3 ms sur le serveur de jeu.

Je n'ai même pas utilisé les classes avec Python, seulement des fonctions : pas de variables de type drone.pos.x par exemple. Tout est donc rangé dans des tableaux, des tableaux de tableaux de tableaux, etc.. à grands coups de

[f(n) for _ in xrange(N)]

C'est compact, rapide à écrire,  jouissif et crade. Les adeptes des grands Java, C++ et C# feraient bien de prévoir la bassine au moment de regarder mon code en cas de maux d'estomac.

Bon, j'ai quand même documenté chaque fonction de mon code, et passé les données en paramètres pour éviter les variables globales, peu nombreuses.

Environnement

Comme d'habitude, je code sous linux en clavier bépo avec Gvim. J'utilise Subversion comme gestionnaire de version en repérant les révisions qui étaient bonnes dans l'arène, ce qui m'a aussi permi d'écrire cet article. C'est dit, ça fait du bien.

En 10 jours de compétition, pas le temps de programmer un environnement de jeu pour tester différentes versions chez moi, et puis le concept même du jeu annule l'intérêt de faire jouer 2 AI quasiment identiques (le score reste à 0/0 à la fin).

Situation de jeu en SVG

Par contre, pour améliorer le déboguage et le développement, j'ai codé une fonction dans mon AI qui écrit une image SVG quand il est en test. Des situations de jeu sont écrites dans des fichiers texte en entrée, et au lieu d'analyser plein de nombres dans plein de tableaux pour voir si le progamme a bien réagi, je regarde une jolie image. J'ai même un script qui relance le bot sur tous les fichiers de test pour vérifier une nouvelle version.

Voici ce que ca donne :

 Les cercles pleins sont les zones de la couleur du joueur qui les a, les points avec les cercles autour les drones et leur rayon d'action, les traits rouges les mouvements décidés par mon AI.

Explication chronologique de l'algorithme

Le jeu a débuté vendredi 14 mars et a fini mardi 25 mars.

Ma première version a été que chaque drone va vers la zone la plus proche. J'ai mis ce code dans l'arène le premier samedi, et j'ai bossé à la suite jusqu'au lundi. Ce mouvement vers la zone la plus proche est restée depuis pour le premier tour de jeu.

Pour le vrai algo, dès le départ, le but a été de trouver les meilleurs zones cibles et d'y répartir les drones. Voici comment je procède :

Pour chaque zone, on inscrit dans un tableau tous les tours de jeu futurs où il y aurait besoin de mettre des drones soit pour prendre la zone, soit pour la garder, en considérant que tous les drones du jeu peuvent y venir. On réunit tous ces objectifs de toutes les zones dans un seul tableau ; ca donne ça. Attaque = prendre le contrôle, défense = le garder

- zone 1 dans 2 tours 1 drone parmi [0,3] peut attaquer

- zone 1 dans 4 tours 3 drones parmi [0,1,3,4] peuvent défendre

- zone 2 dans 3 tours 2 drones parmi [2,3] peuvent défentdre

etc..

Ensuite on trie ce tableau ; les critères de ce tri ont été un gros point de réglage de mon AI par la suite. Dans un premier temps, ils sont :

Puis on prend les objectifs dans l'ordre. Pour chaque objectif on retient les drones qui ne sont pas encore occupés par un autre objectif précédent, ou dont l'objectif est déjà cette zone, ou bien si leur précédent objectif est suffisamment proche de la nouvelle zone pour pouvoir faire les 2 (distance entre les 2 zones <= delta des délais des 2 objectifs)

S'ils sont assez nombreux pour réaliser l'objectif, on fixe le nombre juste suffisant de drones, sinon on les libère et on abandonne cet objectif.

Enfin on prend chaque drone et on le dirige vers son 1er objectif. S'il n'en a pas, ils va vers le barycentre des zones.

J'ai mis cette version dans l'arène dimanche 16/03 au soir, elle faisait 250 lignes. Je ne me souviens plus combien j'étais classé, dans les 30 premiers je crois. 

Premières optimisations de killer

 Sur cette base, lundi 17/03 matin j'ai codé 3 optimisations :

Cette version de lundi, mise dans l'arène, arrive rapidement 8ème puis monte peu à peu 1ère en quelques heures. Elle restera 1ère dans l'arène jusqu'à sa mise à jour 3 jours après, et la légende commence sur la domination du Sauron.

Précision et géométrie

Les jours suivants, je ne met rien dans l'arène et entame un boulot de précision sur les distances (j'en parle plus loin), et les mouvements des drones qui ont plusieurs objectifs.

 C'est donc le moment de faire un peu de géométrie, et de me donner un outil de débug et d'analyse. Tout d'abord, un papier et un crayon :

 Cliquez pour agrandir. Malgré la retouche sous GIMP,

on voit que le recto de la feuille est une partition.

J'ai ensuite essayé d'utiliser gnuplot pour les schémas de façon automatique, mais c'était la galère. J'ai alors décidé que mon AI écrirait une image SVG sur les situations de test, pour dessiner la situation, et ses choix de déplacement. Après avoir regardé du côté de plusieurs librairies python pour le SVG, j'en ai conclu que ce serait plus simple d'écrire directement l'image en XML.

 Une situation de test en cas de 2 objectifs pour un drone

Comme on le voit sur ces beaux schémas, je cherche le meilleur déplacement d'un drone en cas de 2 objectifs (réels tous les deux, ou réel/secondaire). Le but du drone est d'être assez prêt du 1er objectif pour rester dans l'objectif (en 1 tour sur le dernier schéma), et se rapprocher le plus possible du 2ème.

Je considère donc 4 points dans le plan que je met en concurrence : 

De ces 4 points, on retient ceux qui sont encore ok pour le 1er objectifs même après arrondi des positions. De ceux là on prend le plus proche de la 2ème zone.

J'ai aussi amélioré le tri des objectifs en privilégiant les attaques aux défenses, et en faisant passer devant les attaques qui concernent peu de drones. 

J'ai essayé de mettre un avantage de 1 tour aux drones qui veulent attaquer sur les adversaires qui ne vont pas dans la même direction, considérant que sur un groupe de drones immobiles ceux qui prennent l'initiative d'avancer vers une direction avant les autres prennent un tour d'avance, mais je l'ai abandonné (c'était une régression).

Enfin j'ai corrigé beaucoup de bugs, notemment liés aux distances, et j'ai remis une version dans l'arène jeudi 20/03 matin. A ce moment là j'étais encore 1er mais l'écart se réduisait, et plusieurs s'étaient aperçu qu'ils me battaient facilement à 1 contre 1, notamment MasterBox avec qui j'ai parlé sur ce chat.

La première mise en arène jeudi matin fut un échec car je restais 10ème. J'ai encore corrigé plusieurs bugs, et mis une version dans l'arène vers midi, qui est rapidement monté première.

Cette version, avec ces nouveautés et ses 535 lignes, était beaucoup plus mature que la précédente. La gestion des arrondis était valable même si elle n'était pas exacte, et la précision des déplacement pour les drones limitaient les tremblements des drones précédents, traités de fiévreux, comme moi qui était malade cette semaine là. Elle a fait un carton, et jusqu'à dimanche soir j'avais des fois jusqu'à 5 points d'avance sur les suivants.

Améliorations suivantes

J'ai tout de même continué à améliorer mon AI, sans la remettre dans l'arène.

 La chute et la remontée

En me levant lundi matin, Sauron voit que Dieu l'a dégagé de son podium. Il a donc fallu réagir, et ne pas laisser l'anneau être détruit. J'ai commencé le boulot final sur les distances pour lesquelles j'avais enfin compris l'enjeu, et implémenté 2 améliorations :

Après avoir testé plusieurs petits réglages, j'ai mis la version finale vers 10h20 mardi. Elle fait 784 lignes. Mon AI est directement montée à la 2ème place, en restant 1 point sous god. L'après-midi, les points ont fluctué, les challengers se sont rapproché des 2 premiers sans nous inquiéter, et je passais des fois au dessus de god qui a mis une dernière version dans l'après-midi. Le soir, les dernières entrées dans l'arène des joueurs forts m'ont fait rejoindre tranquillement la 1ère place.

Après la fin, j'ai discuté un peu avec god qui a fait un algorithme très proche mais encore plus préçis que moi sur plusieurs points.  Par contre il n'avait pas implémenté mes 2 dernières améliorations, qui je pense m'ont permi de faire face jusqu'à la fin. Je le félicite pour son boulot, et j'espère qu'il écrira un article.

Les problèmes d'arrondis des positions

J'ai dû passer au bas mot la moitié du temps de codage sur les problèmes liés à l'arrondi des positions des drones, et sur les bugs induits. En effet, le serveur de jeu fournit à chaque tour les coordonnées des drones en nombres entiers, et j'ai longtemps cru que ces nombres entiers étaient la position vraiment retenue pour chaque drone.  Je vais juste détailler la solution utilisé dans la version finale, mais auparavant j'avais codé quelque chose qui tenait très bien la route pour la version du jeudi 20/03, mais basée sur des fausses hypothèses.

J'ai mis du temps avant de comprendre le message sur le forum à ce sujet. Je résume le problème en deux mots : le serveur renvoie chaque tour les coordonnées des drones en nombre entiers, mais travaille lui sur des réels flottants qu'il garde d'une fois sur l'autre.

 Par exemple, un drone sur 0x0 qui va vers 1000x1000 aura comme position réelle au prochain tour 70.71067x70.71067 mais le serveur dira qu'il est en 71x71

Si on se base sur ces positions en entiers, les problèmes suivants peuvent arriver (et arrivent) :

Voici ma version finale sur la question des positions et des distances :

1. Si le drone parait avancer de 2 tours d'un coup vers une zone, en fait il n'avance que de un
2. Si le drone parait ne pas avancer vers la zone en nombre de tours, mais que sa position correspond à celle qu'il aurait s'il avait avancé vers cette zone, c'est qu'il est bien à un tour de moins de la zone.

 

 

Améliorations possibles

Je vois deux grosses possibilités :

Conclusion

• C'était cool, merci aux équipes de Codingame et de Parrot.

• J'ai gagné un drone et un super casque audio

• Bravo et merci aux concurrents, notamment MasterBox avec qui j'ai bien discuté, et bien sûr god.

• On se voit donc le 5 avril chez Parrot
  

• Le lien vers le code est ci dessous, avec tous les disclaimers d'usage.