Variante d'un autre jeu de hasard

[Olivier Miakinen]

Bonjour,

Jacques Mathon m'a proposé une variante intéressante au jeu de hasard
que je rappelle ici.

***

Il y a n cartes faces cachées avec les valeurs de 1 à n. Deux joueurs
tirent chacun une carte au hasard, et le but du jeu est d'avoir la
hauteur la plus forte. On fera plusieurs parties, en alternant celui
qui sera nommé « joueur 1 » et celui qui sera donc le « joueur 2 ».

Après avoir regardé sa carte, celui qui est le joueur 1 pour ce tour
décide s'il veut proposer ou non un échange. S'il décide de ne pas
proposer l'échange, on dévoile les cartes, et celui qui a la plus
forte gagne 1 point.

Si le joueur 1 décide de proposer l'échange, le joueur 2 qui a aussi
regardé sa carte décide s'il veut l'accepter ou non. Si le joueur 2
refuse l'échange, on dévoile les cartes, celui qui a la plus forte
gagne 2 points. Mais si le joueur 2 accepte l'échange, on dévoile les
cartes qui sont alors échangées. Celui qui a maintenant la carte la
plus forte (après l'échange) gagne 4 points.

Au bout d'un certain nombre de fois deux parties fixé à l'avance,
celui qui a le plus de points a gagné.

***

Résumé des points :
+1 au gagnant si le joueur 1 ne propose pas l'échange ;
+2 au gagnant si le joueur 1 propose mais le joueur 2 refuse l'échange ;
+4 au gagnant si le joueur 1 propose et le joueur 2 accepte l'échange.

***

La question est : est-ce que cela change la stratégie, par rapport
au jeu précédent où l'on gagnait +1 dans tous les cas, et où la
stratégie optimale consistait à ne jamais rien échanger (ce qui
revient donc à un jeu de pile ou face) ?

[Olivier Miakinen]

Post by Olivier Miakinen
[...]
+1 au gagnant si le joueur 1 ne propose pas l'échange ;
+2 au gagnant si le joueur 1 propose mais le joueur 2 refuse l'échange ;
+4 au gagnant si le joueur 1 propose et le joueur 2 accepte l'échange.

Commençons simple, avec un petit nombre de cartes. Avec 2 cartes
ça n'est pas intéressant car chacun sait immédiatement en voyant
sa carte si celle de l'adversaire est plus forte ou plus faible.
Alors voyons ce que ça donne avec 3 cartes, de valeurs 1, 2 et 3.

Vu qu'il n'est pas forcément pertinent de toujours jouer de la même
façon en fonction de la carte que l'on a tirée, on va attribuer des
probabilités de choix en fonction de chaque situation. Par exemple,
si je suis le joueur 1 et que ma carte est le 1, je vais tirer un
nombre aléatoire de sorte de proposer l'échange avec une probabilité
p1, et de le refuser avec une probabilité 1-p1. Idem avec p2 si ma
carte est un 2, p3 si ma carte est un 3. Pour le joueur 2, on aura
q1 la probabilité d'accepter l'échange s'il a un 1, q2 si c'est un 2
et q3 si c'est un 3. Ensuite on adaptera les probabilités au mieux
pour arriver à la stratégie optimale pour les deux joueurs.

Première remarque : si le joueur 1 a proposé un échange, le joueur 2
devra évidemment l'accepter s'il a un 1 et le refuser s'il a un 3.
On a donc immédiatement q1=1 et q3=0. Reste à calculer p1, p2, p3
et q2.

Pour les calculs, je vais me placer du côté du joueur 1, et compter
donc +1, +2 ou +4 s'il gagne, mais -1, -2 ou -4 si c'est le joueur 2
qui gagne. Calculons donc l'espérance de gain du joueur 1.

Je vais prendre comme exemple de calcul le cas où le joueur 1 a tiré
le 1. Il lance alors son générateur aléatoire pour décider s'il va
proposer l'échange. Avec une probabilité (1-p1), il ne propose pas
l'échange, donc il perd avec son 1, ce qui lui fait -1 point. Mais
avec une probabilité p1 il propose l'échange, et là il y a une
chance sur deux pour que le joueur 2 ait chacune des deux autres
cartes (le 2 ou le 3). Si le joueur 2 a le 2, il refuse l'échange
avec une probabilité (1-q2), ce qui fait -2 points pour le joueur 1,
mais il l'accepte avec une probabilité q2 de faire +4 points. Enfin,
si le joueur 2 a le 3, il refuse l'échange avec une probabilité 1
de faire -2 points.

Résumons. Si le joueur 1 a tiré la carte 1, son espérance de gain vaut :
(1-p1)×(-1) + p1×(1/2)×(1-q2)×(-2) + p1×(1/2)×q2×(+4) + p1×(1/2)×1×(-2)

Tous calculs faits, voici les espérances pour le joueur 1 selon qu'il
a tiré le 1, le 2 ou le 3.
- s'il a le 1 : E(1) = -1 + p1(3⋅q2 - 1)
- s'il a le 2 : E(2) = -3⋅p2
- s'il a le 3 : E(3) = 1 - p3(3⋅q2 + 2)

On voit que quel que soit q2, le joueur 1 maximise son espérance E(2)
avec p2=0 et son espérance E(3) avec p3=0. Ça veut dire que s'il tire
un 2 ou un 3 le joueur 1 a toujours intérêt à ne pas proposer l'échange.
En revanche, ce n'est pas encore clair pour E(1) : tout dépend si q2
est plus grand ou plus petit que 1/3. Pour ça, voyons maintenant le
point de vue du joueur 2.

Le joueur 2 sait que le joueur 1 ne proposera jamais l'échange s'il a
un 2 ou un 3 car ça lui serait toujours défavorable. Par conséquent,
si le joueur 1 lui propose un échange, c'est forcément qu'il a un 1,
ce qui veut dire que le joueur 2 n'aura jamais intérêt à échanger
quand on le lui propose. Donc q2=0.

En reportant q2=0 dans E(1), il vient E(1) = -1 - p1, donc p1=0 pour
optimiser la stratégie du joueur 1.

En conclusion : dans ce cas ça n'a rien changé du tout, la stratégie
pour les deux joueurs reste toujours de ne jamais faire aucun échange.

Question : est-ce que ce sera toujours le cas quel que soit le nombre
de cartes ? Pour le moment je n'en sais rien.

Cordialement,

[Benoît]

Post by Olivier Miakinen

Post by Olivier Miakinen
+1 au gagnant si le joueur 1 ne propose pas l'échange ;
+2 au gagnant si le joueur 1 propose mais le joueur 2 refuse l'échange ;
+4 au gagnant si le joueur 1 propose et le joueur 2 accepte l'échange.

Question : est-ce que ce sera toujours le cas quel que soit le nombre
de cartes ? Pour le moment je n'en sais rien.

Moi non plus et je reste sur le banc de touche. Le principe, évoqué
précédemment, de ne jamais proposé l'échange sauf quand on a un 1 me
laisse pantois.

[Olivier Miakinen]

Post by Benoît

Post by Olivier Miakinen

Post by Olivier Miakinen
+1 au gagnant si le joueur 1 ne propose pas l'échange ;
+2 au gagnant si le joueur 1 propose mais le joueur 2 refuse l'échange ;
+4 au gagnant si le joueur 1 propose et le joueur 2 accepte l'échange.

Question : est-ce que ce sera toujours le cas quel que soit le nombre
de cartes ? Pour le moment je n'en sais rien.

Moi non plus et je reste sur le banc de touche. Le principe, évoqué
précédemment, de ne jamais proposé l'échange sauf quand on a un 1 me
laisse pantois.

Avec la variante proposée par Jacques, c'est même pire que ça : il
ne faut jamais proposer l'échange *même* si on a un 1. En revanche
il ne faut jamais *accepter* l'échange sauf si on a un 1.

[Benoît]

Post by Olivier Miakinen

Post by Benoît

Post by Olivier Miakinen

Post by Olivier Miakinen
+1 au gagnant si le joueur 1 ne propose pas l'échange ;
+2 au gagnant si le joueur 1 propose mais le joueur 2 refuse l'échange ;
+4 au gagnant si le joueur 1 propose et le joueur 2 accepte l'échange.

Question : est-ce que ce sera toujours le cas quel que soit le nombre
de cartes ? Pour le moment je n'en sais rien.

Moi non plus et je reste sur le banc de touche. Le principe, évoqué
précédemment, de ne jamais proposé l'échange sauf quand on a un 1 me
laisse pantois.

Avec la variante proposée par Jacques, c'est même pire que ça : il
ne faut jamais proposer l'échange *même* si on a un 1. En revanche
il ne faut jamais *accepter* l'échange sauf si on a un 1.

Oui, mais ! Cette politique de jeu n'est réalisable que si les deux
l'appliquent et les chances de gain sont 50%. Dans ta version
originelle, si je choisis ma tactique (proposition d'échange si ≤ 5)
j'ai, en moyenne, 80% de chances de gagner.

Ta nouvelle règle et début de réflexion :

- Si j'ai plus que 5 et que je ne propose rien cela veut dire qu'un
tirage sur deux je perds 1€ => -O,5 €
- Si j'ai moins de 5 et le joueur 2 refuse (il a plus que 5) je gagne
en moyenne => +0,8 €
- Si j'ai 5 ou moins et le joueur accepte l'échange (il a 5 ou moins)
cela veut dire qu'en moyenne je ne gagne rien.

Le solde est donc +0,3€ en moyenne par partie. Peut-on faire mieux ?

[Olivier Miakinen]

Post by Benoît

Post by Olivier Miakinen
Avec la variante proposée par Jacques, c'est même pire que ça : il
ne faut jamais proposer l'échange *même* si on a un 1. En revanche
il ne faut jamais *accepter* l'échange sauf si on a un 1.

Oui, mais ! Cette politique de jeu n'est réalisable que si les deux
l'appliquent et les chances de gain sont 50%. Dans ta version
originelle, si je choisis ma tactique (proposition d'échange si ≤ 5)
j'ai, en moyenne, 80% de chances de gagner.

C'est impossible. Dans ma version originelle, si le joueur 2 joue au
mieux, tu ne peux pas faire mieux que 50 % de chances de gagner.
Alors 80 % !

En effet, il suffirait que le joueur 2 refuse systématiquement quelle
que soit ta stratégie pour que tes chances de gagner soient *exactement*
égales à 50 %. Mais s'il t'arrive de proposer l'échange quand tu as
une carte entre 2 et 5, et s'il arrive que le joueur 2 ait en même
temps la carte 1, alors dans ce cas uniquement il accepte l'échange,
ce qui fait chuter tes chances globales de gagner *strictement* en
dessous de 50 %.

Post by Benoît
- Si j'ai plus que 5 et que je ne propose rien cela veut dire qu'un
tirage sur deux je perds 1€ => -O,5 €
- Si j'ai moins de 5 et le joueur 2 refuse (il a plus que 5) je gagne
en moyenne => +0,8 €
- Si j'ai 5 ou moins et le joueur accepte l'échange (il a 5 ou moins)
cela veut dire qu'en moyenne je ne gagne rien.
Le solde est donc +0,3€ en moyenne par partie. Peut-on faire mieux ?

Là encore, il m'étonnerait que la meilleure stratégie du joueur 2
consiste à accepter l'échange à chaque fois qu'il a 5 ou moins.
Mais contrairement à ma version originale où j'en ai la preuve,
dans cette variente cela reste encore à vérifier.

[Benoît]

Post by Olivier Miakinen

Post by Benoît

Post by Olivier Miakinen
Avec la variante proposée par Jacques, c'est même pire que ça : il
ne faut jamais proposer l'échange *même* si on a un 1. En revanche
il ne faut jamais *accepter* l'échange sauf si on a un 1.

Oui, mais ! Cette politique de jeu n'est réalisable que si les deux
l'appliquent et les chances de gain sont 50%. Dans ta version
originelle, si je choisis ma tactique (proposition d'échange si ≤ 5)
j'ai, en moyenne, 80% de chances de gagner.

C'est impossible. Dans ma version originelle, si le joueur 2 joue au
mieux, tu ne peux pas faire mieux que 50 % de chances de gagner.
Alors 80 % !

Oui, les 80% sont dans un cas de figure : refus d'échange.

Post by Olivier Miakinen
En effet, il suffirait que le joueur 2 refuse systématiquement quelle
que soit ta stratégie pour que tes chances de gagner soient *exactement*
égales à 50 %. Mais s'il t'arrive de proposer l'échange quand tu as
une carte entre 2 et 5, et s'il arrive que le joueur 2 ait en même
temps la carte 1, alors dans ce cas uniquement il accepte l'échange,
ce qui fait chuter tes chances globales de gagner *strictement* en
dessous de 50 %.

Post by Benoît
- Si j'ai plus que 5 et que je ne propose rien cela veut dire qu'un
tirage sur deux je perds 1€ => -O,5 €
- Si j'ai moins de 5 et le joueur 2 refuse (il a plus que 5) je gagne
en moyenne => +0,8 €
- Si j'ai 5 ou moins et le joueur accepte l'échange (il a 5 ou moins)
cela veut dire qu'en moyenne je ne gagne rien.
Le solde est donc +0,3€ en moyenne par partie. Peut-on faire mieux ?

Là encore, il m'étonnerait que la meilleure stratégie du joueur 2
consiste à accepter l'échange à chaque fois qu'il a 5 ou moins.
Mais contrairement à ma version originale où j'en ai la preuve,
dans cette variente cela reste encore à vérifier.

Après on peut chercher des tactiques de défense quand on a un joueur
qui utilise ce principe.

Je me demande si on n'a pas intérêt à toujours proposer l'échange. :)
Ce qui nous ramène à du 50/50.

[Olivier Miakinen]

Post by Benoît

Post by Olivier Miakinen

Post by Benoît
Oui, mais ! Cette politique de jeu n'est réalisable que si les deux
l'appliquent et les chances de gain sont 50%. Dans ta version
originelle, si je choisis ma tactique (proposition d'échange si ≤ 5)
j'ai, en moyenne, 80% de chances de gagner.

C'est impossible. Dans ma version originelle, si le joueur 2 joue au
mieux, tu ne peux pas faire mieux que 50 % de chances de gagner.
Alors 80 % !

Oui, les 80% sont dans un cas de figure : refus d'échange.

Tu dis « oui » mais tu contredis ce que je disais (et qui est facile
à vérifier) : en cas de refus systématique, c'est 50 %.

Et s'il arrive au joueur 1 de proposer quand il a autre chose que le 1,
alors c'est moins de 50 % pour lui. Il n'y a aucun moyen d'arriver à
80 % pour le joueur 1 si le joueur 2 joue correctement. C'est ce que
j'expliquais ici :

===

Post by Benoît

Post by Olivier Miakinen
En effet, il suffirait que le joueur 2 refuse systématiquement quelle
que soit ta stratégie pour que tes chances de gagner soient *exactement*
égales à 50 %. Mais s'il t'arrive de proposer l'échange quand tu as
une carte entre 2 et 5, et s'il arrive que le joueur 2 ait en même
temps la carte 1, alors dans ce cas uniquement il accepte l'échange,
ce qui fait chuter tes chances globales de gagner *strictement* en
dessous de 50 %.

===

Post by Benoît
[...]
Je me demande si on n'a pas intérêt à toujours proposer l'échange. :)
Ce qui nous ramène à du 50/50.

Non. Si le joueur 1 propose toujours l'échange, le joueur 2 a plusieurs
stratégies gagnantes pour lui, la plus simple encore une fois étant de
n'accepter d'échanger que s'il a le 1.

[Jacques Mathon]

Post by Olivier Miakinen

Post by Benoît

Post by Olivier Miakinen

Post by Olivier Miakinen
+1 au gagnant si le joueur 1 ne propose pas l'échange ;
+2 au gagnant si le joueur 1 propose mais le joueur 2 refuse l'échange ;
+4 au gagnant si le joueur 1 propose et le joueur 2 accepte l'échange.

Question : est-ce que ce sera toujours le cas quel que soit le nombre
de cartes ? Pour le moment je n'en sais rien.

Moi non plus et je reste sur le banc de touche. Le principe, évoqué
précédemment, de ne jamais proposé l'échange sauf quand on a un 1 me
laisse pantois.

Avec la variante proposée par Jacques, c'est même pire que ça : il
ne faut jamais proposer l'échange *même* si on a un 1. En revanche
il ne faut jamais *accepter* l'échange sauf si on a un 1.

Si tu joues comme ça, je veux bien jouer avec toi. ;-)

Amicalement

[Jacques Mathon]

Post by Jacques Mathon

Post by Olivier Miakinen

Post by Benoît

Post by Olivier Miakinen

Post by Olivier Miakinen
+1 au gagnant si le joueur 1 ne propose pas l'échange ;
+2 au gagnant si le joueur 1 propose mais le joueur 2 refuse l'échange ;
+4 au gagnant si le joueur 1 propose et le joueur 2 accepte l'échange.

Question : est-ce que ce sera toujours le cas quel que soit le nombre
de cartes ? Pour le moment je n'en sais rien.

Moi non plus et je reste sur le banc de touche. Le principe, évoqué
précédemment, de ne jamais proposé l'échange sauf quand on a un 1 me
laisse pantois.

Avec la variante proposée par Jacques, c'est même pire que ça : il
ne faut jamais proposer l'échange *même* si on a un 1. En revanche
il ne faut jamais *accepter* l'échange sauf si on a un 1.

Si tu joues comme ça, je veux bien jouer avec toi. ;-)

En fonction de la valeur de n choisie.

Amicalement

[Olivier Miakinen]

Post by Jacques Mathon

Post by Jacques Mathon

Post by Olivier Miakinen
Avec la variante proposée par Jacques, c'est même pire que ça : il
ne faut jamais proposer l'échange *même* si on a un 1. En revanche
il ne faut jamais *accepter* l'échange sauf si on a un 1.

Si tu joues comme ça, je veux bien jouer avec toi. ;-)

En fonction de la valeur de n choisie.

Nous étions dans le cas n=3. Ça change ton point de vue ?

[Jacques Mathon]

Post by Olivier Miakinen

Post by Jacques Mathon

Post by Jacques Mathon

Post by Olivier Miakinen
Avec la variante proposée par Jacques, c'est même pire que ça : il
ne faut jamais proposer l'échange *même* si on a un 1. En revanche
il ne faut jamais *accepter* l'échange sauf si on a un 1.

Si tu joues comme ça, je veux bien jouer avec toi. ;-)

En fonction de la valeur de n choisie.

Nous étions dans le cas n=3. Ça change ton point de vue ?

Oui, je ne joue pas avec n aussi petit.

L'idée est de montrer que la valeur de n a une incidence sur la stratégie.

Amicalement

[Olivier Miakinen]

Post by Jacques Mathon

Post by Olivier Miakinen
Nous étions dans le cas n=3. Ça change ton point de vue ?

Oui, je ne joue pas avec n aussi petit.

Ok.

Post by Jacques Mathon
L'idée est de montrer que la valeur de n a une incidence sur la stratégie.

Oui, je l'ai montré dans mon autre article (sauf erreurs de calcul
toujours possibles). Tu étais arrivé à la même conclusion ?

[Jacques Mathon]

Post by Olivier Miakinen

Post by Jacques Mathon

Post by Olivier Miakinen
Nous étions dans le cas n=3. Ça change ton point de vue ?

Oui, je ne joue pas avec n aussi petit.

Ok.

Post by Jacques Mathon
L'idée est de montrer que la valeur de n a une incidence sur la stratégie.

Oui, je l'ai montré dans mon autre article (sauf erreurs de calcul
toujours possibles). Tu étais arrivé à la même conclusion ?

Pour l'instant oui mais je n'ai pas regardé ton raisonnement en détail.
J'ai seulement été surpris du fait que tu utilises une fonction
aléatoire qui ne me paraît pas nécessaire (je vais y regarder de plus près).

Je confirme toutefois que je ne joue pas (différemment de toi) avec n
qui vaut 3.

La question deviendrait donc: à partir de quelle valeur de n est-il
possible de contrer la stratégie d'Olivier ?

Amicalement

[Olivier Miakinen]

Post by Olivier Miakinen
+1 au gagnant si le joueur 1 ne propose pas l'échange ;
+2 au gagnant si le joueur 1 propose mais le joueur 2 refuse l'échange ;
+4 au gagnant si le joueur 1 propose et le joueur 2 accepte l'échange.

J'ai l'impression que cette répartition des facteurs multiplicateurs
(doublé en cas de refus, quadruplé en cas d'acceptation) risque de
ne pas changer grand chose, et qu'il vaudrait mieux faire l'inverse
pour inciter le joueur 1 à bluffer, ainsi qu'on le verra plus loin
pour n=4.

=========
Notations
=========

Soit n le nombre de cartes. J'appellerai généralement m (1 ≤ m ≤ n) la
carte tirée par le joueur 1 et j (1 ≤ j ≤ n, j ≠ n) celle tirée par le
joueur 2.

En gardant toujours une récompense de 1 au gagnant lorsque aucun échange
n'a été proposé, j'appelle Kr la récompense si l'échange a été proposé
mais refusé, et Ka si l'échange a été proposé et accepté.

Je note (p1, p2, ... pn) la stratégie du joueur 1 et (q1, q2, ... qn)
celle du joueur 2. Les pm et les qj sont des probabilités, donc des
nombres entre 0 et 1. Si le joueur 1 a la carte m, il proposera un
échange avec la probabilité pm, la probabilité qu'il ne le propose
pas étant donc 1-pm. Si un échange est proposé, le joueur 2 l'acceptera
avec la probabilité qj et le refusera avec la probabilité 1-qj. Bien
entendu, chacune de ces probabilités *peut* valoir exactement 0 ou
exactement 1 ; par exemple le joueur 2 acceptera systématiquement s'il
a le 1 (q1=1) et il refusera systématiquement s'il a le n (qn=0).

Soit E(m) l'espérance de gain du premier joueur s'il a tiré la carte m.
Cette espérance se calcule de la façon suivante. On regarde chacun des
deux choix qu'il a (avec une probabilité pm de proposer l'échange et
une probabilité 1-pm de ne pas le faire). Puis on regarde chacune des
n-1 possibilités pour la valeur j de la carte du second joueur (avec
à chaque fois une probabilité de 1/(n-1)). Si le joueur 1 avait proposé
l'échange, il faut dans chaque cas pour j examiner le cas d'acceptation
de l'échange (probabilité qj) ou de refus (probabilité 1-qj), alors que
si le joueur 1 n'avait pas proposé l'échange il suffit de regarder si
j<m ou si j>m.

Vu que dans tous les cas il y a une multiplication par 1/(n-1), pour
simplifier les calculs je vais calculer S(m) = (n-1)E(m) plutôt que
juste E(m).

=============
Avertissement
=============

Attention, dans ce qui suit je ne me sens jamais à l'abri d'une erreur
de calcul même si j'essaye de toujours tout vérifier plusieurs fois.
Alors ceux qui auront le courage de vérifier, merci de me dire si c'est
correct ou si je me suis trompé !

==============================
Calcul de l'espérance de gains
==============================

Voici la formule que je trouve pour S(m) en fonction de n, de Kr et Ka,
de pm et de tous les qj :

S(m) = (1+pm⋅(Kr-1))⋅U(m) - pm⋅(Kr+Ka)⋅V(m)

où U(m) est le nombre de cartes plus petites que m moins le nombre de
cartes plus grandes que m, et V(m) est la somme des qj pour j plus
petit que m moins la somme des qj pour j plus grand que m.

U(m) = somme( 1, 1≤j<m ) - somme( 1, m<j≤n ) = 2⋅m - (n+1)
V(m) = somme( qj, 1≤j<m ) - somme( qj, m<j≤n )

=================================================
Et maintenant on en fait quoi, de cette formule ?
=================================================

Sachant que l'espérance de gain globale du joueur 1 est 1/n fois la
somme des E(m) pour 1≤m≤n, c'est-à-dire 1/(n(n-1)) fois la somme des
S(m), il faut ajuster les pm et les qj de telle sorte que cette
espérance ne puisse que diminuer si on change les pm, et qu'elle ne
puisse qu'augmenter si on change les qj.

Ça me semble assez difficile à faire dans le cas général. Du coup,
j'ai voulu voir ce que ça donnait dans le cas n=4, en prenant comme
hypothèse que le joueur 2 refuse toujours l'échange sauf quand il
a le 1, auquel cas il l'accepte. C'est-à-dire q1=1 et q2=q3=q4=0.

Sachant cela, le joueur 1 peut calculer des valeurs optimales pour
p1 à p4. Si, connaissant ces valeurs de p1 à p4, le joueur 2 trouve
que ses propres valeurs optimales de q1 à q4 sont inchangées, je
crois que cela voudra dire que notre hypothèse était la bonne et
qu'on ne peut pas faire mieux (je n'ai plus mon bouquin de théorie
des jeux pour le vérifier). Si au contraire cela amène à réviser
les valeurs de q1 à q4, alors il est sûr que notre hypothèse n'était
pas la bonne, mais je ne saurai pas forcément comment progresser.

Voici ce que je trouve :
S(1) = -3 - 3⋅p1⋅(Kr-1)
S(2) = -1 - p2⋅(2⋅Kr+Ka-1)
S(3) = +1 - p3⋅(Ka+1)
S(4) = +3 + p4⋅(2⋅Kr-Ka-3)

Sachant que Kr≥1 et Ka≥1, les trois premières lignes montrent que le
joueur 1 a intérêt à ne jamais proposer l'échange s'il a un 2 ou un 3,
et à ne jamais le proposer non plus s'il a un 1 et que Kr>1. En ce qui
concerne S(4) et p4, cela dépend des valeurs de Kr et Ka. Dans le cas
où Kr=2 et Ka=4 comme le proposait Jacques, c'est la même chose : le
joueur 1 ne doit pas proposer l'échange. Mais si au contraire on a
Kr=4 et Ka=2, c'est là que le bluff sera payant s'il réussit !

Bon, vérifions quand même si notre hypothèse était correcte.

Dans le cas où on arrive à la conclusion que p1=p2=p3=p4=0, oui, notre
hypothèse était correcte puisque rien ne peut inciter le joueur 2 à
changer ses qj (de toute manière on ne lui proposera jamais d'échange).

Mais dans le cas où Kr=4 et Ka=2, l'hypothèse sur les qj fait que le
joueur 1 ne proposerait l'échange que s'il a un 4. Or, sachant cela,
le joueur 2 serait amené à toujours accepter l'échange puisqu'il
serait assuré de gagner un 4 en échange de sa carte plus faible ! Et
donc notre hypothèse est fausse, et il va falloir chercher plus loin.

===================================
En guise de conclusion (temporaire)
===================================

Il semble donc que le jeu puisse vraiment devenir intéressant à partir
de n=4 avec Kr=4 et Ka=2. Sauf erreurs de calcul de ma part toujours
possibles, bien sûr.

Je vais continuer à y réfléchir, avec donc la formule suivante :

S(m) = (1+3⋅pm)⋅U(m) - 6⋅pm⋅V(m) = U(m) + 3⋅pm⋅(U(m) - 2⋅V(m))
où
U(m) = somme( 1, 1≤j<m ) - somme( 1, m<j≤n ) = 2⋅m - (n+1)
V(m) = somme( qj, 1≤j<m ) - somme( qj, m<j≤n )


Cordialement,

[Jacques Mathon]

Post by Olivier Miakinen

Post by Olivier Miakinen
+1 au gagnant si le joueur 1 ne propose pas l'échange ;
+2 au gagnant si le joueur 1 propose mais le joueur 2 refuse l'échange ;
+4 au gagnant si le joueur 1 propose et le joueur 2 accepte l'échange.

J'ai l'impression que cette répartition des facteurs multiplicateurs
(doublé en cas de refus, quadruplé en cas d'acceptation) risque de
ne pas changer grand chose, et qu'il vaudrait mieux faire l'inverse
pour inciter le joueur 1 à bluffer, ainsi qu'on le verra plus loin
pour n=4.
...

Comme tu produit des raisonnements à une vitesse largement supérieure à
celle à laquelle je peux les... lire et encore plus les... comprendre...

Pour que nous soyons d'accord sur le défi (que j'ai) lancé et pour
vérifier que j'ai bien compris... ce que j'ai proposé ;-)

Avec la règle ci-dessus, il y a deux joueurs qui joue un nombre
significatif de parties et les deux joueurs ne changent pas de stratégie
jusqu'à la fin de toutes les parties.
Le joueur O (comme Olivier) joue la stratégie suivante (à corriger si
nécessaire):
- Quand c'est son tour de jouer, il ne propose jamais d'échange
- Quand ce n'est pas son tour de jouer et que le joueur J (comme
Jacques) propose un échange, il ne l'accepte que si il a un 1.

Je propose une stratégie gagnante (en terme d'espérance mathématique)
pour le joueur J pour une valeur minimum de n (que je ne donne pas pour
l'instant).

Je précise et c'est, de mon point de vue, ce qui fait tout l'intérêt
général du problème qu'il existe (au moins) une stratégie pour le joueur
O qui lui permet d'inverser le résultat à son tour (si le joueur J
applique toujours la même stratégie pour toutes les partie du jeu).

Amicalement

[Olivier Miakinen]

Post by Jacques Mathon

Post by Olivier Miakinen

Post by Olivier Miakinen
+1 au gagnant si le joueur 1 ne propose pas l'échange ;
+2 au gagnant si le joueur 1 propose mais le joueur 2 refuse l'échange ;
+4 au gagnant si le joueur 1 propose et le joueur 2 accepte l'échange.

J'ai l'impression que cette répartition des facteurs multiplicateurs
(doublé en cas de refus, quadruplé en cas d'acceptation) risque de
ne pas changer grand chose, et qu'il vaudrait mieux faire l'inverse
pour inciter le joueur 1 à bluffer, ainsi qu'on le verra plus loin
pour n=4.
...

Comme tu produit des raisonnements à une vitesse largement supérieure à
celle à laquelle je peux les... lire et encore plus les... comprendre...

Désolé. ;-)

Post by Jacques Mathon
Pour que nous soyons d'accord sur le défi (que j'ai) lancé et pour
vérifier que j'ai bien compris... ce que j'ai proposé ;-)
Avec la règle ci-dessus, il y a deux joueurs qui joue un nombre
significatif de parties et les deux joueurs ne changent pas de stratégie
jusqu'à la fin de toutes les parties.

Oui.

Post by Jacques Mathon
Le joueur O (comme Olivier) joue la stratégie suivante (à corriger si
- Quand c'est son tour de jouer, il ne propose jamais d'échange

Euh... non. Je me suis convaincu que c'était la meilleure stratégie
pour n=3, et aussi pour n=4 avec les choix que tu proposais de gains
(×2 en cas de refus d'échange, ×4 en cas d'acceptation d'échange),
mais je n'en sais rien dans le cas général. Et par exemple c'est
déjà faux pour n=4 dans un autre choix de gains (×4 en cas de refus
et ×2 en cas d'acceptation).

Post by Jacques Mathon
- Quand ce n'est pas son tour de jouer et que le joueur J (comme
Jacques) propose un échange, il ne l'accepte que si il a un 1.

Idem.

Post by Jacques Mathon
Je propose une stratégie gagnante (en terme d'espérance mathématique)
pour le joueur J pour une valeur minimum de n (que je ne donne pas pour
l'instant).

D'accord. Vu que tu ne peux rien faire en tant que 2e joueur si le
premier ne propose jamais d'échange, je suppose que ta stratégie est
pour le 1er joueur en supposant que le 2e n'accepte que s'il a un 1.

Pour le moment je cherche une stratégie un peu plus générale, mais
si je n'arrive à rien je reviendrai sur ce cas.

Post by Jacques Mathon
Je précise et c'est, de mon point de vue, ce qui fait tout l'intérêt
général du problème qu'il existe (au moins) une stratégie pour le joueur
O qui lui permet d'inverser le résultat à son tour (si le joueur J
applique toujours la même stratégie pour toutes les partie du jeu).

Oui, bien sûr. Quand on aura trouvé la stratégie optimale pour les deux,
il suffit que tous les deux la connaissent et l'appliquent pour revenir
à du 50 / 50 sur l'ensemble des parties.

[Jacques Mathon]

Post by Olivier Miakinen

Post by Jacques Mathon

Post by Olivier Miakinen

Post by Olivier Miakinen
+1 au gagnant si le joueur 1 ne propose pas l'échange ;
+2 au gagnant si le joueur 1 propose mais le joueur 2 refuse l'échange ;
+4 au gagnant si le joueur 1 propose et le joueur 2 accepte l'échange.

J'ai l'impression que cette répartition des facteurs multiplicateurs
(doublé en cas de refus, quadruplé en cas d'acceptation) risque de
ne pas changer grand chose, et qu'il vaudrait mieux faire l'inverse
pour inciter le joueur 1 à bluffer, ainsi qu'on le verra plus loin
pour n=4.
...

Comme tu produit des raisonnements à une vitesse largement supérieure à
celle à laquelle je peux les... lire et encore plus les... comprendre...

Désolé. ;-)

:-)

Post by Olivier Miakinen

Post by Jacques Mathon
Pour que nous soyons d'accord sur le défi (que j'ai) lancé et pour
vérifier que j'ai bien compris... ce que j'ai proposé ;-)
Avec la règle ci-dessus, il y a deux joueurs qui joue un nombre
significatif de parties et les deux joueurs ne changent pas de stratégie
jusqu'à la fin de toutes les parties.

Oui.

Post by Jacques Mathon
Le joueur O (comme Olivier) joue la stratégie suivante (à corriger si
- Quand c'est son tour de jouer, il ne propose jamais d'échange

Euh... non. Je me suis convaincu que c'était la meilleure stratégie
pour n=3, et aussi pour n=4 avec les choix que tu proposais de gains
(×2 en cas de refus d'échange, ×4 en cas d'acceptation d'échange),
mais je n'en sais rien dans le cas général. Et par exemple c'est
déjà faux pour n=4 dans un autre choix de gains (×4 en cas de refus
et ×2 en cas d'acceptation).

OK !
Mon idée était surtout de tenter de montrer que la(les) stratégie(s)
n'étaient pas nécessairement indépendantes de la valeur de n.

Post by Olivier Miakinen

Post by Jacques Mathon
- Quand ce n'est pas son tour de jouer et que le joueur J (comme
Jacques) propose un échange, il ne l'accepte que si il a un 1.

Idem.

OK!
Je pense donc que tu trouveras (facilement) la(une) stratégie gagnante
face à la stratégie en question.

Post by Olivier Miakinen

Post by Jacques Mathon
Je propose une stratégie gagnante (en terme d'espérance mathématique)
pour le joueur J pour une valeur minimum de n (que je ne donne pas pour
l'instant).

D'accord. Vu que tu ne peux rien faire en tant que 2e joueur si le
premier ne propose jamais d'échange, je suppose que ta stratégie est
pour le 1er joueur en supposant que le 2e n'accepte que s'il a un 1.

Oui.

Post by Olivier Miakinen
Pour le moment je cherche une stratégie un peu plus générale, mais
si je n'arrive à rien je reviendrai sur ce cas.

Il me semble que la recherche d'une telle stratégie générale pourra
s'inspirer du fait que celle-ci pourrait dépendre de la valeur de n.

Post by Olivier Miakinen

Post by Jacques Mathon
Je précise et c'est, de mon point de vue, ce qui fait tout l'intérêt
général du problème qu'il existe (au moins) une stratégie pour le joueur
O qui lui permet d'inverser le résultat à son tour (si le joueur J
applique toujours la même stratégie pour toutes les partie du jeu).

Oui, bien sûr. Quand on aura trouvé la stratégie optimale pour les deux,
il suffit que tous les deux la connaissent et l'appliquent pour revenir
à du 50 / 50 sur l'ensemble des parties.

Si une telle stratégie existe, elle a alors exactement la même
efficacité que celle qui consiste à accepter le tirage (pas de
proposition d'échange). C'est un peu comme chercher la meilleure
stratégie à pierre, feuille, ciseaux voire à sa variante asymétrique
pierre, feuille, ciseaux, puits.

Une stratégie est une approche dans laquelle on tente de diminuer la
part de l'aléatoire. La connaissance de cette stratégie par l'autre
joueur peut conduire à une nouvelle stratégie etc... Y-a-t-il
systématiquement convergence vers une stratégie unique ?
La question me paraît ouverte.

Amicalement

[Olivier Miakinen]

Bonjour,

Pour le moment je ne réponds qu'à la fin.

[...] C'est un peu comme chercher la meilleure
stratégie à pierre, feuille, ciseaux voire à sa variante asymétrique
pierre, feuille, ciseaux, puits.

La meilleure stratégie à pierre, feuille, ciseaux existe, et elle
consiste à choisir aléatoirement chacune des options avec une
probabilité de 1/3 pour chaque. Attention, il faut que ce soit un
choix *vraiment* aléatoire, et pas du genre de pseudo-hasard qu'un
humain pourrait vouloir simuler. Contre un pseudo-hasard généré au
doigt mouillé par un humain, un programme d'intelligence artificielle
pourrait toujours déceler des régularités et en tirer profit pour
gagner plus souvent.

La variante avec le puits, je ne la connais pas, mais je suis sûr
qu'il existera aussi une stratégie faisant intervenir un choix
aléatoire.

Une stratégie est une approche dans laquelle on tente de diminuer la
part de l'aléatoire.

Euh... dans le cas de jeux tels que pierre, feuille, ciseaux, diminuer
la part de l'aléatoire est justement une mauvaise idée... enfin... tout
dépend d'où tu veux retirer de l'aléatoire. Par exemple, si tu veux
choisir aléatoirement quel poids tu donnes à chacun des choix (au lieu
de choisir exactement 1/3, là je suis d'accord que *cette* part de
l'aléatoire doit être supprimée.

La connaissance de cette stratégie par l'autre
joueur peut conduire à une nouvelle stratégie etc... Y-a-t-il
systématiquement convergence vers une stratégie unique ?
La question me paraît ouverte.

Non, je crois que dans ce genre de jeux à somme nulle la question
a été fermée par la théorie des jeux. Il faut que je retrouve des
références.

Le premier jeu de ce type que j'avais vu se présente de la façon
suivante, entre quelqu'un qui tire des boulets de canon et l'autre
qui doit éviter de se faire tuer. Il y a 4 collines : A, B, C et D.
Chaque nuit, le joueur cible choisit derrière quelle colline il va
se cacher. Et chaque jour le tireur envoie son boulet entre deux
collines : entre A et B, ou entre B et C, ou entre C et D. La cible
meurt si le boulet est tiré à côté de la colline où il s'est caché.

[Olivier Miakinen]

Post by Olivier Miakinen
Non, je crois que dans ce genre de jeux à somme nulle la question
a été fermée par la théorie des jeux. Il faut que je retrouve des
références.

En fait peu importe que le jeu soit ou non à somme nulle, mais il faut
que ce soit un jeu fini. Mots-clés : « stratégie mixte » et « équilibre
de Nash ».

[Jacques Mathon]

Post by Olivier Miakinen

Post by Olivier Miakinen
Non, je crois que dans ce genre de jeux à somme nulle la question
a été fermée par la théorie des jeux. Il faut que je retrouve des
références.

En fait peu importe que le jeu soit ou non à somme nulle, mais il faut
que ce soit un jeu fini. Mots-clés : « stratégie mixte » et « équilibre
de Nash ».

Je viens de faire une recherche rapide et j'ai trouvé un fichier pdf qui
en parle...

http://ogossner.free.fr/Theodec/Chapitre5.pdf

Je ne l'ai pas lu en détail mais il prend comme exemple ce qui est
appelé le jeu des penalties dont la règle qui est présentée commence
par: « Un joueur, décide de tirer soit à droite, soit à gauche du
gardien. Le gardien peut plonger soit à droite, soit à gauche... »

Et, pour l'anecdote, pour le penalty que j'ai vu tiré hier au soir, si
le gardien a bien suivi la règle, ce ne fut pas le cas pour le tireur.
Il a fait une... "panenka" et a "donc" marqué. Sans risques ?

Amicalement

[Jacques Mathon]

Post by Olivier Miakinen
Bonjour,
Pour le moment je ne réponds qu'à la fin.

[...] C'est un peu comme chercher la meilleure
stratégie à pierre, feuille, ciseaux voire à sa variante asymétrique
pierre, feuille, ciseaux, puits.

La meilleure stratégie à pierre, feuille, ciseaux existe, et elle
consiste à choisir aléatoirement chacune des options avec une
probabilité de 1/3 pour chaque. Attention, il faut que ce soit un
choix *vraiment* aléatoire, et pas du genre de pseudo-hasard qu'un
humain pourrait vouloir simuler. Contre un pseudo-hasard généré au
doigt mouillé par un humain, un programme d'intelligence artificielle
pourrait toujours déceler des régularités et en tirer profit pour
gagner plus souvent.

Nous sommes (à priori) d'accord.
Remarquons cependant que dans le jeu proposé il s'agit de faire jouer
deux humains l'un avec (contre) l'autre et que leur raisonnement est...
humain.

Post by Olivier Miakinen
La variante avec le puits, je ne la connais pas, mais je suis sûr
qu'il existera aussi une stratégie faisant intervenir un choix
aléatoire.

Si tel est bien le cas (ce que je crois), la meta-stratégie consiste à
ne pas avoir de stratégie (à proprement parler).

Post by Olivier Miakinen

Une stratégie est une approche dans laquelle on tente de diminuer la
part de l'aléatoire.

Euh... dans le cas de jeux tels que pierre, feuille, ciseaux, diminuer
la part de l'aléatoire est justement une mauvaise idée... enfin... tout
dépend d'où tu veux retirer de l'aléatoire. Par exemple, si tu veux
choisir aléatoirement quel poids tu donnes à chacun des choix (au lieu
de choisir exactement 1/3, là je suis d'accord que *cette* part de
l'aléatoire doit être supprimée.

Ce qui revient à ne pas avoir de stratégie ou du moins si on ne veut pas
prendre le risque de jouer sur les mots, d'avoir une "stratégie" qui ne
permet de gagner que si l'autre joueur en utilise une "mauvaise".

Post by Olivier Miakinen

La connaissance de cette stratégie par l'autre
joueur peut conduire à une nouvelle stratégie etc... Y-a-t-il
systématiquement convergence vers une stratégie unique ?
La question me paraît ouverte.

Non, je crois que dans ce genre de jeux à somme nulle la question
a été fermée par la théorie des jeux. Il faut que je retrouve des
références.

Je regarderai à l'occasion.
Cela signifierait que le poker ou dans un autre genre les échecs ou le
go sont des jeux pour lesquels il existe une meilleure stratégie mais
que celle-ci n'étant pas accessible aux humains, ceux-ci ne peuvent
s'affronter les uns les autres qu'en utilisant des "stratégies
heuristiques".

Amicalement

[Olivier Miakinen]

Post by Jacques Mathon

Post by Olivier Miakinen
La meilleure stratégie à pierre, feuille, ciseaux existe, et elle
consiste à choisir aléatoirement chacune des options avec une
probabilité de 1/3 pour chaque. Attention, il faut que ce soit un
choix *vraiment* aléatoire, et pas du genre de pseudo-hasard qu'un
humain pourrait vouloir simuler. Contre un pseudo-hasard généré au
doigt mouillé par un humain, un programme d'intelligence artificielle
pourrait toujours déceler des régularités et en tirer profit pour
gagner plus souvent.

Nous sommes (à priori) d'accord.
Remarquons cependant que dans le jeu proposé il s'agit de faire jouer
deux humains l'un avec (contre) l'autre et que leur raisonnement est...
humain.

C'est vrai, mais rien n'interdit à un humain de s'aider d'un générateur
de nombre aléatoire comme le lancer d'un dé, voire pseudo-aléatoire
comme de regarder la trotteuse de sa montre. Dans ce cas il ne pourra
pas être battu sur le long terme, fût-ce devant un autre humain super
intelligent ou un programme informatique.

Post by Jacques Mathon

Post by Olivier Miakinen
La variante avec le puits, je ne la connais pas, mais je suis sûr
qu'il existera aussi une stratégie faisant intervenir un choix
aléatoire.

Si tel est bien le cas (ce que je crois), la meta-stratégie consiste à
ne pas avoir de stratégie (à proprement parler).

Je ne suis pas d'accord avec ça. Il s'agit d'une stratégie dite mixte,
qui mélange avec des probabilités bien précise des stratégies pures.
Par exemple, si la stratégie optimale consiste à jouer A une fois sur
trois et B deux fois sur trois, alors jouer A une fois sur quatre et
B trois fois sur quatre est une moins bonne stratégie.

Post by Jacques Mathon

Post by Olivier Miakinen

Post by Jacques Mathon
Une stratégie est une approche dans laquelle on tente de diminuer la
part de l'aléatoire.

Euh... dans le cas de jeux tels que pierre, feuille, ciseaux, diminuer
la part de l'aléatoire est justement une mauvaise idée... enfin... tout
dépend d'où tu veux retirer de l'aléatoire. Par exemple, si tu veux
choisir aléatoirement quel poids tu donnes à chacun des choix (au lieu
de choisir exactement 1/3, là je suis d'accord que *cette* part de
l'aléatoire doit être supprimée.

Ce qui revient à ne pas avoir de stratégie ou du moins si on ne veut pas
prendre le risque de jouer sur les mots, d'avoir une "stratégie" qui ne
permet de gagner que si l'autre joueur en utilise une "mauvaise".

Mais une stratégie (sans guillemets) qui permet au moins de s'assurer
de ne pas perdre, c'est-à-dire de faire match nul.

Post by Jacques Mathon

Post by Olivier Miakinen

Post by Jacques Mathon
La connaissance de cette stratégie par l'autre
joueur peut conduire à une nouvelle stratégie etc... Y-a-t-il
systématiquement convergence vers une stratégie unique ?
La question me paraît ouverte.

Non, je crois que dans ce genre de jeux à somme nulle la question
a été fermée par la théorie des jeux. Il faut que je retrouve des
références.

Je regarderai à l'occasion.

D'après ce que j'ai compris, si le jeu est fini (nombre fini de joueurs,
nombre fini de coups possibles), alors il existe au moins un équilibre
de Nash. Si en outre le jeu est à somme nulle, cet équilibre est unique.

Post by Jacques Mathon
Cela signifierait que le poker ou dans un autre genre les échecs ou le
go sont des jeux pour lesquels il existe une meilleure stratégie mais
que celle-ci n'étant pas accessible aux humains, ceux-ci ne peuvent
s'affronter les uns les autres qu'en utilisant des "stratégies
heuristiques".

En ce qui concerne les échecs et le go, même si les ordinateurs battent
maintenant les meilleurs humains, ces deux jeux ne sont pas encore
complètement résolus : on ne connaît pas *la* stratégie, même si on
sait qu'elle existe et que c'est une stratégie pure.

En revanche pour le poker, du moins dans sa version « Heads up Limit
Hold'em », le jeu est complètement résolu :
https://sciencetonnante.wordpress.com/2015/01/19/une-strategie-infaillible-au-poker/

[Jacques Mathon]

Post by Olivier Miakinen

Post by Jacques Mathon

Post by Olivier Miakinen
La meilleure stratégie à pierre, feuille, ciseaux existe, et elle
consiste à choisir aléatoirement chacune des options avec une
probabilité de 1/3 pour chaque. Attention, il faut que ce soit un
choix *vraiment* aléatoire, et pas du genre de pseudo-hasard qu'un
humain pourrait vouloir simuler. Contre un pseudo-hasard généré au
doigt mouillé par un humain, un programme d'intelligence artificielle
pourrait toujours déceler des régularités et en tirer profit pour
gagner plus souvent.

Nous sommes (à priori) d'accord.
Remarquons cependant que dans le jeu proposé il s'agit de faire jouer
deux humains l'un avec (contre) l'autre et que leur raisonnement est...
humain.

C'est vrai, mais rien n'interdit à un humain de s'aider d'un générateur
de nombre aléatoire comme le lancer d'un dé, voire pseudo-aléatoire
comme de regarder la trotteuse de sa montre. Dans ce cas il ne pourra
pas être battu sur le long terme, fût-ce devant un autre humain super
intelligent ou un programme informatique.

Aucune objection de ma part sur ce point.

Post by Olivier Miakinen

Post by Jacques Mathon

Post by Olivier Miakinen
La variante avec le puits, je ne la connais pas, mais je suis sûr
qu'il existera aussi une stratégie faisant intervenir un choix
aléatoire.

Si tel est bien le cas (ce que je crois), la meta-stratégie consiste à
ne pas avoir de stratégie (à proprement parler).

Je ne suis pas d'accord avec ça. Il s'agit d'une stratégie dite mixte,
qui mélange avec des probabilités bien précise des stratégies pures.
Par exemple, si la stratégie optimale consiste à jouer A une fois sur
trois et B deux fois sur trois, alors jouer A une fois sur quatre et
B trois fois sur quatre est une moins bonne stratégie.

Je pense qu'il ne s'agit que d'un désaccord (qui viendrait de moi) sur
la signification du mot stratégie. Je vais tenter d'illustrer ce que je
voulais dire après avoir regardé équilibre de Nash et stratégie mixte et
tâcher de faire le point de la situation actuelle sur la variante.

Si j'ai bien compris, Nash répond à (referme) la question que je posais
comme ouverte dans une précédente contribution: « Une stratégie est une
approche dans laquelle on tente de diminuer la part de l'aléatoire. La
connaissance de cette stratégie par l'autre joueur peut conduire à une
nouvelle stratégie etc... Y-a-t-il systématiquement convergence vers une
stratégie unique ? La question me paraît ouverte.» pour les jeux finis.
Autrement dit, pour un jeu fini donné, quand bien même il existerait une
stratégie mixte, il existe un équilibre de Nash qui permet de trouver la
meilleure stratégie possible. Dans un jeu à somme nulle, si les (deux)
joueurs l'appliquent, aucun ne perd (gagne).

La distinction (discutable) que je faisais sur la signification du mot
stratégie ne concernait que le cas (pierre, feuille, ciseaux par
exemple) pour lesquels le tirage aléatoire ne peut pas être battu. Quand
il n'y a pas d'équilibre de Nash et (donc) pas de stratégie mixte.

Post by Olivier Miakinen

Post by Jacques Mathon

Post by Olivier Miakinen

Post by Jacques Mathon
Une stratégie est une approche dans laquelle on tente de diminuer la
part de l'aléatoire.

Euh... dans le cas de jeux tels que pierre, feuille, ciseaux, diminuer
la part de l'aléatoire est justement une mauvaise idée... enfin... tout
dépend d'où tu veux retirer de l'aléatoire. Par exemple, si tu veux
choisir aléatoirement quel poids tu donnes à chacun des choix (au lieu
de choisir exactement 1/3, là je suis d'accord que *cette* part de
l'aléatoire doit être supprimée.

Ce qui revient à ne pas avoir de stratégie ou du moins si on ne veut pas
prendre le risque de jouer sur les mots, d'avoir une "stratégie" qui ne
permet de gagner que si l'autre joueur en utilise une "mauvaise".

Mais une stratégie (sans guillemets) qui permet au moins de s'assurer
de ne pas perdre, c'est-à-dire de faire match nul.

Oui, je pense que nous sommes donc d'accord... en particulier, s'il ne
s'agit pas de jouer sur les mots ;-)

Post by Olivier Miakinen

Post by Jacques Mathon

Post by Olivier Miakinen

Post by Jacques Mathon
La connaissance de cette stratégie par l'autre
joueur peut conduire à une nouvelle stratégie etc... Y-a-t-il
systématiquement convergence vers une stratégie unique ?
La question me paraît ouverte.

Non, je crois que dans ce genre de jeux à somme nulle la question
a été fermée par la théorie des jeux. Il faut que je retrouve des
références.

Je regarderai à l'occasion.

D'après ce que j'ai compris, si le jeu est fini (nombre fini de joueurs,
nombre fini de coups possibles), alors il existe au moins un équilibre
de Nash. Si en outre le jeu est à somme nulle, cet équilibre est unique.

Il semblerait que j'ai compris la même chose. :-)

Post by Olivier Miakinen

Post by Jacques Mathon
Cela signifierait que le poker ou dans un autre genre les échecs ou le
go sont des jeux pour lesquels il existe une meilleure stratégie mais
que celle-ci n'étant pas accessible aux humains, ceux-ci ne peuvent
s'affronter les uns les autres qu'en utilisant des "stratégies
heuristiques".

En ce qui concerne les échecs et le go, même si les ordinateurs battent
maintenant les meilleurs humains, ces deux jeux ne sont pas encore
complètement résolus : on ne connaît pas *la* stratégie, même si on
sait qu'elle existe et que c'est une stratégie pure.

Oui, ce sont des stratégies pures mais la complexité (au sens de la
calculabilité) du calcul de celles-ci fait que si celle-ci sont
calculables, elle ne le sont pas en temps raisonnable (en pratique).

Remarque (digression): cette question adresse plusieurs classes de
problèmes (pas seulement des jeux) en particulier ceux dits NP complets
voire NP durs bien connus pour d'autres raisons.

Post by Olivier Miakinen
En revanche pour le poker, du moins dans sa version « Heads up Limit
https://sciencetonnante.wordpress.com/2015/01/19/une-strategie-infaillible-au-poker/

Il semblerait... pour une version finie du jeu pas pour le « no limit».
Par ailleurs: « La stratégie est en fait tellement compliquée que pour
la stocker il faut 11 Téra-octets de mémoire ! »

Bon un petit point sur la variante:
- Tu as montré que pour n=3, il n'y a pas de stratégie mixte
- J'ai indiqué qu'il existe une stratégie mixte pour une valeur
supérieure de n
- Tu as montré que cette valeur de n vaut 8
- J'ai indiqué qu'il y avait une parade évidente à la stratégie que je
proposais
- Tu as trouvé la parade en question

Reste(rait) à trouver la stratégie mixte correcte d'une part et/ou si
celle-ci dépend de n

Sommes-nous d'accord ?

Amicalement

[Olivier Miakinen]

[rien que du bon]
Sommes-nous d'accord ?

Oui à tout.

[Olivier Miakinen]

Post by Olivier Miakinen

[rien que du bon]
Sommes-nous d'accord ?

Oui à tout.

Je me permets d'ajouter quelque chose.

JM> Reste(rait) à trouver la stratégie mixte correcte d'une part et/ou si
JM> celle-ci dépend de n

Dans tous les cas simples que l'on a résolus jusqu'à présent, la
stratégie optimale était toujours une stratégie pure. Je conjecture
que ce sera toujours le cas quel que soit n et quelques que soient
les poids des gains que j'ai nommés Kr et Ka. Bien sûr ça reste à
vérifier, mais il semble déjà que la stratégie pour le joueur 2
se ramène toujours à « j'accepte si j'ai telle valeur au maximum,
je refuse sinon ».

[Jacques Mathon]

Le 09/08/2020 à 08:47, Jacques Mathon a écrit :

Je "corrige" l'usage abusif que j'ai fait de l'expression "stratégie mixte".

... > Si j'ai bien compris, Nash répond à (referme) la question que je posais
comme ouverte dans une précédente contribution: « Une stratégie est une
approche dans laquelle on tente de diminuer la part de l'aléatoire. La
connaissance de cette stratégie par l'autre joueur peut conduire à une
nouvelle stratégie etc... Y-a-t-il systématiquement convergence vers une
stratégie unique ? La question me paraît ouverte.» pour les jeux finis.
Autrement dit, pour un jeu fini donné, quand bien même il existerait une
stratégie mixte, il existe un équilibre de Nash qui permet de trouver la
meilleure stratégie possible. Dans un jeu à somme nulle, si les (deux)
joueurs l'appliquent, aucun ne perd (gagne).
La distinction (discutable) que je faisais sur la signification du mot
stratégie ne concernait que le cas (pierre, feuille, ciseaux par
exemple) pour lesquels le tirage aléatoire ne peut pas être battu. Quand
il n'y a pas d'équilibre de Nash et (donc) pas de stratégie mixte.

Dire qu'il n'y a pas d'équilibre de Nash ne signifie pas qu'il n'y a pas
de stratégie mixte. Justement dans l'exemple cité (pierre, feuille,
ciseaux) la stratégie optimale est bien une stratégie mixte (quand bien
même celle-ci est... triviale au sens où les probabilités ne dépendent
pas de la stratégie que pourrait utiliser l'autre joueur).

...
- Tu as montré que pour n=3, il n'y a pas de stratégie mixte
- J'ai indiqué qu'il existe une stratégie mixte pour une valeur
supérieure de n

J'ai montré qu'il existe une meilleure stratégie (mais pure elle aussi)
que celle envisagée initialement.

- Tu as montré que cette valeur de n vaut 8
- J'ai indiqué qu'il y avait une parade évidente à la stratégie que je
proposais
- Tu as trouvé la parade en question
Reste(rait) à trouver la stratégie mixte correcte d'une part et/ou si
celle-ci dépend de n

Resterait à trouver la meilleure stratégie (probablement pure comme
suggéré par Olivier).

Amicalement

[Olivier Miakinen]

Post by Jacques Mathon
[...]

Post by Jacques Mathon
- Quand ce n'est pas son tour de jouer et que le joueur J (comme
Jacques) propose un échange, il ne l'accepte que si il a un 1.

[...]

Je pense donc que tu trouveras (facilement) la(une) stratégie gagnante
face à la stratégie en question.

Je repars du résultat auquel j'étais arrivé :

S(m) = (1+pm⋅(Kr-1))⋅U(m) - pm⋅(Kr+Ka)⋅V(m)

U(m) = somme( 1, 1≤j<m ) - somme( 1, m<j≤n ) = 2⋅m - (n+1)
V(m) = somme( qj, 1≤j<m ) - somme( qj, m<j≤n )

Je reprends aussi tes données de départ, à savoir Kr=2 et Ka=4.

Par ailleurs je fais l'hypothèse de stratégie que tu attribues au
joueur 2, qui est q1=1 et q2=q3=...=qn=0. On en déduit V(1)=0 et
V(2)=V(3)=...=V(n)=1.

Il vient :
S(1) = U(1) + pm⋅U(1)
S(m) = U(m) + pm⋅(U(m)-6) pour m>1

Pour que le joueur 1 ait intérêt à choisir un pm différent de 0 (et en
fait égal à 1), il faut que ce par quoi il est multiplié soit positif.
Ce n'est clairement pas le cas de U(1) = 1-n, donc le joueur 1 ne
proposera pas l'échange s'il a un 1. Il faut donc regarder les cas
où m>1, et c'est U(m)-6 qui doit être positif.

U(m) - 6 > 0 <=> 2⋅m - (n+1) - 6 > 0 <=> 2⋅m > n+7

Or 2⋅m ≤ 2⋅n, d'où 2⋅n > n+7 et donc n > 7.

En conclusion : si le joueur 2 s'en tient à sa stratégie de n'accepter
l'échange que lorsqu'il tire le 1, le joueur 1 peut gagner à partir de
n = 8 en proposant l'échange s'il tire la carte la plus forte (et pour
des n > 8, il peut proposer l'échange avec d'autres cartes m, pourvu
que 2⋅m soit supérieur à n+7).

Conclusion de la conclusion : la stratégie pour le joueur 2 d'accepter
l'échange uniquement s'il tire le 1 n'est plus une stratégie optimale
pour n ≥ 8.

[Jacques Mathon]

Post by Olivier Miakinen

Post by Jacques Mathon
[...]

Post by Jacques Mathon
- Quand ce n'est pas son tour de jouer et que le joueur J (comme
Jacques) propose un échange, il ne l'accepte que si il a un 1.

[...]

Je pense donc que tu trouveras (facilement) la(une) stratégie gagnante
face à la stratégie en question.

S(m) = (1+pm⋅(Kr-1))⋅U(m) - pm⋅(Kr+Ka)⋅V(m)
U(m) = somme( 1, 1≤j<m ) - somme( 1, m<j≤n ) = 2⋅m - (n+1)
V(m) = somme( qj, 1≤j<m ) - somme( qj, m<j≤n )
Je reprends aussi tes données de départ, à savoir Kr=2 et Ka=4.
Par ailleurs je fais l'hypothèse de stratégie que tu attribues au
joueur 2, qui est q1=1 et q2=q3=...=qn=0. On en déduit V(1)=0 et
V(2)=V(3)=...=V(n)=1.
S(1) = U(1) + pm⋅U(1)
S(m) = U(m) + pm⋅(U(m)-6) pour m>1
Pour que le joueur 1 ait intérêt à choisir un pm différent de 0 (et en
fait égal à 1), il faut que ce par quoi il est multiplié soit positif.
Ce n'est clairement pas le cas de U(1) = 1-n, donc le joueur 1 ne
proposera pas l'échange s'il a un 1. Il faut donc regarder les cas
où m>1, et c'est U(m)-6 qui doit être positif.
U(m) - 6 > 0 <=> 2⋅m - (n+1) - 6 > 0 <=> 2⋅m > n+7
Or 2⋅m ≤ 2⋅n, d'où 2⋅n > n+7 et donc n > 7.
En conclusion : si le joueur 2 s'en tient à sa stratégie de n'accepter
l'échange que lorsqu'il tire le 1, le joueur 1 peut gagner à partir de
n = 8 en proposant l'échange s'il tire la carte la plus forte (et pour
des n > 8, il peut proposer l'échange avec d'autres cartes m, pourvu
que 2⋅m soit supérieur à n+7).
Conclusion de la conclusion : la stratégie pour le joueur 2 d'accepter
l'échange uniquement s'il tire le 1 n'est plus une stratégie optimale
pour n ≥ 8.

J'ai lu rapidement...
Il semblerait que tu aies trouvé (par la calcul) la manière dont je
procède (dans le principe). Et que, du coup, tu vas vite trouver la parade.

Amicalement

[Olivier Miakinen]

Post by Jacques Mathon

Post by Olivier Miakinen
En conclusion : si le joueur 2 s'en tient à sa stratégie de n'accepter
l'échange que lorsqu'il tire le 1, le joueur 1 peut gagner à partir de
n = 8 en proposant l'échange s'il tire la carte la plus forte (et pour
des n > 8, il peut proposer l'échange avec d'autres cartes m, pourvu
que 2⋅m soit supérieur à n+7).
Conclusion de la conclusion : la stratégie pour le joueur 2 d'accepter
l'échange uniquement s'il tire le 1 n'est plus une stratégie optimale
pour n ≥ 8.

J'ai lu rapidement...
Il semblerait que tu aies trouvé (par le calcul) la manière dont je
procède (dans le principe). Et que, du coup, tu vas vite trouver la parade.

Eh bien au moins choisir q2=1 au lieu de 0 je suppose. Je ne l'ai pas
encore vérifié, mais je pense que la stratégie optimale du joueur 2
doit être du style « toujours accepter si j'ai au plus telle valeur
(à déterminer) et toujours refuser si j'ai plus ».