gribouillé 27-03-2014 à 00:39:19

Game of Drones Post Mortem

 

 


 

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 :

 

 

   Ce SVG est foncé sous Gimp et converti en PNG pour les besoins du blog.

 

 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 :

  • On met devant les objectifs les plus proches en nomble de tours
  • En cas d'égalité, on met devant ceux pour lesquels il y a besoin du moins de drones.

 

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 :

  • Pour chaque objectif, on trie d'abord les drones possibles avant de les choisir dans l'ordre. On met en avant d'abord ceux qui ont déjà un autre objectif plus proche et compatible, afin de laisser libres les autres.  Sinon on prend d'abord les drones les plus loins de la zone (sachant qu'ils sont assez près pour le délai de l'objectif). A la fin, ce critère changera et passera au drone le plus près.
  •  Pour décider du mouvement de chaque drone, on regarde si on peut mieux faire que le diriger vers le 1er objectif, pour le moment de façon grossière. On définit le concept de distance confortable à un objectif: si quoiqu'il fasse, le drone reste ok pour cet objectif au tour d'après. Par exemple, un drone à 2 tours de distance de la zone à laquelle il doit être dans 4 tours. Si c'est le cas, le drone ne tient pas compte de cet objectif et regarde les suivants. Il va optimiser sa position vers ses différents objectifs, tout en restant dans les clous pour les premiers (et le 1er en priorité)
  •  Du coup, certains drones sont assez tranquilles et vont seulement vers le barycentre. Je choisis donc pour chaque drone un objectif supplémentaire, irréalisable en l'état, vers une zone neutre ou adverse. Cela rend le jeu beaucoup plus aggressif et ouvre des possibilités de vrais objectifs futurs.

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 : 

  • un mouvement du drone vers un point idéal, qui est l'intersection entre le cercle de la 1ère zone avec comme rayon la distance maximum au dela de laquelle il ne faut pas s'éloigner, et la droite qui relie les 2 zones ; autrement dit le point dans la zone 1 ok pour le 1er objectif, le plus près possible de la 2ème zone
  • les 2 intersections des cercles formés par les mouvements possibles du drone et la limite de la zone qui reste ok pour le 1er objectif
  • un mouvement simple vers la 2ème zone.

 

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.

  • En plus de 2 objectifs, un drone peut prendre en compte n objectifs si les n-1 premiers sont confortables ; alors il avance ce qu'il peut vers le nième pour rester quand même dans les autres.
  • J'ai corrigé encore plusieurs bugs
  •  J'ai amélioré la fonction qui attribue les objectifs secondaires, en implémentant un Voronoï (comme dans tron) pour les drones de tous les joueurs par rapport aux zones et en prenant comme objectif supplémentaire celui qui a le moins de drones d'un adversaire et qui est le plus proche du drone

 


 

  •  J'ai donné la possibilité de limiter le nombre de drones par objectif, pour éviter de lutter pour une zone avec plein de drones alors qu'un 3ème larron se gave autre part. J'ai pas mal cherché sur ce paramètre lors des toutes dernières mises en arène.
  • J'ai retravaillé sur les distances suite à un message sur le forum, ce qui n'a servi à rien car j'ai mal compris à ce moment là.

 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 :

  • Calculer l'espérance de durée de domination d'une zone pour chaque objectif, et la prendre en compte dans le critère de tri de ces objectifs. J'ai essayé plusieurs choses, mais la version finale est de trier avec t = esperance - distance (les deux en nombre de tours) et mettant les plus grands en 1er évidemment. 
  • J'ai réalisé un mode défense quand je suis en train de gagner, pour éviter de faire le fou. Une fonction calcule le nombre de points final de chaque joueur si les zones restent les mêmes jusqu'à la fin. Si j'ai le plus de point, je me met en mode défense.
    En mode défense, les objectifs de défense passent avant ceux d'attaque dans la fonction de tri, et le nombre de drone par objectif n'est pas limité.

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) :

  • L'AI croit qu'un drone peut atteindre une zone  alors qu'en fait il mettra un tour de plus
  • L'inverse est aussi vrai, l'AI peut penser qu'un drone est à n tours d'une zone alors qu'il en est à n-1

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

  • Pour mes drones, toutes les positions sont calculées en nombre réels d'une fois sur l'autre sans tenir compte de ce que donne le serveur, avec le même algorithme que le serveur.
  • Pour les drones adverses, les coordonnées entières fournies à chaque tour sont utilisées, mais  2 vérifications sont faites lors du calcul des distance des drones aux zones en nombre de tour :
  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 :

  • Au lieu de trier les objectifs sur des critères, j'aurais pu faire un vrai algorithme qui optimise vraiment le nombre de zones ou d'objectifs atteints.
  • Mon AI est très pauvre stratégiquement. J'ai pensé inclure des considérations géographiques plus globales, mais je ne savais pas comment l'articuler avec le reste. Avec plus de temps, on aurait sûrement été amenés à optimiser l'espace occupé, regrouper les zones contrôlées, s'adosser contre un bord, etc..

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.

 

 


Réactions

bas    terminé   fermer
 

1. legolas  le 27-03-2014 à 12:40:50  (site)

Dèjà plusieurs commentaires suite à cet article, sur le forum du jeu :
https://groups.google.com/forum/#!topic/codingame-game-of-drones-fr/IlyvDwLWdTI

édité le 27-03-2014 à 12:41:18
édité le 27-03-2014 à 12:41:40
édité le 27-03-2014 à 12:42:20

2. legolas  le 28-03-2014 à 00:44:48  (site)

Je viens d'essayer aussi le challenge de Kirk, n'ayant pas pu y participer. Voici mon code en python 3 pour le 2eme exercice avec le labyrinthe, réalisé en 42min:
http://pastebin.com/Xa0hgmgx

3. Pitiponk  le 28-03-2014 à 10:16:36  (site)

Tu as gagné un drone ? wouhou trop classe ! Tu vas l'emmener en rando ? Clin doeil

4. legolas  le 28-03-2014 à 10:32:59  (site)

Avec 15min d'autonomie avec la batterie de base, je ne vais pas marcher bcp... et il est un peu encombrant pour le mettre dans mon sac Rire

5. skypers  le 29-03-2014 à 14:14:21

Juste un petit commentaire : Voronoï, pas Voronai !

6. legolas  le 29-03-2014 à 19:46:19  (site)

Merci, corrigé. J'ai ajouté le lien vers la stratégie de god dans le blog de codingame.

haut    terminé   fermer
 
 
 
 
 

Ajouter un commentaire

- Commentaires seulement à propos de l'article svp.
- Les commentaires sont modérés, ils ne seront pas immédiats.

Merci de laisser une petite trace sur mon blog !
Pseudo : Réserve ton pseudo ici
Email :
Site :
Commentaire :

Smileys

 
 
 
Rappel article
 
 
Un blog comme les autres..