LE MANIEMENT AUTOMATIQUE DE LA COULEUR AU BRIDGE
Joël BRADMETZ
Manier une couleur au bridge, c’est déterminer la façon optimale pour le déclarant (situé en Sud par convention), dont le partenaire
est le mort (situé en Nord), de jouer une couleur de 13 cartes réparties en quatre jeux, dont les deux de l’adversaire (le flanc) sont inconnus, de façon à
maximiser les chances de réaliser un nombre n de levées. Le maniement de la couleur est un chapitre assez bien documenté de la théorie du bridge,
bien qu’il n’y ait à ce jour, à notre connaissance, excepté ScanSuit, aucun programme capable d'analyser exhaustivement n'importe quelle main, et que les jugements des experts
(et les erreurs qu’ils contiennent parfois) soient les principales références [1,2].
La théorie du maniement repose sur un constat et deux hypothèses. Le constat selon lequel toute rentrée dans la couleur par le flanc ne peut lui
apporter d’avantage permet de limiter l’initiative du jeu à la ligne Nord-Sud et de ne pas lui faire craindre de perdre la main (selon les règles du bridge, le joueur qui entame une
nouvelle levée est celui qui a réalisé la précédente). Les hypothèses sont que : i) Nord-Sud n’est pas limité dans ses reprises de
main (assurées par les autres couleurs) et que : ii) Est-Ouest jouent la meilleure défense, autrement dit qu’ils ont la connaissance du diable, c’est-à-dire
non seulement celles des jeux de Nord et Sud mais aussi celle de la stratégie du déclarant. Cette hypothèse est rendue nécessaire par le fait que, dans certaines situations,
le jeu de bridge n'a pas d'équilibre de Nash.
Un jeu possède un équilibre de Nash lorsque les joueurs connaissent mutuellement leurs stratégies et que ce fait ne conduit pas à les
modifier. [Ce qui n'assure pas un gain optimal pour les deux, l'équilibre peut être catastrophique (perdant-perdant) comme dans le cas du dilemme du prisonnier].
Le jeu Pierre, feuille, ciseaux
par exemple, n'a visiblement pas un tel équilibre : si je sais que mon adversaire va jouer feuille, je joue ciseaux mais s'il sait que je vais jouer ciseaux je jouerai pierre, auquel cas il jouera
feuille, et ainsi de suite sans fin. Certaines positions de bridge sont équilibrées, d'autres non. Considérons la donne suivante à titre d'exemple.
Vxx | |||||||||||||||
Rx | |||||||||||||||
xxxxx | |||||||||||||||
xxx | |||||||||||||||
xxx | |||||||||||||||
.... | |||||||
.... | |||||||
La remise en main de Sud par le 9 de coeur paraît assurer le contrat puisque Sud doit conserver sa Dame de carreau troisième. Mais, si Sud se doute de la remise en main, alors, il gardera son 8 de coeur
et fera deux levées. Mais si Est devine cette stratégie, alors il tirera As et Roi de carreau. mais si Sud connaît cette stratégie, il gardera sa Dame troisième, etc. etc.
Est n'a aucun moyen de savoir qui de Sud ou de Nord a conservé le dernier coeur, Sud n'a pas le moyen non plus de savoir quelle stratégie va adopter Est. En conséquence l'issue du contrat est incertaine.
Pour éviter ce genre de situation qui ferait reposer un gain du déclarant sur une erreur du flanc, la théorie de la meilleure défense postule que le flanc connaît toujours la stratégie du déclarant.
Ainsi, dans cet exemple, Sud fera systématiquement chuter le contrat en ayant défaussé en fonction de la stratégie ultérieure d'Est.
Cette théorie du maniement exclut également les coups aléatoires aussi bien que les stratégies mixtes.
La meilleure défense peut conduire à certaines situations assez peu réalistes.
Par exemple, Sud souhaite réaliser 3 levées avec AR32 - V98 (les cartes sont données dans l’ordre Sud-Nord) et il envisage de
jouer petit vers 9 puis de laisser courir
le V. (Ce n’est pas sa meilleure stratégie mais il peut souhaiter se prémunir contre DX qu’il croit à tort en Est).
Sur le départ du 2, et avec D65,
Ouest ne jouera pas D que remonterait minimax, et qui assure au moins une levée, mais 5 qui, dans ce cas, en apportera deux.
Le nombre de cartes est réduit, les règles sont élémentaires, le problème peut paraître simple. En fait il est NP-complet [3] et a une requête en calcul exponentielle sur la taille de l’arbre. Le déclarant ne peut pas énumérer tous les mondes adverses et combiner les minimax qu’il calculerait avec chacun d'eux car il aboutirait dans ce cas à une fusion de stratégies [4]. Avec AD-32 par exemple, le but du déclarant est simple : réaliser D pour faire deux levées. Contre tous les R en Est (50%), minimax prescrit l’impasse : 2xD ; contre R sec en Ouest, minimax prescrit de jouer 2xA. Le déclarant sait quoi faire dans chaque monde mais ne sait pas dans quel monde il est et devra donc prendre une décision après 2x. Dès les cas un peu complexes, cette décision ne peut pas être fondée sur des critères probabilistes revenant à choisir l’option la plus probable (ici R en Ouest) car elle se heurterait à des contre-mesures du flanc. Prenons, pour le montrer, l’exemple de R954 - AV32 et le projet de réaliser quatre levées (trois levées se font à p = 1). Après 5X, faut-il jouer A ou V ? Le dénombrement des mondes résiduels montre que le X peut provenir de 16 positions réparties dans 8 mondes distincts (les cartes ex-aequo sont codées de façon identique):
DX888 (1cas) ; X888-D (1 cas) ; DX88-8 (3 cas) ; X88-D8 (3 cas) ; DX8-88 (3 cas) ; X8-D88 (3 cas) ; DX-888 (1 cas) X-D888 (1 cas).
De ces seize cas, il apparaît que D est 7 fois en Est et prenable en jouant A suivi de V, contre 4 fois seulement en Ouest et pouvant être capturé e par l’impasse. Ce rapport de 7 contre 4 conseille donc de jouer A. Seulement, après 58, une analyse semblable aurait conseillé de faire l’impasse. Ce qui fait que le flanc, avec DX8 en Ouest sauvera sa Dame en jouant X et avec X88 ou X8, sauvera celle d’Est en jouant 8, et le déclarant perdra sur (presque) tous les tableaux. Cela signifie qu’un sous-arbre du jeu ne peut être analysé séparément, phénomène que Frank [4] nomme non-localité.
On peut imaginer une analyse combinatoire des probabilités qui envisage toutes les réponses simultanément. Ici l’examen de VV, VA, AV et AA sur 48 et 4X montre des réussites de 9/30, 6/30, 5/30 et 7/30 et suggère qu’il faut, qu’Ouest joue 8 ou X, toujours jouer V. Seulement cette façon de faire, correcte ici, risque encore de conduire à l’échec dans d’autres cas. Voyons un exemple sur les feuilles de l’arbre du jeu 432 - RV98 et une ambition de 3 levées.
Après 4A87 4DR7 47, il reste deux mondes adverses et deux stratégies:
Le second est plus probable (.0533 contre .0484 au départ du jeu et .5238 contre .4762 à ce niveau). Donc Nord devrait jouer V pour trouver le X en Est s’il écoute les probabilités, mais il perd dans ce cas dans les deux mondes car, dans le premier, le flanc joue A au premier tour (séquence du texte) et dans le second il joue 7 pour réaliser le X en Est, ce qui fait que la réussite passe de .2400 (double impasse pour tous les cas où DX sont en Ouest), à .1550 (ces probabilités tiennent compte des places vacantes).
La solution du problème est donc purement combinatoire et revient, pour chaque objectif (i.e. nombre de levées), à chercher le sous-ensemble des mondes qui apporte la meilleure probabilité de réussite pour une stratégie déterminée. Autrement dit, il faut dénombrer tous les sous-ensembles de mondes du flanc et toutes les stratégies du déclarant.
Une stratégie de MAX est un arbre de recherche dont le facteur de branchement est de 1 aux noeuds MAX. Autrement dit, la carte
jouée dans chaque situation est unique et arrêtée à l'avance.
Une stratégie réalise un nombre n de levées contre un sous-ensemble précis de répartitions des cartes du flanc
(par exemple Sud = 3 2 et Nord = A D
réalise deux levées contre tous les Rois en Ouest).
Si le flanc possède n cartes, il y a 2n
répartitions de ces cartes. Une stratégie fonctionne contre une bi-partition
de ces sous-ensembles, et il y a 22n telles bi-partitions.
Si MAX possède p cartes en Nord et q cartes en Sud, il a p! x q! stratégies différentes.
Trouver le meilleur maniement consiste à confronter chacune des p! x q! stratégies à chacune des 22n
bi-partitions, pour chaque nombre n de levées souhaité.
Soit par exemple AV85 – D963, les cartes du flanc : RX742 sont réparties dans un ensemble de cardinal 25 = 32 mondes. L’ensemble des parties de cet ensemble est de cardinal 232 = 4 295 967 294, soit autant que d’adresses mémoires possibles sur un PC 32 bits… Et chacun de ces sous-ensembles de mondes doit être confronté à toutes les façons possibles de jouer. Pour ce calcul, nous avons élaboré un algorithme combinatoire sur un treillis de formes normales disjonctives n-aires, puisque le jeu n’a pas simplement deux issues mais autant que de levées réalisables. Ginsberg [5] présente la théorie d’un tel treillis distributif dans le cas de l’atteinte d’un seul objectif et son treillis binaire peut alors être simplifié grâce à des algorithmes de réduction des OBDD (ordered binary decision diagram) et la structure de donnée peut se réduire aux sous-ensembles eux-mêmes et non aux valeurs réalisées. Nous n’avons pas cette possibilité et la réduction des formes disjonctives n-aires est beaucoup plus complexe. Néanmoins, certains élagages permettent de réduire ce temps de façon appréciable et d’aboutir à des solutions pour toutes les distributions possibles (par exemple, les 660 positions analysées dans [1] sont calculées en quelques dizaines de secondes), mais les combinaisons des livres sont simples, comparées par exemple à AD83 - X75 pour laquelle la meilleure stratégie pour 2 levées (.9516) apparaît seulement en 8 240ème position parmi 77 579 statégies disjointes.
La dernière version du logiciel ScanSuit a sensiblement accru la vitesse de résolution des positions en introduisant la recherche par partition ( habituellement utilisée dans
les solveurs double-mort ) dans le calcul des stratégies. Cette technique est assez complexe car cette recherche s'effectue dans tous les mondes explorés simultanément,
et non pas dans un seul comme c'est le cas avec un solveur double-mort. Elle ne permet pas de reconstituer l'ensemble des stratégies et de les jouer en raison des élagages trop importants de l'arbre de jeu.
L'utilisateur voulant détailler une stratégie laissera simplement l'option recherche normale et patientera un ou deux dixièmes de secondes supplémentaires dans la plupart des cas....
Il y a 52 ! façons de ranger un jeu de bridge, soit 8,065 * 1067. Il n’y a pas autant de mains différentes puisque toutes les permutations des cartes de rang modulo 1, 2, 3 et 4 laissent les jeux invariants. Il y a 13 ! telles permutations pour chaque rang soit en tout 13 ! 4 = 1,50356173 * 1039 . Le nombre de distributions différentes entre 4 joueurs est donc le nombre de façons de ranger le jeu, divisé par ces permutations, soit : 8,065 * 10 67 / 1,503 * 10 39 = 5,364 * 10 28. Nous retrouvons ce résultat par un autre raisonnement fondé sur les combinaisons. Il y a C(13,52) * C(13,39) * C(13*26) distributions possibles des cartes soit : 5,364 * 10 28
Du point de vue de la partie et des maniements (mais non pas des contrats et des enchères), ce nombre peut encore être réduit puisque les couleurs sont permutables. Si l’on divise le nombre de distributions par 4 ! (les permutations de couleur) il en reste finalement 13 411 184 439 699 948 178 299 803 550.
Le maniement d’une seule couleur constitue souvent un module cloisonné et indépendant du jeu global, bien qu’aucune théorie générale n’explique comment articuler plusieurs maniements ensemble. Si la même ligne conservait la main durant les 13 levées de la partie, le problème serait trivialement celui de quatre maniements de couleur indépendants et la seule chose à surveiller serait les défausses maladroites du partenaire. La complexité du bridge n’apparaît qu’avec les reprises de main.
Il y a 413 distributions d’une couleur entre les 4 joueurs. Si l’on considère le seul point de vue du déclarant et que l’on cache les mains adverses, il y a alors 313 distributions (chacune des 13 cartes va soit en Sud, soit en Nord, soit chez l’adversaire). Dans le cas idéal où les reprises de main ne sont pas limitées en Sud ni en Nord (conventionnellement le mort), ce nombre peut être ramené par symétrie à (313 +1) / 2 (on ne peut diviser simplement par 2 parce qu’une distribution n’est pas permutable : celle où Sud et Nord sont vides). Nous atteignons alors le nombre beaucoup plus raisonnable de 797 162 et, par convention, Sud se verra toujours attribuer un jeu au moins aussi long que celui de Nord. Il y a 213 = 8192 mains globales différentes laissées au flanc, à l’intérieur desquelles on doit considérer toutes les répartitions Est-Ouest.
La répartition de ces cas est donnée dans le tableau 1. Dans l'article sur le calcul des fréquences, on montre que d'autres réductions empiriques sont encore possibles.
Les parties de bridge réelles proposent la plupart du temps des situations où le déclarant possède des informations, même minimes,
sur les jeux du flanc. Un logiciel réaliste doit en tenir compte. C’est ce que fait le programme ScanSuit qui estime tous les maniements en pouvant attribuer à un joueur du flanc
des cartes de la couleur maniée ou d’une autre couleur (afin de modifier les places vacantes), en tenant compte des défausses antérieures dans la couleur d’un joueur quelconque,
en connaissant le joueur long et/ou le joueur fort du flanc, en fixant la parité d’un joueur, en limitant les reprises de main de Sud et/ou Nord. Le programme fournit également
les maniements à observer lorsque le nombre de levées brutes, après codage en points, est converti dans les cotations spécifiques du tournoi par paires ou du match
par quatre. Dans le premier cas, on doit tenir compte de la stratégie du champ, dans le second, de celle de l’autre table. Dans ces deux cas, les maniements recommandés
peuvent différer des maniements théoriques.
[1] Francis, H.G., Truscott, A.F. (2002) The official encyclopedia of Bridge. 6th edition. New-York : D.A. Francis.
[2] Roudinesco, J.M. (1995). Le dictionnaire des maniements de couleur. Paris : Editions du Rocher.
[3] Frank, I & Basin, D. (2001). A theoretical and empirical investigation of search in imperfect information games. Theoretical Computer Science, 252, 217-256.
[4] Frank, I . (1998). Search and planning under incomplete information : a study using bridge card play. Springer-Verlag, Distinguished Dissertation Series.
[5] Ginsberg, M. (2001). GIB : Imperfect information in a computationnaly challenging game. Journal of Artificial Intelligence Research, 14, 303-358.
Tableau 1. Répartition des maniements de couleur.
A |
B |
C |
D |
E |
F |
G |
|
0*0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1*1 |
13 |
13 |
13 |
13 |
13 |
2 |
2 |
2*1 |
78 |
78 |
78 |
78 |
23 |
3 |
2 |
2*2 |
78 |
78 |
78 |
78 |
78 |
10 |
10 |
3*2 |
858 |
726 |
726 |
506 |
296 |
23 |
21 |
3*3 |
286 |
286 |
286 |
286 |
286 |
56 |
56 |
4*2 |
2145 |
1540 |
1540 |
1540 |
349 |
27 |
23 |
4*3 |
2860 |
2200 |
2200 |
1705 |
1219 |
201 |
198 |
4*4 |
715 |
715 |
715 |
715 |
715 |
330 |
330 |
5*3 |
12870 |
7425 |
7425 |
6303 |
3831 |
631 |
612 |
5*4 |
6435 |
4455 |
4455 |
3663 |
2879 |
1723 |
1719 |
5*5 |
1287 |
1287 |
1287 |
1287 |
1287 |
1287 |
1287 |
6*3 |
17160 |
7260 |
7260 |
7260 |
2269 |
607 |
575 |
6*4 |
25740 |
11880 |
11880 |
10494 |
7288 |
7288 |
7254 |
6*5 |
10296 |
6336 |
6336 |
5412 |
4495 |
4495 |
4494 |
6*6 |
1716 |
1716 |
1716 |
1716 |
1716 |
1716 |
1716 |
7*4 |
60060 |
17640 |
17640 |
16134 |
10484 |
10484 |
10315 |
7*5 |
36036 |
12936 |
12936 |
11682 |
8799 |
8799 |
8777 |
7*6 |
12012 |
6468 |
6468 |
5676 |
4890 |
4890 |
4889 |
7*7 |
1716 |
1716 |
924 |
924 |
924 |
924 |
924 |
8*4 |
45045 |
8001 |
8001 |
8001 |
3343 |
3343 |
3212 |
8*5 |
72072 |
14112 |
14112 |
13077 |
9377 |
9377 |
9271 |
8*6 |
36036 |
9702 |
6104 |
5564 |
3627 |
3627 |
3626 |
8*7 |
10296 |
4752 |
1638 |
1428 |
1097 |
1097 |
1096 |
8*8 |
1287 |
1287 |
252 |
252 |
252 |
252 |
252 |
9*5 |
90090 |
8820 |
6376 |
5951 |
2259 |
2259 |
2220 |
9*6 |
60060 |
7350 |
3275 |
3015 |
1502 |
1502 |
1501 |
9*7 |
25740 |
4950 |
1290 |
1135 |
668 |
668 |
667 |
9*8 |
6435 |
2475 |
385 |
329 |
242 |
242 |
241 |
9*9 |
715 |
715 |
70 |
70 |
70 |
70 |
70 |
10*5 |
36036 |
1596 |
389 |
379 |
101 |
101 |
101 |
10*6 |
60060 |
2940 |
714 |
692 |
192 |
192 |
191 |
10*7 |
34320 |
2400 |
597 |
511 |
192 |
192 |
191 |
10*8 |
12870 |
1650 |
258 |
218 |
116 |
116 |
115 |
10*9 |
2860 |
880 |
90 |
75 |
53 |
53 |
52 |
10*10 |
286 |
286 |
20 |
20 |
20 |
20 |
20 |
11*6 |
36036 |
588 |
64 |
62 |
19 |
19 |
18 |
11*7 |
25740 |
540 |
64 |
62 |
19 |
19 |
18 |
11*8 |
12870 |
450 |
60 |
59 |
19 |
19 |
18 |
11*9 |
4290 |
330 |
50 |
40 |
19 |
19 |
18 |
11*10 |
858 |
198 |
21 |
17 |
12 |
12 |
11 |
11*11 |
78 |
78 |
6 |
6 |
6 |
6 |
6 |
12*6 |
6006 |
28 |
4 |
4 |
2 |
2 |
2 |
12*7 |
10296 |
48 |
6 |
6 |
3 |
3 |
2 |
12*8 |
6435 |
45 |
6 |
6 |
3 |
3 |
2 |
12*9 |
2860 |
40 |
6 |
6 |
3 |
3 |
2 |
12*10 |
858 |
33 |
6 |
6 |
3 |
3 |
2 |
12*11 |
156 |
24 |
5 |
4 |
3 |
3 |
2 |
12*12 |
13 |
13 |
2 |
2 |
2 |
2 |
2 |
13*7 |
1716 |
1 |
1 |
1 |
1 |
1 |
1 |
13*8 |
1287 |
1 |
1 |
1 |
1 |
1 |
1 |
13*9 |
715 |
1 |
1 |
1 |
1 |
1 |
1 |
13*10 |
286 |
1 |
1 |
1 |
1 |
1 |
1 |
13*11 |
78 |
1 |
1 |
1 |
1 |
1 |
1 |
13*12 |
13 |
1 |
1 |
1 |
1 |
1 |
1 |
13*13 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Total |
797162 |
159094 |
127842 |
116477 |
75073 |
66728 |
66141 |
Légende :
La première colonne indique la main, X-Y, avec X= total des cartes Nord-Sud, Y=nombre de cartes de Sud
A = Total des mains avec Sud >= Nord; Dans chaque nouvelle colonne on ôte les mains correspondant aux réductions ci-dessous.
B = Permutations (AV72-D84 = AD82-V74)
C = Cartes au-delà des cartes utiles (ADX987-V432 = ADX765-V432)
D = Cartes sous séquence de la main courte (RX87-DV = RX32-DV)
E = Cartes sous la plus faible carte utile (RDV9-864 = RDV9-432)
F = Cartes inférieures à la sentinelle adverse (AV7-D6 = AV2-D6)
G = Mains jumelles (AD42-R53 = ARD5-432)