Qui n’a pas joué au tic-tac-toe ? Que révèle une analyse mathématique de ce jeu ?

Le tic-tac-toe, aussi appelé « morpion » en France et « OXO » en Belgique, est un jeu de réflexion très simple qui se pratique entre deux joueurs. Placés devant une grille comportant neuf cases disposées sur trois lignes et trois colonnes, les opposants remplissent à tour de rôle l’une des cases vides de la grille en y apposant le symbole qui leur est attribué, soit un X ou un O.

Le gagnant du jeu est celui qui parvient le premier à aligner trois symboles identiques, horizontalement, verticalement ou en diagonale. En général, le symbole X est associé au premier joueur. Les origines du tic-tac-toe remontent, paraît-il, à l’Égypte antique et on en retrouve des variantes dans pratiquement toutes les civilisations.

La popularité du tic-tac-toe auprès des enfants ne se dément pas. Cependant, les adultes s’en lassent généralement très vite car une partie entre joueurs vigilants se solde presque invariablement par une nulle. En raison de sa relative simplicité, le jeu se prête bien à une étude mathématique qui lève le voile sur la façon de s’y prendre pour analyser d’autres jeux, déterminer si le premier joueur jouit d’un avantage ou trouver des stratégies gagnantes.

Combien y a-t-il de parties de tic-tac-toe possibles ?

De toute évidence, il existe un nombre fini de parties de tic-tac-toe distinctes et un répertoire complet de tous les matchs possibles permettrait, par simple dénombrement, de répondre à toutes les autres questions que l’on pourrait se poser à propos de ce jeu.

Par abus de langage, appelons X le premier joueur et O son adversaire. Puisqu’une grille de tic-tac-toe comporte neuf cases, X dispose de neuf choix au premier tour et O peut envisager huit réponses possibles. Au second tour, X a sept choix et O en a six, etc. Au final, il y a donc au plus

\[\begin{array} {r l l}9! &= &9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 \\&=& 362 880 \end{array}\]

parties possibles, mais il s’agit là d’une estimation conservatrice (une borne supérieure, en termes mathématiques) car plusieurs parties finissent bien avant le 9^e coup.

Pour compter le nombre de parties possibles, la façon la plus simple consiste à argumenter en fonction du nombre N de coups nécessaires pour qu’un joueur soit déclaré vainqueur ou qu’il y ait partie nulle. Il est clair que N ne peut varier qu’entre 5 et 9, car il faut au minimum trois X et deux O pour que le premier joueur soit déclaré vainqueur.

Les calculs requis sont présentés en encadré et résumés dans la première colonne du tableau 1. La seconde colonne donne quant à elle le nombre de parties possibles lorsque l’on tient compte des symétries. En effet, deux parties peuvent être considérées comme équivalentes si leur déroulement est le même, au prix de rotations ou de réflexions.

Ceci complique passablement les calculs, qui ne sont pas présentés ici, mais pour le premier coup, par exemple, on réalise rapidement que X n’a pas neuf choix mais bien trois : jouer au milieu, jouer sur une case adjacente au centre, ou alors jouer dans un coin.

On ne s’étonne pas, dès lors, que les nombres figurant dans la deuxième colonne soient environ neuf fois plus petits que ceux de la première colonne. Si le ratio n’est pas exactement égal à 9, cela vient du fait qu’il y a plusieurs manières de définir l’équivalence de deux parties par symétrie. On peut montrer par énumération qu’à l’issue d’une partie il y a 138 configurations possibles de X et de O, une fois les symétries prises en compte. De celles-ci, 91 sont favorables à X, 44 sont favorables à O et les 3 autres correspondent à des matchs nuls.

Tableau 1
Nombre de parties de tic-tac-toe possibles ventilées en fonction du nombre de coups joués. Colonne A : Énumération brute, telle que détaillée dans le premier encadré ; colonne B : énumération après prise en compte des symétries.

Quelle stratégie employer pour gagner ?

Lorsque les participants jouent strictement « au hasard » (sans prise en compte des symétries), la colonne A du tableau 1 montre que 131 184 parties sont gagnées par X, 77 904 sont gagnées par O et 46 080 parties, soit environ 18 % d’entre toutes, se soldent par un match nul. Dans ces conditions, il y a donc avantage à jouer le premier.

Dans la pratique, le pourcentage de parties nulles est beaucoup plus grand que 18 % car des joueurs le moindrement aguerris peuvent mettre en œuvre diverses stratégies pour s’assurer la victoire ou, du moins, éviter une défaite. Par exemple, on peut montrer que si X ne commet pas d’erreur, il ne peut jamais perdre s’il joue son premier coup dans un coin. Au pire, il fera match nul.

De fait, il existe une stratégie qui permet aussi à O de s’assurer de ne jamais perdre, ce qui relègue le tic-tac-toe au rang de jeu futile. Une stratégie optimale est décrite dans le second encadré, qui dicte le comportement à adopter par chacun des joueurs. C’est un bon exercice que de traduire ces règles en un programme informatique. Essayez !

C’est d’ailleurs le tic-tac-toe qui a l’honneur d’avoir été, dès 1952, le tout premier jeu vidéo programmé sur ordinateur. L’auteur du programme, l’informaticien britannique Alexander Sandy Douglas (1921-2010), était alors doctorant à l’Université de Cambridge.

Intéressé par l’interaction entre l’humain et la machine, il avait besoin d’un banc d’essai. Son programme était codé sur un ruban troué lu par EDSAC, un ordinateur de première génération, et transposé sur le tube à rayons cathodiques d’un oscilloscope (voir figure 1). Il s’agit là du tout premier exemple (primitif) d’intelligence artificielle, puisque c’était l’ordinateur qui déterminait ses propres coups.

Figure 1 :
Photographie de l’Electronic Delay Storage Automatic Calculator (EDSAC), ordinateur de première génération mis en service en 1949 à l’Université de Cambridge, Royaume-Uni.

La simplicité du tic-tac-toe n’a pas non plus empêché des célébrités de s’y intéresser, notamment l’informaticien Allen Newell (1927-1992) et le célèbre Herbert Simon (1916-2001), lauréat du Prix dit Nobel d’économie en 1978. En début de carrière, ces deux chercheurs affiliés à l’Université Carnegie- Mellon de Pittsburgh s’intéressaient à la psychologie cognitive. Ceci les a amenés à mettre au point, en 1959, un programme capable en principe de résoudre n’importe quel problème formalisé, qu’il s’agisse de démonstrations de théorèmes, de problèmes géométriques ou de parties d’échecs. Leur algorithme, baptisé GPS (abréviation de General Problem Solver), a effectivement permis de solutionner des problèmes relativement simples tels que le tic-tac-toe et le jeu des tours de Hanoï, mais il est facilement victime de l’explosion combinatoire, caractérisée par la croissance exponentielle du nombre de solutions possibles.

Généralisations

Le tic-tac-toe est un exemple de jeu de type (m, n, k) dans lequel deux adversaires jouent tour à tour sur une grille de taille m × n jusqu’à ce que l’un d’entre eux réussisse le premier à aligner k symboles sur une ligne, une colonne ou une diagonale (dont la définition doit être précisée). Dans le tic-tac-toe, on a m = n = k = 3 et le Gomoku style libre, qui a des millions d’adeptes en Extrême-Orient, correspond au cas m = n = 15 et k = 5.

Un argument classique de théorie des jeux montre que dans un jeu de type (m, n, k), il n’existe aucune stratégie qui assure une victoire au second joueur. Ceci vient du fait que nul ne saurait être désavantagé s’il peut jouer un coup de plus que son adversaire.

Supposons en effet que le second joueur dispose d’une stratégie gagnante. Le premier joueur peut alors commencer par jouer un coup arbitraire et adopter ensuite la stratégie gagnante de l’autre ! Il peut toujours le faire sauf si la stratégie en question exige de jouer là où il l’a lui-même fait au premier coup. Si cela se produit, le premier joueur peut cependant jouer un autre coup arbitraire et adopter ensuite la stratégie gagnante du second joueur. Puisqu’un coup de plus ne peut pas le désavantager, il dispose donc d’une stratégie gagnante. On aboutit ainsi à une contradiction, ce qui montre qu’il n’existe pas de stratégie gagnante pour le second joueur.

Évidemment, cet argument ne renseigne pas quant à la meilleure stratégie à adopter. Il ne permet pas non plus de déterminer si une telle stratégie est garante d’une victoire pour le premier joueur ou si elle ne lui permet que d’éviter la défaite. On peut donc chercher à classifier les jeux de type (m, n, k). Par exemple, une recherche intensive sur ordinateur, menée par l’informaticien néerlandais Louis Victor Allis (1965- ), a permis de montrer l’existence d’une stratégie gagnante pour le premier joueur dans une certaine version du Gomoku.

Faits cocasses

Figure 2  : Carré magique d’ordre 3

Le tic-tac-toe peut prendre des formes parfois inattendues et déroutantes. C’est le cas du scrabble numérique, dans lequel deux joueurs choisissent en alternance et sans remise des nombres entre 1 et 9. Le gagnant est le premier qui obtient une somme de 15 et si nul ne réussit, la partie est … nulle. En disposant les nombres de 1 à 9 dans un carré magique, comme dans la figure 2, on constate rapidement que pratiquer ce jeu revient effectivement à jouer au tic-tac-toe.

Tout comme aux échecs, on peut pratiquer le tic-tac-toe à trois dimensions, mais ce jeu-là est encore plus trivial que la version classique car le premier des deux concurrents peut très facilement l’emporter en jouant son premier coup au centre.

Jeu de Qubic

La version jouée sur un cube 4 × 4 × 4 s’appelle Qubic. L’informaticien américain Oren Patashnik (1954- ), qui a fait sa thèse sous la direction du légendaire Donald Knuth (1938- ), a montré en 1980 que le premier joueur peut toujours vaincre. Sa démonstration, réalisée par ordinateur, a nécessité plus de 1500 heures de calcul. La stratégie à employer est toutefois très compliquée et difficile à mémoriser pour la plupart des gens. Sachant que Knuth a été un pionnier de l’algorithmique et le concepteur du logiciel de traitement de texte LaTeX très répandu en recherche, on ne s’étonnera pas que Patashnik ait été l’un des auteurs du programme BibTeX qui permet de compiler rapidement des références bibliographiques.

Pour en s\(\alpha\)voir plus !

• NEWELL, A., SIMON, H.A. (1972). Human Problem Solving. Prentice-Hall, Englewood Cliffs, NJ.

PDF