Probabilité gagner au morpion (hasard)

[poujinet]

Bonjour,

Je suis actuellement sur un problème de probabilité assez ardu et j'aurais besoin d'aide pour y comprendre quelque chose. Voila l'énoncé :

-Deux joueurs jouent au jeu du "Morpion" sur une grille carrée de 3X3 cases. Les deux joueurs n'ont pas la volonté de gagner et jouent totalement aléatoirement, sans aucune stratégie. Calculer la probabilité que l'un des joueurs gagne (en alignant 3 de ses symboles horizontalement, verticalement ou en diagonal).

Tout ce que j'ai réussi à faire pour l'instant est ceci :

On part d'une grille de neuf cases, donc toutes les différentes combinaisons peuvent être énumérés. On remarque alors que huit d'entre elles sont gagnantes :

1 2 3
4 5 6 Les combinaisons gagnantes sont : 123/456/789/147/258/369/159/357
7 8 9

La probabilité que le joueur choisisse de poser un symbole dans la case 1 est de 1/9ème. Pour terminer la partie il faudrait que ces deux prochains coups soit : le 2 puis le 3 ou le 4 puis le 7 ou le 5 puis le 9. La chance de completer une suite d'un coup serait alors de 1/9^3 = 1/729 (?). Or il faut prendre en compte que l'adversaire puisse poser son symbole sur l'un des numéros énuméré. Et comme le joueur qui a commencé joue aléatoirement il ne cherchera pas à gagner.
J'en suis donc bloqué là, si quelqu'un pouvait me donner une piste je lui en serais très reconnaissant.

[Dlzlogic]

Bonjour,
Moi, j'essayerais en commençant par la fin.
Toutes les cases étant occupées, quel est le nombre de cas possibles et quel est le nombre de cas favorables ?

[poujinet]

Je connais le nombre de cas favorable, il y'en a 8 (si j'ai bien compris ce que vous vouliez dire par favorable). Cependant je sèche pour le nombre de cas possible. Il me semble qu'il faut faire 9^9 mais comme il n'y a que 2 choix possible : X et O (au vu des symboles utilisés au morpion) je pencherai plutôt vers 9^2 = 81 solutions possible (comprenant les solutions gagnantes). J'en déduirai donc qu'il y ai 8/81ème de chance de gagner en jouant au hasard ? Ou alors je m'égare complètement. :hein:

[Dlzlogic]

Je connais le nombre de cas favorable, il y'en a 8 (si j'ai bien compris ce que vous vouliez dire par favorable). Cependant je sèche pour le nombre de cas possible. Il me semble qu'il faut faire 9^9 mais comme il n'y a que 2 choix possible : X et O (au vu des symboles utilisés au morpion) je pencherai plutôt vers 9^2 = 81 solutions possible (comprenant les solutions gagnantes). J'en déduirai donc qu'il y ai 8/81ème de chance de gagner en jouant au hasard ? Ou alors je m'égare complètement. :hein:

Imaginez les 9 cases écrites l'une après l'autre comme un nombre composé de chiffres (0 ou X ; 0 ou 1)
Ca fait combien de possibilités ?
Les cryptogrammes qu'on voit maintenant sur tous les courriers (banque, impôts etc..) résultent exactement du même principe.
Seul détail différent, le nombre de cases 0 et X au morpion est le même à un près.

[Skullkid]

Bonjour poujinet, ignore les indications de Dlzlogic si tu veux avoir une chance de résoudre ton problème (qui est beaucoup plus compliqué que ce qu'il essaye de te faire croire). Pour l'instant je ne vois pas d'autre méthode que le calcul bourrin de toutes les grilles possibles et de leur proba d'apparition, ce qui nécessiterait probablement le secours d'un ordinateur (toutes les grilles ne sont pas équiprobables et le nombre total de grilles n'est pas évident à calculer).

Ce problème vient-il d'un manuel scolaire ?

[Iroh]

Bonjour, en simulant l'expérience 100000 fois sur pc j'arrive à 87463 victoires. (Grilles morpions générées (joueur1 = 1, joueur2 = 2, case vide = 0))

Edit: ils jouent chacun à leur tour.

[Skullkid]

Bonjour poujinet, ignore les indications de Dlzlogic si tu veux avoir une chance de résoudre ton problème (qui est beaucoup plus compliqué que ce qu'il essaye de te faire croire). Pour l'instant je ne vois pas d'autre méthode que le calcul bourrin de toutes les grilles possibles et de leur proba d'apparition, ce qui nécessiterait probablement le secours d'un ordinateur (toutes les grilles ne sont pas équiprobables et le nombre total de grilles n'est pas évident à calculer).

Ce problème vient-il d'un manuel scolaire ?

Bon en fait je dois de plates excuses à Dlzlogic (savoure !), j'avais trop hâtivement lu "probabilité que le premier joueur gagne" et non pas "probabilité que l'un des deux joueurs gagne" du coup on peut faire comme si le jeu ne s'arrêtait pas lorsque l'un des joueurs gagne et continuer à remplir le tableau jusqu'au bout.

[beagle]

Bonjour, en simulant l'expérience 10000 fois sur pc j'arrive à 87463 victoires. (Grilles morpions générées (joueur1 = 1, joueur2 = 2, case vide = 0))

Edit: ils jouent chacun à leur tour.

10 miyes parties et
87 miyes victoires
dans un jeu à deux joueurs, wouah!

[Iroh]

10 miyes parties et
87 miyes victoires
dans un jeu à deux joueurs, wouah!

Oublié un zéro: 100K parties.
Merci ...

[beagle]

Oublié un zéro: 100K parties.
Merci ...

Merci surtout à toi pour la simule,
cela fait beaucoup de victoires finalement!

[Dlzlogic]

Il y a une autre méthode peut-être plus simple :
le premier joueur joue : 1 choix sur 9
à son tout 1 choix sur 7
à son tour 1 choix sur 5
à son tour 1 chois sur 3
résultat 9 * 7 * 5 * 3 = 945 soit 8/945 = 118

le premier joueur joue : 1 choix sur 8 (en seconde position)
à son tout 1 choix sur 6
à son tour 1 choix sur 4
à son tour 1 chois sur 2
résultat 8 * 6 * 4 * 2 = 384 soit 8/384 = 1/48

Soit en moyenne, ils commencent chacun leur tour, 1/83
Je dois pas être très loin du calcul du PC de Iroh.

[EDIT]En relisant le calcul de Iroh, sur 100 parties il y a 87 victoires, ie 43 pour joueur 1 et 43 pour joueur 2 ?
Mais j'ajoute que je ne suis pas du tout sûr de mon résultat, je préfère la logique de 2^9 à partager en 2, en envisageant les 2 cas : J1 commence ou J2 commence.
Mais comme chacun sait, c'est pas du tout ma spécialité (l'analyse combinatoire).

[Skullkid]

Il y a une autre méthode peut-être plus simple :
le premier joueur joue : 1 choix sur 9
à son tout 1 choix sur 7
à son tour 1 choix sur 5
à son tour 1 chois sur 3
résultat 9 * 7 * 5 * 3 = 945 soit 8/945 = 118

le premier joueur joue : 1 choix sur 8 (en seconde position)
à son tout 1 choix sur 6
à son tour 1 choix sur 4
à son tour 1 chois sur 2
résultat 8 * 6 * 4 * 2 = 384 soit 8/384 = 1/48

Soit en moyenne, ils commencent chacun leur tour, 1/83
Je dois pas être très loin du calcul du PC de Iroh.

Que dénombres-tu dans ce calcul ? En appliquant la méthode que tu as suggérée dans ton premier post on trouve que la proba que l'un des deux joueurs gagne est de 55/63, soit environ 0,873. 1/83 ça fait environ 0,012.

[Dlzlogic]

Que dénombres-tu dans ce calcul ? En appliquant la méthode que tu as suggérée dans ton premier post on trouve que la proba que l'un des deux joueurs gagne est de 55/63, soit environ 0,873. 1/83 ça fait environ 0,012.

J'ai fait un édit à lire.
l'un des deux joueurs gagne est de 55/63,
Lequel des deux gagne 55/63 J1 ou J2,
Si on ne sait pas tous les deux gagnent la même chose c'est à dire 110 parties sur 63 jouées.
Je crois qu'au morpion, maême en faisant attention on gagne beaucoup moins souvent.

[Skullkid]

Ce qu'on cherche à calculer c'est la proba qu'il y ait un gagnant, cette proba vaut 55/63 (qui tu le remarqueras est relativement proche des 87463/100000 obtenus par Iroh via simulation). Si tu veux calculer la proba qu'un joueur donné gagne, ça devient beaucoup plus compliqué et on en revient à mon premier post.

[Dlzlogic]

Ce qu'on cherche à calculer c'est la proba qu'il y ait un gagnant, cette proba vaut 55/63 (qui tu le remarqueras est relativement proche des 87463/100000 obtenus par Iroh via simulation). Si tu veux calculer la proba qu'un joueur donné gagne, ça devient beaucoup plus compliqué et on en revient à mon premier post.

Oui, OK.
En fait ce genre d'exercice ne m'intéresse pas, je cherchais seulement à trouver une orientation de recherche pour notre ami, puis qu'il était bloqué.
Mais j'observe qu'encore une fois, j'aurais mieux fait de me taire.

[Skullkid]

Ben, tu lui as donné la bonne méthode. Ce qui est dommage c'est que tu n'as pas l'air d'avoir réfléchi à pourquoi c'était la bonne méthode, et que tu ne l'as pas appliquée...

[Dlzlogic]

Ben, tu lui as donné la bonne méthode. Ce qui est dommage c'est que tu n'as pas l'air d'avoir réfléchi à pourquoi c'était la bonne méthode, et que tu ne l'as pas appliquée...

Je crois que je n'ai jamais donné la solution d'un problème scolaire.
D'abord c'est contraire à mes principes et ensuite, en matière de math scolaire, il y a autant de bonnes réponses que de niveau. Donc je m'abstiens toujours.

[fatal_error]

slt,

sauf erreur de coding:
la proba que l'un des deux gagne : 0.8248175182481752
proba que le premier joueur gagne : 0.48094079480940793
proba que le second gagne : 0.34387672343876724

code (javascript):

Code: Tout sélectionner

function Grid(x,y){
   this.m=[];
   for(var i=0;i<x;i++){
      this.m[i]=[];
      for(var j=0;j<x;++j){
         this.m[i][j]=' ';
      }
   }
   this.copy=function(){
      var grid=new Grid(x,y);
      for(var i=0;i<x;i++){
         for(var j=0;j<x;++j){
            grid.m[i][j]=this.m[i][j];
         }
      }
      return grid;
   }
   this.toString=function(){
      var str='';
      this.m.forEach(function(x){
         str+=x.join('|');
         str+="\n";
      });
      return str;
   }
   this.isColumn=function(i,j){
      var r=(this.m[i][j]==this.m[(i+1)%3][j] && this.m[i][j]==this.m[(i+2)%3][j]);
      return r;
   }
   this.isLine=function(i,j){
      var r=(this.m[i][j]==this.m[i][(j+1)%3] && this.m[i][j]==this.m[i][(j+2)%3]);
      return r;
   }
   this.isDiagTlBr=function(i,j){
      var r=(i==j && this.m[i][j]==this.m[(i+1)%3][(j+1)%3] && this.m[i][j]==this.m[(i+2)%3][(j+2)%3]);
      return r;
   }
   this.isDiagBlTr=function(i,j){
      var r=(i+j==2 && this.m[i][j]==this.m[(i+2)%3][(j+1)%3] && this.m[i][j]==this.m[(i+1)%3][(j+2)%3]);
      return r;
   }   
   this.isWinning=function(i,j){
      return this.isColumn(i,j) || this.isLine(i,j) || this.isDiagTlBr(i,j) || this.isDiagBlTr(i,j)
   }
}
var opponent={
   'X':'O',
   'O':'X'
}
function play(i,j,grid, playerId){
   grid = grid.copy();
   grid.m[i][j]=playerId;
   if(grid.isWinning(i,j)){
      //console.log('winning '+i+','+j);
      //console.log(grid.toString());
      g_winner[playerId]++;
      return true;
   }else{
      var stillToPlay=false;
      for(var u=0; u<3;++u){
         for(var v=0;v<3;++v){
            if(grid.m[u][v]==' '){
               stillToPlay=true;
               play(u,v,grid,opponent[playerId]);
            }   
         }
      }
      if(!stillToPlay){
         //console.log('looser');
         //console.log(grid.toString());
         g_looser++;
      }
   }
}
   var g_winner={
      'X':0,'O':0
   }
   var g_looser=0;
(function(){
   var grid=new Grid(3,3);
   play(0,1,grid,'X');
   console.log((g_winner['X']+g_winner['O'])/((g_winner['X']+g_winner['O'])+g_looser));
   console.log(g_winner['X']/((g_winner['X']+g_winner['O'])+g_looser));
   console.log(g_winner['O']/((g_winner['X']+g_winner['O'])+g_looser));
})();


edit: bon lol.
Déjà j'ai initialisé que sur la case 0.1, merci les symmétries :marteau:
Ensuite, ya aussi le fait qu'on tient compte de l'ordre dans lesquels les croix et ronds sont posés, ce qui semble normal, mais mieux vaut le préciser

[beagle]

Bonjour fatal_error,
tu peux revoir ton code si tu as le temps,
déjà en gain total tu es à 82% soit 5% de moins que les réponses de Skullkid et Iroh,
et ensuite la répartition des gains joueur en premier et joueur en second me semble pas top non plus.

Dans ce jeu, celui qui commence a le droit de jouer son cinquième coup?

[Iroh]

Bizarre, j'obtiens des proba de victoire très proches pour les deux joueurs (j1: proba de gagner si on commence la partie, j2 = proba de gagner si on ne commence pas la partie):

Tx: 0.873190, j1: 0.585820, j2: 0.574740 (sur 100K jeux)

Principe:
- on fixe un nombre n de jeux consécutifs.
- on tire au sort celui qui joue le premier jeu, ensuite les joueurs jouent les n jeux en commençant chacun à leur tour.
- chaque joueur met son symbole dans la grille à une case libre au hasard.

Erreur de code peut-être.