Fin de la Tron Battle : bravo à tous !

STAY CONNECTED, FOLLOW CODINGAME NOW

Il y a deux mois, nous lançions la Tron Battle sans réellement savoir si le concept allait vous plaire.
Au final, vous avez été 1564 à tenter l'expérience et 672 à pousser votre IA dans l'arène.

Vendredi dernier (le 28/02) à 1h, c'était la dernière ligne droite pour poster son IA.
Il y a eu des retournements de situation de dernière minute... c'était plus que serré et finalement, les joueurs sur le podium du Top 3 dans le leaderboard sont : ThomasNzO, yvesmocq et hau. Ils repartent comme promis avec un t-shirt CodinGame. Bravo à eux et à vous tous qui avez participé !

Pour répondre aux questions qu'il y a eu sur la mailing list ou ailleurs, nous ne prévoyons pas de publier un classement par langages. Quant aux code source, on ne les affichera pas automatiquement non plus, puisque la battle a été ajoutée aux exercices de la page training, et qu'il faut bien que les nouveaux venus se creusent un peu la tête... :) Vous pourrez malgré tout reposter vos IA et les retravailler encore si souhaité.

Par contre, on vous invite à partager votre code sur les réseaux que vous aimez (Github, Quora, blogs persos...). On sait que plus d'un seront impatients de savoir quelles stratégies vous avez utilisées !
Voici d'ores et déjà quelques initiatives intéressantes de débriefs et publications, (on en oublie sûrement, faites-nous savoir ce que vous avez produit, on se fera un plaisir de relayer) :
  • Loujo a publié un article sur son blog
  • yvesmocq nous envoie son code ("buggé") ;)
  • Manwe a rédigé un article complet sur la mailing list, avec le lien vers les fichiers sources, de manière à vous permettre de compiler son bot via "make bot" (sous linux) après avoir renommé le fichier Makefile.txt en Makefile (manwe.cpp, main.cpp, makefile.txt). Voici l'article :


Débrief de Manwe:

Strategie

MaxN Tree a profondeur progressive
Comme beaucoup de joueur, mon bot fait une recherche a profondeur progressive pour savoir quel est le meilleur coup a jouer jusqu'a ce qu'un timeout se déclenche (a 80ms dans mon cas). Je construit donc ce qu'on appel un MaxN Tree, représentant l'intégralité de tout ce que les joueurs peuvent jouer, puis je considère que chaque joueur va jouer son meilleur coup et fait donc remonter progressivement le meilleur coup de chacun. Si un joueur n'a plus de possibilité, je fais une copie du jeu pour continuer l'exploration (l'opération étant difficilement réversible) et je continue l'exploration. Tout réside donc dans la fonction d'évaluation qui va permettre de definir quelle situation est la meilleure.

Fonction d'évaluation
Pour cela je procède en trois passes:

Première passe
Une première passe partage l'espace "bêtement" en considérant qu'une case appartient à un joueur du moment qu'elle est plus proche de lui. Elle permet aussi de calculer deux informations capitales : a quelle distance la plus proche se trouve les autres têtes de serpent ce qui me permet de determiner qui est dans une zone close, ainsi que la distance la plus proche a laquelle se trouve les murs des serpents de chaque autre joueur.

Deuxième passe
Une deuxième passe calcule le maximum de cases qui pourront êtres couvertes en ne considérant que les cases qui sont dans notre territoire (defini par la première passe). Je ne cache pas ici que je me suis fortement inspiré du code du gagnant du google ai challenge de 2011 (sur tron) : a1k0n. Je n'avais pas participé à l'époque, mais j'avais fait les deux contests suivants (planetwars/antwars). Le principe est donc d'identifier sur la carte des points d'articulations qui une fois traversés nous forceront a faire un choix entre deux zones bien définies (un embrachement en T ou en + par exemple). Le principe est donc de construire récursivement des groupes de cases que l'on peut parcourir comme on veut (car ce ne sont pas des points d'articulations), et d'essayer de les parcourir dans l'ordre qui donnera le plus grand chemin. Ca permet par exemple si on a plusieurs embranchements de ne considérer que le chemin le plus long. Quand il n'y a que deux joueurs j'ai conservé la notion de front d'a1k0n (qui ne marche pas a plus de joueurs car elle réduit beaucoup les valeurs estimées en créant plusieurs fronts). Celle-ci permet en gros de faire un choix quand une partie du territoire est en contacte avec une zone controlée par l'autre joueur. Soit de l'ignorer, soit d'essayer d'aller combattre pour celle là, et dans ce cas considérer qu'on se rends le plus vite possible dans cette zone. On fait ensuite le total des cases du chemin le plus long, et on compte aussi le nombre de liens antre ces cases. Les liens entre les cases permettent en cas d'égalité du nombre de cases de privilégier des mouvement qui conserveront un maximum de liens, et donc eviteront de creer des couloirs. Dans chaque groupe, on compte le nombre de cases blanches et noires (comme un echiquier) ce qui permet en plus d'ajuster le nombre de cases en fonction de la couleur de la case d'entrée, et la couleur de la case de sortie. Ca permet d'avoir une meilleur estimation dans les cas ou il faudra de toute facon laisser une case de coté.

Troisième passe
Une troisième passe enfin ajuste le nombre de cases atteignables : si un autre bot est enfermé seul, et donc condamné car il lui reste seulement n cases disponibles, j'ajuste alors le nombre de cases des autres bots qui ont une distance minimale a un de ses murs supérieure au nombre n de cout qu'il lui reste a jouer (car je suis sur qu'ils pourront l'atteindre après sa mort). En écrivant ce texte je me rends compte que j'aurais certainement même pu considéré la distance la plus grande... Dans ce cas je réparti les cases restantes, ainsi que tous les tours joués depuis le départ entre les joueurs. Ca permet donc de voir d'assez loin un territoire qui va se libérer et de le prendre en compte

Optimisations

Afin d'économiser du CPU, je fais une première évaluation avec l'état du jeu courant. Je "désactive" alors les joueurs qui sont isolés et seuls (aucune autre tête dans leur territoire). Je ne les fait donc plus jouer quand je parcourt l'arbre de jeu, mais je décompte seulement le nombre de cases qu'il leur reste a jouer. Ca permet de les supprimer du jeu si besoin quand il ne leur reste plus de cases, sans consommer beaucoup de CPU.
Les coups de différents joueurs sont facilement réversibles. J'ai donc un seul état du jeu qui me permet de parcourir l'arbre. Les points d'articulations sont aussi rafraichis au fur et a mesure des déplacements. Ce qui fait que quasiment 90% de mon CPU est utilisé dans la fonction d'évaluation.
J'étais assez déçu de ne pas pouvoir choisir les options de compilations. En effet, j'ai mesuré avec callgrind que mon code était 4 fois plus rapide en -O2... En cherchant sur le net comment forcer ces options, je suis tout de même tombé sur un attribut de GCC permetant de forcer l'inlining de certaines méthodes. Ca m'a permis de quasiment doubler les perfs. C'est mieux que rien!

Historique des fonctionnalités

En utilisant un simple partage des cases et en prenant le meilleur score a chaque fois j'étais rapidement rentré dans le top 50. En ajoutant une recherche en profondeur fixe a six, et en prenant en compte la mort des joueurs dans l'arbre, je m'étais classé dans le top 15 (assez instable à l'époque), flottant entre la 2/3e place et le top 15. J'ai ensuite essayé plusieurs stratégies de calculs des scores (est ce que je fait des différences avec les autre etc...)
J'ai désespérément essayé ensuite d'implémenter un équivalent de l'élagage alpha-béta qu'on a sur un MinMax. J'ai trouvé cet article très intéressant sur le sujet : https://www.aaai.org/Papers/AAAI/2000/AAAI00-031.pdf. Malheureusement, après une semaine et demi passée sur son implémentation, je n’ai pas réussi, et donc a moins d'une semaine de la fin du concours j'ai laissé tombé.
Jusqu’à mercredi 26 je n'avais donc que la première passe, ainsi qu'une recherche en profondeur avec un timeout. J'avais déja implémenté un calcul des liens entre les cases qui me permettait de préférer la construction d'espaces sans tunnels quand je me déplacait, mais pas grand chose de plus. Je me suis donc repenché sur le code d'a1k0n afin de prendre sa fonction de calcul de l'espace connexe le plus grand. Ca a placé mon bot dans le top 5.
J'ai ensuite tenté de ne considérer seulement le bot le plus proche afin de rendre mon comportement plus agressif en désactivant tous les autres. Je trouvais que je perdais trop de matchs a reculer car j'étais cernés par des bots. Ca ne s'est pas révélé concluant, je me suis retrouvé 11e vendredi matin avec cette mise a jour...
J'ai donc codé la troisième passe vendredi 28 en rentrant dans le train, et j'ai soumis dans la foulée a 19h30. J'ai pas voulu prendre le risque de faire une nouvelle mise a jour dans la soirée, et je me suis donc contenté de regarder des matchs, et suivre l'évolution du classement

Ameliorations

Il est clair que mettre en place une stratégie d'élagage aurais permis a mon bot d'aller voir beaucoup plus loin dans l'arbre des coups. C'est certainement un des grands axes d'améliorations. Au minimun si on arrive pas a mettre en place ce qu'il y a dans l'article cité plus haut, quand on est enfermé a juste deux joueurs, on doit pouvoir facilement mettre en place l'elagage alpha-beta du minmax

J'ai codé la prise en compte des serpents qui vont mourir dans les dernières heures. Déjà je pense qu'on pourrais prendre la distance max au lieu de la min, et on pourrais pousser plus loin, et pendant le calcul des cases dispo, utiliser cet algo pour vraiment définir combien de cases on peut parcourir avant d'avoir vraiment fermé tous les accès à son mur et avoir donc perdu la possibilité d'utiliser le terain qu'il va libérer

Outils

J'ai travaillé tout le challenge sur mon pc portable, la plupart du temps dans mes trajets pour aller au boulot dans le train. J'ai codé sous linux à l'aide d'Eclipse. J'ai fait des tests unitaires pendant tout le concours a l'aide des Google tests. Mes mesures de perfs, et la vérification de la mémoire a été faite a l'aide de valgrind/callgrind.
J'ai utilisé les scripts python de Loujo pour tester mes bots entre eux en local. Un grand merci a lui au passage, c'était très utile!
Enfin j'ai utilisé un repository git couplé a drop box (des fois que je crash mon PC...) afin de gérer mes sources, faire mes modifications, creer des branches pour faire des essais sur de nouvelles stratégies etc.

IRL

Dans la vie je suis développeur C++/Java chez Murex depuis 2005. Si vous avez envie de relever des challenges dans une ambiance conviviale, on recrute sur codingame :)

Remarques pour les prochain challenge

Les timouts ont étés un vrai problème. On a tous lu le thread sur le sujet, et je pense que pour le prochain challenge, il faut qu'on ais la garantie d'avoir un coeur rien que pour notre bot. Ou en tout cas essayer de voir si le temps consommé par le bot sur le CPU n'a pas exédé 100ms au lieu de mesurer l'écart de temps entre les entrées sorties.
Il faudrait aussi pouvoir choisir les options de compil pour le C++ : il y a une vrai différence de perf...Quite a ce que dans l'environement de dev on puisse lancer le tout en mode normal et gdb.

//Mauvais perdant on
Enfin j'ai du mal a m'enlever de la tête que le classement du top4 est l'inverse des dates de submit...Il y a très peu d'écart de points entre nous.J'ai soumis vers 19h30, Hau vers 22h, Yves a 23h30 et Thomas a 0h15. J'ai peur qu'avoir fait plus de matchs passés 1h, (car ayant toujours des matchs a jouer), ait eu un impact sur le classement final.
Pour le prochain challenge, il faudrait je pense remettre tout le monde a zero, puis faire des matchs avec plusieurs phases afin de réduire progressivement le nombre de joueurs. Si par exemple au bout de deux heures de matchs on réduisait aux 200 premiers puis chaque heure suivante 100/50/25/10, je pense qu'on aurais un résultat qui feras plus l'unanimité.
//Mauvais perdant off

Si j'ai du temps, j'essayerais d'ajouter quelques schémas a ce texte pendant le week end pour donner plus de clareté aux différentes parties dela fonction d'évaluation :)

Vos commentaires sont biensur les bienvenus! Et encore une fois, j'aimerais bien savoir comment vous vous avez fait :)

Manwe

7 commentaires :

  1. Merci pour l'explication ce fut fort interressant ! :)

    RépondreSupprimer
  2. Merci pour l'explication c'était très instructif, j'attends la suite détaillée avec impatience ;)

    RépondreSupprimer
  3. Merci à toi Manwe pour ton article. Pour ma pars, je n'ai pas du tout procédé de cette manière. C'était à la base l'idée la plus évidente qui m'était venu en tête, mais je me suis rendu compte qu'en réfléchissant au tour le tour, on pouvait arriver à des réactions totalement cohérentes pour un temps de calcul relativement faible. (mon ia donne une réponse en moins de 10ms (en tout cas en local) contre 3 adversaires). Si cela intéresse, je pourrais vous expliquer mon algorithme qui est vous le verrez relativement simple pour un résultat pas si mauvais que çà. Je n'ai malheureusement pas pu aller jusqu'au bout de mes idées d'amélioration du fait d'un manque de temps personnel, mais j'aurai au moins atteint mon objectif qui pour ma pars était le top 10.

    En tout les cas, ce fut un concours très sympathique que je réitérerais volontiers. Je suis un peu tombé par hasard sur ce concours (Je suis passé à coté une personne qui était dessus et cela m'a intrigué) , et je n'en suis pas déçu.

    Personnellement, ce qui m'a le plus dérangé lors du concours, c'est de devoir implémenter l'IA sur un seul et même fichier, et la limite des 50000 caractères que je connaissait pas (d'autant plus que pas mal étaient bouffé par les header en c++), ce qui m'a poussé à revoir un peu mon code que implémentais en local (donc pas de limite de caractère...).
    Si j'avais une suggestion à faire ce serai peut être de mettre en place un repo (git ou autre) de manière pouvoir pusher le code directement sans avoir à passer par la plateforme web, ce que j'ai trouvé relativement contraignante (avec notamment l'auto-complétion un peu longue). Et à la limite proposer les deux solutions.

    Ce dernier point qui m'a d’ailleurs poussé à ré implémenter une application pour tester mon code en local avec quelques fonctionnalités en plus comme de pouvoir choisir les positions de départ, ou mieux encore, de pouvoir re-générer un combat à partir d'un certain moment précis (Généralement quand on se rendait compte que son IA faisait une erreur à un moment précis. Cela évitait entre autre à générer 25 combats pour tomber sur LE cas ou l'erreur se produisait).

    En lisant l'article, j'ai pu constater qu'il y avait un forum dédié à ce concours... Si j'avais remarqué ça avant, j'aurai volontiers partagé mon application... Toujours est il que si des personnes sont intéressés, je suis entièrement disposé à la partager. Elle a été implémentée en c++ avec qt. Seul bémol, l'application ne tourne que sur linux du fait d'utilisation de fonctions system.

    Voila voila.

    PS : pour ceux qui se poseraient la question, mon pseudo est monsieurV.

    Encore merci pour ce concours!

    RépondreSupprimer
    Réponses
    1. Ce serais intéressant que tu nous poste l'application sur le forum. En plus tu pourrais nous décrire comment tu t'es classé dans le top 10 avec une consommation CPU aussi faible :)

      J'ai ajouté des schémas sur le forum dans le même post ou je décris ma stratégie. Je reviens plus en détail sur les trois phases:
      https://groups.google.com/forum/#!topic/codingame-tron-battle-fr/7XwWq4oyWQA

      Manwe

      Supprimer
    2. Salut MonsieurV,
      Pour ma part j'avais partagé sur le forum des scripts en python avec ncurses pour faire jouer des bots. Je serais intéressé de voir ta réalisation avec QT, ainsi que ton bot, si je comprend bien sans recherche en profondeur ?

      J'ai aussi eu des problèmes avec la taille de 50ko, ayant tout prototypé au début. En regardant le code de Manwe, j'ai vu que lui ne l'avait pas fait ; dans un seul fichier ce n'est peut-être pas la peine..

      LouJo

      Supprimer
    3. Non, pas de recherche en profondeur, ou pour être exact, plus de recherche en profondeur étant donné que j'avais commencé comme ça sur ma première IA.

      Voila un liens dropbox pour le programme : https://www.dropbox.com/s/6z60wafheyypv8k/TRON.zip

      En ce qui concerne l'IA à proprement parler, je viens de poster mon code source sur github : https://github.com/aurelienvernerey/tron-IA

      Voila. J'essayerai de faire un post pour expliquer mon ia plus en détail, ça sera certainement plus pertinent que de juste regarder le code source.

      MonsieurV

      Supprimer
  4. Hello,

    je viens de m’apercevoir qu'il n'y a jamais eu de link vers l'article que j'avais écris à l'époque :)
    Je mets le lien ici : https://www.codingame.com/blog/fr/2014/03/tron-battle-le-debrief-de-thomasnzo.html

    ThomasNzO

    RépondreSupprimer