Des nouvelles d’AlphaGo

alphago-team-go

Il y a un peu plus d’un an, un match de go historique avait lieu entre Lee Sedol et AlphaGo.
AlphaGo l’avait emporté 4/1 alors même que personne n’aurait parié sur la victoire d’une IA contre les meilleurs pros quelques mois avant. On n’attendait pas ce type de résultat avant 10 ou 20 ans.
Ceci étant, Lee avait quand même arraché une partie, et Ke Jie, alors numéro 1 mondial, avait estimé pouvoir battre AlphaGo et demandait à jouer un match officiel à son tour.

La semaine dernière, Ke a pu se mesurer à AlphaGo (qui avait a priori largement progressé de son côté pendant l’année écoulée), et sans surprise AlphaGo a gagné le match 3/0, alors même que Ke a joué à un excellent niveau d’après ce que j’ai pu lire ici ou là.

En parallèle de ce match malheureusement sans gros suspense (ce qui me fait regretter que AlphaGo ait été si fort si vite), les organisateurs ont eu la bonne idée de faire jouer des humains avec AlphaGo en Pair-Go, et aussi d’opposer l’équipe nationale chinoise (en photo) à AlphaGo. Même si  je ne suis pas convaincu à 100% qu’ils soient nettement plus forts à 5 que seuls, l’idée était très sympa et c’est pourquoi j’ai choisi cette photo pour illustrer l’article.
Bon, ils ont également perdu, mais au moins on dirait qu’ils se sont bien marrés !

Que retenir de tout cela au final ?

  • AlphaGo a déjà fait des émules, et même si DeepMind n’a pas ouvert le code source, d’autres programmes se sont largement inspirés des techniques utilisées et commencent à être très forts eux aussi
  • DeepMind a annoncé la fin de carrière compétitive d’AlphaGo avec ce match, ils vont maintenant se consacrer à un outil d’apprentissage du Go basé sur AlphaGo, et surtout essayer d’appliquer leurs recherches à d’autres domaines (médecine, énergie, matériaux…)
  • DeepMind a livré une cinquantaine de parties d’AlphaGo jouant contre lui même. Les parties sont très étranges avec des coups que beaucoup jugeraient affreux. J’ai pu lire d’un joueur top 10 français « C’est de la grosse merde », « il y a clairement des mauvais coups, des mauvais échanges ».
    Mais qui sommes-nous pauvres humains pour juger un « joueur » qui nous bat tous ? Le débat et l’analyse de ces parties ne font que commencer.
  • Pour les tournois d’humains, il va falloir anticiper les risques de triche (adieu les tournois en ligne avec gros enjeux, exit la consultation de smartphones pendant des parties de tournoi…), sinon le Go pourrait souffrir des même scandales qu’aux échecs
Publicités

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’à !

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

… et on suit un match de Go historique !

AlphaGo-vs-Lee-Sedol

Historique, pour les amateurs du jeu de Go ou de l’intelligence artificielle, très clairement. Alors quand on est fan des deux…

C’est donc demain que le match entre Lee Sedol (bio en français et anglais) et AlphaGo (développé par Google DeepMind) commence.
Il se jouera en 5 parties sans handicap, avec 2h par personne + 3 périodes d’une minute de byo-yomi, et sera streamé en direct sur Youtube.

Forte de sa victoire sans appel (5/0) en Octobre contre Fan Hui (français d’origine chinoise et triple champion d’Europe en 2013/2014/2015), l’IA de Google aura d’après les experts beaucoup plus de mal contre Lee Sedol, l’un des meilleurs joueurs au monde, si elle joue au même niveau que contre Fan.
Sauf que… 6 mois se sont écoulés depuis Octobre, et qu’en 6 mois AlphaGo se sera améliorée en jouant autant de parties qu’un humain l’aurait fait en quelques milliers d’années !
Sans compter que les ingénieurs de Google ont probablement travaillé à fond pour peaufiner leur IA.

Bref, on espère que le spectacle sera au rendez-vous, et il sera très intéressant de voir si Lee Sedol va essayer de compliquer ou au contraire de simplifier les parties, sachant qu’il a un style habituellement très agressif.

Dans tous les cas ça fait plaisir de voir le retentissement qu’a l’évènement dans les médias, beaucoup d’encre a coulé à ce sujet sur le net, mais si je ne devais donner qu’un lien d’article, allez hop ce serait celui là (en anglais).
Et un lien de vidéo, ce serait ici, en français cette fois. Le contenu semble (pas encore eu le temps de tout regarder) très intéressant, car toutes ces questions sont abordées :

  • Qu’est-ce que le jeu de go ?
  • Pourquoi ce jeu intéresse-t-il les chercheurs et les géants de l’internet ?
  • Lee Sedol peut-il gagner ?
  • Quelles conséquences si la machine gagne ?

Alors, Lee Sedol sera-t-il le nouveau Kasparov et AlphaGo le nouveau DeepBlue ?
Début de réponse demain, mais pour ma part je pronostique 4/1 en faveur de Lee Sedol !