On dispose plusieurs tas de pierres, et deux joueurs retirent des pierres à tour de rôle. Il n'y a que deux règles : à chaque tour, on ne peut prendre que dans un seul tas, et on peut y prendre de 1 pierre jusqu'au tas entier. Celui qui prend la dernière pierre gagne. Les règles sont aussi simples que ça, et pourtant, chose étonnante, on peut prédire parfaitement, avant même le début de la partie, qui va gagner.

Le secret consiste à combiner le nombre de pierres de chaque tas avec une opération appelée XOR (ou exclusif). Le XOR compare deux nombres chiffre par chiffre en binaire et donne, pour chaque position, 0 si les chiffres sont égaux et 1 s'ils diffèrent. Par exemple, avec les tas [3, 4, 5], on a en binaire 3=011, 4=100, 5=101. En calculant le XOR chiffre par chiffre : le premier chiffre donne 0⊕1⊕1=0, le deuxième 1⊕0⊕0=1, le troisième 1⊕0⊕1=0. La valeur du XOR est donc 010, c'est-à-dire 2.

3 = 011 4 = 100 5 = 101 XOR = 010 = 2 0 si les chiffres sont égaux,
1 s'ils diffèrent
Écris le nombre de chaque tas en binaire et calcule le XOR chiffre par chiffre

Si cette valeur du XOR (appelée « somme de Nim ») n'est pas 0, le joueur dont c'est le tour a un coup qui lui garantit la victoire. Il suffit de calculer le XOR du nombre de chaque tas avec cette valeur, et de trouver le tas pour lequel le résultat est plus petit que le nombre de départ. Avec [3,4,5], le XOR valait 2 : 5 XOR 2=7 et 4 XOR 2=6 sont tous deux plus grands, donc ça ne marche pas, mais 3 XOR 2=1 est plus petit, donc celui-là convient. En prenant 2 pierres dans le premier tas (de 3) pour n'en laisser qu'une, les tas deviennent [1,4,5], et leur XOR vaut 1⊕4⊕5=0.

À l'inverse, si le XOR vaut déjà 0, le joueur dont c'est le tour est désavantagé. Tant que l'adversaire joue parfaitement, quel que soit ton coup, le XOR redevient différent de 0, et l'adversaire n'a qu'à le ramener à 0 à chaque fois, jusqu'à ce que ce soit lui qui prenne la dernière pierre. La stratégie gagnante du Nim est donc remarquablement simple : « toujours faire en sorte que le XOR vaille 0 à la fin de son tour ».

Pourquoi est-ce justement le XOR qui fonctionne ? Le XOR a la propriété « d'annuler ce qui va par paires ». Quand la partie se termine (tous les tas sont à 0), le XOR vaut naturellement 0 lui aussi. Et à partir d'un état où le XOR vaut 0, modifier un seul tas le rend forcément différent de 0 (car changer un seul tas rompt l'équilibre). Inversement, quand le XOR n'est pas 0, il existe toujours un tas dont on peut corriger le déséquilibre pour ramener le XOR à 0. Ces deux propriétés s'emboîtent pour faire marcher la stratégie gagnante : « rends toujours la main à ton adversaire avec XOR=0, et il finira coincé ».

Sur notre page d'activité, l'ordinateur joue exactement avec cette stratégie du XOR : s'il part d'une position avantageuse, il est vraiment difficile à battre. Mais si tu utilises le bouton d'indice pour vérifier la valeur du XOR et le coup conseillé à chaque tour, toi aussi tu peux le battre. Essaie différentes dispositions de tas, et prends l'habitude de vérifier dès le départ si le XOR vaut 0 (ce qui veut dire que tu es désavantagé) ou non.