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].




Le maniement de couleur

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.




La meilleure défense

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
Vxx      ARDx
Dxxxx      A9
x      ARV
ARxx      Dxxx
   xxx
   VX8x
   Dxxx
   xx

Est joue 6 SA. L'entame du Valet de Coeur est suivie de D, R et A. Après avoir réalisé ses quatre piques et ses quatre trèfles, Est se retrouve en main dans la position suivante:
   
   ....
   ....
       
xxxx       9
-       ARV
       
   X       [X8]
   Dxx    [Dx]
   

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 calcul automatique des maniements de couleur

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....




Le dénombrement des mains


Le jeu complet

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.


La couleur simple

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 maniements concrets

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)