théorie des jeux combinatoires

Trois tas contiennent 3, 4 et 5 jetons. Deux personnes retirent à tour de rôle autant de jetons qu'elles le souhaitent, mais dans un seul tas. Rien n'est caché, aucun dé ne décide et chaque choix modifie les coups encore possibles.

La théorie des jeux combinatoires transforme ce type de duel en objet mathématique. Une position devient un point de départ, chaque coup mène à une nouvelle position et l'ensemble forme un arbre. Étudier cet arbre aide à reconnaître les choix qui laissent l'adversaire sans bonne réponse.

La théorie des jeux combinatoires est une branche des mathématiques discrètes consacrée à des jeux à deux joueurs. Les joueurs agissent à tour de rôle. Aucun événement aléatoire n'intervient. L'état du jeu est connu de la même manière par les deux joueurs à chaque instant. Le Puissance 4, le Morpion, les Échecs, les Dames, le Go et Nim entrent dans cette famille au sens large.

Une position décrit entièrement l'état courant. Ses options sont les positions accessibles en un coup légal. En reliant chaque position à ses options, puis chaque option à ses propres suites, on construit un arbre de jeu. Une feuille représente une position sans coup possible ou une issue arrêtée par les règles. L'analyse remonte alors des feuilles vers la position initiale afin de distinguer les choix favorables des choix qui offrent une réponse gagnante à l'adversaire.

Nim fournit un modèle particulièrement lisible : une position est une liste de tailles de tas et un coup réduit exactement une taille. Dans la règle où la personne qui prend le dernier jeton gagne, la somme de Nim est le « ou exclusif » bit à bit des tailles. Une somme nulle signale une position perdante pour la personne qui doit jouer, si l'adversaire répond correctement. Le domaine s'est affirmé comme champ de recherche autonome à partir des années 1970, notamment avec les travaux de Conway.

Une partie de Nim commence avec trois tas de 3, 4 et 5 jetons. À chaque tour, une personne retire au moins un jeton d'un seul tas. La personne qui prend le dernier jeton gagne. Les écritures binaires des tailles sont 011, 100 et 101.

1. On effectue le « ou exclusif » colonne par colonne : $3\oplus 4\oplus 5=23\backslash oplus4\backslash oplus5=2$. La somme de Nim n'est donc pas nulle.
2. On cherche une réduction qui rende cette somme nulle. Retirer 2 jetons du tas de 3 donne les tailles 1, 4 et 5.
3. Le contrôle donne $1\oplus 4\oplus 5=01\backslash oplus4\backslash oplus5=0$.

Le coup vérifié consiste donc à passer de (3, 4, 5) à (1, 4, 5). Pour refaire le contrôle, on écrit 001, 100 et 101 : dans chaque colonne, le nombre de chiffres 1 est pair. La somme de Nim vaut bien 0.

Pour une petite position, on peut dessiner toutes les réponses possibles jusqu'à la fin, puis remonter l'arbre. Cette méthode est préférable lorsqu'il y a assez peu de branches pour n'en oublier aucune.

Pour Nim, calculer la somme de Nim évite de développer tout l'arbre. On choisit ce raccourci lorsque la position est bien une liste de tas et que chaque coup retire des objets dans un seul tas.

Pour comparer deux règles d'un même jeu, on précise d'abord ce qui termine la partie et qui gagne. Si la règle du dernier coup change, il faut refaire l'analyse au lieu de réutiliser automatiquement la même stratégie.

La théorie des jeux au sens économique étudie aussi des décisions stratégiques, mais peut admettre des choix simultanés, du hasard ou une information inégalement répartie. Une partie de poker, avec cartes cachées et distribution aléatoire, ne satisfait pas les conditions données ici ; Nim les satisfait.

La combinatoire compte et organise des configurations discrètes sans exiger deux adversaires. Le critère décisif est la présence d'une succession de coups opposant deux joueurs : compter des arrangements relève de la combinatoire, analyser leurs choix alternés peut relever des jeux combinatoires.

Une position connue ne suffit pas si une donnée reste cachée. Si les joueurs ne voient pas les mêmes cartes ou le même état, l'arbre des positions observables ne décrit plus à lui seul leurs décisions. Il faut intégrer l'information disponible à chacun.

Un tirage aléatoire rompt le cadre annoncé. Un dé ou une distribution au hasard crée des branches auxquelles aucun joueur ne choisit d'accéder. Il faut alors attribuer des probabilités à ces branches, et non les traiter comme des coups ordinaires.

La règle de fin appartient au modèle. Dans l'exemple, prendre le dernier jeton fait gagner. Si le dernier coup fait perdre, la somme de Nim nulle ne donne pas partout la même consigne près de la fin ; il faut analyser cette variante séparément.

Un arbre peut être trop vaste pour être déployé. Les Échecs ou le Go répondent aux conditions générales, mais l'énumération de toutes leurs suites devient impraticable. On emploie alors des propriétés de positions ou des méthodes de recherche partielles, sans prétendre avoir parcouru l'arbre entier.

Le formalisme développé autour de Conway pousse plus loin l'idée d'option : une position est décrite récursivement par les positions accessibles aux deux joueurs. Cette lecture permet d'étudier la structure d'un jeu sans dépendre de son plateau ou de ses pièces.

L'article Les mathématiques se prêtent au jeu ouvre sur d'autres rencontres entre raisonnement mathématique et situations de jeu, notamment autour du Go.