Billy the Kid, Lucky Luke et stratégie

[oualos]

Et si on calcule par une probabilité bayésienne on devrait avoir un série qui doit converger fatalement.
Ce raisonnement marcherait-il ?

1° Si Lucky Luke est malin, il se doute que si Billy est malin, il va prendre le chemin auquel il s'attend le moins, c.-à-d. le moins probable
2° Si Billy est malin, il se doute que si Lucky Luke est malin il va penser que Billy va prendre le chemin auquel il s'attend le moins soit le moins probable ==> donc Billy va prendre le chemin le plus probable

etc.
et ainsi de suite. Si on calcule en toute rigueur les emboitements de pensée on devrait en théorie obtenir une série infinie qui doit décroître très vite, peut-être de façon géométrique.
Dans la réalité ça doit s'arrêter quelque part quand même
Et il faut introduire les probabilités de Si Lucky Luke est malin... et si Billy est malin...

etc.
-----

[Liet Kynes]

Y a pas besoin de se faire de noeuds aux cerveau non plus: si avant la séparation du chemin on dispose un portique à deux entrées avec une entrée qui correspond au choix le plus favorable à Billy et une entrée qui tire au sort le chemin pris; on comprends vite que l'issue est à trois possibilités dont deux sont à 60%.

[Deedee81]

Salut,

Et si on calcule par une probabilité bayésienne on devrait avoir un série qui doit converger fatalement.
Ce raisonnement marcherait-il ?

Je ne sais pas. Faut essayer. Je n'en suis pas du tout certain (les maths sont parfois peu dociles ).

Y a pas besoin de se faire de noeuds aux cerveau non plus

Sauf si on aime bien

Mais le fait est que la théorie des équilibres de Nash, le théorème du minimax von Neumann, les stratégies mixtes.... C'est pas bien compliqué et en plus vraiment puissant et intéressant.

Dans mon vieux encyclopédie Alpha des sciences (un volume était sur les maths) j'ai pas mal passé de temps sur tout ça. J4aimais beaucoup. Et ça m'a beaucoup inspiré par la suite pour faire joujou dans la conceptions d'algorithmes d'apprentissage pour des jeux (je prenais souvent le tictactoe comme "modèle" à cause de sa simplicité et de la rapidité des résultats).

En plus on a des chiffres surprenant : quand on compte le nombre de coups au tictactoe c'est évidemment très petit, le nombre de parties possibles n'est pas énorme non plus alors que le nombre de stratégies (au sens de la théorie des jeux !) est astronomique !!!!

[Liet Kynes]

Perso j'ai du mal à rentrer dans la régression infinie rien que du fait de l'incertitude sur le comportement de Lucky -> cela m'oblige à prendre en compte le fait qu'il a le choix aussi. Avec ce doute je ne maximiserait pas mes chances en choisissant autre chose que les 60% du chemin sans tirage au sort, donc le fait de respecter la règle implique que je suive ce chemin favorable même si je sais que Lucky choisira le même.

[ArchoZaure]

Quelle régression infinie ?

[ArchoZaure]

Silence...
Ça cogite ou ça s'est endormi ?

Explication.
Disons que Billy finit par déduire qu'il a plus de chance de se faire choper (statistiquement) sur le chemin A (quelle qu'en soit la méthode,... connue des deux), il va donc prendre le chemin B.

Mais comme Lucky sait LA MÊME CHOSE que Billy, il sait que Billy va prendre le chemin B, donc il va aussi prendre le chemin B.
Mais comme Billy sait LA MÊME CHOSE que Lucky, il sait que Lucky va prendre le chemin B, donc il va finalement prendre le chemin A.
Mais comme Lucky sait LA MÊME CHOSE que Billy, il sait que Billy va prendre le chemin A, donc il va aussi prendre le chemin A.
Mais comme Billy sait LA MÊME CHOSE que Lucky, il sait que Lucky va prendre le chemin A, donc il va finalement prendre le chemin B.

Mais comme Lucky sait LA MÊME CHOSE que Billy, il sait que Billy va prendre le chemin B, donc il va aussi prendre le chemin B.
Mais comme Billy sait LA MÊME CHOSE que Lucky, il sait que Lucky va prendre le chemin B, donc il va finalement prendre le chemin A.
Mais comme Lucky sait LA MÊME CHOSE que Billy, il sait que Billy va prendre le chemin A, donc il va aussi prendre le chemin A.
Mais comme Billy sait LA MÊME CHOSE que Lucky, il sait que Lucky va prendre le chemin A, donc il va finalement prendre le chemin B.

...

La boucle est bouclée.
C'est pas une régression mais une boucle.

[stefjm]

Boucle ou appel récursif sont équivalent.Non?

[Deedee81]

Salut,

Boucle ou appel récursif sont équivalent.Non?

Pour le coup (de feu de Lucy Luke, non je rigole, je veux dire ici dans ce contexte), oui, c'est équivalent

Mais je reste non persuadé qu'une "limite" d'approche récursive converge (tel que suggéré plus haut).
Et la méthode des stratégies mixtes est franchement pas difficile.
EDIT enfin, la méthode est simple mais minimiser l'espérance est un peu chiant, c'est une expression avec contraintes (les proba c'est entre 0 et 1), parfois c'est un peu énervant à faire

[ArchoZaure]

Boucle ou appel récursif sont équivalent.Non?

Si on veut mais c'est pour bien distinguer le cas où on ne tend vers rien (on boucle) et le cas où le résultat TEND vers quelque-chose (j’entends parler de MAXIMISATION, or c'est FAUX) ou le cas où le résultat dépend de l'ENSEMBLE des résultats antérieurs.
Ici il y a un simple motif en boucle.

[ArchoZaure]

Mais je reste non persuadé qu'une "limite" d'approche récursive converge (tel que suggéré plus haut).

Voilà, moi non plus.
Et ça se montre simplement, comme dans le message #66
Ça ne tend vers rien, ça ne converge pas.

[oualos]

Mais comme Lucky sait LA MÊME CHOSE que Billy, il sait que Billy va prendre le chemin B, donc il va aussi prendre le chemin B.
Mais comme Billy sait LA MÊME CHOSE que Lucky, il sait que Lucky va prendre le chemin B, donc il va finalement prendre le chemin A.
Mais comme Lucky sait LA MÊME CHOSE que Billy, il sait que Billy va prendre le chemin A, donc il va aussi prendre le chemin A.
Mais comme Billy sait LA MÊME CHOSE que Lucky, il sait que Lucky va prendre le chemin A, donc il va finalement prendre le chemin B.

Mais comme Lucky sait LA MÊME CHOSE que Billy, il sait que Billy va prendre le chemin B, donc il va aussi prendre le chemin B.
Mais comme Billy sait LA MÊME CHOSE que Lucky, il sait que Lucky va prendre le chemin B, donc il va finalement prendre le chemin A.
Mais comme Lucky sait LA MÊME CHOSE que Billy, il sait que Billy va prendre le chemin A, donc il va aussi prendre le chemin A.
Mais comme Billy sait LA MÊME CHOSE que Lucky, il sait que Lucky va prendre le chemin A, donc il va finalement prendre le chemin B.

...

La boucle est bouclée.
C'est pas une régression mais une boucle.

Ça se discute
Mettons qu'on numérote ces 4 premières propositions de 1 à 4.
La probabilité finale sera du genre:
P= (probabilité de 1) + (probabilité de 2 sachant 1) + (probabilité de 3 sachant 1 et 2) + (probabilité de 4 sachant 1, 2 et 3) etc. donc des probas conditionnelles qui s'ajoutent car elles sont indépendantes à première vue.

On voit que plus le cerveau sera capable de raisonner en profondeur, plus il y aura de propositions à prendre en compte c.-à-d. qu'on rajoutera 5,6... propositions analogues jusqu'à éventuellement 1000
... si Billy en est capable
En théorie jusqu'à l'infini mais évidemment le cerveau humain a des capacités limitées et seul un ordinateur serait capable d'aller suffisamment loin pour estimer la limite théorique calculée mathématiquement et dont il s'approchera par les séries: et cette série ça doit forcément converger.
bon on peut discuter de ce problème des heures voir des jours durant mais évidemment, quand Billy se trouve à l'embranchement il a mettons quelques secondes tout au plus pour décider de sa stratégie, donc il pourra aller jusqu'à une profondeur de raisonnement en miroir de mettons 5 ou 6. Jusqu'au moment où son cerveau se mettra à embrouiller les idées et l'urgence fera qu'il choisira vite et finalement sans trop réfléchir...

donc pragmatiquement il va compter que Lucky Luke va faire les mêmes réflexions soit estimer les probas suivant une sommation jusqu'au moment où le cerveau de Luke va s'embrouiller aussi.
donc finalement Billy aura une chance sur deux de prendre le chemin A ou B. Il se rend compte de la complexité du problème finalement et je pense que c'est tout.
Pour moi compte tenu de ces contraintes, la probabilité que Billy prenne le chemin A ou B est de 50%

Et symétriquement Luke va choisir un chemin au hasard se rendant compte de la complexité de la situation - aussi un effet-miroir - et qui rend la solution de ce problème quasiment indécidable
et lui aussi aura très peu de temps pour décider

Et donc lui aussi va choisir à 50% un des chemins A ou B

[Deedee81]

Ça ne tend vers rien, ça ne converge pas.

Même une probabilité bayésienne comme suggéré, ça doit faire "flip flop" sans converger.
Ok je suis convaincu (que ça ne marche pas comme ça)

EDIT on s'est croisé. Oualos j'ai du mal à te suivre. Peux-tu calculer la probabilité de l'étape N (ou au moins disons des premières étapes) ?

REEDIT ah oui, on voit une autre lacune, la boucle/récursion donne toujours UN choix alors qu'on sait que la solution est obligatoirement probabiliste. Donc comment cela pourrait-il converger ???? Mais bon, le calcul proba d'abord (puisque c'est ce que tu suggères), la méthode ensuite

[oualos]

Ce problème c'est comment faire mathématiquement d'un problème basique -ou en tout cas qui paraît simple voire élémentaire- quelque chose de vraiment compliqué que seul un ordinateur saurait résoudre.
Deedee81, je vais essayer de formaliser tout cela par les maths mais il faut tenir compte que les maths sont loin pour moi.
Même si le calcul de probabilités dans les maths est quelque chose d'assez basique, l'expression rigoureuse c.-à-d. celle qu'on va traduire en code pour un ordinateur est relativement compliquée.
Si on veut être rigoureux bien sûr et tenir compte de tous les cas de façon hyper-exacte selon les mathématiques des probas...

Je reviens à ma conclusion: en pratique comme Billy et Luke se retrouvant à l'embranchement avec très peu de temps pour choisir, je pense que pragmatiquement, se rendant compte de la complexité du raisonnement en miroir, il vont choisir avec le hasard le plus total c.-à-d. à 50% le chemin A ou B. En se disant en fait que tous les raisonnements à base de supputations de ce que va faire l'autre se valent finalement.
Tous les 2.

[Deedee81]

Ce problème c'est comment faire mathématiquement d'un problème basique -ou en tout cas qui paraît simple voire élémentaire- quelque chose de vraiment compliqué que seul un ordinateur saurait résoudre.

La stratégie mixte elle ne nécessite pas quelque chose de vraiment compliqué.
Et la solution n'est pas 50/50

[ArchoZaure]

La stratégie mixte elle ne nécessite pas quelque chose de vraiment compliqué.
Et la solution n'est pas 50/50

Oui mais quelle que soit la méthode pour déterminer un chemin plus favorable qu'un autre :

Disons que Billy finit par déduire qu'il a plus de chance de se faire choper (statistiquement) sur le chemin A (quelle qu'en soit la méthode,... connue des deux), il va donc prendre le chemin B.

C'est connu des DEUX.
Donc c'est pas fini...

Le seul moment où c'est "fini" (quelle que soit la méthode) c'est si aucun chemin ne révèle un avantage sur un autre... donc 50/50.
Dans ce cas, on ne peut que choisir au hasard.
Pile ou face.

[Deedee81]

Dans ce cas, on ne peut que choisir au hasard.

Ca c'est clair, et je l'avais même dit tout au début Mais il y a hasard et hasard. Et la probabilité de choisir peut être différente de 50/50
La stratégie mixte montre que l'un comme l'autre ont intérêt à choisir les probabilités 60/40 plutôt que 50/50
(à noter que le jeu n'a pas besoin d'être itéré pour ça, et bien entendu ça n'a rien avoir avec la boucle/récursion, la stratégie mixte ne fait pas ce raisonnement "récursif")

[oualos]

Disons que Billy finit par déduire qu'il a plus de chance de se faire choper (statistiquement) sur le chemin A (quelle qu'en soit la méthode,... connue des deux), il va donc prendre le chemin B.

C'est finalement aussi mon avis. Si j'étais Billy c'est ce que ferais.
Ces problèmes sont appelés des casse-têtes et c'est pas pour rien!
Il y a des livres entiers avec des problèmes qui ont l'air simples au départ mais qui nécessitent une vraie réflexion si on veut les résoudre rigoureusement: disons que la version élaborée pourrait être posée au grand oral de Polytechnique.
Le facteur "réel" fait qu'aucun des deux n'a le temps de s'asseoir à l'embranchement , de résoudre mathématiquement ce problème par les probas
et ensuite de le programmer sur son ordinateur portable (au Far West, ils devaient tout au plus disposer d'un boulier ou caisse enregistreuse) et d'attendre que l'ordi leur donne la meilleure solution.

[Juzo]

Oui mais quelle que soit la méthode pour déterminer un chemin plus favorable qu'un autre :
Disons que Billy finit par déduire qu'il a plus de chance de se faire choper (statistiquement) sur le chemin A (quelle qu'en soit la méthode,... connue des deux), il va donc prendre le chemin B.
C'est connu des DEUX.
Donc c'est pas fini...

Le seul moment où c'est "fini" (quelle que soit la méthode) c'est si aucun chemin ne révèle un avantage sur un autre... donc 50/50.
Dans ce cas, on ne peut que choisir au hasard.
Pile ou face.

Si les deux choisissent leur chemin à Pile ou Face, Lucky Luke a 25% de chance d'attraper Billy (0,5*0,5*0,6 + 0,5*0,5*0,4).

Si Billy choisit une stratégie mixte (60% pour le chemin ou il a 40% de chance de se faire attraper), Lucky Luke quel que soit son choix aura "seulement" 24% de chance d'attraper Billy (0,6*0,4). Donc la stratégie mixte s'impose pour Billy, et c'est bien du 50/50 pour Lucky Luke à ce moment-là.

Ce que je me demande c'est pourquoi la stratégie mixte s'impose à Billy et pas Lucky Luke, et comme un raisonnement logique permet de passer de la boucle au choix de la stratégie mixte par billy, y compris pour Lucky Luke qui doit logiquement savoir que Billy choisira la stratégie mixte.

[oualos]

Je vais prendre une aspirine et je vous réponds

[ArchoZaure]

A noter aussi pour éviter les confusions.
Le fait que 60% + 40% = 100% n'est qu'une simple coïncidence.
On peut tout à fait avoir pour le chemin A une chance de 1/1000000 de se faire attraper et pour le chemin B 1/2000 de se faire attraper, la somme de ces fréquences ne doit pas nécessairement faire 1.

[Deedee81]

Ah oui bien vu, hummm je suppose que la solution est alors "à la proportionnelle" mais ça reste à vérifier.

[oualos]

Bon comme je pense qu'on a exploré pas mal de pistes, je laisse la parole à chatGPT qui sans hésiter choisit la stratégie mixte

Pour résoudre ce problème, on peut utiliser le concept de "stratégie mixte" en théorie des jeux. Une stratégie mixte permet à un joueur de choisir aléatoirement parmi plusieurs options, chaque option ayant une probabilité associée.

https://forums.futura-sciences.com/n...reply&t=943736

[Deedee81]

le lien ne marche pas

[Juzo]

Raisonnement peut-être faux : si Billy a une probabilité d'être attrapé par LL sur le chemin A, et une probabilité sur le chemin B.

- Dans le cas où les deux choisissent à Pile ou Face la probabilité pour LL d'attraper Billy sera de .

- La stratégie mixte sera imposée par le joueur qui verra sa probabilité de victoire augmentée en cas de stratégie mixte...

Ce joueur choisira alors une répartition de probabilité telle que chaque chemin donnera à l'autre autant de chance de gagner, si bien que le choix de l'autre n'importera plus.

Ainsi, si P(A) est sa probabilité de choisir le chemin A, on a nécessairement : , avec
Donc .

Par ailleurs : , c'est la probabilité pour LL d'attraper Billy sur chaque chemin en stratégie mixte.

Billy n'a plus qu'à prendre sa calculatrice (ou demander à son cheval, il paraîtrait que certains savent compter ), et vérifier si , ou plus simplement . Dans ce cas il choisira la stratégie mixte.
Or

Billy est donc toujours gagnant en stratégie mixte sauf si a = b

Voilà pourquoi Billy choisit la stratégie mixte.

[Juzo]

Edit : je n'ai pas eu le temps de préciser que P(A) dans la suite ces calculs est la probabilité que Billy choisisse le chemin A quand il suit la stratégie mixte.

En faisant le même raisonnement avec les choix de Lucky Luke qui suivrait une stratégie mixte, on retombe sur les mêmes probabilités qu'il choisisse chaque chemin.

Désolé pour le double message.

[Juzo]

Re-edit sorry, mais j'ai oublié de conclure :

- Si les chemins A et B n'ont pas les mêmes probabilités a et b que Billy soit attrapé, celui-ci choisit le chemin A avec une probabilité de \frac{b}{a+b}
- Lucky Luke peut laisser Jolly Jumper décider

[agitateur]

Si Billy prends le B, il a la certitude d'avoir au minimum 60% de chances de s'en tirer, dans le pire des cas ( avec lucky aux fesses ). C'est déjà supérieur à 50% à 1 coup, c'est pas la peine de chercher plus loin.

Prendre A en espérant que celà soit plus gagnant que B ( et donc mieux que plus de 60 % ) suppose que Luke ait bcp plus de chance de prendre B. Sauf qu'en raisonnant en boucle ou en mixte ou 2 gars intelligents, ce ,n'est pas prêt d'arriver.

L'approche intuitive serait plus "nette" avec 99 et 1%, mais le mécanisme est identique. Et il le serait à 51 / 49, mais la question eut été encore plus surnoise.

Chronologiquement les tirages ne sont pas simultanés, mais en terme de proba ils le sont. C'est là aussi un petit biais cognitif posé par le pb.

je me souviens plus du truc ( désolé ) mais j'avais lu un pb, écrit de manière "habile" qui poussait à calculer en Arrangement et pas Combinaisons ( ou l'inverse ). L'écrit est parfois "fort" pour suggérer une "mauvaise" méthode.

[stefjm]

L'écrit est parfois "fort" pour suggérer une "mauvaise" méthode.

Par exemple, "Faire Truc1, puis faire Truc2" suggère que la commande sera obligatoirement séquentielle alors qu'elle peut n'être que combinatoire.

[Juzo]

Si Billy prends le B, il a la certitude d'avoir au minimum 60% de chances de s'en tirer, dans le pire des cas ( avec lucky aux fesses ). C'est déjà supérieur à 50% à 1 coup, c'est pas la peine de chercher plus loin.

Billy a 75% de chance de s'en tirer si les deux choisissent leur chemin à Pile ou Face, il a 76% de chance de s'en tirer s'il prend la stratégie mixte. C'est mieux que 60% (ce qui est important s'il risque d'être pendu).

[oualos]

Désolé pour le lien je me suis servi de la nouvelle procédure pour les fichiers joints ici mais je vais faire un doublon en cas de...

Solution Lucky et Billy par chatGPT

Lucky_Luke_Billy.jpg
Résumé Billy & Lucky Luke

voilà j'espère que ça marche vous n'êtes pas obligés de vous inscrire pour voir le lien