Le bridge, prochaine frontière de l'intelligence artificielle

Le bridge, dont les championnats du monde viennent de débuter à Lyon, est l'un des derniers grands jeux où l'homme surpasse encore la machine. Créer une intelligence artificielle meilleure que les champions de bridge pourrait donc constituer un défi majeur des années à venir. Et les chercheurs français disposent de sérieux atouts pour remporter la course.

Les jeux, terrain d'expériences pour les chercheurs

Les jeux constituent depuis toujours un terrain d'expérimentation rêvé pour tester la capacité des technologies informatiques. Les règles sont souvent simples, en nombre limité et une solide expertise humaine s'est accumulée au fil des temps, rendant le champ des jeux bien plus facile à comprendre et à modéliser que le monde réel.

Le premier jeu complexe où l'ordinateur a surpassé l'humain est les dames anglaises où le logiciel Chinook a obtenu en 1994 un titre de champion du monde face à un humain. Plus connu, Deep Blue développé par IBM a battu en 1997 le champion du monde d'échecs de l'époque Garry Kasparov. Chinook, Deepblue et leurs successeurs s'appuient sur des techniques dites de force brute et ont émergé grâce à la progression fulgurante de la puissance des machines dans les années 1990.

La longue bataille du jeu de Go

En ce qui concerne les programmes de Go, le nombre de combinaisons de jeu et la difficulté croissante pour évaluer une position donnée rendent inefficaces les programmes de type force brute (qui se limitent à essayer toutes les solutions possibles). En conséquence, pendant de nombreuses années, les meilleurs programmes ne dépassaient pas le niveau d'un joueur amateur moyen. Ce n'est qu'en janvier 2016 que la société britannique Deepmind a fait une percée décisive avec Alphago, une IA (Intelligence Artificielle) couplant réseaux de neurones profonds et apprentissage par renforcement. En mai 2017, Alphago écrase le meilleur joueur du monde, Ke Jie, par 3 parties à 0. Dans la foulée, Dennis Hassabis, CEO de DeepMind, annonce qu'Alphago a joué là son dernier match de compétition, ses équipes de recherche étant allées au bout de leur travail de recherche sur ce sujet.

Très récemment, l'Intelligence Artificielle est également venue à bout du poker: en janvier 2017, le système Libratus a remporté un tournoi de poker no-limit Texas hold'em en heads-up (un contre un) contre 4 joueurs professionnels de niveau mondial. Pour s'exprimer comme un hacker, le poker a été plus difficile à « craquer » que le go car il s'agit d'un jeu à information incomplète: au poker on voit ses deux cartes (cachées) et celles du flop mais pas celles des adversaires alors qu'au go l'emplacement des pièces est connu de tous.

Pourquoi le bridge a résisté jusque-là aux avancées scientifiques

Le bridge est encore plus difficile à aborder que le poker à cause de l'incomplétude du jeu, qui y est plus forte. Le bridge se joue à quatre (deux équipes de deux) et il y a trois jeux cachés : le jeu des deux adversaires et le jeu de notre partenaire. Il y a donc 13 cartes inconnues pour chaque joueur alors qu'au poker il n'y en a que deux. Par ailleurs, si le bridge intègre comme le poker des éléments de bluff (existant seulement dans les jeux à information imparfaite), le besoin de collaboration entre partenaires apporte une complexité supplémentaire. Enfin, pendant la phase des enchères, chaque joueur a l'obligation d'expliciter le sens de ses actions, difficulté supplémentaire pour un système automatisé.

Dans la vie réelle, les problèmes que nous rencontrons sont la plupart du temps en information incomplète et certains nécessitent la coopération de plusieurs acteurs qui communiquent entre eux et doivent expliquer la rationalité de leurs actions: toute percée scientifique dans le domaine du bridge automatisé est donc susceptible d'avoir des répercussions qui vont bien au-delà de la sphère ludique.

La France bien placée dans la course à la résolution du bridge

Jusqu'à maintenant la complexité du bridge a constitué une barrière à l'entrée pour les chercheurs, peu d'entre eux ayant le niveau de compréhension du bridge nécessaire à la poursuite de recherches approfondies dans ce domaine. L'impulsion décisive est venue de France grâce à Véronique Ventos, chercheuse en Intelligence Artificielle au Laboratoire de Recherche Informatique de Paris-Saclay et par ailleurs joueuse de bridge experte. Trouvant là une occasion unique de conjuguer sa passion du bridge et son travail de recherche, elle a constitué une équipe regroupant des chercheurs issus des différents domaines de l'Intelligence Artificielle comme Olivier Teytaud (un des pionniers des IA de Go) et des champions de bridge comme Jean-Christophe Quantin (multiple champion d'Europe de bridge).

Véronique Ventos a publié en juin 2017 dans la Revue d'Intelligence Artificielle un article présentant ses premiers pas vers une IA de bridge dont l'architecture sera composée de modules issus de travaux récents en apprentissage automatique. Cette architecture permettra à la fois de jouer à un niveau supérieur à celui des IA actuelles et d'expliquer de manière intelligible à un humain le raisonnement effectué par le programme. Ses résultats ont été utilisés par Yves Costel, ingénieur lyonnais qui a créé en 1980 le logiciel de bridge WBridge5, et qui a remporté les derniers championnats du monde de computer bridge en octobre 2016 à Wroclaw (Pologne).

La France dispose donc de bons atouts pour remporter la course à la résolution du bridge. Et compte tenu à la fois de l'effet médiatique, mais, surtout, des applications à d'autres domaines, c'est un jeu à prendre au sérieux !

___

Par Jean-Baptiste Fantun
pour l'Observatoire du Long Terme