Pile ou Face

Olympiades mathématiques, énigmes et défis
GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Pile ou Face

par GaBuZoMeu » 12 Mar 2021, 23:10

Oui, on peut s'efforcer de minimlser le nombre d'états. Je n'ai pas regardé en détail, je reviendrai dessus. Mais ça complique énormément l'écriture de la procédure, car c'est difficile d'écrire les choses uniformément.



Vassillia

Re: Pile ou Face

par Vassillia » 12 Mar 2021, 23:52

Tu as bien eu raison de ne pas t’embêter surtout que tu ne cherchais que les cas n=3 ou n=4, aucun intérêt d'optimiser pour sortir la valeur numérique dans nos cas d'étude (même si on passe quand même d'un rang égal à à inférieur ou égal à ce qui n'est pas négligeable dès que n augmente). Mais il y a peut-être au moins un petit intérêt, on voit apparaitre les comparaisons entre les dernières lettres d'une suite et les premières lettres de l'autre pour écrire les retours en arrière et cela devrait faire plaisir à Conway !

A la base, je l'ai surtout fait pour manipuler un peu vu que je ne connaissais pas mais si cela peut me permettre de comprendre la logique entre les 2 méthodes, je suis preneuse, j'aime bien quand tout est relié, les choses sont mieux rangées dans ma petite tête.

lyceen95
Membre Complexe
Messages: 2255
Enregistré le: 15 Juin 2019, 01:42

Re: Pile ou Face

par lyceen95 » 13 Mar 2021, 02:10

Alors :
La matrice de passage : ok, compris.
Et le fait que tu supprimes les chaines comme PP par exemple dans le 2ème tableau, PP n'est ni plus ni moins que P, ok. C'était ma façon de voir la matrice de passage, donc ça aide.
Je ne vois pas pourquoi tu sépares en 2 matrices Q et R. A priori, l'idée est d'avoir des calculs plus simples. Tu veux que la matrice à inverser soit plus petite.
R est en gros une dernière étape, on la traite comme une formalité. En enlevant cette dernière étape, on raccourcit un peu le chemin, autant pour le joueur 1 que pour le joueur 2, c'est neutre.

Vassillia

Re: Pile ou Face

par Vassillia » 13 Mar 2021, 03:21

Ah si c'est ça qui t’embête, je plaide non coupable, porte plainte contre GaBuZoMeu, c'est lui qui a eu l'idée de faire des chaines de Markov absorbantes :lol:
Moi, j'ai juste suivi le mouvement comme j'y connaissais encore rien il y a 24h, mais cela me semble sensé car c'est particulièrement bien adapté à ce genre de problème je trouve

Si tu veux retrouver la matrice d'origine que tu sembles mieux connaitre, tu rajoutes 2 lignes en dessous de la matrice Q avec uniquement des 0, tu rajoutes 2 lignes en dessous de la matrice R où tu écris l'identité et tu colles les matrices l'une à l'autre.
Ces 2 nouvelles lignes correspondant aux états qui ne sont pas dans la matrice Q mais qui sont dans la matrice R et comme ils sont absorbants, ils font une boucle sur eux même avec une probabilité 1.
Je t'ai fait une version très "usage pratique" par contre je ne sais pas si tu as vu mais c'est aussi ce que fait la procédure de GaBuZoMeu à quelques détails près :
Il met toutes les suites possibles de n-1 lettres dans la matrice Q
Il met uniquement les 2 suites de n lettres qui nous intéressent dans la matrice R.
Du coup, contrairement à moi qui part de rien et qui multiplie par (1;0;...;0) lui il va multiplier par (1/l;1/l;...;1/l) car il part du fait qu'on est sachant n-1 lettres tirées au hasard et donc il faut regarder tous les états possibles dès le début. M'enfin il t'expliquera cela mieux que moi parceque je ne sais pas trop quoi te répondre d'autres que c'est les démos données dans le lien.

GaBuZoMeu
Habitué(e)
Messages: 6016
Enregistré le: 05 Mai 2019, 11:07

Re: Pile ou Face

par GaBuZoMeu » 13 Mar 2021, 09:32

Vassillia a écrit:Tu as bien eu raison de ne pas t’embêter surtout que tu ne cherchais que les cas n=3 ou n=4


Non, la procédure que j'ai écrite est pour une longueur quelconque. Il est vrai que ça commence à ramer pour des longueurs importantes. Par exemple pour une longueur de 10, le Prob(A,B) prend de l'ordre de 60ms, et comme il faut le faire 1000 fois pour trouver le meilleur opposant à A ... on arrive à environ une minute
Même avec la formule de Conway, vois-tu un moyen autre que de comparer A à tous les autres ?

Vassillia

Re: Pile ou Face

par Vassillia » 13 Mar 2021, 10:23

Je sais bien que ta procédure fonctionne pour tout n mais ce que je voulais dire c'est que tu as recyclé un ancien fil où l'objectif était n=3 ou n=4 donc je comprends que tu n'ai pas vu d’intérêt à optimiser. Je ne critiquais pas ta procédure, au contraire, elle fait parfaitement l'affaire ;)

Je te proposerai bien de te servir du fait que la meilleure suite sera celle avec P ou F puis les n-1 premiers termes de l'autre suite mais tant que je ne sais pas vraiment le démontrer, c'est un peu de la triche ceci dit il y a surement moyen d'en virer de l'analyse quand même.
Une autre idée serait de ne pas refaire tous les calculs à chaque fois. Entre 2 suites que tu testes, il n'y a qu'une lettre qui change, il y a peut-être moyen de prévoir le nouveau résultat à moindre cout avec le précédent résultat mais je n'ai pas réfléchi à la question, pourquoi ?

Vassillia

Re: Pile ou Face

par Vassillia » 14 Mar 2021, 14:40

J’ai bien compris que mon pseudo-code est difficilement lisible donc j’en ai fait un code exécutable et tant qu’à faire en Python pour éviter la barrière du langage. Seul petit changement, ma liste d’état contient d’abord les sous-suites communes à X et Y puis les sous-suites qui sont uniquement à X puis les sous-suites qui sont uniquement à Y.

Code: Tout sélectionner
# Fabrique la liste des sous-suites de A et B
def Liste(A,B) :
    L=['']
    for i in range (len(A)-1):
        if A[:i+1]==B[:i+1] :
              L.append(A[:i+1])
        else :
              L.append(A[:i+1])
              L.append(B[:i+1])       
    return L


Code: Tout sélectionner
import numpy as np
def Prob(A,B) :
    L=Liste(A,B)
    l=len(L)
    Q=np.zeros((l,l)) ; R=np.zeros((l,2))
    R[l-2,0]=1/2 ; R[l-1,1]=1/2

    for T in L :
        TP=T+'P'
        if TP != A and TP != B :
            retour=-1;vide=1
            while retour != len(T):
                retour = retour + 1
                if TP[retour:]in L:
                     Q[L.index(T),L.index(TP[retour:])]=1/2
                     retour = len(T)
                     vide=0
            if vide==1 :Q[L.index(T),0]=1/2
       
        TF=T+'F'
        if TF != A and TF != B :
            retour=-1;vide=1
            while retour != len(T):
                retour = retour + 1
                if TF[retour:]in L:
                     Q[L.index(T),L.index(TF[retour:])]=1/2
                     retour = len(T)
                     vide=0
            if vide==1 :Q[L.index(T),0]=1/2                   
    # Vecteur initial
    init=np.array([1]+(l-1)*[0])
    # 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)


Rien de nouveau pour la suite, j'ai juste calculé le maximum des probas ou lieu de les trier.
Code: Tout sélectionner
def Champion(A) :
    L=LTPF(len(A))
    p=0.5
    for B in L :
        if B!= A :
            q=Prob(A,B)[1]
            if q>p:
               p=q
               resultat=B
    print("Contre {0} : {1}, avec {2:.1%} de chances de gagner"\
          .format(A,resultat,p))


Je ne sais pas si cela fera un vrai gain de temps au final car sur le compilateur en ligne, cela ne se ressent pas vraiment mais c'est très approximatif comme calcul. Je sens bien qu’il faut minimiser quelque chose comme la distance des retours en arrière des sous-suites de Y et on les voit bien apparaitre dans cette matrice Q. On devrait pouvoir en faire un critère sélectif avant de calculer en force brute toutes les probas (voir même trouver la bonne réponse et pas juste soit P soit F devant les n-1 premières lettres de X) mais c’est encore loin d’être limpide pour moi donc si vous avez mieux, n’hésitez pas.

PS : Il y aurait eventuellement d'autre chose à optimiser, je me suis facilitée la vie en utilisant index, ce serait mieux de passer par les indices pour restreindre le parcours de la liste mais c'est pénible comme tout. On n'a plus aucun interet à stocker la liste des tirages à pile ou face LTPF(n), autant utiliser une fonction python qui transforme en base 2, avec un peu de chance, cela doit exister sinon c'est pas trop difficile à écrire. C'était avant tout pour rendre un peu plus clair ce que j'essaye de faire.

Vassillia

Re: Pile ou Face

par Vassillia » 14 Mar 2021, 22:39

Arf, je fais du mimétisme sur la procédure de GaBuZoMeu sans réfléchir. Dans mon cas, il est complétement idiot d’inverser la matrice, c’est un temps de calcul catastrophique pour rien, je sais à l’avance quel coefficient va m’intéresser.

Je calcule pour avoir est la probabilité de gain donc je ne m’intéresse qu’à la première ligne de . Je sais aussi par ma manière de placer mes états que dans la 2ème colonne de R, seul le dernier coefficient est non nul et vaut 1/2.
Donc est le coefficient en haut en droite de divisé par 2 et je rappelle que la matrice inverse est la transposée de la comatrice divisée par le déterminant.

Bilan avec le mineur de la matrice où on supprime la 1er colonne et la dernière ligne. J’imagine que python doit savoir calculer le déterminant si on lui demande gentiment et comme les matrices sont de taille inférieur ou égale à , ce n'est pas un temps de calcul déraisonnable du tout.

Il me parait hautement probable que cette formule redonne celle de Conway mais comme je n’aime pas les calculs (même littéraux) pas sure que je me motive à le montrer proprement, peut-être que quelqu’un d’autre sera plus courageux. J'ai atteint mon objectif, cela me parait logique le lien entre ces 2 méthodes

Vassillia

Re: Pile ou Face

par Vassillia » 28 Mar 2021, 11:36

Bonjour,
Comme finalement personne n'est revenu sur ce fil, est-ce que le sujet intéresse toujours ?
Je peux vous recopier le moyen trouvé par D.Felix pour choisir entre P et F devant les n-1 premiers termes de la suite adversaire. C'est pas hyper facile et je ne suis pas sure que ce soit plus pratique que de tester les 2.
On peut aussi reprendre l'idée de Lyceen95 qui voulait lutter contre 2 adversaires en même temps. Si le 2ème adversaire choisit la stratégie optimale comme il le proposait, on devrait pouvoir s'en sortir avec la même méthode pas trop mal par contre s'il choisit au hasard, cela se complique.

 

Retourner vers ⚔ Défis et énigmes

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 9 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite