Pour le premier coup, X a $9$ cases possibles. Pour chacune, O a $8$ cases libres. D'après le principe multiplicatif, il y a donc $9 \times 8 = 72$ façons de jouer les deux premiers coups, puis $9 \times 8 \times 7 = 504$ façons de jouer les trois premiers.

Une suite de $k$ coups, c'est une liste ordonnée de $k$ cases distinctes choisies parmi $9$ : c'est un $k$-uplet d'éléments distincts d'un ensemble à $9$ éléments. Leur nombre est

Imaginons qu'on joue toujours jusqu'à remplir les neuf cases, même après un alignement. Une partie est alors une façon d'ordonner les neuf cases, c'est-à-dire une permutation de l'ensemble des cases :

Ce nombre est un majorant, pas le nombre de parties : une partie s'arrête dès qu'un joueur aligne trois symboles. Beaucoup de permutations décrivent donc la même partie, prolongée de façons différentes après la victoire.

Personne ne peut gagner avant le cinquième coup, puisqu'il faut trois symboles alignés et que X n'en a que trois après le cinquième coup. Comptons les parties qui s'arrêtent au cinquième coup.

Le même raisonnement se complique d'un détail, et ce détail est instructif. O gagne au coup $6$ : ses trois ronds forment un alignement ($8$ choix, puis $3! = 6$ ordres), et X a joué trois coups, dans l'ordre, parmi les $6$ autres cases, soit $6 \times 5 \times 4 = 120$ suites. Mais il faut retirer les cas où les trois croix sont alignées : X aurait alors gagné dès le coup $5$, et la partie se serait arrêtée.

• Si l'alignement de O est une ligne ou une colonne ($6$ cas), les six autres cases forment deux lignes (ou deux colonnes) complètes : X a $2$ alignements possibles, chacun dans $3! = 6$ ordres. Il reste $120 - 12 = 108$ suites.
• Si l'alignement de O est une diagonale ($2$ cas), les six autres cases ne contiennent aucun alignement complet : les $120$ suites conviennent.

Au total, il y a

parties gagnées par O au sixième coup.

Pour les coups suivants, les cas à exclure se multiplient, et le calcul à la main devient pénible. On confie alors le travail à un programme. L'idée est récursive : le nombre de parties qui partent d'une position est égal à $1$ si la position est finale (victoire ou grille pleine), et sinon à la somme des nombres de parties qui partent de chacune des positions obtenues en jouant un coup. Le programme mémorise les positions déjà traitées, ce qui évite de refaire le même calcul des milliers de fois.

Le programme trouve $255\,168$ parties : $131\,184$ gagnées par X, $77\,904$ gagnées par O et $46\,080$ nulles. Il confirme les deux valeurs calculées à la main.

Sur les $127\,872$ parties qui vont jusqu'au neuvième coup, $81\,792$ sont gagnées par X au dernier coup et $46\,080$ sont nulles.

Une position est l'état de la grille, sans tenir compte de l'ordre dans lequel les coups ont été joués. Après $k$ coups, X a joué $\lceil k/2 \rceil$ fois et O a joué $\lfloor k/2 \rfloor$ fois. Pour décrire la position, on choisit les cases de X, puis celles de O parmi les cases restantes : ce sont des combinaisons. Par exemple après $4$ coups :

Le même calcul pour chaque valeur de $k$ donne le tableau suivant.

La somme de ces dix nombres vaut $6\,046$.

Ce total compte encore des grilles impossibles, par exemple celles où les deux joueurs ont un alignement, ou celles où le jeu aurait dû s'arrêter plus tôt. Le programme précédent, qui ne parcourt que les positions réellement atteintes, en trouve $5\,478$.

Faire tourner la grille ou la retourner ne change rien au jeu. Les transformations qui laissent le carré en place sont au nombre de huit : l'identité, les rotations d'un quart de tour, d'un demi-tour et de trois quarts de tour, et les quatre symétries axiales (par rapport aux deux médianes et aux deux diagonales). Une même position peut donc être dessinée de huit façons, parfois moins si elle est elle-même symétrique.

Premier coup. Les $9$ cases se rangent en trois familles : le centre (1 case), les coins (4 cases) et les bords (4 cases). Par symétrie, il n'y a que $3$ premiers coups vraiment différents.

Deux premiers coups. On examine chacun des trois premiers coups de X.

• X au centre : O joue dans un coin ou sur un bord, soit $2$ cas.
• X dans un coin : la diagonale qui passe par ce coin est un axe de symétrie. O peut jouer au centre, dans le coin opposé, dans un coin voisin (les deux sont symétriques), sur un bord voisin (idem) ou sur un bord éloigné (idem) : $5$ cas.
• X sur un bord : la médiane qui passe par ce bord est un axe de symétrie. O peut jouer au centre, sur le bord opposé, sur un des deux autres bords, dans un coin voisin ou dans un coin éloigné : $5$ cas.

Il y a donc $2 + 5 + 5 = 12$ débuts de partie vraiment différents, au lieu de $72$.

Trois premiers coups. Le même travail, plus long, donne $38$ positions différentes. Pour l'ensemble du jeu, en remplaçant chaque position par la plus petite de ses huit images (dans l'ordre alphabétique de son écriture), un programme ramène les $5\,478$ positions à $765$ positions essentiellement différentes. C'est ce genre de réduction qui a rendu possible la machine MENACE, plus bas.

Au tic-tac-toe, il n'y a ni dé ni carte cachée : chaque joueur voit tout, et une partie dure au plus neuf coups. Pour de tels jeux, Ernst Zermelo a démontré en 1913 (à propos des échecs) un résultat remarquable : une seule des trois situations suivantes est vraie. Ou bien le premier joueur a une stratégie qui gagne à coup sûr, ou bien c'est le second, ou bien chacun des deux a une stratégie qui lui assure au moins le nul. On dit que le jeu a une valeur : $+1$, $-1$ ou $0$.

Le principe est un raisonnement « en remontant » : on connaît le résultat des positions finales ; on en déduit celui des positions à un coup de la fin, puis à deux coups, et ainsi de suite jusqu'à la grille vide. C'est exactement ce que fait l'algorithme minimax de la partie suivante.

Avant même de calculer, un raisonnement par l'absurde montre que O ne peut pas avoir de stratégie gagnante. Cet argument, dit de la « stratégie volée », est souvent attribué à John Nash, qui l'a utilisé pour un autre jeu, le Hex (voir le texte sur l'équilibre de Nash).

Ce raisonnement prouve que la valeur du jeu vaut $+1$ ou $0$, mais il ne dit pas laquelle, et il ne donne aucune stratégie. Pour trancher, il faut calculer.

On attribue à chaque position finale une valeur : $+1$ si X a gagné, $-1$ si O a gagné, $0$ si la partie est nulle. Quand c'est à X de jouer, il choisit le coup qui donne la valeur maximale ; quand c'est à O, il choisit la valeur minimale. D'où le nom minimax.

Prenons la position ci-dessous, où c'est à X de jouer, avec trois cases libres : $0$, $1$ et $4$.

• Si X joue en $0$ ou en $1$, O joue au centre et aligne la diagonale $2$-$4$-$6$ : ces deux coups valent $-1$.
• Si X joue au centre, il bloque cette diagonale et crée deux menaces à la fois : la diagonale $0$-$4$-$8$ et la colonne $1$-$4$-$7$. O ne peut en boucher qu'une, et X joue l'autre : ce coup vaut $+1$.

La valeur de la position est le maximum des trois : $\max(-1\,;\,-1\,;\,+1) = +1$. Une menace double comme celle-ci s'appelle une fourchette ; c'est l'arme principale du jeu.

Le programme suivant applique la même règle depuis la grille vide, en mémorisant les valeurs déjà calculées. Il affiche la valeur du jeu, puis la valeur de chacun des neuf premiers coups possibles de X.

Résultat : la valeur du jeu est $0$. Le tic-tac-toe est un jeu nul : si les deux joueurs jouent bien, personne ne gagne. Les neuf premiers coups valent tous $0$ : aucun premier coup ne perd, mais aucun ne gagne. Le coin est cependant le plus « piégeux » pour un adversaire humain : après X dans un coin, la seule réponse de O qui ne perd pas est le centre ; après X au centre, O doit jouer dans un coin, car toute réponse sur un bord perd.

L'idée de minimax a une portée qui dépasse ce jeu : en 1928, John von Neumann démontre le théorème du minimax pour les jeux à deux joueurs où ce que l'un gagne, l'autre le perd. C'est l'acte de naissance de la théorie des jeux, qui mène ensuite à l'équilibre de Nash et à ses applications en économie.

Le plateau ci-dessous est piloté par le même algorithme. Quand plusieurs coups ont la meilleure valeur, l'ordinateur en tire un au hasard, pour varier les parties. Il ne perd jamais : le mieux que l'on puisse obtenir est le nul. Une seule erreur, et il gagne.

En 1961, le chercheur britannique Donald Michie, qui avait travaillé pendant la guerre avec les décrypteurs de Bletchley Park, veut montrer qu'une machine peut apprendre à jouer sans qu'on lui donne de stratégie. N'ayant pas d'ordinateur à sa disposition, il en construit un avec des boîtes d'allumettes : MENACE, pour Matchbox Educable Noughts And Crosses Engine.

Une reconstitution moderne de MENACE, boîtes rangées selon le coup joué : une seule boîte (jaune) pour le premier coup, $12$ (vertes) pour le deuxième coup de MENACE, qui correspondent aux $12$ débuts de partie comptés plus haut, puis les boîtes du troisième et du quatrième coup. Photo : Matthew Scroggs, Wikimedia Commons, licence CC BY-SA 4.0.

• Chaque boîte correspond à une position où MENACE (qui joue X, en premier) doit jouer. Grâce aux symétries et en retirant les coups forcés, Michie se contente d'environ $300$ boîtes : le nombre de $304$ est celui que donnent les récits de l'expérience.
• Chaque boîte contient des perles de couleur, une couleur par case libre.
• Pour jouer, on prend la boîte de la position, on tire une perle au hasard, et on joue sur la case de sa couleur.
• Au départ, chaque case libre a quelques perles (d'après les récits : $4$ pour le premier coup, $3$ pour le deuxième, $2$ pour le troisième, $1$ pour le quatrième).
• À la fin de la partie, on récompense ou on punit chaque perle jouée : en cas de victoire, on la remet avec $3$ perles de plus de la même couleur ; en cas de nul, avec $1$ de plus ; en cas de défaite, on la retire.

MENACE ne « comprend » rien au jeu. Mais les coups qui mènent à la victoire deviennent plus probables, et ceux qui mènent à la défaite disparaissent peu à peu. Selon le récit de Michie, après quelques centaines de parties, MENACE obtenait le plus souvent le nul contre lui.

Une boîte contient par exemple $3$ perles rouges (case $0$), $1$ verte (case $4$) et $2$ bleues (case $8$). On tire une perle au hasard : chaque perle a la même probabilité, donc la probabilité de jouer la case $4$ est $\dfrac{1}{6}$. Si la case $4$ mène à une victoire, on ajoute $3$ perles vertes : la probabilité devient $\dfrac{4}{9}$. Si au contraire la case $0$ mène à une défaite, on retire une perle rouge, et la probabilité de jouer $0$ passe de $\dfrac{3}{6}$ à $\dfrac{2}{5}$.

Une partie de MENACE est une succession de tirages dans des boîtes différentes : la probabilité d'une partie est le produit des probabilités le long d'un chemin de l'arbre, comme dans un arbre pondéré de terminale.

La figure simule une MENACE qui joue $2\,000$ parties contre un adversaire choisi. Comme chez Michie, les positions symétriques partagent la même boîte ; une simplification : une boîte qui se vide est remplie à nouveau. Par paquets de $50$ parties, on trace la proportion de victoires, de nuls et de défaites de MENACE. Contre un adversaire qui joue au hasard, les victoires augmentent et les défaites diminuent nettement, sans disparaître. Contre l'adversaire parfait (minimax), qui ne perd jamais, MENACE ne peut pas gagner : en quelques centaines de parties, elle apprend à faire nul presque à chaque fois.

MENACE est un ancêtre de l'apprentissage par renforcement, la méthode qui a permis bien plus tard à des programmes d'apprendre le jeu de go en jouant contre eux-mêmes. Pour un autre modèle simple de machine qui apprend, voir le texte sur le neurone artificiel.

Sur une grande grille où il faut aligner cinq symboles (le « morpion » des cahiers à carreaux, appelé gomoku au Japon), le premier joueur a un avantage décisif : sur une grille de $15 \times 15$ et sans règle particulière, Victor Allis a montré par ordinateur, au début des années 1990, qu'il gagne à coup sûr. C'est pour cela que les compétitions ajoutent des règles qui gênent le premier joueur.

Le puissance 4 (une grille de $7$ colonnes et $6$ lignes, les pions tombent au fond) a été résolu en 1988, indépendamment par James Allen et par Victor Allis : le premier joueur gagne, à condition de commencer dans la colonne du milieu. Les dames anglaises ont été résolues en 2007 par l'équipe de Jonathan Schaeffer, après près de vingt ans de calculs : comme le tic-tac-toe, c'est un jeu nul.

En 1950, Claude Shannon, le fondateur de la théorie de l'information, estime le nombre de parties d'échecs. Son raisonnement est un principe multiplicatif approximatif : à chaque coup, un joueur a en moyenne une trentaine de possibilités, donc un coup blanc suivi d'un coup noir offre environ $30 \times 30 \approx 10^3$ possibilités. Une partie typique dure environ $40$ paires de coups, d'où

C'est un ordre de grandeur, pas un dénombrement exact, mais il suffit à montrer qu'aucun ordinateur ne pourra jamais parcourir toutes les parties comme on l'a fait pour le tic-tac-toe : on estime le nombre d'atomes de l'univers observable à environ $10^{80}$. Les programmes d'échecs utilisent donc minimax sur quelques coups seulement, puis une estimation de la position. Le dénombrement du jeu (grains de blé et suites géométriques, nombre de parties) est développé dans l'animation Échecs et mathématiques.

Au go, on pose des pierres sur les $361$ intersections d'une grille de $19 \times 19$ ; chaque intersection est vide, noire ou blanche. Il y a donc au plus $3^{361}$ positions. Le logarithme décimal donne l'ordre de grandeur :

et comme $\log 3 \approx 0{,}477$,

soit $3^{361} \approx 10^{172}$. Toutes ces grilles ne sont pas des positions autorisées : en 2016, John Tromp a calculé qu'il y en a environ $2{,}08 \times 10^{170}$, soit à peu près une sur $80$.

Pour un jeu aussi vaste, minimax seul est impuissant. En mars 2016, le programme AlphaGo de l'entreprise DeepMind bat pourtant le champion Lee Sedol, par quatre parties à une. Il combine des réseaux de neurones, qui estiment les positions et proposent des coups, des simulations de parties au hasard (une méthode de Monte-Carlo, voir le texte sur la méthode de Monte-Carlo) et un apprentissage par renforcement en jouant contre lui-même, dans l'esprit de MENACE.