Comment écrire un programme qui joue au Bridge ?

Question posée dans le courrier de Sabrina :
" Comment résoudre ce problème : sachant que j'ai les 2 jeux de NS dans une couleur, analyser par programmation quel est le meilleur maniement. J'ai de bonnes idées sur la programmation de la recherche de toutes les répartitions adverses possibles, mais pas l'ombre d'une idée pour faire jouer le programme, sachant qu'il y a des maniements stupides, par exemple :
J'ai AD au mort, je joue petit de Sud, Ouest intercale le Roi et le mort met la Dame... Bref je me pose des questions basiques ! "

Réponse :

Soit la situation suivante (ici, à 2 cartes seulement dans chaque main, mais généralisable) :

     P| A D
     C| ---
     K| ---
     T| ---

P| R        P| 8
C| A        C| 7
K| ---      K| ---
T| ---      T| ---

     P| 5
     C| 6
     K| ---
     T| ---

Sans-Atout
Sud doit jouer la 1ère carte.

1^ère approche :
Recherche systématique de la meilleure carte à jouer à chaque levée, en construisant un arbre de décision qui explore systématiquement tous les coups possibles (Algorithme du minimax).

				RACINE
Sud		5P				6C
Ouest		RP				AC
Nord	AP		DP		AP		DP
Est	8P		8P		7C		7C

Nord	DP		AC		RP		RP	Ouest
Est	7C		AP		DP		AP	Nord
Sud	6C		7C		8P		8P	Est
Ouest	AC		6C		5P		5P	Sud
	Branche 1		Branche 2		Branche 3		Branche 4
	2 levées		0 levée		0 levée		1 levée

La solution est 2 levées au mieux pour NS.

Elle est obtenue à partir d'un arbre de 12 noeuds (les lignes 2 à 5 du tableau ci-dessus), et correspond à la branche 1 de l’arbre.( Les 16 autres noeuds des lignes 7 à 10 décrivent une situation certaine, puisqu’il s’agit alors de la dernière levée, où chaque main ne détient plus qu’une carte.)

La bourde de Nord évoquée dans la question (fournir la Dame sur le Roi d’Ouest) correspond à la branche 2.

La branche 3 décrit une autre jolie bourde possible pour Nord: sur le 6 de Cœur de son partenaire, défausser l’As de Pique !

Enfin la branche 4 correspond à une simple maladresse: jouer d’abord Cœur, ce qui est sanctionné par la perte d’une levée.

L’algorithme de construction et d’évaluation de l’arbre choisit bien sûr la branche 1, la seule qui décrive une ligne de jeu procurant le maximum de levées.

2ème approche :
En fait, Sabrina n’adopte pas cette solution de recherche systématique de la meilleure carte à jouer, qui exploite la " force brutale " de l’ordinateur.

Sabrina appartient à la famille des systèmes experts. On lui a inculqué le savoir-faire d’un joueur de Bridge, sous forme de règles dites de connaissance.

Pour jouer une carte, Sabrina consulte ces règles, et applique la première qui soit pertinente.

Exemple précédent : Sud doit jouer la 1^ère carte.

Sabrina parcourt les règles suivantes :

' (J1-1) SI dernière levée :
        ALORS jouer sa carte unique ; FIN

' (J1-2) SI on ne détient plus qu'une seule couleur,
        ALORS pas de choix de couleur possible.
            ' (J1-2-1) SI L'As sec dans l'autre main
                     ALORS jouer petit
            ' (J1-2-2) SI L'As en main et Roi second en face
                     ALORS jouer petit
            ' (J1-2-3) SINON: jouer gros

' (J1-3) SI tous les atouts sont purgés
'            ET SI on détient assez de cartes maîtresses pour gagner le contrat,
              ALORS :
              '(J1–3-1): SI aucune carte maîtresse dans l'autre main
                        ALORS jouer ses cartes maîtresses
              '(J1–3-2): SI l’autre main recèle des cartes maîtresses
                        ' (J1–3-2-1.a):
                        SI on est sec dans une de ces couleurs C1
                           SI on peut remonter par une autre couleur C2
                              ALORS jouer petit dans cette couleur C2
                        ' (J1–3-2-1.b):
                        SINON
                            SI on est plus court dans C1
                                ALORS jouer gros dans cette couleur C1
                            SINON jouer petit dans cette couleur C1

' (J1-4) SINON
              Rechercher et/ou Appliquer stratégie adéquate

Voyons comment Sabrina va appliquer ces règles avec les cartes de l’exemple :

P| A D
C| ---

P| 5
C| 6 Règle (J1-1) : non vérifiée. (plus d’une carte)
Règle (J1-2) : non vérifiée. (plus d’une couleur)
Règle (J1-3) : vérifiée, car à SA, atouts purgés par définition
                    et nombre de levées à gagner indéterminé
          Règle(J1–3-1): non vérifiée(car AP maître en Nord)
          Règle(J1–3-2): vérifiée (car AP maître en Nord)
              Règle (J1–3-2-1.a): non vérifiée (on n’est pas sec à Pique)
              Règle (J1–3-2-1.b): vérifiée (on a du Pique)
                  Comme on n’est pas plus court (1 carte dans chaque main)
                      on joue petit (donc le 5 de Pique).

L’algorithme heuristique ci-dessus conduit au même résultat que l’exploration systématique de l’arbre de décision.

Ouest prend ce 5 de Pique avec son Roi. C’est maintenant à Sabrina de jouer une carte en troisième position.

Sabrina parcourt alors les règles suivantes :

' (J3-1) ANALYSE DE LA SITUATION
'        (1) Notre partenaire, jouant en N°1, est maître,
'             et le restera définitivement, car N°2 a fourni petit ou défaussé
'             et N°4 ne peut pas prendre et ne coupera pas
'        (2) Notre partenaire, jouant en N°1, est maître,
'             mais le N°4 a la possibilité de gagner la levée; avec une carte maîtresse.
'        (3) Notre partenaire, jouant en N°1, est maître,
'             mais le N°4 a la possibilité de gagner la levée en coupant.
'        (4) L'adversaire a monté en N°2.
'        (5) L'adversaire a coupé en N°2.

' (J3-2) SI dernière levée
'             ALORS jouer son unique carte

' (J3-3) SI on possède une seule carte dans la couleur
'             ALORS la fournir

' (J3-4) SI le partenaire a battu atout, et est définitivement maître
'           ET SI on n'est pas sec
'              ALORS fournir petit

' (J3-5) SI le partenaire a battu atout,
'           ET SI l'adversaire en 2 a monté,
'              ET SI on n'est pas sec
'                  ALORS prendre si possible

' (J3-6) SI Situation d'impasse au Roi (AD en main, Roi chez l’adversaire)
'              ALORS
'               (J3-6-1) SI le Roi est apparu
'                   ALORS prendre de l’As
'              (J3-6-2) SINON passer la Dame

' (J3-7) SI Situation d'impasse à la Dame
'              ALORS…

' (J3-8) SI Situation de coup à blanc
'              ALORS…

' (J3-9) SI on est sec
'              ALORS
'              (J3-9-1) SI couleur demandée = atout
'                              ALORS défausser
'              (J3-9-2) SINON
'                              SI on n’a plus d’atout
'                                  ALORS défausser
'                              SINON
'                  Choisir entre coupe et défausse

' (J3-10) SINON
'              Appliquer stratégie choisie

Voyons de nouveau comment Sabrina va appliquer ces règles avec les cartes de l’exemple :

P| A D
C| ---

Sur le tapis : 5P et RP

P| -
C| 6
Règle (J3-1) : Analyse de la situation : L'adversaire a monté en N°2.
Règle (J3-2) : non vérifiée. (plus d’une carte)
Règle (J3-3) : non vérifiée. (plus d’une carte de la couleur demandée)
Règle (J3-4) : non vérifiée. (Sans-Atout)
Règle (J3-5) : non vérifiée. (Sans-Atout)
Règle (J3-6) : vérifiée. (AD en main, Roi chez l’adversaire)
Règle (J3-6-1) : vérifiée (le Roi est apparu)
                 Donc, prendre de l’As de Pique. FIN

Avantages de chaque approche

1^ère approche : arbres de décisions explorés systématiquement

Algorithmes théorisés et prouvés.
Assurance théorique de parvenir à la meilleure solution
Code informatique plutôt compact et élégant

2ème approche : base de connaissances sous forme de règles heuristiques

Stratégies reproduisant celles des experts
Excellente visibilité de ce que fait le programme
Possibilité d’applications pédagogiques

Inconvénients de chaque approche

1^ère approche : arbres de décisions explorés systématiquement

Algorithmes complexes et temps de calcul importants
Grande opacité de ce que fait le programme
Intelligence totalement étrangère à celle du Bridgeur humain

2ème approche : base de connaissances sous forme de règles heuristiques

Difficultés pour traduire en code les règles des experts
Code informatique volumineux et peu élégant
Difficultés pour éliminer toutes les erreurs de logique
Qualité de jeu limitée à la qualité de la base de connaissances

Page d'accueil

Qu'est-ce que Sabrina?

Comment Sabrina apprend

Sabrina en duplicate contre Wbridge5