fabernovel loader

Jun 28, 2018 | 6 min de lecture

Tech

Jeu d'échecs et intelligence artificielle : les jeux combinatoires sont-ils voués à être résolus?

Arielle Le Bail

Project Analyst


FABERNOVEL INNOVATE
Deep Blue, AlphaGo, AlphaZero… Les intelligences artificielles développées ces vingt dernières années ont renforcé, sinon fait naître, l’étonnement, la fascination, l’inspiration et les craintes autour d’un jeu vieux de plus de quinze siècles. Le jeu d’échecs, tout comme le go, est un jeu combinatoire, ce qui signifie qu’il possède un nombre fini de positions différentes… Il est donc théoriquement résoluble, ce qui questionne fondamentalement son sens pour les humains si les machines l’ont résolu.

Le 11 mai 1997, Deep Blue battait Garry Kasparov, joueur d’échecs russe sacré meilleur joueur mondial en 1984 et resté numéro un mondial pendant plus de vingt ans. 1,8 mètres, 1,4 tonnes, et 256 puissants microprocesseurs ont été nécessaires pour réussir ce coup de maître historique. Mais alors qui est ce nouveau concurrent surpuissant de Garry Kasparov ? Développé par IBM, Deep Blue est un ordinateur spécialiste du jeu d’échecs. Une sorte d’intelligence artificielle avant l’heure. Ou presque. Car Deep Blue est une IA “sous perfusion” de l’intelligence humaine : dans sa mémoire (comme dans celle d’un grand maître) sont enregistrées les évaluations de très nombreuses positions, «notées» par les consultants grands maîtres. Et Deep Blue n’effectue de calculs poussés que pour les positions sélectionnées par les humains. Sans l’homme, Deep Blue n’aurait jamais pu battre Garry Kasparov seule.

Près de vingt ans plus tard, avec dix ans d’avance sur les prévisions, AlphaGo, l’IA créée par DeepMind, l’antenne de Google, terrassait Lee Sedol, le champion du monde de go, ce jeu extrêmement complexe qui comprend encore bien plus de possibilités que les échecs. Un véritable tremblement de terre dans le monde du go. Lee Sedol lui-même est incroyablement surpris, et affecté par sa défaite, comme on peut le voir dans le superbe documentaire Netflix “AlphaGo”. Mais, là aussi, l’IA était nourrie par l’intelligence humaine : elle jouait à l’aide d’une base de données de plus de 100 000 parties…humaines.

Fort de ce succès, et plus ambitieux que jamais, DeepMind a aujourd’hui un nouvel objectif : créer une IA capable de résoudre des problèmes complexes avec un minimum de connaissances « a priori ». En fin d’année dernière, AlphaZero, la nouvelle version d’AlphaGo, a ainsi encore surpassé ses performances en s’attaquant une nouvelle fois aux échecs. Mais au lieu d’apprendre à partir d’une base de données de parties jouées par des humains, elle a simplement été programmée avec les règles du jeu et des algorithmes. A partir de là, l’IA a appris « seule » et en jouant « contre elle-même ». En à peine 4 heures, AlphaZero a assimilé toutes les connaissances connues sur le jeu et est devenu un véritable maître. Et sur les 100 matchs disputés contre Stockfish, le meilleur programme d’échecs jamais développé, l’IA en a gagné 25 en jouant avec les blancs, 3 avec les noirs, tandis que le reste des parties se sont soldées par des nulles. Une vraie prouesse.

En ce qui concerne le go, AlphaZero a également fait preuve d’une puissance étonnante. Seulement huit heures d’auto-apprentissage ont été nécessaires pour battre la dernière version d’AlphaGo.

Mais sur quoi repose la machine AlphaZero ?

L’IA se base sur trois éléments : des réseaux de neurones profonds, une méthode de recherche arborescente MCTS (Monte-Carlo Tree Search), et le self-play. AlphaZero fonctionne comme un cercle vertueux d’amélioration perpétuelle.

 

 

Concrètement, comment ça marche ?

Les réseaux de neurones profonds travaillent avec un algorithme MCTS, qui est une méthode d’exploration arborescente. Le programme identifie le meilleur coup à jouer en essayant tous les coups possibles et en évaluant les réponses de chacun de ses coups, ainsi que les coups suivants etc. Pour limiter la profondeur et la largeur de cette exploration, AlphaZero utilise une fonction de prédiction qu’il a apprise en s’observant jouer avec une stratégie antérieure. La fonction de prédiction évalue la valeur d’une position et donne une distribution de probabilité correspondante. Au final, l’IA évalue l’écart entre la politique choisie et la fonction de prédiction, ce qui améliore cette dernière.

Pour s’améliorer en permanence, l’IA joue contre elle-même (Self-Play) et enregistre ses parties et toutes les données générées pendant celle-ci, ce qui permet d’améliorer la qualité de l’algorithme. C’est ce qu’on appelle l’apprentissage par autorenforcement.

Et c’est étonnamment ce qui rend AlphaZero plus “humaine”, comme le soulignait DeepMind : “AlphaZero recherche seulement 80 000 positions par seconde aux échecs contre 70 millions pour Stockfish”. AlphaZero compense ce faible nombre en utilisant son réseau de neurones profonds pour se concentrer beaucoup plus sélectivement sur les variantes les plus prometteuses – une approche de recherche plus « humaine », puisque nous calculons en général aussi seulement les suites de coups qui nous paraissent les meilleures intuitivement.

 

Alors, les IA seront-elles bientôt capables de « résoudre » le jeu d’échecs, et les autres jeux combinatoires comme le go?

Les données les plus récentes estiment à 10^123 le nombre de parties possibles aux échecs. Nombre déjà très important mais encore bien inférieur au jeu de go, qui malgré des règles plus simples, offre des possibilités de l’ordre de 10^600. Il y a plus de parties possibles au go que d’atomes dans l’univers. Impossible pour un humain, mais faisable pour une IA ? Tout dépend du type de résolution : il en existe trois types. La résolution forte, qui fournit un algorithme produisant les meilleurs coups dans n’importe quelle situation ; la résolution faible, dont l’algorithme garantit une victoire pour l’un des deux joueurs ou un match nul quel que soit le coup initial de l’adversaire ; et enfin la résolution ultra-faible, qui définit simplement si le joueur ayant les blancs va gagner, perdre ou faire match nul à partir de la position initiale.

Il y a plus de parties possibles au go que d’atomes dans l’univers.

En tant que joueuse d’échecs, ces changements fondamentaux dans l’univers des jeux de plateau me passionnent, et m’intriguent, car l’intervention de l’IA pose des questions fondamentales sur le jeu lui-même et sur son intérêt. L’IA sera-t-elle capable de résoudre le jeu d’échecs ? Un jeu résolu est-il toujours aussi intéressant ? Y-aura-t-il encore une place pour la créativité dans les échecs ? Finalement, les meilleurs joueurs mondiaux sont-ils voués à être battus par une IA, ou seront-ils rendus plus puissants et créatifs avec l’ouverture de nouvelles possibilités grâce à l’IA ? Ou faudra-t-il au contraire oublier la technologie pour maintenir l’intérêt du jeu d’échecs ?

Pour répondre à ces questions essentielles, quoi de mieux que d’en discuter avec Maxime Vachier-Lagrave, meilleur joueur français et sixième meilleur joueur mondial ? Puisqu’il n’a que trois ans de plus que moi, j’ai pu le côtoyer durant les championnats jeunes nationaux et internationaux et j’ai donc eu la chance et le plaisir de pouvoir le recontacter pour discuter de ce sujet.

Maxime maintient que l’IA aura plutôt des effets bénéfiques sur le jeu, dans la mesure où le but reste de s’affronter entre humains. Les parties proposées par les IA sont aussi l’occasion d’explorer de nouvelles pistes, de nouveaux schémas dont il est possible de s’inspirer. Après étude de l’échantillon de parties disponibles, c’est plus motivant que décourageant puisque je découvre de nouvelles pistes prometteuses pour permettre de déséquilibrer les débats, en sachant bien que le but reste de s’affronter humain à humain. Tant que ce combat là conservera son intérêt il n’y a pas de raison de se décourager.

En ce qui concerne la résolution du jeu, il est également plutôt optimiste : “Pour moi, même si le jeu d’échecs est à terme résolu – qu’il s’agisse d’une résolution forte ou comme ce serait plus probablement le cas ultra faible, tant que cette résolution est hors de portée des humains le jeu conservera son intérêt à échelle humaine.

Et de plus, une grande partie de l’intérêt que présente le jeu d’échecs pour les joueurs est l’émotion suscitée par lui. C’est d’ailleurs un argument important pour Maxime « Les émotions humaines permettent d’apprécier la beauté inhérente à une position, une idée… ce qui constitue un des moteurs principaux pour le joueur que je suis ».

Alors, s’il est indéniable que les performances des programmes de DeepMind sont fascinantes, il n’en résulte pas moins que les jeux de plateaux sont encore loin d’être résolus. Et quand bien même ils viendraient à l’être, c’est aussi à nous de ne pas oublier que le but reste avant tout de s’affronter entre humains, et que notre jeu peut aussi se nourrir de l’inspiration apportée par le jeu des IA. Les échecs, le go ou encore le shogi ont donc encore de beaux jours devant eux.

Ce sujet vous intéresse et vous souhaitez en discuter davantage ? 

Contactez-nous
Cet article appartient à une enquête
logo business unit

FABERNOVEL INNOVATE

FABERNOVEL INNOVATE explore et construit le futur de vos industries. À la vitesse des startups.

à lire