Navigation : << 8-CombinatorialGames (track principal) | Index
Autres side tracks : 8b-Lean-CombinatorialGames | 8d-Lean-CGT-Native
Kernel : Python 3
Ce notebook est un side track du notebook 8 (CombinatorialGames). Il suppose que vous avez déjà etudie : - Les positions P et N - Le jeu de Nim et le theoreme de Bouton - La fonction mex et les valeurs de Grundy - Le theoreme de Sprague-Grundy
Ici, nous explorons des jeux plus complexes et des techniques avancees :
A l’issue de ce notebook, vous saurez :
# Configuration et imports
import numpy as np
import matplotlib.pyplot as plt
from functools import lru_cache
from typing import List, Set, Tuple, Optional
print("Notebook 8c - Jeux Combinatoires : Approfondissement")
print("="*55)Notebook 8c - Jeux Combinatoires : Approfondissement
=======================================================Lecture ancrée : Ce notebook explore les jeux combinatoires impartials à travers plusieurs exemples classiques et illustratifs : jeux de soustraction, Wythoff, jeux composés et Chomp. Chaque section illustre un concept fondamental de la théorie des jeux avec des implémentations Python exécutables.
Ces fonctions sont définies dans le notebook 8. Nous les rappelons ici pour l’autonomie du notebook.
Lien avec la formalisation Lean : Le theoreme de Sprague-Grundy et le jeu de Nim sont formellement prouves dans le module
Conway/Nim.leande l’hommage Conway. En particulier,nimSum_self(deux tas egaux forment une P-position) etisWinningNim_345(position [3,4,5] est gagnante) y sont verifies parnative_decide. Le notebook companion 8b-Lean-CombinatorialGames explore ces preuves en detail.
def mex(s: set) -> int:
"""Minimum excludant."""
n = 0
while n in s:
n += 1
return n
def grundy_subtraction(n: int, moves: set, memo: dict = None) -> int:
"""Valeur de Grundy pour le jeu de soustraction S(moves)."""
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n == 0:
return 0
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
def nim_sum(*values) -> int:
"""XOR de plusieurs valeurs."""
result = 0
for v in values:
result ^= v
return result
print("Fonctions de base chargees.")Fonctions de base chargees.Lecture ancrée : Les fonctions mex (minimum excludant) et find_periodicity sont les outils de base pour analyser les jeux de soustraction. La fonction mex calcule le nombre de Grundy d’une position, tandis que find_periodicity détecte les motifs répétitifs dans ces valeurs, essentiel pour déterminer les stratégies gagnantes optimales.
Lecture ancrée : Le code met en œuvre la définition exacte : grundy_subtraction explore chaque coup m ≤ n, collecte les valeurs atteintes dans reachable et leur applique mex ; le dictionnaire memo évite tout recalcul. nim_sum accumule le XOR de plusieurs valeurs — l’opération qui, par le théorème de Sprague-Grundy, donnera la valeur d’une somme de jeux.
Pour les jeux de soustraction, les valeurs de Grundy deviennent souvent periodiques après un certain point.
Pour tout jeu de soustraction \(S(M)\) ou \(M\) est fini, les valeurs de Grundy sont ultimement periodiques : il existe \(p\) (periode) et \(n_0\) (pre-periode) tels que :
\[\forall n \geq n_0 : G(n + p) = G(n)\]
def find_periodicity(moves: set, max_n: int = 500, min_period: int = 1) -> Tuple[int, int, List[int]]:
"""
Detecte la periode et la pre-periode des valeurs de Grundy.
Retourne (pre-periode, periode, sequence).
"""
memo = {}
sequence = [grundy_subtraction(n, moves, memo) for n in range(max_n)]
# Chercher une periode
for pre_period in range(max_n // 3):
for period in range(1, (max_n - pre_period) // 3):
is_periodic = True
for i in range(min(100, max_n - pre_period - period)):
if sequence[pre_period + i] != sequence[pre_period + period + i]:
is_periodic = False
break
if is_periodic and period >= min_period:
return pre_period, period, sequence
return -1, -1, sequence # Periode non trouvee
# Analyser plusieurs jeux de soustraction
games = [
{1, 2}, # Nim modifie
{1, 3}, #
{1, 3, 4}, # Exemple classique
{1, 2, 5}, #
{2, 5, 7}, # Sans 1
]
print("Periodicite des jeux de soustraction")
print("="*50)
print(f"{'Moves':<15} | {'Pre-periode':>12} | {'Periode':>8}")
print("-"*50)
for moves in games:
pre, period, seq = find_periodicity(moves)
if period > 0:
print(f"{str(moves):<15} | {pre:>12} | {period:>8}")
else:
print(f"{str(moves):<15} | {'?':>12} | {'?':>8}")Periodicite des jeux de soustraction
==================================================
Moves | Pre-periode | Periode
--------------------------------------------------
{1, 2} | 0 | 3
{1, 3} | 0 | 2
{1, 3, 4} | 0 | 7
{1, 2, 5} | 0 | 3
{2, 5, 7} | 0 | 22Lecture ancrée : Le tableau montre que chaque configuration de coups possibles ({1,2}, {1,3}, {1,3,4}, etc.) produit sa propre périodicité. Par exemple, le jeu S({1,3,4}) a une période de 7, ce qui signifie donc que les valeurs de Grundy correspondantes se répètent tous les 7 jetons. Cette régularité permet de calculer efficacement les stratégies gagnantes pour des nombres arbitrairement grands.
L’analyse de periodicite revele des structures interessantes. Les périodes reportées sont les périodes fondamentales (la plus petite \(p\) telle que \(G(n+p)=G(n)\)) :
| Jeu S(M) | Période | Motif | Observation |
|---|---|---|---|
| {1, 2} | 3 | [0, 1, 2] | Période courte, motif cyclique simple |
| {1, 3} | 2 | [0, 1] | Période minimale (alternance) |
| {1, 3, 4} | 7 | [0, 1, 0, 1, 2, 3, 2] | Période moyenne, structure riche |
| {1, 2, 5} | 3 | [0, 1, 2] | Identique à {1, 2} : le coup 5 n’augmente pas la période |
| {2, 5, 7} | 22 | [0, 0, 1, 1, 0, 2, …, 3, 2] | Période longue sans le coup « 1 » |
Observations cles :
Presence du coup 1 : Les jeux contenant 1 dans \(M\) ont des périodes courtes (2, 3 ou 7). Le coup « retirer 1 » borne la croissance des valeurs de Grundy et régularise la séquence.
Absence de 1 : Le jeu \(S(\{2, 5, 7\})\) a une période beaucoup plus longue (22), car sans le coup « 1 » certaines positions deviennent inaccessibles directement, créant des structures plus complexes.
Pre-periode nulle : Tous les exemples ont une pré-période de 0, ce qui signifie que la périodicité commence immédiatement (\(n_0 = 0\)). C’est typique des jeux de soustraction simples.
Périodes fondamentales vs multiples : on cherche ici la plus petite période valide, pas un multiple. Pour \(S(\{1,2\})\) la séquence \(0,1,2,0,1,2,\ldots\) est de période fondamentale 3 (tout multiple de 3 est aussi une période, mais seule la plus petite est informative).
Theoreme de Guy : Pour tout jeu de soustraction fini, la sequence de Grundy est ultimement periodique. La periode peut etre bornee, mais les bornes exactes restent un problème ouvert.
# Visualisation de la periodicite
moves = {1, 3, 4}
pre, period, seq = find_periodicity(moves, max_n=100)
fig, (ax1, ax2) = plt.subplots(2, 1, figsize=(14, 8))
# Graphique 1: Sequence complete avec coloration
n_values = list(range(len(seq)))
colors = ['lightgray' if i < pre else plt.cm.Set1((seq[i] % 8) / 8) for i in n_values]
ax1.bar(n_values, seq, color=colors, edgecolor='none')
ax1.axvline(x=pre, color='red', linestyle='--', linewidth=2, label=f'Fin pre-periode ({pre})')
ax1.axvline(x=pre + period, color='blue', linestyle=':', linewidth=2, label=f'Fin 1ere periode ({pre + period})')
ax1.set_xlabel('n')
ax1.set_ylabel('Grundy(n)')
ax1.set_title(f'Jeu de soustraction S({moves}) - Periode = {period}')
ax1.legend()
# Graphique 2: Une periode isolee
one_period = seq[pre:pre + period]
ax2.bar(range(period), one_period, color=[plt.cm.viridis(g / max(one_period) if max(one_period) > 0 else 0) for g in one_period])
ax2.set_xlabel('Position dans la periode')
ax2.set_ylabel('Grundy')
ax2.set_title(f'Une periode : {one_period}')
plt.tight_layout()
plt.show()
print(f"\nPre-periode: {pre}, Periode: {period}")
print(f"Motif periodique: {one_period}")
Pre-periode: 0, Periode: 7
Motif periodique: [0, 1, 0, 1, 2, 3, 2]Lecture ancrée : La sortie donne Pre-periode: 0, Periode: 7 : le cycle [0, 1, 0, 1, 2, 3, 2] démarre dès n = 0, sans pré-période — le cas le plus simple de l’ultime périodicité (théorème de Guy, 1996). Le graphique colore chaque barre selon sa valeur de Grundy et marque en pointillés la fin de la pré-période et de la première période.
Le jeu de Wythoff (1907) est une generalisation elegante du Nim a 2 tas :
Les P-positions sont \((\lfloor n\phi \rfloor, \lfloor n\phi^2 \rfloor)\) ou \(\phi = \frac{1+\sqrt{5}}{2}\) (nombre d’or).
Premières P-positions : (0,0), (1,2), (3,5), (4,7), (6,10), (8,13), …
# Nombre d'or
PHI = (1 + np.sqrt(5)) / 2
def wythoff_p_positions(n_max: int) -> List[Tuple[int, int]]:
"""Genere les P-positions du jeu de Wythoff."""
p_positions = []
for n in range(n_max):
a = int(n * PHI)
b = int(n * PHI * PHI)
if b <= n_max:
p_positions.append((a, b))
return p_positions
def is_wythoff_p_position(a: int, b: int) -> bool:
"""Verifie si (a,b) est une P-position (Beatty sequence)."""
if a > b:
a, b = b, a
if a == 0 and b == 0:
return True
# Utiliser la caracterisation de Beatty
n = b - a
expected_a = int(n * PHI)
expected_b = int(n * PHI * PHI)
return a == expected_a and b == expected_b
# Afficher les premieres P-positions
p_pos = wythoff_p_positions(20)
print("P-positions du jeu de Wythoff:")
print("="*40)
for i, (a, b) in enumerate(p_pos[:15]):
diff = b - a
print(f" n={i}: ({a}, {b}) [difference = {diff}]")
print(f"\nNombre d'or phi = {PHI:.6f}")
print(f"phi^2 = {PHI**2:.6f} = phi + 1")P-positions du jeu de Wythoff:
========================================
n=0: (0, 0) [difference = 0]
n=1: (1, 2) [difference = 1]
n=2: (3, 5) [difference = 2]
n=3: (4, 7) [difference = 3]
n=4: (6, 10) [difference = 4]
n=5: (8, 13) [difference = 5]
n=6: (9, 15) [difference = 6]
n=7: (11, 18) [difference = 7]
n=8: (12, 20) [difference = 8]
Nombre d'or phi = 1.618034
phi^2 = 2.618034 = phi + 1Lecture ancrée : Les P-positions de Wythoff s’alignent sur deux droites de pentes φ et 1/φ. Le nombre d’or vaut φ ≈ 1.618034 et vérifie φ² = 2.618034 = φ + 1 (sortie du notebook). Cette structure se lit déjà dans le tableau : la différence des coordonnées de chaque paire vaut exactement n (n = 8 : (12, 20), différence = 8) et croît régulièrement d’une ligne à l’autre.
Les résultats montrent la structure elegante des P-positions de Wythoff :
| n | P-position \((a_n, b_n)\) | Différence \(b_n - a_n\) |
|---|---|---|
| 0 | (0, 0) | 0 |
| 1 | (1, 2) | 1 |
| 2 | (3, 5) | 2 |
| 3 | (4, 7) | 3 |
Proprietes remarquables :
Différence croissante : \(b_n - a_n = n\) pour tout \(n\). Cette propriete caracterise completement les P-positions.
Sequences complementaires : Les valeurs \(\{a_n\}\) et \(\{b_n\}\) partitionnent \(\mathbb{N}^*\) (chaque entier positif apparait exactement une fois).
Identite du nombre d’or : \(\phi^2 = \phi + 1\) explique pourquoi \(b_n \approx a_n + n\) : en effet, \(n \cdot \phi^2 = n \cdot \phi + n\).
Application stratégique : Pour determiner si \((a, b)\) est une P-position, il suffit de verifier si \(a = \lfloor (b-a) \cdot \phi \rfloor\).
# Visualisation des P-positions de Wythoff
fig, ax = plt.subplots(figsize=(10, 10))
max_val = 30
# Creer une grille de positions
grid = np.zeros((max_val + 1, max_val + 1))
# Marquer les P-positions
for a, b in wythoff_p_positions(max_val):
if a <= max_val and b <= max_val:
grid[a, b] = 1
grid[b, a] = 1 # Symetrie
# Afficher
ax.imshow(grid, cmap='RdYlGn', origin='lower', extent=[-0.5, max_val+0.5, -0.5, max_val+0.5])
# Ajouter les points
for a, b in wythoff_p_positions(max_val):
if a <= max_val and b <= max_val:
ax.plot(b, a, 'ko', markersize=8)
ax.plot(a, b, 'ko', markersize=8)
# Diagonale
ax.plot([0, max_val], [0, max_val], 'b--', alpha=0.3, label='Diagonale')
# Lignes de pente phi et 1/phi
x = np.linspace(0, max_val, 100)
ax.plot(x * PHI, x, 'r--', alpha=0.5, label=f'Pente 1/phi')
ax.plot(x, x * PHI, 'g--', alpha=0.5, label=f'Pente phi')
ax.set_xlim(-0.5, max_val + 0.5)
ax.set_ylim(-0.5, max_val + 0.5)
ax.set_xlabel('Tas B')
ax.set_ylabel('Tas A')
ax.set_title('P-positions du jeu de Wythoff\n(Vert = P-position, Rouge = N-position)')
ax.legend()
ax.set_aspect('equal')
plt.show()
print("Les P-positions s'alignent sur des droites de pente phi et 1/phi !")
Les P-positions s'alignent sur des droites de pente phi et 1/phi !Lecture ancrée : Chaque point noir de la figure marque une position perdante ; les deux faisceaux suivent les pentes φ ≈ 1.618 et son inverse 1/φ ≈ 0.618.
Le graphique revele la structure geometrique remarquable des P-positions de Wythoff :
| Propriete | Observation |
|---|---|
| Distribution | Les P-positions (points noirs) forment deux faisceaux de droites |
| Pentes | Les droites ont des pentes phi et 1/phi, liees au nombre d’or |
| Complementarite | Chaque entier positif apparait exactement une fois comme première ou seconde coordonnee |
Sequences de Beatty : Les P-positions correspondent aux sequences de Beatty : - \(a_n = \lfloor n \cdot \phi \rfloor\) (sequence inferieure) - \(b_n = \lfloor n \cdot \phi^2 \rfloor\) (sequence superieure)
Ces deux sequences partitionnent les entiers positifs - c’est le theoreme de Beatty (1926).
Connexion profonde : Le lien entre Wythoff et le nombre d’or n’est pas fortuit. La recurrence de Fibonacci \(F_{n+1} = F_n + F_{n-1}\) encode exactement les transitions entre P-positions consecutives.
def wythoff_winning_move(a: int, b: int) -> Optional[Tuple[int, int]]:
"""
Trouve un coup gagnant au Wythoff.
Retourne la nouvelle position (a', b') ou None si P-position.
"""
if is_wythoff_p_position(a, b):
return None
# Essayer tous les coups possibles
# Type 1: Retirer de A seul
for new_a in range(a):
if is_wythoff_p_position(new_a, b):
return (new_a, b)
# Type 2: Retirer de B seul
for new_b in range(b):
if is_wythoff_p_position(a, new_b):
return (a, new_b)
# Type 3: Retirer le meme nombre des deux (diagonale)
for k in range(1, min(a, b) + 1):
if is_wythoff_p_position(a - k, b - k):
return (a - k, b - k)
return None # Ne devrait pas arriver pour une N-position
# Exemples de strategie
examples = [(5, 8), (7, 11), (3, 5), (10, 15)]
print("Strategie optimale au Wythoff")
print("="*50)
for a, b in examples:
pos_type = "P" if is_wythoff_p_position(a, b) else "N"
move = wythoff_winning_move(a, b)
print(f"({a}, {b}) [{pos_type}]:", end=" ")
if move:
print(f"-> {move}")
else:
print("Position perdante")Strategie optimale au Wythoff
==================================================
(5, 8) [N]: -> (5, 3)
(7, 11) [N]: -> (7, 4)
(3, 5) [P]: Position perdante
(10, 15) [N]: -> (9, 15)Lecture ancrée : La stratégie gagnante consiste à déplacer les jetons vers une P-position. Par exemple, depuis (5,8), le coup (5,3) aligné les pieces sur la droite de pente φ, forçant l’adversaire dans une position perdante.
Lecture ancrée : La sortie illustre les trois familles de coups du Wythoff — retirer du tas A seul, du tas B seul, ou le même nombre des deux (diagonale). Depuis (7, 11) le coup gagnant est (7, 4) ; depuis (10, 15) c’est (9, 15) ; mais (3, 5) est une P-position : la fonction rend None. L’exercice suivant demande de générer ces positions par la formule du nombre d’or et de les vérifier avec is_wythoff_p_position.
Objectif : Generer les N premières P-positions de Wythoff en utilisant la formule du nombre d’or, verifier chaque position avec is_wythoff_p_position, puis trouver un coup gagnant depuis une N-position donnee.
Contexte : Les fonctions wythoff_p_positions, is_wythoff_p_position et wythoff_winning_move sont déjà implementees. Utilisez-les pour explorer la structure.
def exercice_wythoff_verification(n_max: int = 15) -> dict:
"""
Genere et verifie les P-positions de Wythoff.
Args:
n_max: nombre de P-positions a generer
Returns:
dict avec :
'p_positions': liste des (a, b) P-positions
'all_verified': True si toutes passe is_wythoff_p_position
'winning_moves': dict {(a,b): coup_gagnant} pour des N-positions
"""
return {"p_positions": [], "all_verified": False, "winning_moves": {}} # TODO etudiant
result_wythoff = exercice_wythoff_verification(15)
print(f"P-positions: {result_wythoff['p_positions'][:8]}")
print(f"Toutes verifiees: {result_wythoff['all_verified']}")
print(f"Coups gagnants: {result_wythoff['winning_moves']}")
print("Exercice a completer")P-positions: []
Toutes verifiees: False
Coups gagnants: {}
Exercice a completerLe theoreme de Sprague-Grundy nous permet d’analyser des combinaisons de jeux :
\[G(J_1 + J_2 + ... + J_k) = G(J_1) \oplus G(J_2) \oplus ... \oplus G(J_k)\]
Considerons un jeu composite : 3 tas de soustraction avec des règles différentes.
class CompositeGame:
"""Un jeu compose de plusieurs sous-jeux de soustraction."""
def __init__(self, games: List[Tuple[Set[int], int]]):
"""
games: liste de (moves, taille) pour chaque composante
"""
self.games = games
self.memos = [{} for _ in games]
def grundy(self, component: int, size: int) -> int:
"""Grundy d'une composante."""
moves = self.games[component][0]
return grundy_subtraction(size, moves, self.memos[component])
def total_grundy(self, sizes: List[int]) -> int:
"""Grundy total = XOR des Grundy individuels."""
return nim_sum(*[self.grundy(i, s) for i, s in enumerate(sizes)])
def position_type(self, sizes: List[int]) -> str:
"""P ou N."""
return 'P' if self.total_grundy(sizes) == 0 else 'N'
def find_winning_move(self, sizes: List[int]) -> Optional[Tuple[int, int]]:
"""Trouve un coup gagnant LEGAL. Retourne (composante, nouvelle_taille).
Ne considere que les soustractions legales (m dans moves) : la taille
resultante doit etre atteignable en un seul coup, pas juste avoir le bon
Grundy (sinon on suggererait un retrait impossible, ex. retirer 4 d'un jeu
S({2,3})). Sprague-Grundy garantit qu'un coup legal gagnant existe pour
toute position N (composante portant le bit de poids fort du Grundy total).
"""
if self.total_grundy(sizes) == 0:
return None
for i, (moves, _) in enumerate(self.games):
target_g = nim_sum(*[self.grundy(j, sizes[j]) for j in range(len(sizes)) if j != i])
# Chercher un coup LEGAL (retrait de m tokens, m dans moves) menant
# au Grundy cible. sorted(moves) pour un resultat deterministe.
for m in sorted(moves):
if m > sizes[i]:
continue
new_size = sizes[i] - m
if self.grundy(i, new_size) == target_g:
return (i, new_size)
return None
# Creer un jeu composite : 3 jeux de soustraction differents
composite = CompositeGame([
({1, 2}, 7), # Composante 0: S({1,2}) avec 7 jetons
({1, 3, 4}, 5), # Composante 1: S({1,3,4}) avec 5 jetons
({2, 3}, 6), # Composante 2: S({2,3}) avec 6 jetons
])
sizes = [7, 5, 6]
print("Jeu composite : 3 jeux de soustraction")
print("="*50)
print(f"Composante 0: S({{1,2}}) avec {sizes[0]} jetons -> G={composite.grundy(0, sizes[0])}")
print(f"Composante 1: S({{1,3,4}}) avec {sizes[1]} jetons -> G={composite.grundy(1, sizes[1])}")
print(f"Composante 2: S({{2,3}}) avec {sizes[2]} jetons -> G={composite.grundy(2, sizes[2])}")
print(f"\nGrundy total: {composite.total_grundy(sizes)}")
print(f"Position: {composite.position_type(sizes)}")
move = composite.find_winning_move(sizes)
if move:
i, new_size = move
print(f"\nCoup gagnant: Composante {i}, reduire de {sizes[i]} a {new_size}")
new_sizes = sizes.copy()
new_sizes[i] = new_size
print(f"Nouvelle position: {new_sizes} -> G={composite.total_grundy(new_sizes)}")Jeu composite : 3 jeux de soustraction
==================================================
Composante 0: S({1,2}) avec 7 jetons -> G=1
Composante 1: S({1,3,4}) avec 5 jetons -> G=3
Composante 2: S({2,3}) avec 6 jetons -> G=0
Grundy total: 2
Position: N
Coup gagnant: Composante 1, reduire de 5 a 1
Nouvelle position: [7, 1, 6] -> G=0Lecture ancrée : Le calcul montre comment la fonction de Grundy d’un jeu composé se détermine par le XOR des valeurs de Grundy de ses composantes. Ici, le XOR des valeurs (1, 3, 0) donne 2, ce qui classe la position comme gagnante (N-position). La réduction proposée sur la composante 1 passe le Grundy total à 0.
Objectif : Construire un jeu composite avec trois composantes de soustraction différentes, calculer le Grundy total via XOR, determiner le type de position (P ou N), et trouver un coup gagnant si possible.
Contexte : La classe CompositeGame implemente le theoreme de Sprague-Grundy pour les jeux composites. Utilisez-la pour analyser une nouvelle configuration.
def exercice_composite_grundy() -> dict:
"""
Analyse un jeu composite avec S({1,2,3}), S({2,4}), S({1,5}).
Returns:
dict avec :
'component_grundys': liste des Grundy individuels
'total_grundy': Grundy total (XOR)
'position_type': 'P' ou 'N'
'winning_move': (composante, nouvelle_taille) ou None
"""
return {"component_grundys": [], "total_grundy": 0, "position_type": "P", "winning_move": None} # TODO etudiant
result_comp = exercice_composite_grundy()
print(f"Grundy individuels: {result_comp['component_grundys']}")
print(f"Grundy total: {result_comp['total_grundy']}")
print(f"Position: {result_comp['position_type']}")
print(f"Coup gagnant: {result_comp['winning_move']}")
print("Exercice a completer")Grundy individuels: []
Grundy total: 0
Position: P
Coup gagnant: None
Exercice a completerCreons une visualisation des valeurs de Grundy pour mieux comprendre leur structure.
def visualize_grundy_comparison(games_dict: dict, max_n: int = 50):
"""
Compare les valeurs de Grundy de plusieurs jeux.
"""
n_games = len(games_dict)
fig, axes = plt.subplots(n_games, 1, figsize=(14, 3 * n_games), sharex=True)
if n_games == 1:
axes = [axes]
for ax, (name, moves) in zip(axes, games_dict.items()):
memo = {}
values = [grundy_subtraction(n, moves, memo) for n in range(max_n)]
# Colorer par valeur de Grundy
colors = [plt.cm.tab10(v % 10) for v in values]
ax.bar(range(max_n), values, color=colors, edgecolor='none')
ax.set_ylabel('Grundy')
ax.set_title(f'S({moves}) : {name}')
# Marquer les P-positions
p_pos = [i for i, v in enumerate(values) if v == 0]
ax.scatter(p_pos, [0] * len(p_pos), color='red', s=50, zorder=5, marker='v', label='P-positions')
# Ajouter la periode si trouvee
pre, period, _ = find_periodicity(moves, max_n=200)
if period > 0:
ax.text(0.98, 0.95, f'Periode: {period}', transform=ax.transAxes,
ha='right', va='top', fontsize=10,
bbox=dict(boxstyle='round', facecolor='wheat'))
axes[-1].set_xlabel('n (taille du tas)')
plt.tight_layout()
plt.show()
# Comparer plusieurs jeux
games_to_compare = {
"Fibonacci-like": {1, 2},
"Classique": {1, 3, 4},
"Impair seulement": {1, 3, 5},
"Pair seulement": {2, 4, 6},
}
visualize_grundy_comparison(games_to_compare)
Lecture ancrée : La visualisation compare les fonctions de Grundy de quatre jeux de soustraction différents. Malgré des ensembles de coups variés, chaque jeu atteint une périodicité stable, démontrant la puissance de l’analyse par la fonction de Grundy en théorie des jeux combinatoires.
Le jeu de Chomp est un jeu partizan (contrairement a Nim qui est impartial) :
Le premier joueur a une stratégie gagnante pour toute tablette \(m \times n\) avec \(m, n \geq 2\).
Mais : la preuve est non-constructive (“strategy stealing argument”), et trouver la stratégie optimale est NP-difficile !
def chomp_moves(position: Tuple[int, ...]) -> List[Tuple[int, ...]]:
"""Genere tous les coups legaux depuis une position."""
moves = []
for col in range(len(position)):
for row in range(1, position[col] + 1):
# Manger (row, col) et tout ce qui est au-dessus/a droite
new_pos = list(position)
for c in range(col, len(position)):
new_pos[c] = min(new_pos[c], row - 1)
# Supprimer les colonnes vides a droite
while new_pos and new_pos[-1] == 0:
new_pos.pop()
if tuple(new_pos) != (0,) and new_pos:
moves.append(tuple(new_pos))
return moves
@lru_cache(maxsize=10000)
def chomp_is_losing(position: Tuple[int, ...]) -> bool:
"""Determine si une position est perdante (P-position)."""
if position == (1,) or position == ():
return True
for move in chomp_moves(position):
if chomp_is_losing(move):
return False
return True
# Analyser Chomp 3x3
print("Analyse du jeu de Chomp 3x3")
print("="*40)
initial = (3, 3, 3)
print(f"Position initiale: {initial}")
print(f"Type: {'P (perdante)' if chomp_is_losing(initial) else 'N (gagnante)'}")
print("\nCoups depuis la position initiale:")
for move in chomp_moves(initial)[:8]:
status = "P" if chomp_is_losing(move) else "N"
print(f" {move} [{status}]")Analyse du jeu de Chomp 3x3
========================================
Position initiale: (3, 3, 3)
Type: N (gagnante)
Coups depuis la position initiale:
(1, 1, 1) [N]
(2, 2, 2) [N]
(3,) [N]
(3, 1, 1) [P]
(3, 2, 2) [N]
(3, 3) [N]
(3, 3, 1) [N]
(3, 3, 2) [N]Lecture ancrée : Parmi les 8 coups légaux depuis (3, 3, 3), un seul — (3, 1, 1) — mène à une P-position ; les 7 autres laissent une N-position à l’adversaire. C’est le coup optimal, et la fonction ci-dessous le visualise sur la tablette : carré empoisonné en rouge au coin (0, 0), carrés de chocolat, une figure par position.
L’analyse de Chomp 3x3 revele plusieurs points importants :
| Position | Type | Signification |
|---|---|---|
| (3,3,3) | N | Le premier joueur peut forcer la victoire |
| (3,1,1) | P | Position perdante - coup gagnant optimal |
| (1,1,1), (3,3), etc. | N | Le second joueur peut contre-attaquer |
Observations cles :
Stratégie gagnante : Depuis (3,3,3), le coup optimal est de jouer vers (3,1,1), l’unique P-position accessible.
Asymetrie du jeu : Contrairement a Nim, Chomp n’est pas symetrique - la stratégie “copier l’adversaire” ne fonctionne pas a cause du carre empoisonne.
Complexite computationnelle : Bien que nous puissions calculer les positions pour de petites tablettes, le problème est NP-difficile en general. Le theoreme de Gale garantit l’existence d’une stratégie gagnante sans la construire explicitement.
Note technique : La fonction
chomp_is_losingutilise la memoisation (@lru_cache) car le nombre de positions croit exponentiellement avec la taille de la tablette.
def visualize_chomp(position: Tuple[int, ...], title: str = "Chomp"):
"""Visualise une position de Chomp."""
if not position:
position = (0,)
max_height = max(position) if position else 1
n_cols = len(position)
fig, ax = plt.subplots(figsize=(max(6, n_cols), max(4, max_height)))
for col in range(n_cols):
for row in range(position[col]):
color = 'red' if (col == 0 and row == 0) else 'chocolate'
rect = plt.Rectangle((col, row), 0.9, 0.9, facecolor=color, edgecolor='brown')
ax.add_patch(rect)
ax.set_xlim(-0.1, n_cols + 0.1)
ax.set_ylim(-0.1, max_height + 0.1)
ax.set_aspect('equal')
ax.set_title(f"{title}\nPosition: {position}")
ax.set_xlabel('Colonne')
ax.set_ylabel('Ligne')
ax.plot([], [], 's', color='red', markersize=15, label='Poison')
ax.plot([], [], 's', color='chocolate', markersize=15, label='Chocolat')
ax.legend(loc='upper right')
plt.show()
# Visualiser quelques positions
visualize_chomp((3, 3, 3), "Position initiale 3x3")
visualize_chomp((2, 2, 1), "Apres un coup")
visualize_chomp((1,), "Position finale (perdante)")
Trouvez la periode et la pre-periode du jeu de soustraction S({1, 2, 4, 8}).
Dans le Wythoff (k), on peut retirer jusqu’a k fois le même nombre des deux tas. Implementez l’analyse pour k=2.
Implementez un joueur optimal pour Chomp 4x4 et jouez contre lui.
# Exercice 1 - A completer
# Utilisez la fonction find_periodicity() definie ci-dessus pour analyser
# le jeu de soustraction S({1, 2, 4, 8}).
#
# TODO:
# 1. Definir l'ensemble de coups moves = {1, 2, 4, 8}
# 2. Appeler find_periodicity(moves, max_n=200)
# 3. Afficher la pre-periode, la periode, et les 20 premiers termes
# 4. Interpreter: quelles positions sont perdantes (Grundy = 0) ?
# Votre code ici
pass
print("Exercice a completer : jeux combinatoires")Exercice a completer : jeux combinatoiresCe notebook a approfondi la théorie des jeux combinatoires au-dela des fondations du notebook 8, en explorant trois axes complementaires. Premierement, l’analyse de la periodicite des valeurs de Grundy a revele que les sequences deviennent predictibles après un certain point, avec des periodes d’autant plus longues que l’ensemble de coups est inhabituel (l’absence du coup “1” engendre ainsi des periodes nettement plus etendues). Deuxiemement, le jeu de Wythoff a illustre un lien remarquable entre combinatoire et geometrie : les P-positions s’alignent sur des droites de pente egale au nombre d’or, formalisees par les sequences de Beatty qui partitionnent les entiers positifs. Troisiemement, l’étude du jeu de Chomp a introduit les jeux partizans et le theoreme de Gale, dont la preuve non-constructive par “strategy stealing” garantit l’existence d’une stratégie gagnante pour le premier joueur sans la construire.
Ces approfondissements montrent que la théorie de Sprague-Grundy, loin de se limiter au Nim, offre un cadre unificateur pour une large classe de jeux. La retour au track principal s’effectue avec le notebook sur l’induction arriere : GameTheory-09-BackwardInduction-Python.
| Concept | Description |
|---|---|
| Periodicite | Les Grundy des jeux de soustraction sont ultimement periodiques |
| Wythoff | P-positions liees au nombre d’or phi |
| Jeux composites | Grundy total = XOR des Grundy individuels |
| Chomp | Jeu partizan NP-difficile, stratégie non-constructive |
Navigation : << 8-CombinatorialGames | Index | 8b-Lean-CombinatorialGames