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

CodinGame

cg_home

Ça faisait un bon moment que je voulais te parler de CodinGame, et cette fois c’est la bonne !

J’ai découvert CodinGame il y a deux ans, dans le cadre du boulot. CodinGame, c’est un site qui porte plutôt bien son nom : on y joue à coder des algorithmes qui vont résoudre des problèmes posés sous forme de jeux. Ces jeux peuvent être solo, d’optimisation, ou multi-joueurs. Quelques exemples parleront beaucoup plus qu’un long discours, alors c’est parti !

Exemple 1 (solo / optim) : qui n’a jamais rêvé de programmer un vaisseau qui doit atterrir sur Mars ? CG l’a fait ! Toutes les secondes on te donne ta vitesse et ton inclinaison, et à toi (ou plutôt à ton programme) de prendre les bonnes décisions de puissance / rotation pour atterrir dans de bonnes conditions, et si possible en utilisant un minimum de fuel !

https://www.codingame.com/replay/solo/182832834

Exemple 2 (solo) : empêche Skynet de trouver une sortie, en détruisant plutôt judicieusement à chaque tour un des liens du réseau :

https://www.codingame.com/replay/solo/182835969

Exemple 3 (multi) : grosse course où chaque joueur contrôle deux pods, mais il suffit de passer la ligne d’arrivée avec l’un des deux pour gagner la course. Du coup, le second pod est souvent utilisé pour « tamponner » le premier pod adverse, et ça donne de jolies courses. Le replay est pas de moi, mon programme est pas au top du tout sur ce jeu !

https://www.codingame.com/replay/182833831

Exemple 4 (multi) : un jeu de stratégie où on contrôle rapidement plusieurs dizaines de drones, et où il faut explorer intelligemment pour capturer des zones de production, et finalement conquérir la base ennemie :

https://www.codingame.com/replay/174971402

Exemple 5 (multi) : un jeu qui ressemble un peu à Tetris, où il faut monter des gros combos pour remplir la grille de l’adversaire. Bon, mon bot est clairement pas terrible, mais on voit quand même quelques combos sympa :

https://www.codingame.com/replay/173439426

Voilà, il y a énormément de langages disponibles (26 pour être précis), donc n’importe qui ayant des bases minimales de programmation peut commencer facilement sur le site.
Pour débuter, je conseille les puzzle (problèmes) faciles de la section entrainement, ils permettent de se familiariser avec la plateforme, et se résolvent en moins de 50 lignes de code.

Ensuite, les compétitions multi-joueurs organisées en général sur une semaine (environ tous les 2 ou 3 mois) sont clairement le top.
Avec la pression du temps ça oblige à faire de nombreux choix, car il y a beaucoup de choses à faire :

  • choisir son langage à utiliser (pour ceux qui en maitrisent plus d’un, mais moi c’est Java ou rien)
  • définir son algorithme principal, et le peaufiner tout au long de la semaine
  • choisir de coder « vite et sale », au risque de faire une assiette de spaghettis qu’on ne peut plus toucher sans rajouter 10 bugs, ou « pas trop vite mais propre », au risque de pas finir à temps
  • investir ou pas du temps dans des tests unitaires, qui permettront de limiter les risques de régressions lorsqu’on fera évoluer le code
  • travailler sur les performances du code en terme de temps d’exécution (pour les algos gourmands), car on a que 100 ms à chaque tour pour prendre une décision,
  • passer du temps à bien comprendre les mécanismes du jeu, notamment quand il y a de la physique et des maths sous-jacentes,
  • analyser les stratégies des meilleurs, pour essayer de comprendre ce qui est important dans le jeu,
  • et plein d’autres choses qui dépendront du jeu en lui même…

Finalement, concernant la communauté des CodinGamers, elle est au top, beaucoup d’entraide sur le forum et sur le chat intégré, même pendant les compétitions !
A la fin des compétitions, les meilleurs écrivent un « post-mortem » où ils partagent largement leur stratégie (voir par exemple celui de la dernière compétition), si ce n’est des fois leur code en entier (ou presque) ! Il n’y rien de mieux pour apprendre et progresser, et là on est vraiment dans l’intelligence artificielle, avec des algos génétiques, du Monte-Carlo, du recuit simulé, etc…

Bon de mon côté (compte Jahz), après deux ans, j’ai fini une bonne partie des puzzles solos, accroché un moment un top 10 sur un jeu d’optimisation, mais rien de très remarquable (hormis une compétition « privée » dans mon entreprise). Mais le plus important, c’est que ce site m’a clairement redonné le gout de la programmation, et je pense avoir beaucoup progressé depuis que je suis sur CG.

Bref, je participerai très probablement à la prochaine compétition qui commence pile dans deux semaines. Et toi ?

cg_ghost