A vous de jouer !

Jouez au morpion

Rappelons que le morpion est un jeu qui se joue sur une grille de trois lignes et trois colonnes. Chacun des joueurs possède un symbole (croix ou rond). Le premier qui arrive à aligner trois symboles a gagné.

Je vous invite à faire une partie contre le programme, en cliquant ici.

Etes vous arrivé à gagner une partie ?

Je suis sur que non !

Comment je le sais ?

La réponse est simple: ce programme est tout simplement imbattable ! Le mieux que vous puissez faire, c'est partie nulle.

La raison de cette invicibilité sera expliqué plus loin.

Vous serez par ailleurs amené à réaliser votre propre version de ce programme dans un des exercices de ce cours.

Jouez au super morpion

Mais avant cela, je vous invite à jouer à un autre jeu. C'est un jeu que j'ai inventé. Je l'appelle "super morpion'. Il est un peu plus complexe que le morpion car il se joue sur une grille de cinq lignes et cinq colonnes. Pour gagner, il faut arriver à obtenir cinq alignements de trois symboles. Un alignement de quatre symboles compte comme deux alignements de trois symboles. Un alignement de cinq symboles compte comme trois alignements de trois symboles.

Cliquez ici pour jouer.

Il s'agit en fait toujours du même programme (vous trouverez son code dans Exemple/Morpion-Generalise.js). Ce programme est capable de jouer aux deux jeux (Morpion simple et Super-Morpion) selon la manière dont il est paramètré.

Etes vous arrivé à gagner une partie ?

Peut être que oui (et dans ce cas bravo !), car le programme n'est pas invincible lorsqu'il joue au super morpion.

Versions explicatives

Le programme que vous venez d'utiliser peut fonctionner en mode explicatif. Dans ce mode de fonctionnement, il donne des indications à l'utilisateur pour chaque coup possible (les cases vides donc)

• Une case vide en vert indique une victoire certaine pour l'utilisateur, s'il joue cette case (et qu'il joue au mieux par la suite !). Avec le morpion classique, cela ne se produira jamais, car vous ne pouvez pas gagner. Par contre, cela pourra se produire avec le super-morpion.
• Une case vide en rouge indique une défaite certaine pour l'utilisateur, s'il joue cette case (même s'il joue le mieux possible).
• Une case vide grise indique une partie nulle obligatoire (à condition que l'utilisateur choisisse les bons coups par la suite). Cette indication n'est possible que pour le morpion classique. Au super morpion, l'ordinateur n'est pas capable d'affimer qu'un coup aboutit forcément à un nul.
• Une case vide jaune indique le meilleur coup à jouer (en dehors des cases vertes bien sur). Attention : "meilleur" ne signifie pas une victoire certaine. Cela signifie simplement que d'après les calculs du programme, c'est ce coup qui vous donne les meilleurs chances de gagner. Cette indication ne pourra pas se produire pour le morpion classique, car dans ce cas le programme est toujours capable de prédire de manière certaine à quoi aboutit un coup (défaite, victoire ou nulle).

En plus de cela, un nombre est affiché dans chaque case vide rouge ou verte: c'est le nombre maximum de coups nécessaires pour atteindre le résultat prévu.

Voici, un exemple d'indications pour le morpion classique (l'ordinateur joue les ronds):

Ici les coups A1, A2, C1, C2 mènent à une défaite en trois coups et les autres coups lui permettent de faire partie nulle.

Voici, un exemple d'indications pour le super-morpion (l'ordinateur joue les ronds):

Si l'utilisateur joue A3 (case verte), il est sur de pouvoir gagner en deux coups au plus. Les coups C1 (case jaune), C5 (case blanche) et E4 (cases blanche) sont incertains et parmis ces trois coup C1 est celui qui a le plus de chance d'aboutir à une victoire.

Faites un essai

Pour exécuter le morpion classique (respectivement le super-morpion) en mode explicatif, cliquez sur l'entrée "Jouer au morpion classique" (respectivement "Jouer au super-morpion") dans l'entrée Version Explicative du menu gauche.

Avec le morpion classique, vous pouvez être sur d'atteindre partie nulle (c'est le mieux que vous puissiez faire!) en cliquant sur les cases grises jusqu'à la fin du jeu. Si vous cliquez sur une case rouge, vous êtes sur de perdre.

Avec le super-morpion, si vous souhaitez avoir le plus de chance de gagner:

• s'il n'y a pas de cases vertes, cliquez sur une des cases jaunes.
• s'il y a une case verte, cliquez dessus, puis continuer à cliquer sur une case verte jusqu'à la fin du jeu. Vous êtes certain d'aboutir à une victoire.

Arbre de preuve

Les possibilités d'explication du programme vont encore plus loin: lorsqu'il vous indique que vous allez perdre, ou que vous pouvez gagner en un certain nombre de coups, il peut vous en donner la preuve.

Pour obtenir la preuve, il faut d'abord cocher la case Prouver (et il vous faudra donc décocher cette case pour pouvoir continuer à jouer) :

Puis vous cliquez sur la case qui vous intéresse. Dans l'exemple ci-dessus, en cliquant sur A2, vous obtiendrez la preuve que ce coup mène obligatoirement à une défaite en trois coups maximum.

La preuve s'affiche dans une fenêtre divisée en deux cadres. Le cadre gauche contient la preuve sous la forme d'un texte:

Il y a ici 9 alternatives, c'est à dire 9 suites de coups possibles. Elles mènent toutes à la défaite de l'utilisateur.

La preuve consiste à proposer une réponse unique de l'ordinateur pour chaque coup possible de l'utilisateur. Voici, le même arbre sous forme graphique. Les noeuds de l'arbre représentent les coups joués. En rouge: ceux qui sont perdants pour le joueur qui les exécute (ici l'utilisateur). En vert: ceux qui sont gagnants pour le joueur qui les exécute (ici l'ordinateur).

Le cadre droit permet de visualiser graphiquement une alternative particulière. Il suffit de cliquer sur la suite de coups qui vous intéresse. Par exemple, en cliquant sur la suite de coup A2-C3-A1-B3, le cadre droit contiendrait ceci.

Cas du Super Morpion

Le principe est le même pour le super morpion. Pour passer en mode explicatif, cochez la case Prouver:

Ici, le programme indique une victoire en deux coups pour l'utilisateur s'il joue D2.

En cliquant sur cette case, une fenêtre d'explication composée de deux cadres s'affiche.

Dans le cadre gauche, le texte de la preuve (comme la copie d'écran ne permettait pas de capturer tout le cadre gauche, vous ne voyez ici que les huit premières alternatives) : :

En cliquant par exemple sur l'alternative D2-A3-E1, cette suite de coups s'affiche dans le cadre droit. Cliquez ici pour visualiser cet affichage.

Pour lire la suite du cours sur les jeux déterministes cliquez ici, ou sur l'entrée Décidabilité du menu.