|
Un
logiciel de bridge doit être en mesure de conduire la
totalité d'une partie, enchères et jeu de la
carte. 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 peut priver 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 conventionnelle 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. La référence
à des ouvrages classiques ne peut que poser les bases d'un
système et ils 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
utilisables tels quels en raison de leur imprécision, quand
par exemple, pour décider entre contrer ou surenchérir,
on vous dit qu'il faut de l'expérience, du jugement et du
sang-froid. Personne n'a évidemment la moindre idée
de la façon dont ces banalités peuvent devenir
opérationnelles. 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, ils ne
fournissent en général aucun élément
de théorie compétitive (mesure du risque, théorie
des 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 cinq 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. Pour les donnes difficiles 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
polynomiales 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. On peut télécharger une
application de démonstration sur le présent site.
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 plaît-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.
|