Pile ou Face

[Vassillia]

Bonjour à tous, une petite énigme sur le jeu de pile ou face, je crois savoir qu’il y a des amateurs

Il y a 2 joueurs et chacun d’eux va choisir une suite de 3 résultats (ex : PFP ou PPP…).
Les joueurs ne peuvent pas choisir la même combinaison. Une pièce parfaitement équilibrée est lancée autant de fois que nécessaire pour que l’une des suites apparaisse pour la première fois. Le joueur correspondant a alors gagné.

Le joueur « confiant » choisit en premier sa suite
Le joueur « averti » choisit en second sa suite connaissant le choix de son adversaire.

Existe-t-il une stratégie pour maximiser ses chances de gagner que ce soit pour l’un ou pour l’autre des joueurs ? Si oui laquelle avec tant qu’à faire la probabilité de succès ?
Pour les plus motivés, mêmes questions si les joueurs devaient choisir une suite de n résultats ?

Édit pour remplacer le mot combinaison par suite pour qu'il n'y ait pas d'ambiguïté

[lyceen95]

Le joueur n°1 choisit ABC (A, B et C sont à remplacer chacune par P ou F).
Moi, joueur n°2, j'ai intérêt à choisir XAB : X est à choisir, au mieux, et il complète par AB, c'est à dire les 2 premières lettres du choix de A.
Comme ça, je vais couper l'herbe sous le pied de son adversaire le plus souvent possible : La séquence ABC n'arrive pas souvent, et en plus, dans la moitié des cas, cette séquence va arriver un coup trop tard pour mon pauvre ami, parce que ma séquence de 3 lettres, celle que j'ai choisie, vient juste de sortir.

Reste à choisir quoi mettre devant AB.
Déjà, on va faire en sorte de ne pas avoir une position symétrique. Si le joueur 1 avait choisi PFP, on ne va pas choisir FPF, on serait à égalité parfaite. On va choisir PPF. Et s'il avait choisi FPF, on va choisir FFP.

Reste à traiter les autres cas, mais il se fait tard.

[Vassillia]

Tu as la bonne idée, bravo
Il ne reste plus qu'à compléter et à calculer les probas mais je te laisse dormir tout de même

[GaBuZoMeu]

Bonjour,

Il me semble qu'il y avait eu un fil sur ce sujet. J'y ai retrouvé une allusion ici :
https://www.maths-forum.com/enigmes/nombre-jet-moyen-necessaire-pour-obtenir-pilefaceface-t213473.html#p1395407

[Vassillia]

Je vois que vous vous êtes déjà pas mal amusé à chercher l'espérance du nombre de tirage pour arriver à une suite. Cela peut répondre à la question pour le joueur "confiant" qui choisit en premier mais pas pour le joueur "averti" qui choisit en connaissant le choix de l'adversaire. Comme tu l'as fait remarquer, la probabilité de gain d'une suite contre l'autre n'est pas intuitivement liée à l'espérance. C'est à cela que je propose de m'intéresser cette fois et du coup à la meilleure stratégie de contre. Mais je te fais confiance pour nous sortir un joli dessin ou un joli programme ou une jolie démonstration au choix

[GaBuZoMeu]

J'ai déjà ça dans mes cartons, quelque part. C'était pour une discussion sur ce sujet dans un forum (pas celui-ci, semble-t-il ?).
Le problème, c'est de le retrouver !

[lyceen95]

Ici : http://www.les-mathematiques.net/phorum/read.php?12,1688582,1798332#msg-1798332

C'était exactement ce même sujet.

[Vassillia]

Pas exactement puisqu'ils veulent avoir une proba > 1/2 quelque soit le choix de l'adversaire alors que je veux la meilleure proba sachant le choix de l'adversaire. Mais la valeur des probas est clairement donnée pour le cas n=3 et n=4 donc autant s'en servir pour conclure immédiatement.
Reste juste à généraliser au cas n, perso, je n'ai pas de démonstration, juste une stratégie pas trop mauvaise.

[GaBuZoMeu]

Lyceen95 a retrouvé le fil auquel je pensais. merci ! Mais il y en a peut-être un autre.
En tout cas la procédure permet bien sûr de répondre à la question du présent fil.
La procédure Sage que j'ai écrite dans le fil déterré par Lyceen95 est maladroite. On peut faire plus simple en pensant chaîne de Markov absorbante.

[GaBuZoMeu]

Je donne une procédure qu'on peut faire tourner en Python (avec numpy) :

Code: Tout sélectionner

# Fabriquer des listes de tirages de longueur voulue
def LTPF(n) :
    if n==0 : return ['']
    else :
        L=LTPF(n-1)
        return ['P'+T for T in L]+['F'+T for T in L]

Code: Tout sélectionner

import numpy as np

# Calcul de la probabilité de victoire en fonction des choix A et B
def Prob(A,B) :
    # liste des tirages à pile ou face de longueur 1 de moins que A et B
    L=LTPF(len(A)-1)
    l=len(L)
    # Fabrication de la matrice de transition
    Q=np.zeros((l,l)) ; R=np.zeros((l,2))
    for j in range(l) :
        S=L[j]+'P'
        if S==A : R[j,0]=1/2
        elif S==B : R[j,1]=1/2
        else : Q[j,L.index(S[1:])]=1/2
        T=L[j]+'F'
        if T==A : R[j,0]=1/2
        elif T==B : R[j,1]=1/2
        else : Q[j,L.index(T[1:])]=1/2
    # Vecteur initial
    init=np.array(l*[1/l])
    # Matrice fondamentale
    N=np.linalg.inv(np.identity(l)-Q)
    # Retour des probabilités de victoire pour A et B
    return init.dot(N).dot(R)

Code: Tout sélectionner

# Meilleure chance contre une suite donnée

def Champion(A) :
    L=LTPF(len(A))
    G=[]
    for B in L :
        if B!= A :
            G.append([Prob(A,B)[1],B])
    G.sort(key= lambda i : i[0])
    print("Meilleure chance contre {0} : {1}, avec {2:.1%} de chances de gagner"\
          .format(A,G[-1][1],G[-1][0]))

Un exemple d'utilisation :

Code: Tout sélectionner

Champion("FFPFFFPP")

Meilleure chance contre FFPFFFPP : PFFPFFFP, avec 67.6% de chances de gagner

[Vassillia]

Je n'avais pas fais attention au pseudo des contributeurs sur l'autre fil, décidément tu es partout

Je pense qu'on peut aussi utiliser l'algorithme de Conway :
une première suite
une deuxième suite

pour tout entier de à alors si et sinon

est écrit en base 2 qu'on transforme ensuite en base 10
P( gagne devant ) =
Avec comme info gratuite =temps moyen d'attente de la séquence (je le signale juste au passage comme tu en avais parlé dans le premier fil)

Il semble que la meilleure combinaison de gagner pour est de choisir soit soit . Je suis bien d'accord avec l'argument de Lyceen95 comme quoi, on coupe l'herbe sous le pied de l'adversaire mais je ne sais pas le prouver ni comment choisir systématiquement entre les 2 même si la proba est toujours supérieure ou égale à 9/14 apparemment.
Je n'ai jamais vu la démo de l'algorithme de Conway et je ne suis pas spécialement à l'aise avec les chaines de Markov n'ayant jamais eu l'occasion d'en étudier dans ma scolarité mais c'est peut-être l'occasion de m'y mettre, je m'ennuie un peu de ne plus rien apprendre de nouveau.

[lyceen95]

Déjà, je vais me lancer des fleurs : je cherchais une expression du langage commun pour décrire la stratégie du 2ème joueur, et je trouve que 'couper l'herbe sous le pied' décrit parfaitement la stratégie.

Ensuite, partant de l'exemple :
Joueur 1 joue FFPFFFPP
On va donc jouer FFFPFFFP ou PFFPFFFP.
Si on choisit FFFPFFFP, on se coupe l'herbe sous le pied à soi-même. On joue une chaine du type ABCDABCD.
Les 4 premières lettres du début coïncident avec les 4 dernières lettres de cette séquence. Gros gachis.

Il faut éviter que la chaine qu'on va jouer commence avec la chaine de fin de l'adversaire, ou avec la chaine de fin de notre propre chaine.

On pousse le challenge ?
On introduit un 3ème joueur.
Le joueur 1 a joué .. plus ou moins au hasard.
Le joueur 2 a pu adapter sa stratégie pour battre autant que faire se peut le joueur 1.
Que doit jouer le joueur 3 quand il connaît les paris des joueurs 1 et 2 ?

[GaBuZoMeu]

As-tu une référence pour l'algorithme de Conway ?

Pour les chaînes de Markov absorbantes, tu peux voir ici : https://www.idpoisson.fr/berglund/probamass_html/node18.html. Ce n'est pas compliqué, et je n'ai fait qu'implémenter ça dans ma procédure.

[Vassillia]

Je l’avais trouvé dans une revue de vulgarisation « Pour la science » de mémoire donc il n’y avait pas de démonstration malheureusement sinon je l’aurai lu quand même.
Je ne me suis jamais senti ni le courage ni le niveau pour le prouver donc je l’ai considéré comme acquis (à tort peut-être). Pourquoi, c’est faux ? Si oui, c’est surement moi qui ai mal compris et il doit surement y avoir une publication un peu plus sérieuse vu que John Horton Conway est vraiment mathématicien.
Edit : tu as raison, j'avais fais une erreur, je corrige

@Lyceen95 Je sens bien ce que tu veux dire et je te jette des fleurs aussi, ton expression est parfaite, mais je n'appelle pas vraiment cela une démonstration ni une manière de choisir systématiquement. C'est l'idée intuitive que je m'en fais aussi

[Vassillia]

Je viens de retrouver l’article et il précise que le problème a été résolu sous sa forme générale en remplaçant par un dé à k faces
D. Felix : Optimal Penney Ante strategy via correlation polynomial identities, The Electronic Journal of Combinatorics, vol. 13-1, R35, 2006

Je te mets les autres références données au cas où tu retrouves plus facilement :
R. Nickerson et P. Ante, Counterintuitive probabilities in coin tossing, The UMAP Journal,vol. 28, pp. 523-532, 2007
M. W. Andrews, Anyone for a nontransitive paradoxe ? The case of Penney Ante, prépublication, 2004 (m.andrews@ucl.ac.uk)
S. Collings, Coin sequence probabilities and paradoxes, Bull. of the Inst. of Math. and its Applic., vol. 18, pp. 227-232, 1982
L. Guibas et A. Odlyzko, Stringoverlaps, pattern matching, andnontransitive games, Journal of Combinatorial Theory, vol. A30-2,pp. 183-208, 1981.

[GaBuZoMeu]

Merci, j'ai pu récupérer des articles - mais je ne les lirai pas tout de suite

[Vassillia]

Pas de souci, prends ton temps, j’ai aussi trouvé la première référence et l’ayant ouvert, tu devrai trouver ton bonheur dedans. Sauf erreur de leur part, l’algo de Conway est valable et d’ailleurs c’est très joli leurs résultats. Je vais quand même essayer de comprendre la démonstration mais à priori, j’ai plutôt confiance puisque c’est une publication « officielle »

[Vassillia]

J’ai enfin compris ce que fait la fonction Prob(A,B) et effectivement ce n’est pas compliqué.
M’enfin quand on ne connait ni python ni les chaines de markov absorbantes, il faut un petit temps d’adaptation quand même. J’avais mal interprété L.index(S[1:]) et donc je ne percutais pas du tout ce que tu regardais comme état (certes, après coup, c’est évident).
Cela valait la peine de comprendre finalement par contre inverser une matrice carré d’ordre me parait nettement plus couteux en temps de calcul que l’algo dont je parlais même s'il y a beaucoup de 0 dedans.

[Vassillia]

Encore moi, promis après je reste tranquille

J’ai réfléchi à cette histoire de chaine de Markov et de matrice carré d’ordre qui me parait quand même énorme, est-ce que j’ai le droit de faire le truc suivant ?
et je pose
et je pose
J’étudie l’ensemble des états donc au pire éléments mais possiblement moins et c’est parti pour écrire les matrices Q et R, quand j’utilise max, il faudra comprendre élément de longueur max.

Si alors et
Tant que s'incrémente en vérifiant on peut fusionner les éléments
et
//Dans l’idée, j’avance si j’ai de la chance et sinon je recule le moins loin possible entre l’endroit où je suis et l’ensemble vide pour que cela reste compatible avec mes derniers tirages

Pour la première fois où alors



Pour jusqu'à on ne pourra plus jamais fusionner les éléments
et
et
//L’idée est la même qu’avant mais je dois en plus vérifier que je ne tombe dans l’autre branche plutôt que de continuer à reculer

et
et

J'ai fais attention aux indices mais c'est un peu pénible à écrire donc possible que je me sois loupée, en fait je voulais surtout savoir si c’est réglementaire comme manière de voir les choses, c’est ma toute première matrice de transposition (comme tout nouveau joujou, il faut que je le manipule un peu avant de m’en servir correctement). J’ai mis un exemple et j’ai vérifié cela donne le bon résultat donc je trouve plutôt cela encourageant.

Edit pour rajouter les images des chaines en espérant convaincre Lyceen95

[lyceen95]

Si GabuZoMeu comprend ce que tu veux dire, je lui tire mon chapeau