On sait que les algorithmes permettent de fournir des mécanismes qui gagnent contre les humains aux jeu d’échecs ou à des jeux plus complexes comme le jeu de go… mais qu’en est-il du jeu de bridge ? Ce jeu, au-delà de la combinatoire, laisse une place importante aux interactions humaines. Le robot de bridge, Nook, développé par NukkAI se positionne au meilleur niveau grâce à la combinaison de l’IA symbolique et de l’IA numérique.

Le bridge est un jeu de cartes dans lequel une équipe de 2 joueurs essaie d’atteindre un objectif commun appelé un « contrat » déterminé au cours de la phase des enchères. Réaliser un contrat consiste à faire au moins un certain nombre de plis face à une équipe adverse qui va collaborer selon des règles codifiées pour essayer de faire chuter le contrat.

À la différence des jeux de plateaux comme les échecs ou le go, le bridge est un jeu à information incomplète. Au départ, chaque joueur ne connaît que les 13 cartes qu’il a en main. Au cours de la partie, en raisonnant sur les informations transmises pendant la phase des enchères et sur les cartes jouées à chaque pli, chaque joueur peut restreindre ses hypothèses sur les cartes restant en jeu mais il doit prendre ses décisions (choisir la carte à jouer à chaque pli) sans la connaissance complète des cartes restant en main de son partenaire ou de ses adversaires.

Bien jouer au bridge implique de maîtriser différents types de compétences :

• Faire des déductions (si tel joueur a joué telle séquence de coups, il a ou n’a pas telle carte)

• Émettre et réviser des hypothèses (tel adversaire a au moins 5 cartes à Pique ou n’a plus de cartes à Cœur)

• Anticiper un certain nombre de coups probables de l’équipe adverse

• Évaluer les probabilités des différentes mains adverses possibles pour guider la prise de risque et calculer l’espérance de gain des coups à jouer.

Les champions humains battus

L’intelligence artificielle de Nook, en tirant parti de la force combinée d’approches d’IA symbolique et de techniques d’IA numérique, a réussi à surpasser le niveau de 8 champions de bridge de niveau mondial sur plusieurs centaines de parties avec le même contrat à réaliser (3 Sans Atout). Pour une juste comparaison entre Nook et les joueurs humains, Nook et chaque champion ont joué les mêmes jeux, dans la même position de déclarant, contre deux robots Wbridge5 constituant l’équipe adverse. Wbridge5 (développé par Yves Costel) est multi champion du monde des robots de bridge dans le cadre de compétitions opposant uniquement des robots. Chaque champion humain (tout comme Nook) joue avec son jeu (caché) et le jeu de son partenaire (qui fait le « mort ») visible de tous, contre deux adversaires ici simulés par Wbridge5 paramétré en position de défenseur.

A la différence de jeux à information complète (comme les échecs ou le go), dans un arbre de jeu pour le bridge les coups adverses possibles en riposte au choix d’un coup par le robot dépendent des cartes des mains adverse, qui ne sont pas connues par le robot. Pour chaque nœud Min de l’arbre (c’est-à-dire un nœud qui modélise les ripostes des adversaires), Il faut donc générer des mondes possibles (les mains possibles des adversaires), et pour chacun explorer les ripostes les plus probables des adversaires à la carte jouée par le robot.

La force de Nook est d’explorer de façon intelligente un arbre de jeu avec des mondes possibles en s’appuyant sur quatre techniques complémentaires :

• Raisonnement automatique sur des règles

• Apprentissage automatique à partir d’un échantillon de parties déjà jouées afin d’apprendre la stratégie des adversaires

• Génération aléatoire de mondes possibles de type Monte Carlo contrainte par les règles du domaine et les modèles de l’adversaire

• Recherche arborescente de type MinMax avec élagage Alpha-Beta dans chaque monde possible en exploitant les modèles des différents joueurs.

Plus précisément, l’algorithme d’exploration de l’arbre de jeu des mondes possibles de Nook est une extension de l’algorithme AlphaMu développé par Tristan Cazenave et Véronique Ventos et optimisé. A chaque étape du jeu, l’algorithme génère différents mondes possibles aléatoirement tout en vérifiant leur compatibilité avec les contraintes inférées par règles et par les modèles de l’adversaire observés ou appris. Dans chacun des mondes possibles, les différents coups possibles sont évalués par un algorithme MinMax rendu très sélectif par l’exploitation des modèles de l’adversaire.

Certains modèles de joueurs sont des réseaux de neurones qui ont été entraînés à leur tâche spécifique de façon automatique. Les données d’entraînement sont obtenues à partir de centaines de milliers de parties jouées par WBridge5 contre lui-même. Le réseau de neurones utilisé, de type ResNet, n’est pas très gros, et la taille de l’ensemble des données d’entraînement est raisonnable. De ce fait, l’étape d’entraînement, réalisée sur l’ordinateur Jean Zay du CNRS, a demandé 200 000 fois moins de ressources de calcul que l’entraînement du réseau de neurones utilisé dans AlphaGo de DeepMind, qui a battu le maître de jeu de Go Lee Sedol en 2016.

Une IA compréhensible

Le raisonnement automatique sur des règles est la clef pour restreindre la combinatoire et expliquer les décisions. Les règles fournies à Nook modélisent les connaissances d’un joueur de bridge, pour inférer, à partir de la séquence des enchères, des contraintes positives ou négatives sur les mains des différents joueurs. Par exemple, une enchère “2 Sans Atout” du partenaire après une ouverture “1 Sans Atout” suivi de Passe de l’adversaire implique que le partenaire a une distribution régulière ou moins de 5 cartes à Coeur ou à Pique. D’autres règles décrivent comment l’adversaire choisit la première carte (Module d’entame).

Ces règles sont interprétables par les humains (car exprimées avec des concepts qui font sens pour des joueurs comme « distribution régulière ») et exploitables par la machine à qui on a fourni le lien entre ces concepts abstraits et des distributions concrètes de mains. A partir de la connaissance abstraite et inférée qu’une main a une distribution régulière, on peut générer automatiquement toutes les mains concrètes correspondantes (et leurs probabilités) en fonction des cartes que l’on a dans sa propre main et, au fur et à mesure de la partie, des cartes jouées par les différents joueurs.

On comprend donc bien l’intérêt des règles pour restreindre au fil du temps les mondes possibles et ainsi guider la génération aléatoire au cœur de l’exploration arborescente de type Monte Carlo.

L’autre intérêt de ces règles est qu’elles peuvent être utilisées pour expliquer, à tout moment de la partie, la vision à haut niveau et probabiliste des mains cachées des adversaires. En effet, au bridge, répondre à des questions du type « pourquoi avoir joué cette carte ? » fait partie des règles de bonne conduite pour vérifier en particulier qu’il n’y a pas de tricherie de la part d’un joueur ou qu’un coup n’est pas juste un coup de chance.

Même si Nook ne joue pour l’instant qu’une partie des « contrats » existants au bridge (le « trois sans-atout »), ses concepteurs ont d’ores et déjà prouvé le bénéfice d’une IA « hybride » qui lui donne notamment la possibilité d’expliquer ses choix. Cette nouvelle approche, que NukkAI envisage de déployer dans d’autres domaines comme la cybersécurité, l’éducation ou les transports, ouvre une voie pour avoir « quelque chose qui ressemble plus à de l’intelligence que ce que l’on a vu ces dernières années », souligne Cédric Villani, auteur d’un rapport parlementaire qui en 2018 avait inspiré la stratégie du gouvernement français sur l’intelligence artificielle, venu observer le défi en direct.