Le but du jeu


Le morpion est un jeu de réflexion se pratiquant à deux joueurs au tour par tour et dont le but est de créer le premier un alignement.

Le jeu se joue généralement sur du papier et avec un crayon (ou stylo...).

  Morpion ou Morpions ?

On distingue en fait deux jeux très proches appelés tous deux « morpion » :

  • Le premier type de morpion, également appelé Tic-Tac-Toe se joue sur une grille carrée de 3x3 cases.
    Deux joueurs s’affrontent.
    Ils doivent remplir chacun à leur tour une case de la grille avec le symbole qui leur est attribué : O ou X.
    Le gagnant est celui qui arrive à aligner trois symboles identiques, horizontalement, verticalement ou en diagonale.

    En raison du nombre de combinaisons limité, l’analyse complète du jeu est facile à réaliser : si les 2 joueurs jouent chacun de manière optimale, la partie doit toujours se terminer par un match nul.

  • Le deuxième type de morpion se joue sur une grille libre (sans limites... enfin, juste la taille de la feuille de papier !).
    Les joueurs inscrivent tour à tour leur symbole X ou O sur la grille.
    Le premier qui parvient à aligner cinq de ses symboles, horizontalement, verticalement ou en diagonale, gagne la partie.

    Le morpion libre donne un avantage assez important à celui qui commence.
    Des formes évoluées existent, comme le Gomoku ou le Pente, qui ajoutent à la notion d’alignement une notion de prise.
    Le Renju prévoit des handicaps pour le joueur qui commence, ce qui permet d’équilibrer les chances des deux joueurs.

  Jouer au Tic-Tac-Toe

  Modélisation informatique

Vous vous demandez peut-être comment fonctionne l’application ci-dessus ?
En fait, c’est très simple !

On part d’une grille de neuf cases. L’espace de jeu étant fini, les différentes combinaisons peuvent être toutes énumérées, et l’on remarque vite qu’il existe alors que huit possibilités pour gagner.

Il suffit pour cela d’aligner les cases :

  • 123,
  • 456,
  • 789,
  • 147,
  • 258,
  • 369,
  • 159
  • ou 357.

Le but du programme va donc consister à enregistrer, pour chaque joueur, les cases cochées pour chaque combinaison.
On détermine ainsi les combinaisons finies dans un tableau, où l’on attribue pour chaque joueur une note.

Par exemple, prenons le cas où les deux joueurs arrivent à ce résultat :

On aura les valeurs suivantes dans le tableau :

Si le joueur 1 coche la case 9, la valeur de la combinaison ’159’ pour ce joueur passe alors à 3. Il remporte donc la partie !

Toute la gestion du jeu est basé sur ce tableau.
Dès qu’une combinaison atteint 3 pour un joueur, cela indique qu’il a gagné.
Pour faire jouer l’ordinateur, on étudie donc le tableau en regardant :

  • S’il est possible d’atteindre cette valeur pour chaque combinaison.
  • Sinon, on vérifie que l’adversaire humain ne puisse pas le faire.
  • Enfin, si rien de tout cela n’est possible, on amène l’ordinateur à cocher une case d’une combinaison qui ne soit pas déjà bloqué. C’est-à-dire qu’il faut que cette combinaison n’ait pas déjà été entamée par l’adversaire (donc, qu’il y ait bien 0 de l’autre côté du tableau).

  Le Morpion sur un ordinateur à ADN

En 2002, J. Macdonald, D. Stefanovic et M. Stojanovic ont créé un calculateur à ADN capable de jouer au jeu du morpion contre un joueur humain [1].

Le calculateur est constitué de neuf bacs correspondant aux neuf cases du jeu.
Chaque bac contient un substrat et diverses combinaisons d’ADN enzymatique.
Le substrat est lui-même constitué d’un brin d’ADN auquel on a greffé à une extrémité un groupe chimique fluorescent, et à l’autre un groupe répresseur.
La fluorescence n’est active que si les molécules du substrat sont coupées en deux.
Les ADN enzymatiques simulent des fonctions logiques. Par exemple, tel ADN se dépliera si l’on a introduit deux types particuliers de brin d’ADN, reproduisant la fonction logique ET.

Par défaut, le calculateur est supposé jouer en premier dans la case centrale.

Le joueur humain possède en entrée huit différents types de brins d’ADN affectés à chacune des huit cases qu’il est susceptible de jouer. Pour indiquer qu’il coche la case n°i, le joueur humain déverse dans tous les bacs les brins correspondant à l’entrée n°i.
Ces brins se lient à certains ADN enzymatiques présents dans les bacs, ce qui entraîne, dans l’un d’entre eux, la déformation de l’ADN enzymatique qui se lie au substrat et le découpe.
Le bac correspondant devient alors fluorescent, indiquant quelle case joue le calculateur à ADN.

Les divers ADN enzymatiques sont répartis dans les divers bacs de façon à assurer la victoire du calculateur à ADN contre le joueur humain.

  Au Cinéma et à la Télévision

  • Dans le film « WarGames » (1984), le jeu de morpion (Tic-Tac-Toe) est utilisé pour apprendre à un ordinateur pris de folie destructrice qu’il existe des jeux auxquels on ne peut pas toujours gagner...
  • Dans le film « Top secret ! » (1984), le héros Nick Rivers se retrouve dans une maison abritant des résistants et prise d’assaut par des soldats Allemands.
    Caché près d’une vitre à 9 carreaux, il tire à travers, faisant des trous ronds, tandis que les balles ennemies traversent les carreaux en laissant une marque en forme de croix.
    Nick ayant réussi à aligner 3 ronds, son adversaire meurt...
  • L’émission « L’Académie des neuf » diffusée sur Antenne 2 à partir de 1982, réunissait neuf invités sur trois étages. Deux candidats jouaient au morpion en faisant poser des questions aux invités par l’animateur.
  • Dans la série animée « Les Simpson », Apu Nahasapeemapetilon possède un doctorat en informatique obtenu grâce à sa création, le premier jeu de morpion avec intelligence artificielle !

P.-S.

  • Image illustrant l’ordinateur à ADN par Jean-François Podevin.

Notes

[1J. Macdonald, D. Stefanovic et M. Stojanovic, Des assemblages d’ADN rompus au jeu et au travail, Pour la Science, n°375, janvier 2009, p.68-75