BridgeBalma

  • Augmenter la taille
  • Taille par défaut
  • Diminuer la taille

Une curiosité : maniements et équilibre de Nash

Voici un article mathématico-bridgesque en l'honneur de John Forbes Nash, mathématicien et économiste américain, décédé en mai 2015. Il a eu de gros problèmes de santé, ce qui ne l'a pas empêché de contribuer de façon significative à la théorie des jeux, notamment ses applications en économie. Il avait reçu quelques jours avant le prix Abel, considéré comme l'équivalent du prix Nobel pour les mathématiques.

L'exemple habituel des "équilibres de Nash" est un jeu de cour de récréation avant l'invention des smartphones : "pierre-feuille-ciseaux" où chaque joueur propose en même temps que son adversaire un des trois objets. La pierre est plus forte que les ciseaux (elle les émousse), les ciseaux sont plus forts que la feuille (ils la coupent), mais à son tour la feuille est plus forte que la pierre (elle l'enveloppe). Et bien sûr, coup pour rien si les deux ont choisi le même objet.

On sait que pour ne pas perdre il faut jouer au hasard, et choisir pierre, feuille ou ciseaux à une chance sur 3, et sans tenir compte des choix précédents de son adversaire ou de soi-même. C'est ce qu'on appelle une "stratégie mixte", où la solution est probabiliste. Si l'on s'écarte de cette stratégie (par exemple en choisissant un peu trop souvent la pierre), l'adversaire va s'en apercevoir et augmenter ses chances de gain (en choisissant un peu plus souvent la feuille). Idem si un joueur a un comportement un peu trop cyclique (c'est-à-dire qu'il choisit trop souvent autre chose que le coup précédent et l'avant-dernier) : son comportement devient un peu prévisible.

A pierre-feuille-ciseaux, on gagne ou on perd ou c'est match nul, mais il serait facile de changer la règle du jeu : par exemple convenir que le duel pierre-ciseaux gagne 2 points (parce que c'est très embêtant d'émousser les ciseaux), les deux autres duels gagnant 1 point. Ceci fait apparaître la notion de matrice des gains ou des enjeux. Que devient la solution ? Intuitivement on aurait envie de surpondérer la pierre (pour risquer de gagner 2 et perdre 1), mais l'adversaire qui n'est pas idiot va surpondérer la feuille... En fait l'équilibre pour les deux joueurs est une stratégie mixte à 50% de feuille, 25% de pierre et autant de ciseaux. Ceci se calcule à partir de la matrice des gains. Pas si évident a priori...

 

Pourquoi parler de cela sur un site consacré aux mathématiques du bridge et surtout aux maniements de couleur ?

Parce qu'il existe de rares cas de maniements de couleur où il n'existe pas de meilleure solution...

Cela ne concerne que le tournoi par paires, où il faut adopter la stratégie -ici le maniement- qui fait plus de levées que la stratégie des autres paires dans la diagonale, en moyenne sur les répartitions adverses ; attention, on ne fait pas la moyenne des levées réalisées sur les différents cas de répartition, mais la moyenne de 100% si on fait mieux, 0% si on fait autant, -100% si on fait moins de levées.

Eh bien, il existe des cas où cette stratégie n'existe pas ! Dans le principe c'est un peu étrange de se dire qu'il n'y a pas de meilleure ligne de jeu. En fait il y en a une mais elle est une combinaison de plusieurs.

Précisons aussi que c'est pour le fun, parce que ces situations sont rares, et impossibles à traiter à la table.

Comme c'est un peu complexe, nous allons voir tout cela en développant un exemple.

 


Les différents maniements

Comment jouez-vous cela ?

J'imagine, assez automatiquement : le Roi en coup de sonde, puis petit pour l'impasse à la D, en oubliant le 10 (T dans la suite pour éviter X et le risque de confusion avec une petite carte x).

Effectivement, c'est la stratégie A, la meilleure pour faire 4 levées, à 29% (quand vous avez en Nord DTxxxx, DTx, DT, Dxxxx, Dxxx, Dxx, Txxxx), le plus souvent 3, parfois 2 à environ 21% (Txxx, xx, x ou -).
C'est aussi cette stratégie dite "max", celle qui donne le plus de levées en moyenne : 3,07.

En général la stratégie max est celle qu'il faut retenir en TPP, mais justement pas ici...

 

On peut utiliser la stratégie B : intéressante si vous jouez en par 4 et que vous devez chercher 3 levées, et donc éviter de n'en faire que 2, B est la meilleure à 85% (contre 79% pour la stratégie A). Comment faire ?

Tirer l'As, puis le Roi, puis petit vers V 9... Vous ne perdez 2 levées que contre DVxxx ou DVxx placés en Sud derrière V9, c'est-à-dire x ou xx en Nord, environ 5% et 10%. Si c'est le rare DVxxxx vous vous apercevez que Nord est chicane, et alors vous jouez soit le V soit 8 ou 9, en impasse forçante pour faire tomber un des honneurs adverses. Vous ferez 2,96 levées en moyenne. La sécurité a souvent un prix à payer : moins de 11% de chances de faire 4 levées.

Nota : ce n'est pas le cas de ce maniement, mais il existe des situations exceptionnelles, en match par 4, et même pour des jeux de manche, où la stratégie optimale n'est pas celle qui maximise la probabilité de faire son contrat. Ceci car le nombre de levées de mieux et de chute est pris en compte dans le calcul des IMP. Un maniement de sécurité particulièrement acrobatique (disons plus efficace dans 1 ou 2% des cas pour assurer le contrat) peut être moins bon s'il vous fait chuter d'une levée de plus ou vous empêche de faire du mieux dans 30% des cas. J'ai eu l'occasion de présenter des exemples en commentant certains problèmes de Michel Lebel. Mais en général l'effet est totalement négligeable.


Mais, surprise, le programme SuitPlay liste 3 stratégies exotiques, C, D et E. Leur principal intérêt est qu'elles interviennent dans ce fameux équilibre de Nash.

C : petit en Ouest et double impasse, on passe le 8 si rien ne se montre en Nord. Si le 8 est pris du T, partir du V et faire l'impasse. Résultat : 4 levées à 24% (moins bon que A), 3+ levées à 76% (moins bon que A et que B), 3,00 levées en moyenne.

D : petit en Ouest et impasse à la Dame, si elle rate on part du 8 et on fait l'impasse au T (sûrement exact, mais bizarre, moi avec 7 cartes j'aurais joué la répartition en tirant R et A) ; si elle réussit, là on joue la répartition si le T ne tombe pas, sinon l'impasse au 3è tour). Résultat : 4 levées à 19,5% (encore un peu moins bon), 3+ à 76% comme C, 2,96 en moyenne.

E : celle-là, il faut la trouver, c'est le "Buffalo", on part du V en impasse forçante. E est intéressant si on a de bonnes raisons (compte de mains) de penser que la Dame est en Sud. 3 cas : si Sud couvre de la D, on prend du R et on fait l'impasse au T contre Nord. Si le V tient, on joue le R. Si Nord prend avec la D, on continue du 8 comme dans la stratégie D. Résultat : 4 levées à 21% (entre A et B), 3+ à 81% (entre B et A), 3,02 levées en moyenne, pas mal.

Comparaison en Tournoi Par Paires

Le programme SuitPlay calcule, dans une logique de TPP, le nombre de fois où la stratégie X est meilleure que la stratégie Y, et peu importe si c'est d'une ou deux levées. Ceci pour toutes les répartitions possibles en NS, et pour tous les X et Y dans ABCDE. Voici la "matrice des gains", copie d'écran SuitPlay.

On constate que le maniement B (meilleur en par 4 pour 3 levées) est battu par tous les autres. Et de façon non négligeable : 17% par A, 4 à 7% par CDE. C'est-à-dire que si vous l'adoptez en TPP, vous allez en moyenne perdre 17% sur cette donne, même si vous avez besoin de 3 levées pour réussir la manche. Car aux autres tables, ils vont chuter un peu plus souvent, mais ils feront encore un peu plus souvent une de mieux.

B étant éliminé, car toujours perdante, c'est là que la comparaison va être très étrange...

On constate que A est meilleur que D (11%), D meilleur que E (11% aussi), E bien meilleur que C (20%). A est aussi meilleur que E (3%). Les chiffres sont arrondis.

On aurait donc envie de choisir A... Sauf que C est meilleur que A (10%). Et C est meilleur que D (22%).

Il est donc impossible, en TPP, de classer ces stratégies. La solution est un équilibre mixte, consistant à choisir au hasard l'un des maniements avec des probabilités judicieusement calculées, voir en annexe.

Que faire alors ?

On peut se dire que le calcul est infaisable à la table, que l'immense majorité des bridgeurs joue très bien sans connaître même le principe des équilibres de Nash.

Le "champ" va probablement adopter le maniement standard (A), ou éventuellement (B) pour les maniaques de la sécurité.

Dans ce cas, il faudrait adopter la stratégie la plus efficace contre (A) qui est la stratégie (C) : vous allez en moyenne gagner 10% sur cette donne : faites donc la double impasse !
Mais ne le répétez pas trop, car si presque tout le monde joue (C) alors les plus malins vont jouer le Buffalo (E) et leur prendre 20% en moyenne.
Mais au bout d'un moment, quand tout le monde jouera (E), il faudra choisir (D) qui lui prend 11%. Etc.

Vous voyez pourquoi John Nash a été traité pour schizophrénie ?

Jouez donc le champ (A), ou pourquoi pas la double impasse (C) qui à la longue vous classera mieux que les adeptes du maniement standard.

Comparaison détaillée des stratégies A et C

Pour bien montrer comment cela fonctionne :

Il y a 20 répartitions possibles en Nord, chacune avec une probabilité, par exemple Dxx à 10,66% ou DT à 1,61% (rappel T signifie le 10). Pour chacune des 20, on regarde si A est meilleur que C et si oui, on cumule la probabilité dans le score PA, inversement si C est meilleur on cumule dans PC ; si le nombre de levées est le même, on ne compte pas.

Le calcul donne A meilleur que C dans 5 cas, avec en Nord : Dxx (+2), Dxxx (+2), Dx, Txxxx, Dxxxx, pour un total PA = 26% (soit 10,66+6,46+6,46+1,21+1,21). Le (+2) signifie qu'il y a deux levées d'écart, sinon une seule.

Et C est meilleur que A dans 6 cas, avec en Nord : DTxx, xx, Txxx, DTxxx, x, ou chicane, pour un total PC = 36% (soit 9,69+9,69+6,46+4,84+4,84+0,75).

Pour mémoire, il y a 100-36-26=38% de cas où les deux stratégies font jeu égal, les 9 cas non comptabilisés dans PA ou PC.

On voit bien qu'en moyenne sur les répartitions Nord-Sud, C sera devant A un peu plus souvent, car PC-PA=10%.

10% ce n'est pas négligeable... Par exemple avec 9 cartes quand il manque la D, on sait qu'il faut jouer la répartition plutôt que l'impasse. Et pourtant l'écart est inférieur à 2%...

C'est le fait que quand A est meilleur que C, c'est plutôt de deux levées (dans 17% des cas parmi les 26%) qui explique ce paradoxe : C est plus souvent meilleur que A, mais A est meilleur que C en moyenne de levées...
Donc l'écart moyen en levées est en faveur de A : 2*0,17 + 0,09 - 0,36 = 0,07. On retrouve bien l'écart entre 3,07 et 3,00 indiqué plus haut. CQFD.

Si le sujet vous plaît, allez jeter un coup d'oeil sur le paradoxe de Condorcet, énoncé en 1785, bien avant Nash, avec ses conséquences étonnantes sur certaines élections.

retour...

 

Annexe 1 : Solution théorique du maniement

Supposons un tournoi TPP très étrange, joué par une armée de robots, qui jouent indéfiniment la même donne ou presque, les mains EW restent les mêmes, celles de NS redistribuées à chaque donne. On considère aussi que les levées dans les 3 autres couleurs ne sont pas impactées, le résultat de la donne sera donc celui du maniement : 2, 3 ou 4 levées. Si tous les robots EW sont programmés pour jouer le maniement "A" sauf une paire qui joue "C", celle-ci sera mieux classée de 10%. Et pourtant elle aura fait en moyenne un peu moins de levées.

Mais si tous les robots connaissent le principe des équilibres de Nash, ils vont jouer dans ce cas une "stratégie mixte" de type pierre-feuille-ciseaux.

Avec ici 4 choix, l'un doit être systématiquement éliminé (un équilibre avec nombre pair de choix ne fonctionne pas, on tombe sur une matrice 4*4 non inversible). L'un des 4 choix est en effet dominé par une combinaison mixte des 3 autres, ici c'est la stratégie D que l'on peut oublier (D gagne contre E de 10,74, mais perd contre A de 11,3 et surtout C de 21,58. Beaucoup de combinaisons raisonnables de ACE battent D). En conservant ACE, il est possible de trouver les probabilités à adopter pour l'équilibre mixte.

On s'est ainsi ramené à un problème de type pierre-feuille-ciseaux, la probabilité de chaque choix ACE est par exemple p(A) = valeur absolue du gain C contre E, divisée par la somme des 3 valeurs absolues des gains.

Les robots doivent jouer ce maniement en choisissant au hasard l'un des maniements :

  • A avec une probabilité d'environ 0,61
  • C avec une probabilité d'environ 0,08
  • E avec une probabilité d'environ 0,31

En gros, 2/3 de maniement standard A, et 1/3 du rusé Buffalo.

On peut vérifier que ce "champ" à stratégie mixte va faire en moyenne jeu nul contre n'importe quelle paire qui adopterait systématiquement une stratégie fixe A, C ou E, ou par linéarité jeu nul contre n'importe quelle stratégie mixte à base de ACE, y compris cette stratégie optimale. Ce n'est pas un résultat très brillant... Mais c'est l'équilibre. Et il gagne contre D (de 5,3%) ou n'importe quelle stratégie contenant un peu de D.

Si les robots savent qu'une partie de la population adopte une stratégie mixte à base d'autres probabilités que celles indiquées, et a fortiori une stratégie fixe, il leur est possible de modifier les probabilités de choix A, C, E (voire D), et alors de gagner en moyenne.

Annexe 2 : Variante, avec le 8 en face du 9, par exemple A V 8 2 / R 9 3

Ce sont toujours les 5 mêmes maniements ABCDE. Toujours 29% de faire 4 levées avec A (R puis impasse à la D), et 85% de faire au moins 3 avec B (A puis R puis petit vers V8). C et D sont également inchangées.

Mais le Buffalo (partir du V) est alors beaucoup moins performant, seulement 2,93 levées en moyenne, 11% d'en faire 4, il est même battu par B. E ne gagne que contre exactement Dxx ou Dxxxx en Sud, et pas Dx car que Sud couvre ou pas, le programme joue ensuite la répartition 3-3 et perd contre le T quatrième. Et si c'est Dxxx, Sud ne couvre pas, le programme fait V A R, et concède la D. Il faudrait qu'il y ait R97 dans la main courte pour se ramener au cas où le Buffalo est intéressant. Tout ça c'est de la faute du 7 !

Aucune des 5 stratégies ne domine toutes les autres. Faut-il s'attendre à un équilibre mixte avec 5 probabilités, qui est théoriquement possible avec 5 ? Eh bien non, car on obtiendrait alors des probabilités négatives pour deux des stratégies, ce qui n'a pas de sens.

En fait, B et D sont toujours dominées par une stratégie mixte. La stratégie optimale est encore une combinaison de ACE avec respectivement 0,43, 0,19 et 0,38. Cette stratégie mixte domine B (8%) et D (4%).

Il est curieux de constater que E, qui est la plus mauvaise des 5 stratégie en termes de nombre moyen de levées, fait partie de la stratégie mixte avec un coefficient non négligeable, 0,38.

retour...