Ghost in the cell

La semaine dernière, j’étais plutôt pris par un … un contest codingame !

Malheureusement, j’ai un peu la flemme de faire le post-mortem avec Asciidoc pour ne pas avoir les images générées par PlantUML.

Donc je vais plutôt en faire une version raccourcie ici.

Qu’est-ce qu’il faut faire ?

Sur un terrain constitué d’un graphe de noeuds produisant des robots, il faut avoir plus de robots à la fin de la partie que l’adversaire.

Mais comment ?

A chaque tour, vous pouvez demander à chacun de vos noeuds d’envoyer autant de cyborgs que vous le voulez vers la destination de votre choix.

Oui, mais comment ?

Là, ça devient compliqué.

J’ai implémenté au début un système qui envoyait les cyborgs vers le noeud ennemi le plus proche (en en envoyant plus que ce qu’a l’ennemi au moment où j’arrive). Mais ça ne marchait pas trop bien. Même si ça m’a emmené jusqu’en bronze.

J’ai ensuite amélioré d’innombrables fois ce système en tentant les choses suivants

  • Envoyer les bombes vers les noeuds ennemis
  • Faire des upgrades des noeuds que je détiens (malin, parce que tout un tas d’ennemis envoient 2 cyborgs à chaque tour, en comptant sur les statistiques) … Ca m’a emmené en argent.
  • Implémenter un peu de solidarité en essayant d’équilibrer le nombre de cyborgs entre les noeuds. Ca a plutôt bien marché … mais je n’ai pas franchi l’argent
  • Et le dernier : trier les noeuds au début de chaque tour par distance au centre des noeuds de mon équipe. Et utiliser ce tri pour chacune des opérations précédentes. Et ça m’a emmené en or.

Résultat ?

683ème.

Pas forcément un mauvais score.

Mais nettement moins bon que mon collègue Nicolas, qui termine 41ème en Legend ! Et que je félicite.

Mais il y a des trucs qui n’ont pas marché ?

Tellement !

La plus grosse déception a été pour moi la tentative d’utiliser l’algorithme dynamique de résolution du problème du sac à dos, qui ne donnait pas vraiment de différence de score de mon algorithme naïf et brutal.

A côté de ça, j’aurais peut-être dû aussi tenter des algorithmes plus … intelligents.

Et des leçons à en tirer ?

Je connaissais bien Bomberman, donc j’ai pu utiliser un peu d’expertise pour sentir les bons algorithmes dans Hypersonic.

Par contre, là, les graphes, je n’y connais rien. Enfin, si, en terme d’algorithmique, de navigation, je m’y connais … un peu. Par contre, ce genre de jeux, vraiment, je n’y connais rien, et je suis nul. Et je sais pourquoi : on est là dans le même genre de problème que pour le go : c’est un jeu distribué sans valeur autre que positionnelle. En effet, un noeud vaut plus par le nombre de cyborgs qu’il produit que par toute autre valeur ou information.

Et du coup, c’est très difficile à appréhender pour l’esprit humain qui est fondamentalement focalisé sur un objectif, et pas sur une situation globale.

Et ça, c’est une super leçon : il est difficile pour moi de concevoir un algorithme intelligent si je ne connais pas vraiment bien l’espace du problème.

Oh, bien sûr, j’ai atteint une position au moins aussi bonne qu’à hypersonic. Mais quelque part, et même si j’étais hier extrêmement content d’atteindre l’or, j’ai quand même une petite pointe de déception de ne pas avoir fait un meilleur score (qui aurait pu être Legend, mais c’est ma prétention habituelle).

Le quidditch, c’est pas si facile

Pour la troisième fois, je me suis lancé dans un des contests de Codingame.

Cette fois-ci, Harry Potter était à l’honneur.

fantastic_bits_ld-compressor-1

Oui, enfin, sans les combats de sorciers

En particulier, le quidditch. Enfin, un quidditch un peu simplifié : seulement deux sorciers, et, surtout, pas de vif d’or. Et heureusement, parce que j’en ai bien bavé pour en arriver à résultat un peu meilleur que la dernière fois, et surtout, cette fois-ci, raisonnablement satisfaisant, vu le temps investi :

score

707 sur 1950 qui passent atteignent le bronze, c’est bien. Mais s’arrêter à la porte de la ligue gold, ça craint.

EDIT : heureusement, une heure plus tard

score_1

Alors, comme la dernière fois, il y a des leçons à retenir.

D’abord, mon code magique qui produit des tests directement à partir du jeu est très pratique, mais nécessite que le code n’utilise jamais de random() sous quelque forme que ce soit. Cela dit, c’est tellement pratique ! regardez mes classes InGameTest, comme par exemple ici

test_generator

Et n’oubliez pas que ça vient directement de l’état du jeu à instant donné !

Ensuite, utiliser le bug tracker de GitHub comme bloc-note, c’est évidement pratique pour me garantir que j’ai traité le sujet efficacement. Et je m’en resservirai.

Enfin, j’avais une première implémentation que je savais boiteuse dès jeudi. Mais, si vous regardez mon historique de commit, vous verrez … rien ! En effet, le code que j’ai mis en place samedi et dimanche n’a pas été placé dans GitHub avant ce soir … Le fameux rush de fin de projet :-). Cela dit, il n’y avait peut-être pas de commits, mais il y avait des tests ! Et j’utilise toujours avec autant de profit mon plugin Maven qui génère le fichier source de codingame. Mais pour en revenir à cette histoire d’implémentation, clairement, il va falloir que je passe plus rapidement à la deuxième implémentation. Je dis deuxième, mais pour Hypersonic, j’ai enchaîné 4 implémentations différentes, donc n’en avoir que deux, c’est déja un net progrès. D’ailleurs, je pense ne pas vraiment pouvoir en faire moins. En effet, mis à part pour les super-tueurs genre Magus, il paraît difficile d’obtenir une première version qui soit à la fois correcte conceptuellement et efficace.

Mais bon, tout ça ne doit pas ôter quelque chose que j’ai écrit sur hypersonic : coder une de ces satanées IA est un sacré challenge, mais aussi un sacré fun. Et pour le coup, le quidditch était très bien grâce à sa complexité.

PS : Bravo à nmahoude :

Je ne suis pas hypersonic sur CodinGame

Depuis deux ou trois semaines, avec quelques collègues, nous avons créé des comptes CodinGame et nous nous sommes lancé dans les jeux pour programmeurs qui y sont disponibles.

Au début, c’était simple …

Et puis, il y a deux semaines, ils ont lancé Hypersonic. Bon, hypersonic, c’est pas bien compliqué, c’est faire jouer un bot que vous programmez. Donc j’en ai codé un.

Et j’ai fini quasi-dernier en bronze.

Vous pouvez lire le post-mortem que j’ai écrit pour y voir les leçons techniques.

J’en tire quelques autres leçons, plus humaines.

La première est assez logique, pour un jeu : c’est la chose la plus amusante, la plus prenante, et la plus crispante que j’ai codé au moins cette année, et facilement ces cinq dernières années. Imaginer un algorithme, le développer, et le voir se comporter, même mal, a ce côté démiurgique qui est la raison pour laquelle je suis développeur. Le corollaire évident, c’est que je ne comprend toujours pas pourquoi mon métier est aussi chiant actuellement : j’ai utilisé des méthodes professionnelles pour développer ce bot : tests, profiling, … Et c’était vraiment amusant. J’en tire la conclusion que notre métier est chiant parce que les demandes des clients sont, la plupart du temps, d’un ennui mortel.

La seconde est assez logique, mais moins drôle : j’ai fini 1675ème ! C’est médiocre, évidement. Et c’est vrai que mon bot était médiocre : des timeouts partout, et des décisions suicidaires encore plus souvent. J’ai pris une vraie leçon d’humilité, ce qui est toujours bien.

La dernière est plus intéressante : on est certes loin du fameux « meilleur programmeur de France », mais il y a beaucoup de monde, et qui semble prêt à y passer beaucoup de temps. Autrement dit, les développeurs sont des gens passionnés, prêts à se confronter les uns aux autres, et à communiquer autour de leurs succès ou de leurs échecs.