GameTheory 8 - Jeux Combinatoires

Navigation : << 7-ExtensiveForm | Index | 9-BackwardInduction >>

Side tracks : 8b-Lean-CombinatorialGames | 8c-CombinatorialGames-Python

Kernel : Python 3

---

Introduction

Les jeux combinatoires sont une classe speciale de jeux : - 2 joueurs (Gauche et Droite) - Alternance des coups - Information parfaite (pas de hasard, pas de coups caches) - Terminaison : le jeu finit toujours - Normal play : le joueur qui ne peut plus jouer perd

Contrairement aux jeux stratégiques (Nash, equilibres mixtes), les jeux combinatoires n’ont pas d’utilites numériques - seulement victoire ou defaite.

Jeux impartiaux vs partizans

Type	Coups disponibles	Exemples
Impartial	Mêmes pour les deux joueurs	Nim, Jeux de soustraction
Partizan	Différents selon le joueur	Echecs, Go, Domineering

Dans ce notebook, nous nous concentrons sur les jeux impartiaux et le celebre theoreme de Sprague-Grundy.

Objectifs d’apprentissage

1. Comprendre les positions P et N dans les jeux combinatoires
2. Maitriser le jeu de Nim et le theoreme de Bouton
3. Calculer les valeurs de Grundy via la fonction Mex
4. Appliquer le theoreme de Sprague-Grundy aux jeux de soustraction

Prerequis

• Notebooks 1-7 : fondations de la théorie des jeux
• Notions de base en combinatoire

Duree estimee : 50 minutes

Plan

1. Positions P et N
2. Le jeu de Nim
3. Fonction Mex et valeur de Grundy
4. Theoreme de Sprague-Grundy
5. Jeux de soustraction
6. Exercices

Sources primaires. La théorie mathematique du jeu de Nim est fondee par Charles L. Bouton dans Nim, a Game with a Complete Mathematical Theory (Annals of Mathematics, 2nd ser., 3(1/4):35-39, 1901) – il y etablit le critere de la nim-sum (XOR des tailles de tas) qui caracterise les positions gagnantes. La generalisation a tout jeu impartial fini – tout jeu impartial est equivalent a un tas de Nim – a ete decouverte independamment par Roland P. Sprague (Uber mathematische Kampfspiele, Tohoku Mathematical Journal 41:438-444, 1935) et Patrick M. Grundy (Mathematics and games, Eureka 2:6-8, 1939) ; c’est ce résultat, dit theoreme de Sprague-Grundy, que la section 4 demontre operatoirement.

---

# Configuration
import numpy as np
import matplotlib.pyplot as plt

print("Notebook 8 - Jeux Combinatoires")
print("================================")

Notebook 8 - Jeux Combinatoires
================================

---

1. Positions P et N

Dans un jeu combinatoire, chaque position est soit :

• P-position (Previous player wins) : Le joueur qui vient de jouer gagne
• N-position (Next player wins) : Le joueur qui va jouer gagne

Règles de classification

1. Une position terminale (sans coups possibles) est une P-position
2. Une position est une N-position si elle a au moins un coup vers une P-position
3. Une position est une P-position si tous ses coups menent a des N-positions

Exemple : Jeu de 1-2-3

Règles : Un tas de n jetons, on peut retirer 1, 2 ou 3 jetons. Qui retire le dernier gagne.

def classify_123_game(n_max: int) -> dict:
    """
    Classifie les positions du jeu 1-2-3.
    Retourne un dict {position: 'P' ou 'N'}
    """
    positions = {}
    
    for n in range(n_max + 1):
        if n == 0:
            # Position terminale : le joueur precedent a pris le dernier jeton
            positions[n] = 'P'
        else:
            # Verifier si on peut atteindre une P-position
            can_reach_P = False
            for take in [1, 2, 3]:
                if n >= take and positions.get(n - take) == 'P':
                    can_reach_P = True
                    break
            positions[n] = 'N' if can_reach_P else 'P'
    
    return positions

# Classifier les 16 premieres positions
positions = classify_123_game(16)

print("Position | Type | Motif")
print("-" * 25)
for n in range(17):
    t = positions[n]
    motif = "Perdante (n % 4 == 0)" if t == 'P' else "Gagnante"
    print(f"   {n:2d}    |  {t}   | {motif}")

Position | Type | Motif
-------------------------
    0    |  P   | Perdante (n % 4 == 0)
    1    |  N   | Gagnante
    2    |  N   | Gagnante
    3    |  N   | Gagnante
    4    |  P   | Perdante (n % 4 == 0)
    5    |  N   | Gagnante
    6    |  N   | Gagnante
    7    |  N   | Gagnante
    8    |  P   | Perdante (n % 4 == 0)
    9    |  N   | Gagnante
   10    |  N   | Gagnante
   11    |  N   | Gagnante
   12    |  P   | Perdante (n % 4 == 0)
   13    |  N   | Gagnante
   14    |  N   | Gagnante
   15    |  N   | Gagnante
   16    |  P   | Perdante (n % 4 == 0)

Lecture chiffree — pourquoi la période vaut 4 dans ce tableau. La colonne Motif aligne un P exactement toutes les quatre lignes (n % 4 == 0 aux lignes 0, 4, 8, 12). Le mecanisme se lit dans les coups disponibles {1, 2, 3} : depuis un multiple de 4, soustraire 1, 2 ou 3 fait sortir du multiple — aucun coup n’y reste ; depuis toute autre position n, le coup qui retranche exactement le reste n mod 4 y ramène. La période 4 n’est donc pas une propriete magique de ce jeu : c’est la longueur du plus grand coup plus un, et la couverture complete des restes qui va avec. La section 5 montrera le contre-exemple utile : pour S({1, 3, 4}) la plus grande valeur de Grundy monte a 3 et la période vaut 7, pas 5 — la periodicite des jeux de soustraction est frequente (observation de la section 5) mais sa longueur ne se deduit pas naivement de max(moves).

Exercice : Classification P/N avec ensemble de soustraction arbitraire

Objectif : Generaliser classify_123_game a un ensemble de soustraction arbitraire (par exemple S({1,3}) ou le joueur peut retirer 1 ou 3 jetons). Identifier les P-positions et determiner la periodicite.

Contexte : La classification 1-2-3 montre une periodicite de 4. Avec S({1,3}), la structure change.

• Indice : Adapter classify_123_game en remplacant [1,2,3] par un ensemble parametrable.
• Étape 1 : Implementer classify_game(n_max, moves).
• Étape 2 : Identifier le motif des P-positions.
• Étape 3 : Calculer la periode.

def exercice_classification_pn(n_max: int = 20, moves: set = None) -> dict:
    """
    Classifie les positions P/N pour un jeu de soustraction arbitraire.
    
    Args:
        n_max: taille maximale a analyser
        moves: ensemble des coups autorises (defaut: {1, 3})
    
    Returns:
        dict avec :
            'positions': dict {n: 'P' ou 'N'}
            'p_positions': liste des positions perdantes
            'period': periode detectee (ou None)
    """
    if moves is None:
        moves = {1, 3}
    return {"positions": {}, "p_positions": [], "period": None}  # TODO etudiant

# Test : S({1,3})
result_pn = exercice_classification_pn(20, {1, 3})
print(f"P-positions S({{1,3}}): {result_pn['p_positions']}")
print(f"Periode: {result_pn['period']}")

# Test : S({2,5})
result_pn2 = exercice_classification_pn(20, {2, 5})
print(f"\nP-positions S({{2,5}}): {result_pn2['p_positions']}")

print("Exercice a completer")

P-positions S({1,3}): []
Periode: None

P-positions S({2,5}): []
Exercice a completer

Observation : Les P-positions sont exactement les multiples de 4 !

---

2. Le jeu de Nim

Nim est le jeu combinatoire le plus celebre :

• Plusieurs tas de jetons
• A chaque tour, retirer au moins un jeton d’un seul tas
• Le joueur qui retire le dernier jeton gagne

Theoreme de Bouton (1901)

Une position de Nim avec des tas de tailles n1, n2, …, nk est une : - P-position si n1 XOR n2 XOR … XOR nk = 0 - N-position sinon

def nim_sum(*heaps) -> int:
    """Calcule la nim-sum (XOR) des tailles de tas."""
    result = 0
    for h in heaps:
        result ^= h
    return result

def nim_position_type(*heaps) -> str:
    """Determine si une position est P ou N."""
    return 'P' if nim_sum(*heaps) == 0 else 'N'

# Exemples
examples = [
    (1, 2, 3),
    (1, 2, 4),
    (3, 5, 6),
    (7, 7),
    (1, 1, 1),
]

print("Tas           | Nim-sum | Type")
print("-" * 35)
for heaps in examples:
    ns = nim_sum(*heaps)
    t = nim_position_type(*heaps)
    print(f"{str(heaps):13} | {ns:7} | {t}")

Tas           | Nim-sum | Type
-----------------------------------
(1, 2, 3)     |       0 | P
(1, 2, 4)     |       7 | N
(3, 5, 6)     |       0 | P
(7, 7)        |       0 | P
(1, 1, 1)     |       1 | N

Lecture chiffree — cinq lignes, trois mecanismes de la nim-sum. Les exemples de la sortie se decodent un par un. (7, 7) | 0 | P : deux tas identiques s’annulent entierement — chaque bit present deux fois tombe, le second joueur copie et gagne. (1, 1, 1) | 1 | N : nombre impair de tas identiques, la parite residuelle laisse 1 — l’annulation par paires est le seul mecanisme, l’orphelin survit. (1, 2, 3) | 0 | P et (3, 5, 6) | 0 | P : zero sans aucune paire de tas egaux — en binaire, 01 ⊕ 10 ⊕ 11 = 00 et 011 ⊕ 101 ⊕ 110 = 000, chaque colonne de bits tombe pair. Face a (1, 2, 4) | 7 | N, aucune colonne ne s’equilibre : 001 ⊕ 010 ⊕ 100 = 111. La nim-sum generalise l’annulation par paires a l’annulation par parite de colonnes.

Stratégie gagnante

Si vous etes en N-position (nim-sum != 0), vous pouvez toujours jouer pour atteindre une P-position.

def find_winning_move(heaps: list) -> tuple:
    """
    Trouve un coup gagnant au Nim.
    Retourne (index_tas, nouvelle_taille) ou None si P-position.
    """
    ns = nim_sum(*heaps)
    if ns == 0:
        return None  # P-position, pas de coup gagnant
    
    for i, h in enumerate(heaps):
        # Nouvelle taille pour ce tas
        new_h = h ^ ns
        if new_h < h:  # On doit retirer, pas ajouter
            return (i, new_h)
    
    return None

# Exemple
heaps = [3, 5, 7]
print(f"Position: {heaps}")
print(f"Nim-sum: {nim_sum(*heaps)}")

move = find_winning_move(heaps)
if move:
    i, new_h = move
    print(f"\nCoup gagnant: reduire tas {i} de {heaps[i]} a {new_h}")
    new_heaps = heaps.copy()
    new_heaps[i] = new_h
    print(f"Nouvelle position: {new_heaps}")
    print(f"Nouvelle nim-sum: {nim_sum(*new_heaps)}")

Position: [3, 5, 7]
Nim-sum: 1

Coup gagnant: reduire tas 0 de 3 a 2
Nouvelle position: [2, 5, 7]
Nouvelle nim-sum: 0

Lecture chiffree — le coup gagnant reconstruit la parite. Pour [3, 5, 7], la sortie donne Nim-sum: 1, puis Coup gagnant: reduire tas 0 de 3 a 2 et Nouvelle nim-sum: 0. Le mecanisme : la nim-sum 1 signale qu’un nombre impair de tas portent le bit 1 ; le solveur cherche le tas dont la reduction peut equilibrer toutes les colonnes a la fois — ici 3 → 2, car 10 ⊕ 101 ⊕ 111 = 000. Le detail qui compte : le coup n’attaque pas le plus gros tas ni le tas le plus desequilibre, il attaque le tas ou la correction est realisable en une seule reduction. Toute position N en possede au moins une (theoreme de Bouton) ; aucune position P n’en possede — c’est exactement la definition.

---

3. Fonction Mex et valeur de Grundy

Fonction Mex (Minimum Excludant)

Le mex d’un ensemble S est le plus petit entier naturel absent de S.

def mex(s: set) -> int:
    """Minimum excludant : plus petit entier >= 0 absent de l'ensemble."""
    n = 0
    while n in s:
        n += 1
    return n

# Exemples
examples = [
    set(),           # mex = 0
    {0},             # mex = 1
    {0, 1, 2},       # mex = 3
    {1, 2, 3},       # mex = 0 (0 absent)
    {0, 2, 4},       # mex = 1
]

for s in examples:
    print(f"mex({s}) = {mex(s)}")

mex(set()) = 0
mex({0}) = 1
mex({0, 1, 2}) = 3
mex({1, 2, 3}) = 0
mex({0, 2, 4}) = 1

Lecture chiffree — le mex complete par le bas. Les cinq lignes de la sortie se lisent comme une seule regle : mex(S) est le plus petit entier absent de S. Les deux lignes piegeuses : mex({1, 2, 3}) = 0 — l’ensemble ne contient pas zero, donc le mex tombe a zero meme si l’ensemble est « rempli » au-dela ; et mex({0, 2, 4}) = 1 — le trou le plus bas commande, meme entoure de pairs. mex(set()) = 0 fixe la base : la position terminale sans successeur recoit Grundy 0, qui est la definition meme d’une P-position. Ce choix de mex (et pas de max, ni de somme) garantit que deux positions aux suites de Grundy differentes ne collisionnent jamais — la propriete que la table de la section suivante exploite.

Valeur de Grundy

La valeur de Grundy (ou nimber) d’une position G est définie recursivement :

• Position terminale : Grundy = 0
• Sinon : Grundy(G) = mex{Grundy(G’) : G’ accessible depuis G}

Propriete importante : - P-position ssi Grundy = 0 - N-position ssi Grundy > 0

def grundy_nim(n: int, memo: dict = None) -> int:
    """
    Valeur de Grundy de nim(n) - un seul tas de n jetons.
    (Spoiler: c'est toujours n)
    """
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    
    if n == 0:
        return 0
    
    # Positions accessibles : nim(0), nim(1), ..., nim(n-1)
    reachable = {grundy_nim(i, memo) for i in range(n)}
    result = mex(reachable)
    memo[n] = result
    return result

print("n  | grundy(nim(n)) | Verification")
print("-" * 35)
for n in range(10):
    g = grundy_nim(n)
    verify = "OK" if g == n else "ERREUR"
    print(f"{n:2} | {g:14} | {verify}")

n  | grundy(nim(n)) | Verification
-----------------------------------
 0 |              0 | OK
 1 |              1 | OK
 2 |              2 | OK
 3 |              3 | OK
 4 |              4 | OK
 5 |              5 | OK
 6 |              6 | OK
 7 |              7 | OK
 8 |              8 | OK
 9 |              9 | OK

Lecture chiffree — grundy(nim(n)) = n, ligne par ligne. La table aligne dix verifications OK : pour chaque n de 0 a 9, la valeur de Grundy calculee par la definition recursive (mex des successeurs) vaut exactement n. Autrement dit, un tas de Nim est son propre nimber : Grundy(n) = mex({0, 1, …, n-1}) = n. La colonne Verification ne verifie pas un resultat numerique isole, elle boucle la definition — chaque ligne certifie que le mex des successeurs de n (qui sont exactement tous les entiers de 0 a n-1) retombe sur n. C’est ce pont identite qui rend le theoreme de Sprague-Grundy de la section suivante concret : chaque tas d’une position de Nim se comporte deja comme son nimber, et la somme de jeux s’annoncera comme un simple XOR de ces valeurs.

---

4. Theoreme de Sprague-Grundy

Le theoreme de Sprague-Grundy est le résultat central de la théorie des jeux combinatoires :

Theoreme : Tout jeu impartial est equivalent a un tas de Nim.

Pour une somme de jeux G1 + G2 + … + Gk : Grundy(G1 + G2 + … + Gk) = Grundy(G1) XOR Grundy(G2) XOR … XOR Grundy(Gk)

Cela signifie que pour analyser n’importe quel jeu impartial, il suffit de : 1. Calculer la valeur de Grundy de chaque composante 2. XOR les valeurs ensemble 3. Si le résultat est 0, c’est une P-position, sinon N-position

def analyze_nim_game(heaps: list) -> dict:
    """
    Analyse complete d'une position de Nim.
    """
    grundy_values = heaps  # Pour Nim, grundy(n) = n
    total_grundy = nim_sum(*grundy_values)
    
    result = {
        'heaps': heaps,
        'grundy_values': grundy_values,
        'nim_sum': total_grundy,
        'position_type': 'P' if total_grundy == 0 else 'N',
        'winning_move': find_winning_move(heaps)
    }
    return result

# Exemple
game = analyze_nim_game([4, 7, 9])

print(f"Position: {game['heaps']}")
print(f"Valeurs de Grundy: {game['grundy_values']}")
print(f"Nim-sum: {game['nim_sum']}")
print(f"Type: {game['position_type']}-position")

if game['winning_move']:
    i, new_h = game['winning_move']
    print(f"\nCoup gagnant: tas {i}: {game['heaps'][i]} -> {new_h}")

Position: [4, 7, 9]
Valeurs de Grundy: [4, 7, 9]
Nim-sum: 10
Type: N-position

Coup gagnant: tas 2: 9 -> 3

Lecture chiffree — l’analyse complete d’une position en une sortie. Pour [4, 7, 9], les cinq lignes racontent toute la theorie appliquee. Valeurs de Grundy: [4, 7, 9] — chaque tas est son nimber (section precedente). Nim-sum: 10 — en binaire 100 ⊕ 111 ⊕ 1001 = 1010. Type: N-position — la nim-sum non nulle signe le tour gagnant. Coup gagnant: tas 2: 9 -> 3 — verifier : 100 ⊕ 111 ⊕ 011 = 000, la nouvelle position est une P-position servie au prochain joueur. Le choix 9 → 3 n’est pas unique par principe, mais tout coup gagnant doit reduire un tas exactement a la valeur qui equilibre les deux autres : ici 4 ⊕ 7 = 3, la cible s’impose.

Exercice : Verification du theoreme de Sprague-Grundy

Objectif : Prendre deux jeux de soustraction G1=S({1,2}) et G2=S({1,3}), calculer les valeurs de Grundy individuelles pour n=0..15, puis verifier que Grundy(G1+G2) = Grundy(G1) XOR Grundy(G2) pour plusieurs tailles.

Contexte : Le theoreme de Sprague-Grundy affirme que la somme de jeux impartiaux se decompose via le XOR. Verifions-le sur un exemple concret.

• Indice : Pour chaque n, calculer Grundy de G1 et G2 separement.
• Étape 1 : Calculer grundy_subtraction pour les deux jeux.
• Étape 2 : Pour la somme, le Grundy total = XOR des deux.
• Étape 3 : Verifier que le résultat est coherent avec la classification P/N.

def exercice_sprague_grundy_somme(n_max: int = 15) -> dict:
    """
    Verifie le theoreme de Sprague-Grundy sur la somme S({1,2}) + S({1,3}).
    
    Args:
        n_max: taille maximale a analyser
    
    Returns:
        dict avec :
            'g1_values': liste des Grundy de G1=S({1,2})
            'g2_values': liste des Grundy de G2=S({1,3})
            'xor_values': liste des XOR
            'verification_ok': True si le theoreme est verifie
    """
    return {"g1_values": [], "g2_values": [], "xor_values": [], "verification_ok": False}  # TODO etudiant

result_sg = exercice_sprague_grundy_somme(15)
print(f"G1=S({{1,2}}): {result_sg['g1_values'][:10]}")
print(f"G2=S({{1,3}}): {result_sg['g2_values'][:10]}")
print(f"XOR:           {result_sg['xor_values'][:10]}")
print(f"Verification: {result_sg['verification_ok']}")

print("Exercice a completer")

G1=S({1,2}): []
G2=S({1,3}): []
XOR:           []
Verification: False
Exercice a completer

Lire la sortie d’un exercice non rempli. Les lignes G1=S({1,2}): [], G2=S({1,3}): [], XOR: [] et Verification: False ne sont pas un resultat : les listes vides marquent l’etat du squelette, et le False final n’echoue aucun theoreme — il mesure des donnees absentes. Le contrat, pose par l’enonce : remplir les suites de Grundy des deux jeux de soustraction, former le XOR element par element, et verifier la These de Sprague-Grundy sur leur somme — la position combinee doit etre P exactement quand le XOR des nimbers vaut 0. La sortie remplie affichera deux suites (celles de la section 5 pour {1, 3, 4} commencent 0, 1, 0, 1, 2, 3, 2), leur XOR, et un verdict True sur chaque position testee.

---

5. Jeux de soustraction

Un jeu de soustraction S(M) est défini par un ensemble de coups M : - Un tas de n jetons - On peut retirer m jetons si m est dans M et m <= n

Par exemple, S({1, 3, 4}) : on peut retirer 1, 3 ou 4 jetons.

def grundy_subtraction(n: int, moves: set, memo: dict = None) -> int:
    """
    Valeur de Grundy pour un jeu de soustraction S(moves).
    """
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    
    if n == 0:
        return 0
    
    # Positions accessibles
    reachable = set()
    for m in moves:
        if m <= n:
            reachable.add(grundy_subtraction(n - m, moves, memo))
    
    result = mex(reachable)
    memo[n] = result
    return result

# Analyser S({1, 3, 4})
moves = {1, 3, 4}
memo = {}

print(f"Jeu de soustraction S({moves})")
print("\n n | Grundy | Type")
print("-" * 20)
for n in range(20):
    g = grundy_subtraction(n, moves, memo)
    t = 'P' if g == 0 else 'N'
    print(f"{n:2} | {g:6} | {t}")

Jeu de soustraction S({1, 3, 4})

 n | Grundy | Type
--------------------
 0 |      0 | P
 1 |      1 | N
 2 |      0 | P
 3 |      1 | N
 4 |      2 | N
 5 |      3 | N
 6 |      2 | N
 7 |      0 | P
 8 |      1 | N
 9 |      0 | P
10 |      1 | N
11 |      2 | N
12 |      3 | N
13 |      2 | N
14 |      0 | P
15 |      1 | N
16 |      0 | P
17 |      1 | N
18 |      2 | N
19 |      3 | N

Observation : Les valeurs de Grundy pour les jeux de soustraction sont souvent periodiques après un certain point.

---

6. Exercices

Exercice 1 : Jeu de soustraction avec moves {1, 2, 4}

Calculez les valeurs de Grundy pour le jeu de soustraction ou les moves autorisés sont {1, 2, 4}. Pour quelles valeurs de n le joueur courant perd-il ?

Exercice 2 : Nim a trois tas

Pour le jeu Nim({3, 5, 7}), trouvez le premier coup gagnant en utilisant la fonction find_winning_move.

Exercice 3 : Equivalence de jeux

Montrez que Nim({4}) est equivalent a Nim({1, 3}) (même valeur de Grundy) en calculant les valeurs des deux configurations.

# Espace pour les exercices

# Exemple guide 1 : Jeu de soustraction {1, 2, 4}
# TODO etudiant : calculer les valeurs de Grundy pour n in range(15)
# Indice : utilisez grundy_subtraction(n, moves={1, 2, 4})
def exercice_1():
    pass  # TODO etudiant : remplacer par le calcul

# Exemple guide 2 : Nim({3, 5, 7})
# TODO etudiant : utiliser find_winning_move([3, 5, 7])
def exercice_2():
    pass  # TODO etudiant : afficher le coup gagnant

# Exemple guide 3 : Equivalence Nim({4}) vs Nim({1,3})
# TODO etudiant : calculer grundy_nim(4) et comparer a Nim sur somme XOR de {1,3}
def exercice_3():
    pass  # TODO etudiant : prouver l'equivalence par le Nim-sum

print("Exercice a completer")

Exercice a completer

Lire la sortie d’un exercice non rempli. La ligne « Exercice a completer » ouvre l’espace des exemples guides : le premier (jeu de soustraction, enonce en section 6) attend sa solution ici. Le terrain est deja pose — grundy_subtraction de la section 5 calcule la suite de Grundy de n’importe quel S(moves), et classify_123_game de la section 1 donne le gabarit d’affichage. Une solution remplie montrera la table n / Grundy / Type du jeu demande, ses P-positions alignees, et la lecture de sa periode — le meme geste que la section 5, sur un autre ensemble de coups.

Resume et perspectives

Ce notebook a etabli les fondements de la théorie des jeux combinatoires impartiaux, depuis la classification des positions en P-positions (perdantes pour le joueur courant) et N-positions (gagnantes) jusqu’au theoreme de Sprague-Grundy, résultat central qui affirme que tout jeu impartial fini est equivalent a un tas de Nim. Le theoreme de Bouton a fourni un critere elegant pour determiner la position gagnante au Nim (la nim-sum, ou XOR des tailles de tas), tandis que la fonction mex (minimum excludant) a permis de calculer recursivement les valeurs de Grundy pour des jeux de soustraction plus généraux. L’observation de la periodicite des valeurs de Grundy dans les jeux de soustraction ouvre la porte a l’analyse de jeux plus complexes, ou les structures periodiques simplifient considerablement la recherche de stratégies optimales.

Concepts cles

Concept	Description
P-position	Position perdante pour le joueur a jouer
N-position	Position gagnante pour le joueur a jouer
Mex	Plus petit entier absent d’un ensemble
Valeur de Grundy	Mex des Grundy des positions accessibles
Sprague-Grundy	Grundy(G1 + G2) = Grundy(G1) XOR Grundy(G2)
Nim-sum	XOR des tailles des tas

Les side tracks associes approfondissent ces concepts : le notebook 8b propose une formalisation en Lean 4 avec les PGame de Mathlib, tandis que le notebook 8c explore le jeu de Wythoff et les jeux multi-composantes en Python. La serie principale se poursuit avec l’étude de l’induction arriere pour resoudre les jeux séquentiels : GameTheory-09-BackwardInduction-Python.

Lien avec la formalisation Lean : Les structures de jeux combinatoires (P-positions, N-positions, Nim, Sprague-Grundy) sont formalisees a plusieurs niveaux dans le depot. Le module lean_game_defs/Combinatorial.lean définit les structures de base GameTree, NimHeap, la fonction nimSum (XOR) et le predicat isWinningNim. Le module Conway/Nim.lean demontre nimSum_self (annulation du XOR) et les proprietes des positions de Nim. Le theoreme de Sprague-Grundy correspond au résultat equiv_nim_grundyValue dans Mathlib (Mathlib.SetTheory.Game.Nim). Le notebook compagnon GT-8b-Lean-CombinatorialGames construit interactivement le type inductif SimplePGame (encodage de Conway {L | R}), les jeux primitifs zero, star, la fonction nim, et la valeur de Grundy via mex.

---

Notebook précédent: GameTheory-07-ExtensiveForm-Python
Notebook suivant: GameTheory-08b-Lean-CombinatorialGames-Lean