Nous travaillons à l'écriture d' un logiciel de bridge qui est en mesure de conduire la totalité d'une partie, enchères et jeu de la carte.
Il est en cours d'élaboration depuis 2006. Il développe un certain nombre de traits originaux et se révèlera, le moment venu, nous l'espérons, un compétiteur redoutable.
L'écriture d'un logiciel de ce type est complexe pour plusieurs raisons car, en dehors des problèmes logistiques et ergonomiques auxquels tout programmeur est confronté, le jeu de bridge fait appel à diverses branches complexes de l'algorithmique et du calcul des probabilités. Nous en citons quelques unes ci-dessous, sans objectif d'exhaustivité ni de présentation cohérente du logiciel.


Représentation des mains cachées

Du fait que le bridge est un jeu à information non-complète, on rencontre durant l'ensemble des phases d'enchères et de jeu, des problèmes d'épistémologie dynamique avec la construction progressive de la représentation des mains cachées (et des erreurs d'inférence), où l'approche bayésienne peut être utilisée à divers niveaux.
L'élaboration des structures de données est cruciale et doit englober les représentations des jeux à la première et à la troisième personnes.
Lors de la phase de jeu, il faut envisager aussi la question de la signalisation (effective ou trompeuse) et les subtilités qu'elle recèle.
Plusieurs marges de sécurité sont nécessaires, l'utilisation de dioïdes Min-Max est utile.


Enchères

Un problème essentiel est celui du choix d'un système d'enchères puissant et cohérent. La résolution par une méthode Monte-carlo de simulation, qui finit toujours par survenir, doit se faire le plus tard possible car elle est restreinte aux enchères naturelles et prive de la puissance expressive des conventions.
Un système d'enchères artificiel uniquement fondé sur l'entropie et l'espace disponible, tel que Ginsberg l'a esquissé, serait intellectuellement très satisfaisant mais opaque, coûteux, et peut-être pas plus performant que ceux élaborés par l'intuition et l'expérience au cours de nombreuses décennies de compétition.
En effet, un tel système automatique aurait le cahier des charges suivant :
1. Déterminer l'information maximale, concernant à la fois la forme et la force du jeu, à transmettre au partenaire, sachant que cette information est déjà, pour lui, affectée d'une certaine probabilité. (En effet il s'attend plus par exemple à se voir montrer 7 PH que 14 s'il en a 20 dans sa main, ou 5P plutôt que 5K s'il est 5521).
2. Déterminer la transmission la plus économique de cette information dans le silence adverse ou la transmission la plus compétitive dans l'autre cas.
3. Concevoir un système de décodage de l'information ainsi transmise.
Parmi les problèmes nombreux et complexes que poserait l'automatisation de ces tâches, le moindre ne serait pas celui de la tentation de recourir à des enchères multivoques (c'est-à-dire à plusieurs significations, une disjonction d'enchères en fait, comme par exemple le 2K multicolore). En dehors de l'opacité d'un tel système, il nous semble que de telles enchères sortent sensiblement de l'esprit du bridge qui requiert un degré raisonnable de transparence des enchères. Si chaque joueur affecte une plausibilité distincte à chacun des termes d'une enchère disjonctive en fonction de son jeu propre, on peut penser, sauf si l'expérience montre le contraire, que l'on introduit une charge inférentielle excessive mais surtout, que l'on utilise des enchères trompeuses puisque le jeu du flanc ne lui permettra pas dans certains cas de lever des alternatives fausses, ce qui n'est pas loin de faire disparaître la frontière entre une enchère de ce type et un mensonge.
En admettant, ce qui est très raisonnable, que l'expérience acquise à travers les millions de donnes jouées en compétition a surmonté ces difficultés de façon darwinienne, il est préférable de s'en tenir à l'opinion des experts.
C'est toutefois un travail considérable de que de procéder à l'écriture et au débogage de plusieurs milliers de règles cohérentes et conservatoires de l'expertise acquise.
Notre logiciel utilise le standard français chaque fois qu'une enchère conventionelle est utile, il passe ensuite la main à l'analyse automatique.
La qualité du comportement d'un système expert dépend évidemment de celle des règles qu'on lui donne, mais surtout de leur cohérence globale. Notre référence principale pour le système général de jeu est l'ouvrage de Soulet & Rouffet qui marque une rupture positive par rapport à ce que nous avions pu connaître auparavant (même si de nombreux compléments futurs seront indispensables). Il couvre les situations de jeu de façon assez représentative sans se perdre dans les subtilités de l'analyse des mains rarissimes. Il fait la part assez belle aux situations compétitives et fournit des repères justifiés. Evidemment de tels ouvrages ne peuvent que poser les bases d'un système et ne sont assez complets que pour les situations non-compétitives où il est en général facile de trouver le bon contrat. Pour le reste ils ne sont pas utlisables tels quels en raison de leur imprécision. On ne voit pas comment transformer simplement un ouvrage d'enchères en système de règles à cause de l'évaluation des mains en général insuffisante, des biais d'échantillonnage des mains étudiées et de l'omission de l'immense majorité des cas de figures. Par ailleurs ils ne sont pas écrits dans ce but et le jugement est censé, la plupart du temps, remplacer le calcul et, enfin, last but not least, ils ne fournissent en général aucun élement de théorie compétitive (mesure du risque, loteries, utilisation du contre punitif, etc.).



Surapprentissage et apprentissage non conservatoire

Les règles, comme les règlements, sont souvent stupides. Elles tentent d'apparier des catégories de situations à des catégories de conduites mais, pour des raisons logiques, psychologiques et philosophiques complexes, la catégorisation aussi bien que l'appariement contreviennent souvent à ce qu'il est convenu d'appeler le bon sens.
En effet, si le prototype est une instance réelle d'une classe, il est moins représentatif qu'un condensé d'information (moyenne par exemple) qui lui, ne l'est pas. Quant à l'exemple, d'une ontologie encore plus douteuse, il véhicule souvent trop d'information implicite et d'hypothèses fortes sur son statut de représentant idéal.
Les exemples exposent au phénomène classique de surapprentissage qui érode l'expérience acquise (cf. les réseaux de neurones formels). Le problème central est l'obtention de procédures d'apprentissage conservatoires et capables de progresser indéfiniment.
On rencontre aussi ce phénomène dans l'apprentissage humain avec la courbe sigmoïde classique des apprentissages et la phase de plateau consécutive. Aux échecs ou au bridge, par exemple, il n'est pas inhabituel de voir des joueurs résider pendant des décennies dans les mêmes zones du classement, et pas toujours les plus élevées. Cela s'explique par le fait que certains joueurs analysent peu ou pas leurs parties, par des biais d'échantillonnage des donnes peut-être (en fonction de leur impact différentiel sur les classements des compétitions), mais surtout par des processus internes de généralisation de l'expérience non conservatoires.


Jeu

Une méthode exacte de résolution du jeu (telle que celle utilisée dans le logiciel ScanSuit) ne paraît pas concevable encore pour l'ensemble de la partie, en raison de l'explosion combinatoire. Lorsqu'ils ont fait des inférences correctes sur les mains cachées, les solveurs double mort se révèlent très performants, même s'ils ont tendance à surestimer la qualité du jeu adverse et à amalgamer les lignes de jeu.
Ginsberg a écrit un solveur simple mort qui résout huit levées environ. Même si une simplification importante peut être obtenue s'il est construit sur la base d'un échantillon de mains comme ceux qu'utilisent les solveurs double mort et non pas sur l'ensemble du jeu comme nous le faisons avec ScanSuit pour l'analyse des couleurs simples, cette solution demeure sans issue pour le jeu complet, et il s'est orienté vers une heuristique de substitution. Il annonce un gain de 0,1 IMP par donne avec ce solveur.
Nous avons développé un tel solveur, d'autres sont employés par certains programmes actuels mais, à notre connaissance, aucune étude n'a été publiée sur ce sujet et il est difficile de se faire une idée précise. Il faut noter que, exception faite de Matthew Ginsberg qui est un génie de l'algorithmique dans les arbres de recherche et qui a mis toute la communauté des programmeurs de bridge sur orbite, celle-ci est plutôt mutique, et même assez peu reconnaissante si l'on nous permet cette opinion personnelle.
Notre logiciel utilise, à l'occasion et dans des conditions différentes de celles présentées ci-dessous, un solveur double mort que nous avons écrit pour l'essentiel en Pascal objet (Delphi), et qui présente quelques traits originaux, notamment dans la recherche des plis rapides (levées faites sans rendre la main à l'adversaire).
Ce solveur est également utilisé par les logiciels ScanDeal et ScanGame.
Le temps médian de résolution des mains est d'environ six centièmes de secondes avec un processeur à 3 Ghz. Le temps moyen est un peu plus élevé en raison des donnes très difficiles, à distributions excentriques, qui surviennent dans des proportions non négligeables. Il y a de légères différences entre les performances moyennes à l'atout et à sans atout.
Les performances de ce solveur sont nettement supérieures à celles du DDS de Bo Haglund, dont le code est public et au perfectionnement duquel nous avons contribué à plusieurs reprises (correction de diverses bogues, constitution d'une nouvelle structure de données pour la table de transposition améliorant la vitesse de 15% dans la dernière version).
Ces temps de résolution s'entendent bien sûr sans parallélisation, ils sont à pondérer en fonction du nombre de processeurs que l'on peut utiliser.
Les questions de vitesse sont maintenant secondaires pour les ordinateurs bridgeurs, les méthodes d'échantillonnage sont beaucoup plus importantes, elles reposent sur la qualité des inférences à la base de la représentation des mains cachées.



Les statistiques

Les problèmes posés par le bridge sont NP-complets, c'est-à-dire que l'arsenal traditionnel des statistiques y rencontre vite des limites indépassables.
Les fonctions polynômiales approximent difficilement le monde combinatoire, qui leur est hétérogène. Les méthodes les plus sophistiquées (réseaux de neurones formels par exemple) laissent un appréciable pourcentage de variance inexpliquée et, souvent, une variance d'erreur beaucoup plus élevée que celle d'un système de règles élémentaires comme en utilisent les joueurs. En conséquence elles ne paraissent guère utiles. Avec une exception toutefois pour ce qui concerne le compte des points où la régression linéaire peut se révéler précise, surtout si elle évite les biais induits par les solveurs double mort (notamment dévalorisation des petits honneurs régulièrement pris en impasse). Le logiciel utilise divers systèmes de décompte des points recourant à ces méthodes.


Alpha-beta et élagage

L'algorithme alpha-beta, enrichi notamment de la recherche par partition et de nombreux algorithmes annexes (voir la présentation qu'en donne Bo Haglund sur son site), pose des problèmes complexes d'optimisation (avec des conséquences directes sur la rapidité du solveur double mort) et les règles habituelles de son usage ne conviennent qu'à des situations épurées (facteur de branchement constant dans l'arbre par exemple) hors desquelles il peut fournir des résultats assez contre-intuitifs.
Néanmoins la mise en ordre préalable des mouvements sous chaque noeud demeure un facteur essentiel de la performance et, là aussi, nous pensons qu'un bon système expert est beaucoup plus robuste que les montages statistiques les plus raffinés et se montre capable d'affronter les mains très atypiques avec beaucoup plus de bon sens.


L'écriture d'un logiciel de bridge est très difficile et n'est pas sans rappeler d'autres problèmes voisins rencontrés en informatique et en intelligence artificielle (traduction automatique, reconnaissance de la parole, etc.) qui touchent à l'expertise humaine et auxquels, bizarrement, les joueurs de bridge dans leur immense majorité sont plutôt insensibles, quand ils ne les considèrent pas comme artificiels et se bornent à considérer parfois avec ironie le jeu des ordinateurs. Nous n'avons pas à porter de jugement sur cette attitude, mais simplement à rappeler le fait que dans quelques années ou quelques dizaines d'années, la supériorité des humains sur les machines à ce jeu sera dans les musées avec le cinéma muet, les cabines téléphoniques et les machines à écrire.

Ce travail de programmation pousse son concepteur à ses limites et il sait qu'il ne peut attendre de résultats significatifs avant plusieurs dizaines de milliers d'heures de travail. Aussi nous plait-il de rendre un hommage à la persévération et à l'intelligence exceptionnelles de ceux qui se sont jusqu'à présent illustrés dans ce domaine, et spécialement lorsqu'ils ont travaillé seuls, fournissant ainsi un travail d'une qualité et d'une densité très nettement supérieures à celles de la production scientifique ordinaire.