Probabilité au morpion (Tic-Tac-Toe)

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.

Pour être parfaitement honnête, je ne comprends pas ta question. Que cherches-tu à faire exactement ?

A étudier le jeu du Tic-Tac-Toe de manière à dégager la probabilité de se rapprocher de la victoire, à chaque placement.

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.

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.

Cette illustration est magnifique. On voit bien l'avantage que l'on obtient lorsque l'on commence, et le fait que l'on subit totalement en jouant second, notamment via la symetrie. Magiquement beau.

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.

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à

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.

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.

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

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^^

@ρττ : C'est exactement le cas, merci pour vos indications.

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 !