Les IA qui jouent

🟢 Découverte

Pour jouer au morpion sans jamais perdre, il suffit de tout prévoir : chaque coup, chaque réponse, jusqu'à la fin. Joue contre une IA qui fait exactement ça, et regarde combien de positions elle examine.

🟡 Curieux

L'IA dessine dans sa mémoire un arbre : la position actuelle, puis une branche par coup possible, puis une branche par réponse, et ainsi de suite. Elle suppose que son adversaire choisit toujours la réponse la pire pour elle, et elle choisit le coup dont la pire suite est la meilleure. C'est la méthode minimaxMinimax — Méthode pour choisir un coup dans un jeu à deux : on imagine tous les coups et toutes les réponses, en supposant que l'adversaire choisit toujours la réponse la pire pour nous, et on prend le coup dont la pire suite est la meilleure. L'élagage alpha-bêta évite d'examiner les branches inutiles.. L'élagage alpha-bêta permet d'abandonner une branche dès qu'on sait qu'elle ne sera pas choisie : même coup, bien moins de calcul.

🔴 Ingénieur

Depuis la grille vide, minimax examine 549 946 positions ; avec l'élagage alpha-bêta, 18 297 seulement, dans l'ordre où l'animation essaie les coups. Aux échecs, C. Shannon estime en 1950 qu'il y a environ 30 coups possibles par position et 40 coups par partie, soit de l'ordre de 10¹²⁰ parties : à une par microseconde, il faudrait plus de 10⁹⁰ ans pour jouer le premier coup. D'où son idée : chercher seulement quelques coups à l'avance, puis évaluer la position avec une formule (matériel, mobilité, sécurité du roi), une heuristiqueHeuristique — Règle approximative qui guide une recherche vers les solutions prometteuses, sans tout essayer : par exemple « privilégier les rues qui rapprochent de l'arrivée ». Elle accélère, mais ne garantit pas toujours la meilleure solution..

🟢 Découverte

Et si, au lieu de tout calculer, on apprenait en jouant ? MENACE est fait de boîtes d'allumettes et de perles de couleur. Fais-lui jouer des centaines de parties.

🟡 Curieux

Personne n'explique les règles de stratégie à MENACE. Il tire ses coups au hasard, mais pas tous avec la même chance : les coups qui ont mené à des victoires gagnent des perles, ceux qui ont mené à des défaites en perdent. Partie après partie, les bons coups deviennent les plus probables. C'est l'apprentissage par renforcementApprentissage par renforcement — Façon d'apprendre par essais et erreurs : la machine agit, reçoit une récompense ou une pénalité, souvent tard, et renforce peu à peu les actions qui rapportent le plus. : des essais, des erreurs, et une récompense à la fin.

🔴 Ingénieur

MENACE confond les positions symétriques (une rotation ou un reflet de la grille) : il lui suffit d'environ 300 boîtes. La récompense n'arrive qu'à la fin de la partie, et elle est partagée entre tous les coups joués : c'est le problème de « l'attribution du mérite ». TD-Gammon le résout mieux en apprenant à prédire, à chaque coup, la valeur de la position suivante (apprentissage par différence temporelle).

🟢 Découverte

Au go, il y a bien trop de coups possibles pour explorer l'arbre, même quelques coups à l'avance. Une idée étonnante : jouer au hasard. Pour chaque coup, finis des parties au hasard, et compte combien sont gagnées.

🟡 Curieux

Une partie jouée au hasard ne veut rien dire. Mais des centaines de parties, si : un bon coup laisse plus de chances de gagner, même quand la suite est jouée n'importe comment. C'est la méthode de Monte-Carlo, du nom du casino. AlphaGo l'a combinée avec deux réseaux de neuronesNeurone artificiel — Petite formule : il multiplie chacune de ses entrées par un poids, additionne, puis transforme le résultat. Des milliards de neurones, organisés en couches, forment un réseau de neurones. : l'un propose les coups les plus prometteurs à explorer, l'autre estime qui va gagner sans finir la partie.

🔴 Ingénieur

La recherche arborescente Monte-Carlo construit l'arbre petit à petit, en explorant davantage les coups qui ont le meilleur score, tout en gardant un peu de curiosité pour les autres. En 2017, AlphaZero a supprimé les parties jouées au hasard et toute connaissance humaine : à partir des seules règles, en jouant contre lui-même, il atteint selon DeepMind un niveau surhumain en moins de 24 heures aux échecs, au shogi (les échecs japonais) et au go, grâce à une puissance de calcul considérable.

🟢 Découverte

Aux échecs et au go, tout est sur le plateau. Au poker, tu ne vois pas les cartes des autres, et eux bluffent. Comment une IA peut-elle jouer quand elle ne sait pas tout ?

🟡 Curieux

Il ne suffit plus de trouver le meilleur coup : il faut une stratégie qu'on ne peut pas deviner. Si l'IA misait fort seulement avec de bonnes cartes, ses adversaires le remarqueraient vite. Elle doit donc parfois bluffer, au hasard mais dans des proportions calculées.

🔴 Ingénieur

Ces programmes cherchent une stratégie que personne ne peut exploiter, en jouant contre eux-mêmes. Pendant la partie, Pluribus ne cherche que quelques coups à l'avance, pas jusqu'à la fin de la main : c'est l'une des raisons pour lesquelles il demande si peu de calcul.

🟢 Découverte

Une IA qui bat les champions du monde est-elle imbattable ? Pas forcément : elle peut avoir des angles morts qu'aucun humain n'avait pensé à chercher.

🟡 Curieux

Ces IA ont appris contre elles-mêmes et contre des adversaires sérieux. Un adversaire qui joue très mal, mais d'une façon précise et inhabituelle, peut les mener vers des positions qu'elles n'ont jamais appris à défendre. C'est le même principe que les exemples adverses du module Les IA qu'on trompe exprès.

🔴 Ingénieur

Pour trouver ces failles, des chercheur·ses entraînent une IA dont le seul but est de battre une autre IA précise, en la regardant jouer. Elle ne devient pas forte au go : elle devient forte contre ce programme-là.