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).

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s