Le Tic-Tac-Toe : Mathématiques d’un jeu « simple »

Qui n’a jamais joué au morpion ? Ce petit jeu de grille 3 \times 3, aussi appelé Tic-Tac-Toe, semble tellement simple qu’on s’en lasse vite. Pourtant, derrière cette apparente simplicité se cachent des résultats mathématiques profonds : combinatoire, théorie des jeux, et même théorie des groupes. Plongeons dans l’analyse complète de ce classique !

Formalisation du jeu

Définition

Le Tic-Tac-Toe se joue sur une grille 3 \times 3. Deux joueurs, X et O, jouent alternativement. X commence. Le premier à aligner 3 symboles (horizontalement, verticalement ou diagonalement) gagne. Si la grille est remplie sans vainqueur, c’est un match nul.

Numérotons les cases :

\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 4 & 5 & 6 \\ \hline 7 & 8 & 9 \\ \hline \end{array}

Les 8 lignes gagnantes

Il existe exactement 8 façons de gagner :

– 3 lignes horizontales : \{1,2,3\}, \{4,5,6\}, \{7,8,9\}

– 3 colonnes verticales : \{1,4,7\}, \{2,5,8\}, \{3,6,9\}

– 2 diagonales : \{1,5,9\}, \{3,5,7\}

Dénombrement : d’où viennent les 255 168 parties ?

Comptage naïf

Si on ignore les victoires prématurées, le nombre de façons de remplir la grille serait :

 9! = 362\,880

Mais une partie peut se terminer avant que la grille soit pleine !

Comptage exact par récurrence

Une partie est une séquence de coups (c_1, c_2, \ldots, c_k) où :

– c_i \in \{1, \ldots, 9\} sont distincts

– La partie se termine quand un joueur gagne ou quand k = 9

Notons P(k) le nombre de parties se terminant exactement au coup k :

Calcul détaillé pour k = 5 (première victoire possible)

Pour que X gagne au 5ème coup :

1. X a joué 3 coups formant une ligne gagnante

2. O a joué 2 coups qui ne bloquent pas

3. Le 3ème X doit être le coup gagnant (pas de victoire prématurée au coup 3)

Il y a 8 lignes gagnantes. Pour une ligne donnée L = \{a, b, c\} :

– Choix de l’ordre des 3 coups de X sur L : 3! façons

– Mais le dernier coup doit être le gagnant, donc les 2 premiers X sont placés librement : 3 \times 2 = 6 ordres

– Choix des 2 cases pour O parmi les 6 restantes : \binom{6}{2} = 15

– Ordre des 2 coups de O : 2! = 2

Donc :

P(5) = 8 \times 3! \times \binom{6}{2} \times 2! = 8 \times 6 \times 15 \times 2 = 1\,440

Calcul détaillé pour k = 6 (première victoire de O)

Le cas k = 6 est plus subtil car il faut s’assurer que X n’a pas déjà gagné au coup 5.

Conditions pour une partie de longueur 6 :

1. O place 3 pions formant une ligne gagnante L_O
2. X place 3 pions sur les 6 cases restantes
3. Les 3 pions de X ne forment pas de ligne gagnante

Étape 1 : Choisir la ligne de O et les cases de X

Fixons une ligne L_O parmi les 8 possibles. Les 6 cases restantes forment l’ensemble R.

Combien de triplets de cases dans R forment une ligne gagnante ? Ça dépend du type de L_O :

Cas 1 : L_O est une ligne horizontale ou une colonne (6 cas)

Exemple : si O prend la ligne du haut {1,2,3}, il reste {4,5,6,7,8,9}. Les lignes gagnantes entièrement dans ces cases sont {4,5,6} et {7,8,9} → 2 lignes interdites pour X.

Cas 2 : L_O est une diagonale (2 cas)

Exemple : si O prend la diagonale {1,5,9}, il reste {2,3,4,6,7,8}. L’autre diagonale {3,5,7} contient le 5… qui n’est plus disponible ! → 0 ligne interdite pour X.

Observation clé : Les deux diagonales passent toutes les deux par le centre (case 5). Donc si O en prend une, X ne peut jamais compléter l’autre.

Étape 2 : Compter les configurations valides pour X

• Si L_O est une ligne ou colonne (6 cas) : \binom{6}{3} - 2 = 20 - 2 = 18 configs
• Si L_O est une diagonale (2 cas) : \binom{6}{3} - 0 = 20 configs

Étape 3 : Compter les ordres de jeu

Une partie de 6 coups est une permutation des 6 cases choisies. L’ordre est contraint :

• X joue aux tours 1, 3, 5 (impairs)

• O joue aux tours 2, 4, 6 (pairs)

Pour des cases fixées (3 pour X, 3 pour O), le nombre d’ordres est 3! \times 3! = 36.

Calcul final

P(6) = \underbrace{6 \times 18 \times 36}_{\text{lignes/colonnes}} + \underbrace{2 \times 20 \times 36}_{\text{diagonales}}

On obtient ainsi,

P(6) = 3\,888 + 1\,440 = 5\,328 

Vérification par Python

Voici une vérification naïve permettant de simuler le nombre de parties.

from itertools import permutations
LIGNES = [{1,2,3}, {4,5,6}, {7,8,9},
          {1,4,7}, {2,5,8}, {3,6,9},
          {1,5,9}, {3,5,7}]
def gagnant(coups_x, coups_o):
    for ligne in LIGNES:
        if ligne <= coups_x:
            return 'X'
        if ligne <= coups_o:
            return 'O'
    return None
def compter_parties():
    total = 0
    victoires_X, victoires_O, nuls = 0, 0, 0
    for partie in permutations(range(1, 10)):
        coups_x, coups_o = set(), set()
        for i, coup in enumerate(partie):
            if i % 2 == 0:
                coups_x.add(coup)
            else:
                coups_o.add(coup)
            g = gagnant(coups_x, coups_o)
            if g == 'X':
                victoires_X += 1
                break
            elif g == 'O':
                victoires_O += 1
                break
        else:
            nuls += 1
        total += 1
    return total, victoires_X, victoires_O, nuls
# Résultat : (131184, 77904, 46080)
# Total : 255 168

Résultat final

\boxed{\text{Nombre total de parties} = 255\,168}

Répartition :

• Victoires de X : 131\,184 soit \approx 51.4\%
• Victoires de O : 77\,904 soit \approx 30.5\%
• Matchs nuls : 46\,080 soit \approx 18.1\%

Symétries du plateau : le groupe diédral D_4

Les 8 isométries

Voici un résultat élégant de théorie des jeux : dans tout jeu (m, n, k), le second joueur (O) ne peut jamais disposer d’une stratégie gagnante.

L’argument est surprenant : supposons par l’absurde que O dispose d’une telle stratégie. Alors X pourrait commencer par jouer un coup arbitraire, puis « voler » la stratégie de O ! En effet, avoir un pion supplémentaire sur le plateau ne peut jamais être un désavantage. Cette contradiction montre que O ne peut pas avoir de stratégie gagnante.

Action sur les cases

Le carré possède un groupe de symétrie D_4 d’ordre 8 :

• 4 rotations : R_0 (identité), R_{90}, R_{180}, R_{270}
• 4 réflexions : horizontale, verticale, et les 2 diagonales

Classes d’équivalence des cases

Sous l’action de D_4, les 9 cases se répartissent en * orbites :

• Coins : \{1, 3, 7, 9\} — 4 cases équivalentes
• Bords : \{2, 4, 6, 8\} — 4 cases équivalentes
• Centre : \{5\} — 1 case unique

Conséquence : Pour analyser le premier coup, il suffit d’étudier 3 cas !

Théorème du vol de stratégie

Les jeux (m, n, k) : une famille de jeux

Le Tic-Tac-Toe est un cas particulier d’une famille plus large appelée jeux (m, n, k) :

• Grille de taille m \times n
• Le premier à aligner k symboles gagne
• Le Tic-Tac-Toe correspond à m = n = k = 3

Autres exemples : le Gomoku (15 \times 15, aligner 5), le Puissance 4 (7 \times 6, aligner 4 avec gravité).

Enoncé

Théorème : Dans tout jeu (m, n, k), le second joueur ne peut pas avoir de stratégie gagnante.

Preuve par l’absurde

Supposons que O possède une stratégie gagnante \mathcal{S}.

1. X joue un premier coup arbitraire sur une case c_1
2. X « vole » la stratégie de O : il imagine qu’il est O et applique \mathcal{S}
3. Quand \mathcal{S} recommande de jouer sur c_1 (déjà occupée par X), X joue ailleurs arbitrairement et « oublie » ce pion supplémentaire
4. Observation clé : avoir un pion de plus ne peut jamais être un désavantage dans ce jeu (propriété de monotonie)
5. Donc X, en appliquant \mathcal{S} avec un pion bonus, devrait aussi gagner
6. Contradiction : \mathcal{S} ne peut pas faire gagner les deux joueurs !

Conclusion

\boxed{\text{Le second joueur ne peut pas avoir de stratégie gagnante}}

Autrement dit : soit X gagne avec un jeu parfait, soit c’est match nul.

Analyse complète : COIN vs CENTRE vs BORD

C’est la question stratégique : quel est le meilleur premier coup ? Analysons chaque option en détail.

Propriétés de chaque case

Premier coup au COIN (case 1)

Analysons l’arbre de jeu quand X commence en case 1.

Après X=1, les réponses de O :

\begin{array}{|c|c|c|} \hline \mathbf{X} & ? & ? \\ \hline ? & ? & ? \\ \hline ? & ? & ? \\ \hline \end{array}

Par symétrie, O a seulement 3 réponses distinctes :

• Centre (5) : La seule réponse qui garantit le nul
• Coin opposé (9) : Permet à X de créer une fourchette !
• Bord (2, 4, 6, 8) : Permet à X de créer une fourchette !
• Coin adjacent (3 ou 7) : Permet à X de créer une fourchette !

Cas critique : O joue coin opposé (case 9)

\begin{array}{|c|c|c|} \hline X & \cdot & \cdot \\ \hline \cdot & \cdot & \cdot \\ \hline \cdot & \cdot & O \\ \hline \end{array}

Si X joue maintenant en case 3 :

\begin{array}{|c|c|c|} \hline X & \cdot & X \\ \hline \cdot & \cdot & \cdot \\ \hline \cdot & \cdot & O \\ \hline \end{array}

X menace \{1, 2, 3\}. O doit bloquer en 2. Puis X joue en 7 :

\begin{array}{|c|c|c|} \hline X & O & X \\ \hline \cdot & \cdot & \cdot \\ \hline X & \cdot & O \\ \hline \end{array}

Fourchette ! X menace \{1, 4, 7\} ET \{3, 5, 7\}. O ne peut bloquer qu’une seule → X gagne !

Cas critique : O joue sur un bord (case 2)

\begin{array}{|c|c|c|} \hline X & O & \cdot \\ \hline \cdot & \cdot & \cdot \\ \hline \cdot & \cdot & \cdot \\ \hline \end{array}

X joue au centre (5) :

\begin{array}{|c|c|c|} \hline X & O & \cdot \\ \hline \cdot & X & \cdot \\ \hline \cdot & \cdot & \cdot \\ \hline \end{array}

X menace \{1, 5, 9\}. O bloque en 9. X joue en 7 :

\begin{array}{|c|c|c|} \hline X & O & \cdot \\ \hline \cdot & X & \cdot \\ \hline X & \cdot & O \\ \hline \end{array}

Fourchette ! X menace \{1, 4, 7\} ET \{3, 5, 7\}. → X gagne !

Seule défense : O joue au centre

\begin{array}{|c|c|c|} \hline X & \cdot & \cdot \\ \hline \cdot & O & \cdot \\ \hline \cdot & \cdot & \cdot \\ \hline \end{array}

Maintenant X doit jouer dans le coin opposé (9) pour maintenir la pression :

\begin{array}{|c|c|c|} \hline X & \cdot & \cdot \\ \hline \cdot & O & \cdot \\ \hline \cdot & \cdot & X \\ \hline \end{array}

O doit jouer sur un bord pour bloquer, et avec un jeu parfait → Match nul.

Premier coup au CENTRE (case 5)

\begin{array}{|c|c|c|} \hline \cdot & \cdot & \cdot \\ \hline \cdot & \mathbf{X} & \cdot \\ \hline \cdot & \cdot & \cdot \\ \hline \end{array}

Réponses de O (par symétrie, 2 cas distincts) :

• Coin (1, 3, 7, 9) : La seule réponse qui garantit le nul
• Bord (2, 4, 6, 8) : Permet à X de gagner !

Cas critique : O joue sur un bord (case 2)

\begin{array}{|c|c|c|} \hline \cdot & O & \cdot \\ \hline \cdot & X & \cdot \\ \hline \cdot & \cdot & \cdot \\ \hline \end{array}

X joue dans un coin non adjacent au bord de O, par exemple case 7 :

\begin{array}{|c|c|c|} \hline \cdot & O & \cdot \\ \hline \cdot & X & \cdot \\ \hline X & \cdot & \cdot \\ \hline \end{array}

X menace \{3, 5, 7\}. O bloque en 3. X joue en 1 :

\begin{array}{|c|c|c|} \hline X & O & O \\ \hline \cdot & X & \cdot \\ \hline X & \cdot & \cdot \\ \hline \end{array}

Fourchette ! X menace \{1, 4, 7\} ET \{1, 5, 9\}. → X gagne !

Défense correcte : O joue dans un coin

Avec O dans un coin, la partie se termine en match nul avec un jeu parfait.

Premier coup sur un BORD (case 2)

\begin{array}{|c|c|c|} \hline \cdot & \mathbf{X} & \cdot \\ \hline \cdot & \cdot & \cdot \\ \hline \cdot & \cdot & \cdot \\ \hline \end{array}

C’est le pire premier coup ! La case 2 n’appartient qu’à 2 lignes gagnantes.

O répond au centre (5) :

\begin{array}{|c|c|c|} \hline \cdot & X & \cdot \\ \hline \cdot & O & \cdot \\ \hline \cdot & \cdot & \cdot \\ \hline \end{array}

Maintenant O contrôle le centre et peut facilement forcer le nul. X n’a aucune possibilité de fourchette si O joue correctement.

Tableau récapitulatif

Conclusion stratégique

\boxed{\text{Le COIN est le meilleur premier coup}}

Le centre est un bon coup, mais légèrement inférieur car il laisse moins d’opportunités d’exploiter les erreurs adverses.

Algorithme du jeu parfait

Voici l’algorithme complet pour ne jamais perdre :

FONCTION jouer(position):
    1. SI je peux gagner → jouer le coup gagnant
    2. SI l'adversaire peut gagner → bloquer
    3. SI je peux créer une fourchette → la créer
    4. SI l'adversaire peut créer une fourchette:
        4a. SI je peux bloquer en créant une menace → le faire
        4b. SINON → occuper la case de fourchette
    5. SI le centre est libre → jouer au centre
    6. SI l'adversaire est dans un coin ET le coin opposé est libre:
        → jouer dans le coin opposé
    7. SI un coin est libre → jouer dans un coin
    8. SINON → jouer sur un bord libre

Et voici son implémentation en Python

def meilleur_coup(grille, joueur):
    adversaire = 'O' if joueur == 'X' else 'X'
    # 1. Gagner si possible
    for coup in cases_libres(grille):
        if est_gagnant(jouer(grille, coup, joueur), joueur):
            return coup
    # 2. Bloquer la victoire adverse
    for coup in cases_libres(grille):
        if est_gagnant(jouer(grille, coup, adversaire), adversaire):
            return coup
    # 3. Créer une fourchette
    for coup in cases_libres(grille):
        if cree_fourchette(jouer(grille, coup, joueur), joueur):
            return coup
    # 4. Bloquer les fourchettes adverses
    fourchettes_adv = [c for c in cases_libres(grille)
                       if cree_fourchette(jouer(grille, c, adversaire), adversaire)]
    if len(fourchettes_adv) == 1:
        return fourchettes_adv[0]
    elif len(fourchettes_adv) > 1:
        # Forcer l'adversaire à défendre
        for coup in cases_libres(grille):
            if cree_menace(jouer(grille, coup, joueur), joueur):
                # Vérifier que la défense ne crée pas de fourchette
                defense = case_menacee(jouer(grille, coup, joueur), joueur)
                if defense not in fourchettes_adv:
                    return coup
    # 5. Centre
    if 5 in cases_libres(grille):
        return 5
    # 6. Coin opposé
    coins_opposes = [(1,9), (9,1), (3,7), (7,3)]
    for (c1, c2) in coins_opposes:
        if grille[c1] == adversaire and c2 in cases_libres(grille):
            return c2
    # 7. Coin libre
    for coin in [1, 3, 7, 9]:
        if coin in cases_libres(grille):
            return coin
    # 8. Bord libre
    for bord in [2, 4, 6, 8]:
        if bord in cases_libres(grille):
            return bord

Généralisation : les jeux (m, n, k)

Définition

Un jeu (m, n, k) se joue sur une grille m \times n. Le premier joueur à aligner k symboles gagne.

Résultats connus

• Pour k \geq 8, le jeu (n, n, k) est toujours nul (théorème de Hales-Jewett)
• Pour k = 5 sur plateau infini, le premier joueur gagne

Complexité et chiffres clés du Tic-Tac-Toe

Conclusion

Ce « simple » jeu d’enfant cache une richesse mathématique insoupçonnée : dénombrement, théorie des groupes, théorie des jeux, algorithmique…

À retenir :

– Commencez toujours par un coin

– Le centre est la seule bonne réponse au coin

– Les fourchettes sont la clé de la victoire

– Avec un jeu parfait, personne ne gagne

Le Tic-Tac-Toe est la porte d’entrée idéale vers la théorie des jeux combinatoires. La prochaine fois que vous jouerez au morpion, vous saurez que derrière chaque coup se cache un arbre de 255\,168 parties possibles !