Ghost in the cell

Alors qui va la gagner celle la ? Réponse ici !

C’est donc la semaine dernière qu’a eu lieu le challenge CodinGame dont j’avais parlé dans le dernier article.
Pour concrétiser ce que j’expliquais, je vais détailler un peu comment s’est passé le challenge pour moi.
Pour mieux comprendre la suite, je conseille de jeter un œil aux règles du jeu.
En gros, chaque usine produit des cyborgs pour qui la contrôle, et on peut envoyer ces cyborgs sur n’importe quelle autre usine, en défense sur les siennes, ou en attaque sur les autres.

Samedi :
Découverte avec mon frère et un groupe d’une dizaine de potes du challenge, passage en Bois 2, bière, Bois 1, bière, raclette, Bronze, bières…
La partie modèle de données du code est faite et ne bougera plus beaucoup jusqu’à la fin, en revanche la partie IA est complètement jetable, c’est vraiment de l’expérimentation pour bien assimiler les principes du jeu et passer les ligues. Sur la fin de soirée on découvre que le plus court chemin d’une usine à une autre n’est pas forcément le chemin direct ! On monte une « preuve » rapidos avec un match piloté par une IA « hardcodée », un peu comme dans ce replay d’un autre joueur.
Classement du dimanche matin : ~500 (bronze)

Dimanche / Lundi / Mardi / Mercredi :
Fort de la découverte de samedi, j’essaye de passer le peu de temps disponible à implémenter un algo qui me donnera pour chaque paire d’usines le chemin le plus court. L’algo est correct, mais pas assez optimisé ! Sur les matches à 13 ou 15 usines, j’explose la seconde allouée au premier tour, ce qui implique une défaite par forfait. Il aurait apparemment fallu connaitre, trouver via recherche ou redécouvrir l’algo de Floyd-Warshall. J’ai pas encore regardé les détails, mais ça fera une correction intéressante à mon algo maison !
En tout cas ça fait pas progresser mon IA, et le classement n’en finit pas de chuter.
Classement du jeudi matin : ~1600 (bronze)

Jeudi :
En échec sur le « pathfinding », je décide de simplement ne pas le lancer sur les match à 13 ou 15 usines, et de l’utiliser dans les autres cas. De toutes façons, en y réfléchissant un peu plus, il semble essentiel de faire faire des courtes étapes à nos troupes, pour avoir plus de flexibilité et être moins prévisible, quitte à emprunter un chemin moins optimal. Et le chemin optimal d’ailleurs, rien ne garantit qu’il passe par des usines que l’on contrôle.
Je pars donc sur l’idée de travailler sur une stratégie « locale », usine par usine, en ne considérant comme possibilité de destination pour les troupes d’une usine que ses voisins.
Ma définition des voisins d’une usine A étant toutes les usines B pour lesquelles il n’existe pas d’usine I telle que d(AI) + d(IB) <= d(AB)
Le = est la car si j’ai un chemin direct et un chemin avec intermédiaire de longueur égale, je préfère celui avec intermédiaire pour les raisons citées au-dessus. J’implémente donc le calcul des voisins, une IA spécifique au tour 1, puis une autre IA défensive.
Ça marche plutôt pas mal, mais vu que je n’attaque jamais après le tour 1, ben y’a pas de miracle, je perd presque tous mes matchs.
Classement du vendredi matin : ~1650 (bronze)

Vendredi :
Vers 22h j’implémente enfin une IA d’attaque pour les usines qui contiennent au moins un ennemi parmi leurs voisins, et une IA de « progression vers l’ennemi » pour les usines dont tous les voisins sont des alliés. Et là ça décolle direct, je passe de Bronze à Argent, puis directement d’Argent à Or, en étant même bien classé en ligue Or.
A ce moment je n’envoyais qu’une seule bombe au tour 1, et après un peu de code pour utiliser la seconde, je passe en légende ! Je ne fais toujours aucune amélioration des usines (sacrifice de 10 cyborgs pour augmenter de manière permanente sa production de 1), mais ça passe quand même. Voilà un exemple de partie.
A chaque tour dans l’ordre je vais défendre, puis progresser, attaquer, et éventuellement lancer une bombe pour finir.
Classement du samedi matin : 63 (légende)

Samedi :
Après une petite session d’analyse de replay pour détecter des bugs et les corriger dans la foulée, je me décide à implémenter les améliorations d’usine. Ca semble vraiment compliqué d’évaluer précisément les risques du sacrifice contre les gains de l’augmentation de production, du coup j’implémente ça vraiment vite fait : pour les usines qui n’ont que des alliés, à partir du moment où le round courant est supérieur à la plus grande distance sur la carte, on améliore ! A ma grande surprise, ça marche vraiment bien et je rejoins le top 15.
Classement du samedi soir : 14 (légende)

Dimanche :
J’essaye pendant quelques temps de fixer des petits bugs et de préciser les conditions sous lesquelles lancer une amélioration, mais les tests en IDE sont pas transcendants, je ne soumet donc rien de nouveau en espérant rester dans le top 50 d’ici à la fin. A midi en effet, j’ai déjà reculé à la 39ème place. Un peu après 20h00, je suis même classé 58 ! Mais la centaine de parties relancées pour le top 100 me permettent de revenir à mon rang final de 39, j’ai surement eu un peu de chance sur cette dernière évaluation.
Classement final : 39 (légende)

Conclusion :
Un challenge très intéressant et qui demandait moins de connaissances que le précédent. Simple à comprendre, mais dur à maitriser.
Sur le podium, on retrouve deux français en 1 et en 3 ! Et comme d’habitude, beaucoup de monde a partagé ses stratégies, dont le top 3 (en anglais). Idéal pour progresser.
A titre personnel, c’est de loin mon meilleur résultat, j’ai été super surpris de monter aussi vite entre vendredi soir et samedi aprem, ça fait plaisir !
Ce qui fait plaisir également, c’est de voir que l’application d’une stratégie locale à chaque usine donne quand même un comportement global cohérent, et ça c’était pas vraiment gagné d’avance. Mon frère fait également une très bonne perf et finit une dizaine de places devant moi.
Si t’as envie de voir à quoi ressemble le code, je l’ai mis ici, mais amputé de l’IA de défense qui était la plus compliquée.
A noter que le jeu est de nouveau disponible de manière permanente (ce n’est plus un concours), donc si ça t’as donné envie, y’a plus qu’à !

Publicités