Le Morpion résolu : pourquoi la partie parfaite finit toujours par un match nul
Vous avez certainement vécu cette expérience : après quelques parties de Morpion contre un ami attentif, chaque manche se termine par un match nul. Aucune erreur à exploiter, aucune ouverture à saisir. Ce n’est pas une coïncidence. Le Morpion est ce que les mathématiciens appellent un jeu résolu : la théorie des jeux a démontré qu’avec un jeu parfait des deux côtés, toute partie se termine inévitablement par une égalité. Mais que signifie exactement « résolu » ? Comment les mathématiciens l’ont-ils prouvé ? Et surtout, pourquoi continue-t-on à y jouer avec plaisir ?
Qu’est-ce qu’un jeu résolu ?
En théorie des jeux, un jeu est dit résolu lorsque l’issue de toute partie peut être déterminée à l’avance, en supposant que les deux joueurs jouent de manière optimale. Concrètement, cela signifie qu’il existe une stratégie infaillible, un algorithme qui dicte le meilleur coup dans chaque situation possible, et dont le résultat est connu d’avance.
Les mathématiciens distinguent trois niveaux de résolution :
- Ultra-faiblement résolu : on connaît le résultat théorique (victoire du premier joueur, du second, ou match nul) avec un jeu parfait, sans forcément connaître la stratégie complète.
- Faiblement résolu : on dispose d’une stratégie complète qui garantit le résultat optimal depuis la position de départ, quels que soient les coups de l’adversaire.
- Fortement résolu : on connaît la stratégie optimale depuis n’importe quelle position légale du jeu, même celles qui ne surviendraient jamais dans une partie parfaite.
Le Morpion est fortement résolu. Pour chacune des positions possibles sur la grille 3×3, on sait exactement quel est le meilleur coup et quel sera le résultat si les deux joueurs jouent ensuite de manière optimale. C’est le niveau de résolution le plus complet qui soit.
L’arbre de jeu : 255 168 parties possibles
Pour comprendre comment le Morpion a été résolu, il faut d’abord comprendre la notion d’arbre de jeu. Un arbre de jeu est une représentation de toutes les parties possibles : chaque nœud représente une position, chaque branche représente un coup possible, et les feuilles représentent les résultats finaux (victoire de X, victoire de O, ou match nul).
Au Morpion, l’arbre de jeu est relativement modeste. Le premier joueur a 9 coups possibles. Le second en a ensuite 8, puis 7, et ainsi de suite. Le nombre total de séquences de coups est au maximum 9 ! = 362 880. Mais beaucoup de ces séquences se terminent avant que la grille ne soit remplie (un joueur gagne), ce qui réduit le nombre de parties complètes à exactement 255 168.
Ce chiffre peut sembler élevé, mais il est minuscule comparé aux autres jeux de stratégie. Les échecs ont un arbre de jeu estimé à 10120 positions, le Go à 10360. Même le Puissance 4, avec sa grille 7×6, possède environ 4,5 × 1012 positions. Le Morpion, avec ses 5 478 positions distinctes (en comptant les symétries), est un jeu d’une simplicité combinatoire exceptionnelle.
La démonstration par énumération
La preuve que le Morpion est un match nul avec un jeu parfait repose sur une méthode brutale mais infaillible : l’énumération complète. L’idée est simple : on explore systématiquement toutes les branches de l’arbre de jeu, de la racine (grille vide) jusqu’aux feuilles (fin de partie), en notant le résultat optimal de chaque position.
L’algorithme utilisé est le Minimax, un pilier de la théorie des jeux et de l’intelligence artificielle. Son principe est élégant : le joueur X cherche à maximiser son résultat (victoire = +1, nul = 0, défaite = -1), tandis que le joueur O cherche à le minimiser. En remontant depuis les feuilles vers la racine, on détermine la valeur optimale de chaque position.
Le résultat est sans appel : la valeur de la position initiale (grille vide) est 0, ce qui signifie match nul. Aucun premier coup ne permet à X de forcer la victoire, et aucune réponse de O ne lui permet de gagner non plus, à condition que les deux joueurs jouent de manière optimale.
Les symétries qui simplifient l’analyse
L’une des raisons pour lesquelles le Morpion a pu être résolu bien avant l’ère informatique est l’exploitation des symétries de la grille. Un carré possède huit symétries : quatre rotations (0°, 90°, 180°, 270°) et quatre réflexions (horizontale, verticale, et les deux diagonales).
Grâce à ces symétries, le premier coup n’offre pas vraiment 9 possibilités distinctes, mais seulement trois : jouer au centre, jouer dans un coin, ou jouer au milieu d’un côté. Toutes les autres positions sont équivalentes par rotation ou réflexion. Cette réduction considérable de l’espace de recherche a permis aux mathématiciens d’analyser le jeu à la main, dès le début du XXe siècle.
Les trois premiers coups : où tout se joue
Si le Morpion est un match nul avec un jeu parfait, cela ne signifie pas que tous les coups se valent. Le premier coup optimal est de jouer au centre ou dans un coin. Jouer au milieu d’un côté est légèrement inférieur : bien que cela mène aussi au match nul avec un jeu parfait des deux côtés, cela laisse moins de possibilités de piéger un adversaire imparfait.
Si X joue au centre, O doit impérativement répondre dans un coin pour maintenir l’égalité. Répondre au milieu d’un côté donne à X la possibilité de forcer la victoire. Si X joue dans un coin, O doit répondre au centre ; toute autre réponse mène à une défaite forcée.
C’est dans ces premiers échanges que se concentre la richesse stratégique du jeu. Un joueur parfait ne gagnera jamais, mais un joueur presque parfait peut perdre dès le deuxième coup.
Les autres jeux résolus : une famille grandissante
Le Morpion n’est pas le seul jeu à avoir été résolu. Voici quelques exemples célèbres :
- Le Puissance 4 : résolu en 1988 par Victor Allis. Le premier joueur gagne avec un jeu parfait en jouant au centre.
- Le jeu de Nim : résolu dès 1901 par Charles Bouton. La stratégie gagnante repose sur le calcul binaire (XOR des tas).
- Le Qubic (Morpion 3D sur 4×4×4) : résolu en 1980. Le premier joueur gagne.
- Les Dames (variante anglaise, 8×8) : résolu en 2007 par Jonathan Schaeffer après 18 ans de calculs. Résultat : match nul.
En revanche, les échecs restent non résolus malgré des siècles d’étude. L’arbre de jeu est tout simplement trop vaste pour être exploré complètement, même par les ordinateurs les plus puissants. Le Go, avec son plateau 19×19, est encore plus loin d’être résolu.
Le Morpion et les variantes : quand la résolution change tout
Le fait que le Morpion soit résolu a directement inspiré la création de variantes plus complexes. L’Ultimate Tic-Tac-Toe, par exemple, a été conçu précisément pour échapper à la résolution : son arbre de jeu est si vaste qu’aucun ordinateur n’a pu l’explorer complètement.
Le Gomoku sur grille 15×15 a été résolu (victoire du premier joueur), ce qui a conduit à l’invention du Renju, qui impose des restrictions au premier joueur pour rééquilibrer le jeu. C’est un schéma récurrent dans l’histoire des jeux de stratégie : quand un jeu est résolu, la communauté invente une variante plus complexe pour retrouver l’incertitude.
Pourquoi le Morpion reste amusant malgré tout
Si le Morpion est résolu, pourquoi y joue-t-on encore ? La réponse tient en un mot : l’imperfection. La stratégie parfaite existe, mais les joueurs humains ne la suivent pas toujours. La fatigue, l’inattention, la précipitation créent des ouvertures que l’adversaire peut exploiter.
Le Morpion reste un excellent jeu d’initiation à la pensée stratégique. Pour les enfants qui le découvrent, chaque partie est un puzzle inédit où la notion de menace, de blocage et d’anticipation se construit progressivement. L’apprentissage passe par l’erreur, et c’est précisément l’erreur qui rend le jeu vivant.
De plus, le Morpion possède des qualités irremplaçables : il ne nécessite aucun matériel (un bout de papier suffit), ses règles s’expliquent en trente secondes, et une partie dure moins d’une minute. Cette accessibilité absolue en fait un jeu universel, joué dans toutes les cultures depuis des siècles.
Ce que le Morpion résolu nous apprend
Au-delà du jeu lui-même, la résolution du Morpion illustre des concepts fondamentaux de la théorie des jeux et de l’informatique. Elle montre qu’un problème apparemment simple peut être analysé de manière exhaustive et définitive. Elle démontre la puissance de l’algorithme Minimax, utilisé aujourd’hui dans d’innombrables applications, des échecs informatiques à la planification stratégique.
Le Morpion est aussi un rappel d’humilité : même dans le jeu le plus simple qui soit, le jeu parfait exige une rigueur que la plupart des joueurs humains ne maintiennent pas. C’est cet écart entre la théorie et la pratique qui fait toute la beauté des jeux de stratégie - et qui nous ramène, partie après partie, à cette grille de 3×3 intemporelle.