Probabilité au morpion (Tic-Tac-Toe)

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour,

Depuis un certain temps, je m'amuse à faire des petites démonstrations. J'en ai déjà fait une petite pour calculer des racines, des inverses ou des puissances de décimaux au centième voir millième près sans utiliser la calculatrice, puis j'ai reprit une idée du membre ρττ, pour simplifier des expressions de vecteurs avec l'histoire des barycentres (on en apprend beaucoup avec Wikipédia, jusqu'ici je n'ai pas vu d’ambiguïtés…).

Et aujourd'hui, j'ai le temps de penser à un truc sympa, c'est d'utiliser les probabilités avec le jeu du morpion (dimension simple, (3x3) ), car il existe beaucoup de techniques pour éliminer son adversaire. En fait, j'ai commencer à regarder sur Google, s'il n'existait pas de tel projet, pour aiguiller mes idées car je part sur une base plutôt vaste (ou pas) mais je ne trouve pas grand chose.

Je pensait partir sur un arbre pondéré mais ça serait trop long, existe-il des logiciels pour y parvenir plus rapidement? Comment vous y prendrait-vous dans ce cas?

Merci pour vos conseils. :-D

Éternel curieux

+0 -0
Auteur du sujet

Qu'as-tu essayer jusqu'ici ? Parce qu'il n'est pas bien complique d'explorer explicitement l'arbre des coups possibles vu la faible combinatoire du Morpion.

KFC

Bien sur, il serait possible d'augmenter les dimensions du cadre de jeu (nxn'). Pour l'instant, j'y réfléchi simplement car je n'ai pas le temps de mettre en application mes idées, peut-être ce soir.

Quant aux arbres, je demandais justement s'il existe un logiciel qui permet d'en crée plus rapidement que sur papier, forcément. :-)

Édité par Ozmox

Éternel curieux

+0 -0

On est bien dans la configuration : Je joue au hasard, et mon adversaire aussi joue au hasard, quelle est la probabilité de gain ou de perte ?

Parce que si l'adversaire ne joue pas au hasard mais cherche le meilleur coup, ce n'est pas du tout la même chose.

Édité par elegance

+0 -0

Oui, en réfléchissant un peu tu peux trouver facilement la réponse et la stratégie optimale. Sachant que le morpion est un jeu à somme nulle et à possibilités finies, le théorème du minimax s'applique : il est impossible de gagner si les deux joueurs jouent correctement.

La meilleure stratégie est la suivante (si tu commences ) :

  • Jouer dans un coin
  • Si l'adverse ne joue pas au milieu il a perdu : tu joue le coin aligné au premier coin joué mais sur la ligne où il n'y a pas de point adverse. Ton adversaire doit jouer entre tes deux poins pour te bloquer. Il reste alors deux coins disponibles. Tu joue celui qui te permet d'avoir une ligne non bloqué avec un de tes deux autres coin. Tu as gagné car tu as la diagonale ouverte et une ligne, ton adversaire ne peut pas te bloquer.
  • Ton adversaire joue au milieu, il peut toujours te bloquer.

Si tu ne joue pas en premier c'est l'inverse.

  • Si ton adversaire joue dans un coin tu dois jouer au milieu.
  • sinon tu dois essayer d'appliquer la même stratégie sachant que ton adversaire va te bloquer normalement car il a un coup d'avance. Normalement tu ne peux que faire un match nul.

Voilà :)

Édité par Demandred

"Il est vraiment regrettable que tous les gens qui savent parfaitement comment diriger un pays soient trop occupés à conduire des taxis et à couper des cheveux"

+2 -0
Auteur du sujet

On est bien dans la configuration : Je joue au hasard, et mon adversaire aussi joue au hasard, quelle est la probabilité de gain ou de perte ?

Parce que si l'adversaire ne joue pas au hasard mais cherche le meilleur coup, ce n'est pas du tout la même chose.

elegance

Justement, c'est à travers les trajets de l'arbre pondéré que l'on peut interpréter le comportement des deux joueurs, soit c'est du hasard, soit c'est stratégique. @Spacefox : mon lycée bloque la photo mais KFC me donne l'eau à la bouche.

Éternel curieux

+0 -0

Oui, en réfléchissant un peu tu peux trouver facilement la réponse et la stratégie optimale. Sachant que le morpion est un jeu à somme nulle et à possibilités finies, le théorème du minimax s'applique : il est impossible de gagner si les deux joueurs jouent correctement.

Si tu sous-entends que le theoreme de Von Neumann dit que pour les jeux a somme nulle les strategies optimales permettent de prevenir la victoire d'un joueur sur un autre, c'est faux. Ce n'est pas ce que dit le theoreme de Von Neumann en general. Contre-exemple: le jeu de Hex est a somme nulle et pourtant il est demontree qu'il existe une strategie gagnante pour le premier joueur. Le theoreme est meme constructif dans le cas de plateau de jeu restreint.

Par ailleurs, il faut faire attention a strategie optimale et strategie gagnante. La strategie optimale pour le pierre-feuille-ciseau c'est une tirage aleatoire uniforme sur l'ensemble des alternatives. Cela ne garantie ni la victoire, ni une esperance de gain nulle ; encore moins dans la vraie vie ou l'aleatoire genere par des humains est loin d'etre parfait et ou il existe alors des strategies ad-hoc de type martingales pour maximiser son esperance de gain.

La meilleure stratégie est la suivante (si tu commences ) :

Demandred

Maintenant, deduis-en un algorithme generique pour NxN, avec preuve d'optimalite. :)

+1 -0

Cette réponse a aidé l'auteur du sujet

On est bien dans la configuration : Je joue au hasard, et mon adversaire aussi joue au hasard, quelle est la probabilité de gain ou de perte ?

Parce que si l'adversaire ne joue pas au hasard mais cherche le meilleur coup, ce n'est pas du tout la même chose.

elegance

Justement, c'est à travers les trajets de l'arbre pondéré que l'on peut interpréter le comportement des deux joueurs, soit c'est du hasard, soit c'est stratégique. @Spacefox : mon lycée bloque la photo mais KFC me donne l'eau à la bouche.

Ozmox

Ok. Donc ce que tu veux c'est analyser les coups de l'adversaire, et définir/deviner si l'adversaire joue au hasard ou s'il cherche les meilleurs coups.

Ce que tu peux faire, c'est :

  • à partir d'une position données, analyser tous les mouvementspossibles et leur donner à chacun une note ( par exemple entre 0 et 100)

  • pour chaque mouvement joué par l'adversaire, mémoriser la note du mouvement en question.

Et ainsi pour un certain nombre de mouvements joués par l'adversaire.

Normalement, si l'adversaire joue au hasard, la moyenne de ses notes devrait être proche de 50.

Et s'il joue bien, la moyenne de ses notes devrait être proche de 100.

Il y a des formules statistiques pour déterminer si une série de notes est significativement décalée par rapport à une autre.

Ca fait donc 2 chantiers un peu séparés :

  • donner une note entre 0 et 100 à chacun des mouvements possibles… ( parcours d'arbre …)

  • puis un peu de connaissances en statistiques.

+1 -0

Si tu sous-entends que le theoreme de Von Neumann dit que pour les jeux a somme nulle les strategies optimales permettent de prévenir la victoire d'un joueur sur un autre, c'est faux.

Non ce n'est pas ce que je sous entends, le théorème du minimax dit (comme son nom l'indique assez bien) qu'il existe une stratégie qui permet de maximiser le gain de l'autre joueur. Cela peut être un match null comme une stratégie gagnante à chaque fois.

Mais ici dans le cas présent (grille 3*3) cela conduit à un match null. Pour les grilles supérieurs j'imagine que c'est pareil mais je n'ai pas la réponse.

Maintenant, deduis-en un algorithme generique pour NxN, avec preuve d'optimalite.

Ca c'est un autre problème, je pensais à la base qu'il voulait juste en 3*3. Enfin je penses qu'en cherchant sur internet ça doit être facile à trouver. Mais du coup c'est quoi la régle en NxN ? Aligner N pions ? Si oui le résultat est le même (match null) et la stratégie plus ou moins identique : jouer sur la diagonale pour bloquer le plus de lignes possibles. Après le prouver formellement c'est une autre histoire et ça dépasse mes compétences^^

"Il est vraiment regrettable que tous les gens qui savent parfaitement comment diriger un pays soient trop occupés à conduire des taxis et à couper des cheveux"

+0 -0

Cette réponse a aidé l'auteur du sujet

@Demandred

Le mot « déduire » est important : ce n'est pas une généralisation, n'importe quelle stratégie 3×3 ferait l'affaire. (en tous cas si c'est bien aligner N pions)

On peut faire des variantes : se placer dans (ℤ/p)^2 avec p premier (on prend une grille p×p, et tous les alignement comptent, « à la pacman »). Avec p pas premier ? Et en dimension n ? Je ne sais pas ce que ça donne.

Je crois que je commence à comprendre ce que veut faire Ozmox. Est-ce bien d'analyser la stratégie de l'adversaire sur un certain nombre de parties, la modéliser sous forme de probabilités dépendant uniquement de la situation à laquelle on est, et ensuite construire une stratégie adverse maximisant la probabilité de gagner ? Il faudra aussi intégrer la probabilité de faire partie nulle. Sinon, ça risque de gagner dans 10% et perdre dans 90% des cas, au lieu de gagner dans 5% des cas et partie nulle dans 95%. Peut-être attribuer un poids de -∞ à perdre, de 0 à partie nulle et 1 à gagner, si on veut que ça ne perde jamais.

edit : et sinon, il vaut mieux faire un DAG qu'un arbre (comme un arbre, sauf que les branches peuvent se rejoindre si on se retrouve dans le même cas). On va avoir 3(3×3) = 19'683 nœuds, c'est assez petit. Sinon avec un arbre, ça fonctionne aussi avec 9! cas, vers 105.

edit : normal que je peux pas échapper les "^" dans le markdown ?

Édité par blo yhg

+1 -0

J'ai parcouru rapidement le sujet et ça m'a rappelé cet article, j'ai bien l'impression que ça peut s'inscrire dans le problème d'Ozmox, dans l'aspect analyse des parties précédentes pour "l'induction" d'une stratégie intéressante (de manière assez primitive certes, mais bon, c'est ça qui est cool aussi ! :p). J'avais réussi à retrouver l'article original publié par les créateurs de la «machine», mais le lien plus haut est déjà assez intéressant je trouve.

Et d'ailleurs on se rend compte que le nombre de nœuds à considérer est bien plus petit, du fait des symétries qu'on trouver dans le cas du 3x3, dans l'article on présente le cas où la machine commence à jouer, et je pense qu'avec Burnside on peut sans trop de douleur dénombrer le cas où c'est le joueur qui commence. Enfin, je ne sais pas si ça t'intéressera plus que ça, mais je trouvais ça sympa à partager ! :)

Édité par Nemh

+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte