Un jeu de rien du tout, une théorie complète
Le Nim se joue avec quelques rangées d'allumettes — ici 1, 3, 5 et 7. Chacun son tour, on en retire autant qu'on veut, mais d'une seule rangée ; cliquer une allumette retire celle-ci et toutes celles à sa droite. Dans la version normale que je propose, celui qui prend la dernière allumette gagne. Derrière cette simplicité se cache l'un des rares jeux à être entièrement résolu : on sait mathématiquement, pour chaque position, qui doit gagner et quel coup jouer. C'est ce résultat que j'ai voulu rendre tangible.
La clé, c'est le XOR des tailles de rangées
La théorie des jeux combinatoires attache à chaque position un invariant : le nim-sum, c'est-à-dire le OU exclusif (XOR) des tailles de toutes les rangées. Cette opération bit à bit — la même que celle qu'un développeur manipule tous les jours — suffit à trancher la partie. Une position dont le nim-sum vaut zéro est perdante pour celui qui doit jouer : quoi qu'il tente, il rend la main à son adversaire sur une position gagnante. Une position de nim-sum non nul est, elle, gagnante.
La stratégie optimale de l'IA
L'ordinateur applique directement ce théorème. Quand le nim-sum est non nul, il existe toujours une rangée qu'il peut réduire pour ramener le nim-sum global à zéro — il calcule la nouvelle taille cible par un simple XOR et retire ce qu'il faut. Il repasse ainsi le fardeau au joueur, sur une position perdante. Quand le nim-sum est déjà nul, l'IA est elle-même en position perdante : elle joue alors un coup neutre et attend la faute. Concrètement, l'IA est imbattable dès qu'elle a l'avantage ; le joueur ne l'emporte qu'en partant d'une position favorable et en ne commettant aucune erreur.
Les nombres de Grundy, la généralisation
Ce qui rend le Nim central en théorie des jeux, c'est le théorème de Sprague-Grundy : tout jeu combinatoire impartial équivaut à une rangée de Nim d'une certaine taille, son nombre de Grundy. Une rangée de n allumettes a pour nombre de Grundy n, et le nim-sum n'est que le XOR de ces nombres. Autrement dit, savoir résoudre le Nim, c'est disposer d'une brique réutilisable pour analyser une famille entière de jeux — la même logique de réduction à un invariant se retrouve dans bien des problèmes d'optimisation.
Pourquoi cette démo compte pour vos projets
Un jeu d'allumettes n'a l'air de rien, et pourtant sa résolution tient dans quelques lignes claires parce que j'ai d'abord cherché le bon invariant plutôt que d'empiler des cas particuliers. C'est exactement ma manière de travailler sur vos projets : identifier la structure sous-jacente d'un problème métier, puis écrire un code court, testable et prévisible qui s'appuie dessus. La rigueur mathématique n'est pas un luxe académique — c'est ce qui transforme une logique fragile en un système robuste que vos équipes pourront reprendre en toute confiance.
