Codingame : fin de partie

Il y avait ces dix derniers jours un contest codingame.

Et j’étais assez bien parti, puisque je suis arrivé en ligue silver. Malheureusement, à un moment donné, je me suis rendu compte que j’y passais sans doute trop de temps.

J’ai donc décidé d’arrêter de participer aux contests codingame. D’ailleurs, je ne pense pas me remettre à codingame, même en-dehors des contests, avant un bon moment. Je retire de nombreuses choses de mes participations que je vais tenter de découper en plusieurs morceaux

Wondev Woman

Sur le contest proprement dit, c’était bien. J’avais commencé à coder mardi un algorithme conceptuellement proche de celui que j’utilisais pour Hypersonic, me permettant théoriquement de faire une analyse complète du plateau à plusieurs tours d’avance. J’achoppais sur un problème de chargement des directions possibles, mais j’avais en tête une solution.

Mais avant un peu de vocabulaire

  • J’appelle action une action complète (MOVE&BUILD ou PUSH&BUILD).
  • Un mouvement est un élément d’une action (déplacer la case « active » dans le futur d’une des directions possibles). Donc si on y réfléchit bien, une action est une paire de mouvements. Petite révélation : la différence entre PUSH&BUILD et MOVE&BUILD est que, dans le premier cas, le premier mouvement arrive sur une case occupée

Du coup, mon algorithme devenait quelque chose ressemblant à

  1. Calculer les mouvements possibles au tour courant pour mes pions
  2. Pour chaque mouvement, calculer l’état du terrain après le mouvement (sans tenir compte de la position des joueurs). Il va y avoir des tonnes de superposition, qui correspondent à des futurs communs, ça offre une bonne réduction de l’espace de recherche.
  3. Scorer les positions des pions. Pour les meilleures positions, recommencer à l’étape 1. Le score utilisé doit être indépendant de la longueur des chemins

A mon avis, avec ça, j’aurais pu atteindre l’or. mais.

  • Implémenter un tel code est long, et assez fastidieux.
  • J’ai eu cette idée uniquement parce que j’ai repris hypersonic après la fin du contest
  • Je n’ai ni la motivation, ni le talent pour atteindre la légende (mon meilleur score à été d’atteindre le fond de la ligue gold).

Plus généralement

Ces constats, qui ne sont pas d’ordre techniques mais personnels, sont reproductibles pour tous les problèmes de codingame : il y a de bien meilleurs joueurs que moi, et je le vois clairement.

A mon avis, c’est parfait pour découvrir un nouveau langage. Et en réalité, attaquer ces problèmes en Java était pour moi une facilité. En théorie, j’aurais dû les attaquer en Python, en Scala, ou dans n’importe quel langage dans lequel j’ai envie de progresser vite.

Parce que les structures de données que j’ai mis en place, contrairement à d’autres participants, faisaient la part belle aux design patterns, à la bonne programmation orientée objet, bref au code Java bien idiomatique. Et je sais que j’aurais fait pareil dans d’autres langages.

Du coup, je vais arrêter d’y jouer en Java, et je m’y remettrais si je dois découvrir un nouveau langage.

Publicités

Et pouf, un nouveau projet open-source !

Bon, le projet existe depuis un moment, et est déja utilisé par quelques happy fews.

Il s’agit de codingame-maven-plugins, qui fournit des plugins facilitant le développement et le déploiement pour Codingame.

Le source est chez framagit, parce que je me voyais mal faire un projet en com.github, et que Sonatype tient à ce qu’on détienne le domaine correspondant au groupId.

Du coup, merci framagit, et merci framasoft !

J’abandonne

Samedi dernier, Codingame lançait code4life, le dernier contest en date.

N’écoutant que mon courage, je m’y suis jeté. Avec d’abord une implémentation basique pour atteindre le bronze, puis deux déclinaisons successives d’une machine à état.

Et aujourd’hui, avec cette machine profondément optimisée, je suis environ 250ème en silver. Il ne fait aucun doute que d’ici Lundi matin, je vais perdre encore 500 places. Mais je vais arrêter là ce contest. Plusieurs raisons à ça, que je vais détailler ici (non, je ne mettrai pas de post-mortem sur GitHub).

Fais une chose, et fais-la bien

J’ai commencé mon nouveau poste chez Zenika la semaine dernière. Et j’ai entamé ma première mission ce jeudi. Je pourrais vous mettre la liste des mots-clés ici, mais ce serait sûrement un peu prétentieux. Toujours est-il que beaucoup de technologies dans ce projet sont pour moi une nouveauté, ce qui m’a forcé à courir à fond dans la direction des découvertes techniques, ce qui n’est pas forcément compatible avec la précision, la focalisation nécessaire à la réussite d’un contest. Du coup, depuis avant-hier, je n’ai plus de gaz pour réfléchir correctement au problème.

C’est dommage pour mon succès à Codingame, et contrairement à un autre Nicolas, je ne risque pas de gagner de t-shirt, mais d’un autre côté, avoir trop de choses intéressantes à faire, c’est clairement un problème de riche.

Les streams, c’est fini

A un moment donné, j’ai commencé à avoir des sales problèmes de timeout. J’ai pu, à ma surprise et ma déception, j’ai pu associer chacun de ces timeouts à une utilisation des streams Java. Vous imaginez le truc ? Chaque utilisation de stream a occasionné à un moment ou un autre un timeout.

Attention, je ne dis pas que les streams sont mauvais. Juste que pour un contest codingame, les streams doivent être soigneusement évités.

Et ça n’est pas tout.

Vous avez tous vus les déclarations de Comparator sauce Java8 comme cet exemple

Eh bien de la même manière, chaque déclaration de Comparator avec une fonction s’est révélée trop coûteuse en temps CPU. Du coup, j’ai tout viré et tout réécrit de façon traditionnelle.

Et ça, n’importe quel chef de projet informatique vous le dira, ça a un coût. En l’occurence, du temps passé. En regardant mes commits Git, je dirais que j’ai perdu une heure à corriger ces problèmes de performance, avec à chaque fois ces étapes

  1. Copier le test généré
  2. Exécuter le PerformanceTest avec debug et VisualVM connecté
  3. Trouver le bout de code lent
  4. Remplacer le stream par un foreach façon java5

Démoralisant.

Les machines à état, c’est caca

Quand on regarde les règles, clairement, il y a différents états. J’ai tenté de les détailler dans ce schéma (vous pouvez le regarder en détail, mais franchement, on s’en fout).

sequence

Ca a l’air sophistiqué, non ? Eh ben ça l’est … Et je suis loin d’être sûr de la justesse du truc

En fait, tout ça ne sert à rien.

Ca simplifie peut-être un peu le code, mais d’une façon malsaine : je me retrouve à micromanager alors que je devrais arbitrer. Et du coup, chaque état (qui a certes une classe associée) se complique, devient plus lourd, nécessite plus de maintenance.

En vrai, si j’écoutais ce que des gens plus intelligents disent, ce que j’aurais dû faire, c’est de la programmation dynamique.

C’est-à-dire qu’à chaque tour, j’aurais dû calculer tous les mouvements possibles avec autant de profondeur que possible, et choisir le mouvement qui m’apportait statistiquement le meilleur résultat.

Mais je me suis entêté avec ma machine à état. Et je me retrouve comme un con la veille de la fin, sans avoir le temps de corriger mon code. C’est moche. Très moche.

OK, donc t’es qu’une merde en fait ?

Pas tout à fait non plus.

J’ai un peu modifié mon générateur de tests pour y inclure automatique un assertThat(myCommand).isNotEqualsTo(« La commande exécutée ») et ça me fait gagner encore un peu de temps. Par ailleurs, je compte en gagner encore plus – un jour – via un système d’annotation pour écrire automatiquement la méthode de génération de test unitaire (JavaParser et annotations seront de la partie).

Et je vais prochainement releaser sur maven central mon plugin de génération de classe unique.

Ce ne sont pas des victoires, c’est vrai, et je ne gagne pas de XP. Mais je fais des choses qui m’amusent aussi.

Donc tu vas faire le prochain ?

On verra … Mais je pense que oui.

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.