Magazine WEBridge n° 05

Articles " Libres propos "

Note préliminaire : Si vous souhaitez écrire un article " coup de cœur " ou " coup de ...colère ", n'hésitez pas à nous le proposer en l 'annexant à un message à nous transmettre en cliquant ici.

 

 Bridge & Intelligence Artificielle

par PIerre Cormault

" Chaque aspect de l'apprentissage, ou tout autre caractéristique de l'intelligence, peut, en principe, être décrit si précisément qu'il est possible de construire une machine pour le simuler."

Cette déclaration rédigée par un groupe de chercheurs ¹ réunis à l'Université de Dartmouth College (USA) en 1956, est considérée comme l'acte de naissance de l'intelligence artificielle (IA, par abréviation) en tant que discipline scientifique.

 

Amener les ordinateurs à battre des humains au jeu a été l'un des buts premiers de l'IA.

Avec les jeux, les chercheurs en IA ont en effet un éventail commode de problèmes bien circonscrits auxquels ils peuvent confronter, à chaque étape, la puissance mentale de leurs machines. Contrairement à la plupart des problèmes rencontrés dans la vie quotidienne, les jeux possèdent des définitions claires et ne font appel qu'à un petit nombre d'éléments de base. Ils sont néanmoins suffisamment complexes pour requérir des techniques de résolution qui sont loin d'être simples. En outre, la valeur d'un programme de jeu se mesure aisément : soit il gagne, soit il perd.

Dès 1970, beaucoup de chercheurs en IA abordèrent, pour ces raisons, le jeu d'échecs sur ordinateur, tandis que, réciproquement, beaucoup d'experts du jeu étaient amenés à s'intéresser à l'intelligence artificielle. Depuis lors, le champion du monde Garry Kasparov s'est fait battre à deux reprises par des ordinateurs. Et, dès 1988, le programme d'échecs Deep Thought avait franchi la barre de l'indice ELO 2500 ², ce qui faisait de lui le premier Grand Maître International électronique, surpassant aux échecs à peu près n'importe qui, à l'exception de 200 personnes à travers le monde.

 

Les efforts consacrés à la programmation d'un joueur de bridge électronique, et donc les résultats obtenus, sont à ce jour beaucoup plus modestes. C'est pourquoi le champion Zia Mahmood n'a pas pris beaucoup de risques en offrant une prime de 1 million de Livres à la paire d'ordinateurs qui gagnerait un match contre lui, associé à un partenaire de son choix.

Il est quand même un chercheur américain en IA, Matthew Ginsberg, de l'Université de l'Oregon, pour penser que la suprématie des champions du monde de bridge humains sera bientôt fortement contestée par des programmes d'ordinateur. Et, de fait, Matt Ginsberg et son équipe ont déjà développé GIB, le programme qui détient actuellement le titre de champion du monde des programmes de bridge ³.

L'approche de Ginsberg a consisté dans un premier temps à gommer, autant que faire se pouvait, la différence fondamentale entre les jeux de bridge et d'échecs. Alors que les échecs sont un jeu à information complète (la situation sur l'échiquier, à chaque moment, de chaque pièce amie ou ennemie), le bridge est au contraire un jeu à information très incomplète. Pour bénéficier des avancées conceptuelles des programmes d'échecs, il faut commencer par supposer que l'on joue au bridge à cartes ouvertes. L'exercice entrepris n'est alors plus une partie de bridge, mais la résolution de ce qu'on appelle un problème de bridge. Un tel programme de résolution de problèmes de bridge à cartes ouvertes ⁴ a été écrit par Ginsberg et d'autres, et parvient toujours, après un temps de calcul plus ou moins long, à la solution exacte du problème, au prix de l'examen systématique de toutes les combinaisons de cartes licites possibles, aussi bien pour le déclarant que pour le flanc en défense.

Reste alors, à partir de ce solveur de problèmes à cartes ouvertes, à imaginer un programme jouant véritablement au bridge. C'est dans cette perspective que Ginsberg fait preuve de vues révolutionnaires.

Écoutons-le évoquer, tout d'abord, la question des enchères :

"Les ordinateurs vont utiliser des systèmes d'enchères qu'ils inventeront au fur et à mesure. Leur point de départ sera une base de données gigantesque dans laquelle un million de donnes auront été annoncées dans le cadre d'un système d'enchères de base, puis résolues par le solveur de problèmes de bridge à cartes ouvertes. En match, chaque fois qu'une situation d'enchères conduira à la question du choix entre 2 ou 3 enchères également envisageables, mais vraisemblablement inégalement efficaces, le programme choisira, en consultant dans sa base de données, les séquences comparables et les résultats finaux engendrés."

A ce stade, il est clair que ce projet apparaît comme parfaitement réalisable ⁵. Mais Matt Ginsberg va beaucoup plus loin:

"Dans la séquence d'enchères, il arrive un stade où la base de données d'un million de donnes ne peut plus fournir d'échantillon statistiquement significatif. Imaginons ainsi une donne dans laquelle Sud a déjà décrit une main de 19+ PH avec une majeure sixième non précisée. De son côté, son partenaire a montré une main de structure 5332 avec 2 As et une Dame. On en est à 4T. Mais la base de données ne contient aucun cas similaire qui permettrait de connaître la meilleure continuation possible. Que feront alors les deux programmes partenaires jouant en NS dans cette situation?"

La réponse de Ginsberg est, quelque peu, effrayante :

"Les deux programmes vont alors générer, séparément mais simultanément, la même série de 100 donnes distribuées au hasard, mais respectant les contraintes décrites ci-dessus. Le meilleur contrat pour chacune des 100 donnes sera alors déterminé à l'aide du solveur. Puis, à partir des enchères encore disponibles et du but optimal à atteindre ainsi connu, les deux programmes inventeront simultanément le même système d'enchères local, valable uniquement pour la situation présente. Il sera très décourageant d'affronter une paire qui invente son système d'enchères au fur et à mesure que la séquence progresse, et cela sans tricher, et sans jamais la moindre incompréhension entre les deux partenaires. Bien entendu, les machines auront l'obligation d'expliquer leurs conventions à leurs adversaires ⁶. C'est ainsi qu'après une enchère de 5T par Sud, on pourra parfaitement voir Nord délivrer un message expliquant que son partenaire détient, soit un simpleton Cœur et le Roi de Pique, soit une chicane Cœur sans le Roi de Pique, soit les 2 Dames mineures!"

L'approche proposée pour le jeu de la carte s'inspire des mêmes techniques. Au début de la donne, le programme construit un échantillon de 100 donnes tirées au hasard mais respectant les contraintes connues (séquence d'enchères, carte d'entame, cartes du mort). Puis le solveur à cartes ouvertes résout ces 100 problèmes. L'hypothèse de Ginsberg est alors qu'en appliquant des techniques d'optimisation statistique du type Monte-Carlo, le programme trouvera le plus souvent la meilleure carte possible à jouer. De levée en levée, se dessinera alors la ligne de jeu gagnante.

Pareil comportement est sans aucune analogie avec le raisonnement qui sous-tendra au contraire l'action d'un joueur humain. Car la machine ne fait aucun plan. Elle calcule seulement la meilleure carte à jouer dans la situation du moment.

Cette approche parfaitement inhumaine a des chances sérieuses de devenir extrêmement efficace, à la condition de disposer d'un solveur de problèmes à mains ouvertes capable d'analyser une donne complète en 1 seconde. GIB ne dispose pas encore d'une telle rapidité. mais il ne s'en faut que d'un facteur 20 environ, ce qui en informatique ne paraît nullement insurmontable.

 

Nous venons de voir, qu'emporté par le vent de la compétition, un chercheur peut concevoir un programme capable de gagner au jeu, mais plus du tout de penser comme un humain.

Mais l'intelligence artificielle est une discipline qui se caractérise par sa diversité, et, parfois, par des antagonismes profonds entre approches différentes.

Au début des années 70, deux chercheurs pionniers en IA, Allen Newell et Herbert Simon, avaient décomposé le processus de la pensée en deux capacités fondamentales: celle de chercher, fouiller (c'est-à-dire de tester différentes solutions à apporter à la solution d'un problème), et celle de stocker et de récupérer les connaissances appropriées, sous la forme de règles " Si..alors ".

En 1972, ils rassemblèrent leurs découvertes concernant ce rôle-clé des systèmes de production (l'autre nom pour désigner les ensembles de règles " Si...alors ") dans un volumineux ouvrage "Human problems solving". Ces travaux allaient directement provoquer dans les années 80 la naissance des premiers systèmes experts. Selon cette approche, un programme informatique alimenté en connaissances par des experts, pourrait résoudre convenablement un problème de la seule compétence desdits experts.

Le programme Sabrina (en téléchargement gratuit à l'adresse http://perso.wanadoo.fr/pierre.cormault/ ) est une expérience de ce type, visant à développer une simulation informatique de joueur de bridge. Les connaissances d'experts mises sous la forme d'un système de production y sont pour le moment encore très limitées. Elles consistent en le contenu de l'exposé du Système d'Enseignement Français (SEF)qu'on trouve dans la brochure de 1995 de l'Université du bridge, pour la partie enchères, et en une partie des méthodes et conseils publiés par Berthe et Lébely, dans leur série de " Pas à pas ", pour ce qui concerne le jeu de la carte.

Dans son état actuel, c'est-à-dire seulement muni d'un système de production encore très lacunaire, Sabrina reste beaucoup moins compétent que les spécialistes qui l'ont alimenté en connaissances. Mais par contre, le programme est déjà capable d'élargir les connaissances et compétences des non-experts qui l'utilisent.

Par ailleurs, un système expert tel que Sabrina évoque la pensée humaine par un aspect non négligeable. Contrairement aux programmes évoqués dans la première partie de cet exposé, il est simple et rapide de lui inculquer des notions nouvelles. Il dispose donc d'une faculté d'apprentissage.

 

Notes de renvoi

¹Les quatre organisateurs de la Conférence de Dartmouth étaient Marvin Minsky et John McCarthy, les co-créateurs du groupe d'intelligence artificielle du Massachusetts Institute of Technology (MIT), Claude Shannon, le mathématicien qui énonça le premier, en 1947, le principe de la procédure minimax d'interprétation d'un arbre de jeu ⁴, et Nathaniel Rochester, le concepteur de l'IBM 701, le premier ordinateur universel de série.

---

² Le classement ELO de la Fédération Internationale d'Échecs (FIDE) permet de mesurer le niveau atteint par chaque joueur. Il est conçu de sorte qu'avec une différence de 200 points ELO entre 2 joueurs, le mieux classé battra le moins bien classé 3 fois sur 4. Un joueur devient Maître International au dessus de 2400. les Grands Maîtres Internationaux gravitent autour de 2500-2600. Garry Kasparov a un ELO de 2800.

---

³ Le premier championnat du monde de programmes de bridge semble avoir été organisé en 1997 sous le patronage de l'American Contract Bridge League (ACBL). 5 programmes de nationalités US, japonaises et allemandes y participaient. Le vainqueur en fut le programme Bridge Baron, développé à l'Université de Maryland par une équipe du Professeur Dana Nau.

GIB détrôna Bridge Baron l'année suivante 1998, et confirma son titre en 1999, lors du championnat disputé aux Bermudes. Un challenger inattendu, le programme français WBridge5 (en téléchargement gratuit à l'adresse http://perso.chello.fr/users/y/yvescostel/ ) écrit par Yves Costel, prenait brillamment la seconde place.

En 2000, à Maastricht, GIB ne jugea pas utile de participer, tandis que WBridge5 cédait du terrain devant de nouveaux venus.

  

Sources bibliographiques

 

1 - Je dois une reconnaissance particulière à Daniel Crevier, Professeur à l'Université McGill et à l'Université du Québec, pour les emprunts importants que j'ai fait à son livre "The tumultuous history of the search for artificial intelligence" paru en 1993, et traduit en 1997 sous le titre français " A la recherche de l'intelligence artificielle ", Ed. Flammarion.

 Ces textes sont disponibles sur le site Internet de l'Université de l'Oregon: www.cirl.uoregon.edu