La communication quantique et le protocole BB84

Nouvelle vidéo sur la chaîne, une vidéo « un petit peu spéciale » en partenariat avec Echosciences PACA.

Le défi de cette vidéo était de donner quelques notions de communication quantique dans le format imposé de 3-4 minutes ! Pas la place donc pour y détailler un exemple de protocole d’échange de clé quantique comme le protocole BB84 dont j’esquisse juste le principe dans la vidéo. Voici donc quelques détails !

Non, BB84 n’est pas un lointain descendant du robot BB8, mais le nom du tout premier protocole d’échange de clé quantique qui a été imaginé en 1984 par les cryptologues Charles Bennett et Gilles Brassard. L’idée de ce protocole est de permettre l’échange sécurisé d’une clé de chiffrement, clé qui pourra être ensuite utilisée pour chiffrer un message qui sera ensuite transmis sur un canal de communication classique. Notez bien : ça n’est pas tout le message qui est transmis de façon « quantique », juste la clé de chiffrement. Lire la suite

Une intelligence artificielle peut-elle être créative ? Le cas des jeux.

La vidéo du jour parle de la créativité des IA, vue dans le contexte des jeux !

Pour ceux qui voudraient aller plus loin, quelques compléments d’usage.

Le MinMax

Un premier point que j’ai passé sous silence pour rester simple, c’est la façon dont on décide du « meilleur » coup une fois qu’on dispose de toutes les évaluations. Pour vous l’illustrer, voici une petite énigme.

Imaginez que j’aie 4 coups possibles, A, B, C et D, et que chacun de ces coups puisse appeler 4 réponses. Supposez que les résultats de l’évaluation des 16 positions résultantes soient les suivants, quel coup dois-je choisir ?

Si vous avez répondu « B » car c’est le coup qui mène à la position la plus intéressante (+8), vous êtes tombés dans le piège classique ! En effet il faut partir du principe que si on cherche à maximiser son score, l’adversaire lui a l’objectif inverse. Donc si il n’est pas plus bête que nous, il cherchera toujours à jouer la meilleure réponse (et donc si on joue B il jouera sa 4e option et le score sera 0).

La bonne réponse est donc C, car si l’adversaire joue son meilleur coup on sera à +1, ce qui est le mieux qu’on puisse espérer.

Ce petit exemple illustre le principe du MinMax, c’est-à-dire qu’on cherche le coup qui permet de maximiser son score sachant que l’adversaire va le minimiser.

Sur la manière de chercher dans l’arbre

Ma vidéo suggère qu’un algorithme comme celui qui tournait sur Deep Blue fait une recherche exhaustive dans l’arbre de façon totalement stupide. En réalité ça n’est pas si bourrin que ça.

Un simple petit calcul montre que si Deep Blue voulait chercher de façon exhaustive avec 12 coups d’anticipation, il faudrait 20^{12} évaluations, soit 4 millions de milliards. Même à 200 millions d’évaluations par secondes, cela fait longtemps à réfléchir.

Deep Blue était en fait basé sur une technique classique appelée « L’élagage d’arbre alpha/beta », qui permet d’éviter de visiter des branches dont on sait qu’elles n’amélioreront pas le meilleur résultat qu’on puisse espérer. Stockfish fonctionne sur un principe similaire.

Sur la base de données utilisée par AlphaGo

Il semble que j’ai fait une erreur ou du moins une exagération concernant la base de données utilisée par AlphaGo pour s’entrainer (version « Apprentissage supervisé », celle qui a battu Lee Sedol).

En effet la base est constituée de parties jouées par des joueurs 6e à 9e dan (que j’ai appelé de façon informelle « des grands maitres du go ») et a été extraite de la base online KGS.  Or j’ai l’impression qu’il y a une ambiguïté entre la notion de dan « amateur » et de dan « professionnel ». Et j’ai l’impression que la base KGS référence plutôt des parties amateurs.

Quelque part, c’est plutôt encore mieux pour AlphaGo, qui semble avoir appris en utilisant des données qui ne sont pas uniquement des parties de joueurs de classe internationale.

D’ailleurs c’est en fait un peu plus compliqué que ça puisque l’entrainement du réseau chargé de faire l’évaluation a bénéficié aussi d’apprentissage par renforcement.

Le fameux 37e coup

Quelques précisions concernant ce fameux coup. Je ne joue pas au go donc je n’ai clairement pas le niveau pour expliquer en quoi ce coup était inattendu. Mais il semble que généralement pour ce type de coup (appelé en anglais « shoulder hit ») qui consiste à se mettre en diagonale d’une pierre adverse, on se place sur la 3e ou la 4e ligne suivant qu’on veuille jouer défensif ou agressif. Mais semble-t-il, « jamais » sur la 5e ligne.

Alors en fait c’est plus compliqué que ça, et ça n’est pas le propos ici. Des « shoulder hits » sur la 5e ont l’air tout à fait possible, mais apparemment pas dans la situation qui se présentait à AlphaGo à ce moment là.

AlphaGo, AlphaGoZero et AlphaZero

Pour les besoins de la simplification de l’exposé, j’ai fait un raccourci dans ma présentation. Il y a eu en réalité (au moins) 3 versions de l’algorithme :

  • AlphaGo, qui a battu Lee Sedol
  • AlphaGo Zero, la première version fonctionnant purement en apprentissage par renforcement, mais uniquement pour le go.
  • AlphaZero, fonctionnant aussi bien pour le go, les échecs ou le shogi.

Je n’ai pas évoqué AlphaGo Zero, la version intermédiaire. Et en fait c’est elle qui a battu « Alpha Go Lee Sedol » par 100 à 0.

La différence entre AlphaGo Zero et AlphaZero, est que le premier exploite quelques spécificités du Go pour se simplifier la vie, ce que les spécialistes appellent du « domain knowledge », par exemple l’existence de symétries sur le plateau. Le fait de donner du « domain knowledge » permet de réduire la complexité de l’apprentissage par renforcement (et donc de l’accélérer), mais au prix d’une perte de généralité et de « pureté », puisqu’on aide l’algorithme en lui donnant des infos en plus.

AlphaZero est vraiment la version « pure », on ne lui donne aucun domain knowledge, vraiment juste les règles et rien que les règles. Il est un peu plus long à entrainer que la version précédente, mais l’avantage est qu’il marche aussi pour d’autres jeux abstraits. (Et au go il est légèrement supérieur à AlphaGo Zero).

Et les autres jeux vidéo ?

J’ai hésité dans cet épisode à parler des applications de l’IA à d’autres jeux, notamment vidéo. J’aurai pu par exemple évoquer DOTA2 ou StarCraft. Apparemment j’ai bien fait de m’abstenir, car à l’heure où j’écris ces lignes  DeepMind a annoncé qu’ils allaient faire une grosse annonce concernant StarCraft, le jour qui suit la publication de la vidéo. Donc à suivre !

Le jeu de la vie

La vidéo du jour traite des automates cellulaires, et en particulier de l’intriguant « jeu de la vie ».

Pour ceux que ça intéresse, je vais mettre le code en partage sur GitHub (si j’y arrive). Il est loin d’être parfait, et d’ailleurs je vous encourage à écrire le votre ! Mais vous y trouverez peut être quelques astuces intéressantes sur comment lire les fichiers RLE (qui encodent de façon compacte les situations de départ), ou bien génerer des vidéos à partir d’images MatPlotLib en Python.

Edit du 09/12 : le code est dispo sur GitHub Lire la suite

Le Bitcoin et la Blockchain

La vidéo du jour décrypte les mystères du bitcoin, et vous explique vraiment comment il marche, et ce qu’est cette mystérieuse blockchain.

Pour préparer cette vidéo, j’ai dû pas mal me documenter. J’ai trouvé beaucoup d’endroits où les grands principes du bitcoin sont expliqués, mais assez peu d’infos détaillées sur ce qu’il se passe vraiment « sous le capot ». A force de lecture, je pense avoir compris l’essentiel, et j’espère donc avoir donné à tout le monde les éléments nécessaires pour comprendre comment un système comme le bitcoin pouvait tenir debout, et en quoi le concept de la blockchain assure la décentralisation du système. Lire la suite