Le Morpion et la théorie de l'information : combien de bits pour décrire une partie complète
Le Morpion est le jeu le plus simple du monde. Neuf cases, deux symboles, des parties qui durent rarement plus de quelques secondes. Et pourtant, quand on le regarde à travers le prisme de la théorie de l'information - cette branche des mathématiques fondée par Claude Shannon en 1948 - le Morpion révèle une richesse insoupçonnée. Combien de bits faut-il pour décrire une partie complète ? Combien d'information contient chaque coup ? Le Morpion en ligne est un terrain de jeu parfait pour explorer ces questions fondamentales qui connectent les mathématiques, l'informatique et la stratégie.
Le bit : l'unité de mesure de l'information
Avant de compter les bits d'une partie de Morpion, rappelons ce qu'est un bit. Le bit (binary digit) est l'unité fondamentale d'information. Un bit répond à une seule question par oui ou par non, par 0 ou par 1. Claude Shannon a montré en 1948 que toute information - un texte, une image, une mélodie, une partie de jeu - peut être mesurée en bits. La formule de Shannon calcule le contenu informationnel d'un événement en fonction de sa probabilité : plus un événement est improbable, plus il contient d'information.
Concrètement, si vous devez choisir entre deux options équiprobables, il vous faut 1 bit d'information pour décrire votre choix. Entre quatre options, il faut 2 bits. Entre huit options, 3 bits. La formule générale est le logarithme en base 2 du nombre d'options : log2(n) bits. C'est une mesure de la "surprise" associée à un événement - plus le choix est vaste, plus le résultat est surprenant, plus il contient d'information.
Appliquée au Morpion, cette mesure nous permet de quantifier exactement la complexité informationnelle de chaque coup et de chaque partie. Ce qui semblait trivial devient soudain mesurable et comparable à d'autres jeux.
Compter les bits coup par coup
Au premier coup d'une partie de Morpion, le joueur choisit parmi 9 cases vides. L'information contenue dans ce choix est log2(9) = 3,17 bits. C'est l'information maximale d'un coup au Morpion : au début de la partie, tout est ouvert, et le choix est le plus riche possible.
Au deuxième coup, il ne reste que 8 cases disponibles. L'information est log2(8) = 3 bits exactement. Au troisième coup, 7 cases : log2(7) = 2,81 bits. Et ainsi de suite. Chaque coup contient moins d'information que le précédent, car le nombre de choix diminue. Au neuvième et dernier coup d'une partie qui va jusqu'au bout, il ne reste qu'une seule case : log2(1) = 0 bit. Le dernier coup ne contient aucune information - il est entièrement déterminé.
Si on additionne l'information de tous les coups d'une partie qui remplit les 9 cases, on obtient : log2(9!) = log2(362 880) = environ 18,5 bits. C'est le contenu informationnel maximal d'une partie complète de Morpion. Dix-huit bits et demi suffisent pour décrire entièrement n'importe quelle séquence de neuf coups sur une grille 3x3. C'est remarquablement peu - moins que la taille d'un emoji en mémoire informatique.
L'entropie d'une partie réelle : moins de 18 bits
Le calcul précédent suppose que chaque coup est choisi uniformément au hasard parmi les cases disponibles. Mais les joueurs humains ne jouent pas au hasard. Un joueur qui connaît la stratégie optimale du Morpion fait des choix prévisibles - et un choix prévisible contient moins d'information qu'un choix aléatoire. C'est le concept d'entropie de Shannon : l'entropie mesure l'information moyenne d'une source, en tenant compte des probabilités de chaque message.
Prenons le premier coup. En théorie, 9 choix sont possibles. Mais en pratique, la grande majorité des joueurs expérimentés commencent par le centre. Si 80% des joueurs choisissent le centre, l'entropie du premier coup n'est plus 3,17 bits mais seulement environ 1,5 bit. Le coup est devenu partiellement prévisible, et sa valeur informationnelle a chuté. L'information d'un coup dépend non pas du nombre de choix possibles, mais de leur distribution de probabilité.
En prenant en compte les habitudes des joueurs réels, l'entropie totale d'une partie de Morpion entre joueurs expérimentés tombe à environ 8 à 12 bits - bien en dessous du maximum théorique de 18,5 bits. Cela signifie que la stratégie réduit de moitié le contenu informationnel du jeu. Les bons joueurs sont prévisibles, et c'est précisément ce qui les rend bons : ils font systématiquement les meilleurs choix.
Comparer avec d'autres jeux : la complexité informationnelle
La beauté de la mesure en bits est qu'elle permet de comparer la complexité de jeux très différents sur une échelle commune. Le Morpion, avec ses 18,5 bits maximum, est un jeu à très faible complexité informationnelle. À titre de comparaison, une partie d'échecs typique contient environ 120 bits d'information (40 coups, chacun choisi parmi une moyenne de 30 options). Une partie de Go sur un plateau 19x19 peut contenir plus de 500 bits.
Le Puissance 4, avec ses 7 colonnes et ses parties d'environ 20 coups, se situe autour de 40 à 50 bits - un ordre de grandeur au-dessus du Morpion. Les Dames internationales, avec leur plateau 10x10 et des parties pouvant dépasser 50 coups, atteignent environ 150 à 200 bits. Ces chiffres quantifient une intuition que tout joueur possède : le Morpion est "simple" et le Go est "complexe" - la théorie de l'information met un nombre précis sur cette intuition.
Mais attention : la complexité informationnelle ne mesure pas la difficulté stratégique. Le Morpion est résolu - on connaît la stratégie parfaite qui mène toujours au match nul - alors que les échecs ne le sont pas. Un jeu peut contenir peu d'information et pourtant poser un défi intellectuel. La complexité informationnelle mesure la taille de l'espace des possibles, pas la difficulté de naviguer dans cet espace.
La compression : peut-on décrire une partie en encore moins de bits ?
Shannon a aussi montré que l'information redondante peut être compressée. Si les joueurs de Morpion suivent des patterns prévisibles, alors une partie réelle contient de la redondance - et cette redondance peut être éliminée par un algorithme de compression. C'est le même principe qui permet de compresser un fichier texte en ZIP : les régularités du langage sont exploitées pour réduire la taille du fichier.
Pour le Morpion, la compression peut être spectaculaire. Comme il n'existe que 255 168 parties possibles (en comptant les parties qui s'arrêtent avant de remplir la grille), on pourrait en théorie assigner un numéro unique à chaque partie. Il faudrait alors log2(255 168) = environ 18 bits pour identifier n'importe quelle partie parmi toutes les parties possibles. Mais si on ne considère que les parties jouées entre joueurs raisonnables, l'espace se réduit considérablement, et 10 à 12 bits pourraient suffire.
On peut aller encore plus loin. En exploitant les symétries du plateau - rotations de 90, 180 et 270 degrés, plus les réflexions horizontale, verticale et diagonales - on réduit le nombre de parties essentiellement différentes. Au premier coup, les 9 cases ne représentent en réalité que 3 positions distinctes : le centre, un coin, ou un côté. Cela réduit l'information du premier coup de 3,17 bits à seulement 1,58 bit. La symétrie est une forme naturelle de compression.
L'information stratégique : ce que chaque coup révèle
Au-delà de la question purement mathématique, la théorie de l'information éclaire un aspect stratégique fondamental du Morpion. Chaque coup que vous jouez révèle de l'information à votre adversaire. En choisissant le centre, vous signalez une approche standard. En choisissant un coin, vous indiquez peut-être une stratégie de piège spécifique. En choisissant un côté - le coup le plus rare et le moins optimal - vous envoyez un signal ambigu.
Dans les jeux plus complexes, cette dimension informationnelle du coup devient cruciale. Au poker, par exemple, chaque mise révèle de l'information sur la main du joueur, et la stratégie optimale consiste parfois à randomiser ses actions pour minimiser l'information divulguée. Au Morpion, le jeu est trop simple pour que cette dimension soit réellement exploitable - mais le principe est le même. Un coup qui surprend l'adversaire contient plus d'information qu'un coup prévisible.
La théorie de l'information nous invite à voir le Morpion sous un angle nouveau. Ce jeu que nous considérons comme trivial est en réalité un microcosme qui contient, en miniature, tous les concepts fondamentaux de la théorie de l'information : l'entropie, la compression, la redondance, le signal et le bruit. Il tient en 18 bits - moins de trois octets - et pourtant il suffit à illustrer l'une des plus belles théories mathématiques du XXe siècle. La prochaine fois que vous placerez une croix ou un rond, souvenez-vous que vous êtes en train de générer de l'information - et que Shannon aurait pu vous dire exactement combien.