GameTheory 8c - Jeux Combinatoires : Approfondissement — twin C# .NET

Navigation : << 8-CombinatorialGames (track principal) | Index

Autres side tracks : 8b-Lean-CombinatorialGames

Kernel : .NET (C#) | Twin Python : 8c-CombinatorialGames-Python

Introduction

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 :

Periodicite des valeurs de Grundy
Jeu de Wythoff - une generalisation elegante de Nim
Jeux multi-composantes - application de Sprague-Grundy
Visualisations interactives
Jeu de Chomp - un jeu partizan

Objectifs d’apprentissage

A l’issue de ce notebook, vous saurez :

Reconnaitre la periodicite (ultime) des valeurs de Grundy
Analyser le jeu de Wythoff comme generalisation elegante de Nim
Calculer les valeurs de Grundy de jeux multi-composantes via le theoreme de Sprague-Grundy
Explorer le jeu de Chomp et la notion de jeu partizan

Duree estimee : 45 minutes

Prerequis

Notebook 8 : Jeux Combinatoires (concepts de base)

// Configuration et imports
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;

Console.WriteLine("Notebook 8c - Jeux Combinatoires : Approfondissement (twin C# .NET)");
Console.WriteLine(new string('=', 55));

Notebook 8c - Jeux Combinatoires : Approfondissement (twin C# .NET)
=======================================================

Fonctions de base (rappel du notebook 8)

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.lean de l’hommage Conway. En particulier, nimSum_self (deux tas egaux forment une P-position) et isWinningNim_345 (position [3,4,5] est gagnante) y sont verifies par native_decide. Le notebook companion 8b-Lean-CombinatorialGames explore ces preuves en detail.

// Fonctions de base (rappel du notebook 8) : mex, Grundy (soustraction), nim-sum.
static int Mex(IEnumerable<int> values)
{
    var s = values.ToHashSet();
    int n = 0;
    while (s.Contains(n)) n++;
    return n;
}

static int GrundySubtraction(int n, HashSet<int> moves, Dictionary<int, int> memo)
{
    if (memo.TryGetValue(n, out var cached)) return cached;
    if (n == 0) return 0;
    var reachable = new HashSet<int>();
    foreach (var m in moves)
        if (m <= n) reachable.Add(GrundySubtraction(n - m, moves, memo));
    int result = Mex(reachable);
    memo[n] = result;
    return result;
}

static int NimSum(params int[] values)
{
    int r = 0;
    foreach (var v in values) r ^= v;
    return r;
}

Console.WriteLine("Fonctions de base chargees : mex, grundy_subtraction, nim_sum.");

Fonctions de base chargees : mex, grundy_subtraction, nim_sum.

1. Periodicite des valeurs de Grundy

Pour les jeux de soustraction, les valeurs de Grundy deviennent souvent periodiques après un certain point.

Theoreme (Guy, 1996)

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)\]

// Detection de periodicite (theoreme de Guy 1996) : les Grundy des jeux de
// soustraction finis sont ULTIMEMENT periodiques : G(n+p) = G(n) pour n >= n0.
static (int pre, int period, List<int> seq) FindPeriodicity(HashSet<int> moves, int maxN = 500, int minPeriod = 5)
{
    var memo = new Dictionary<int, int>();
    var sequence = Enumerable.Range(0, maxN).Select(n => GrundySubtraction(n, moves, memo)).ToList();
    for (int prePeriod = 0; prePeriod < maxN / 3; prePeriod++)
    {
        for (int period = 1; period < (maxN - prePeriod) / 3; period++)
        {
            bool isPeriodic = true;
            int check = Math.Min(100, maxN - prePeriod - period);
            for (int i = 0; i < check; i++)
            {
                if (sequence[prePeriod + i] != sequence[prePeriod + period + i]) { isPeriodic = false; break; }
            }
            if (isPeriodic && period >= minPeriod)
            {
                // Minimisation : un candidat p peut admettre un diviseur d comme
                // periode reelle (ex: motif 0,1,2,0,1,2 detecte a p=6 mais reelle=3).
                // On balaie les diviseurs d de p dans l'ordre croissant et on
                // retourne le MIN d tel que le motif de longueur p soit lui-meme
                // periodique de periode d.
                int minD = period;
                for (int d = 1; d * 2 <= period; d++)
                {
                    if (period % d != 0) continue;
                    bool divisorOk = true;
                    for (int i = 0; i + d < period && divisorOk; i++)
                        if (sequence[prePeriod + i] != sequence[prePeriod + i + d]) divisorOk = false;
                    if (divisorOk) { minD = d; break; }
                }
                return (prePeriod, minD, sequence);
            }
        }
    }
    return (-1, -1, sequence);
}

var games = new List<HashSet<int>>
{
    new HashSet<int> { 1, 2 },      // Nim modifie
    new HashSet<int> { 1, 3 },
    new HashSet<int> { 1, 3, 4 },   // Exemple classique
    new HashSet<int> { 1, 2, 5 },
    new HashSet<int> { 2, 5, 7 },   // Sans le coup 1
};

Console.WriteLine("Periodicite des jeux de soustraction");
Console.WriteLine(new string('=', 50));
Console.WriteLine($"{"Moves",-15} | {"Pre-periode",12} | {"Periode",8}");
Console.WriteLine(new string('-', 50));
foreach (var moves in games)
{
    var (pre, period, seq) = FindPeriodicity(moves);
    string movesStr = "{" + string.Join(", ", moves.OrderBy(x => x)) + "}";
    string preStr = period > 0 ? pre.ToString() : "?";
    string perStr = period > 0 ? period.ToString() : "?";
    Console.WriteLine($"{movesStr,-15} | {preStr,12} | {perStr,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 |       22

Interpretation des résultats

L’analyse de periodicite revele des structures interessantes :

Jeu S(M)	Periode	Observation
{1, 2}	3	Période courte, motif cyclique simple
{1, 3}	2	Période minimale (alternance)
{1, 3, 4}	7	Periode = max(M) + 3
{2, 5, 7}	22	Periodes longues sans le coup “1”

Observations cles :

Regularite : Les jeux contenant 1 dans M ont souvent des periodes courtes et regulieres.
Absence de 1 : Le jeu S({2, 5, 7}) a une periode beaucoup plus longue (22), car l’absence du coup “1” créé des structures plus complexes.
Pre-periode nulle : Tous les exemples ont une pre-periode de 0, ce qui signifie que la periodicite commence immediatement. C’est typique des jeux de soustraction simples.

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.

#load "../Probas/Infer/SvgChartHelper.cs"
// Visualisation de la sequence de Grundy (valeurs G(n)) et de sa structure periodique.
// Rendu SVG inline statique via SvgChartHelper.cs (#6942/#6927) : zero dependance, s'affiche
// sur GitHub / nbviewer / offline. L'ancien CDN Plotly rendait BLANC en sandbox statique
// (aucun script tiers execute). Le code couleur par-barre (pre-periode / 1ere periode /
// repetitions) est porte nativement par SvgChartHelper.Bar(colors:, legend:). Cf #3801 / C548-L2.

var moves = new HashSet<int> { 1, 3, 4 };
var (pre, period, seq) = FindPeriodicity(moves, maxN: 100);
int show = Math.Min(35, seq.Count);

var xLabels = Enumerable.Range(0, show).Select(i => i.ToString()).ToArray();
var yGrundy = seq.GetRange(0, show).Select(v => (double)v).ToArray();

// Couleur par barre : rouge = pre-periode (transitoire), bleu = 1ere periode (motif),
// gris = repetitions du motif. Le changement de couleur materialise les frontieres
// (fin de pre-periode, fin de la 1ere periode) sans lignes/annotations (rendu SVG inline).
var barColors = Enumerable.Range(0, show).Select(i =>
    i < pre ? "#C44E52"
    : i < pre + period ? "#4C72B0"
    : "#888888").ToArray();

// Legende honnete : n'inclure que les categories reellement presentes (pre-periode vide si pre=0).
var legend8 = new List<(string, string)>();
if (pre > 0) legend8.Add(("#C44E52", "pre-periode"));
legend8.Add(("#4C72B0", "1ere periode"));
if (show > pre + period) legend8.Add(("#888888", "repetitions"));

display(SvgChartHelper.Bar(
    "Sequence de Grundy du jeu de soustraction S({1,3,4})",
    xLabels, yGrundy, width: 900, height: 340, colors: barColors, legend: legend8));

var onePeriod = seq.GetRange(pre, period);
Console.WriteLine($"Jeu de soustraction S({{1,3,4}}) - Periode = {period}, Pre-periode = {pre}");
Console.WriteLine($"Motif periodique: [{string.Join(", ", onePeriod)}]");

Jeu de soustraction S({1,3,4}) - Periode = 7, Pre-periode = 0
Motif periodique: [0, 1, 0, 1, 2, 3, 2]

2. Jeu de Wythoff

Le jeu de Wythoff (1907) est une generalisation elegante du Nim a 2 tas :

Deux tas de jetons \((a, b)\)
A chaque tour, on peut :
1. Retirer des jetons d’un seul tas (comme Nim)
2. Retirer le même nombre des deux tas (diagonale)

P-positions

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), …

// Jeu de Wythoff (1907) : generalisation de Nim a 2 tas (retrait diagonal permis).
// P-positions = (floor(n*phi), floor(n*phi^2)) ou phi = nombre d'or (Beatty 1926).
double PHI = (1.0 + Math.Sqrt(5.0)) / 2.0;

static List<(int a, int b)> WythoffPPositions(int nMax, double phi)
{
    var result = new List<(int, int)>();
    for (int n = 0; n < nMax; n++)
    {
        int a = (int)(n * phi);
        int b = (int)(n * phi * phi);
        if (b <= nMax) result.Add((a, b));
    }
    return result;
}

static bool IsWythoffPPosition(int a, int b, double phi)
{
    if (a > b) (a, b) = (b, a);
    if (a == 0 && b == 0) return true;
    int n = b - a;                    // difference = index de Beatty
    int expectedA = (int)(n * phi);
    int expectedB = (int)(n * phi * phi);
    return a == expectedA && b == expectedB;
}

var pPos = WythoffPPositions(20, PHI);
Console.WriteLine("P-positions du jeu de Wythoff:");
Console.WriteLine(new string('=', 40));
for (int i = 0; i < Math.Min(15, pPos.Count); i++)
{
    var (a, b) = pPos[i];
    Console.WriteLine($"  n={i}: ({a}, {b})  [difference = {b - a}]");
}
Console.WriteLine();
Console.WriteLine($"Nombre d'or phi = {PHI.ToString("F6", CultureInfo.InvariantCulture)}");
Console.WriteLine($"phi^2 = {(PHI * PHI).ToString("F6", CultureInfo.InvariantCulture)} = 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 + 1

Interpretation des P-positions

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 ASCII des P-positions de Wythoff (grille -> P/. sur la demi-diagonale).
int maxVal = 16;
var pList = WythoffPPositions(maxVal, PHI);
bool IsP(int a, int b)
{
    int x = Math.Min(a, b), y = Math.Max(a, b);
    return pList.Contains((x, y));
}
Console.WriteLine($"Grille Wythoff {maxVal}x{maxVal} (P = P-position, . = N-position, \\ = diagonale)");
Console.WriteLine();
Console.Write("A\\B ");
for (int b = 0; b <= maxVal; b++) Console.Write((b % 10).ToString()[0]);
Console.WriteLine();
for (int a = maxVal; a >= 0; a--)
{
    string label = "A=" + a.ToString().PadLeft(2);
    Console.Write(label + " ");
    for (int b = 0; b <= maxVal; b++)
    {
        if (IsP(a, b)) Console.Write('P');
        else if (a == b) Console.Write('\\');
        else Console.Write('.');
    }
    Console.WriteLine();
}
Console.WriteLine();
Console.WriteLine("Les P-positions s'alignent sur des droites de pente phi et 1/phi !");

Grille Wythoff 16x16 (P = P-position, . = N-position, \ = diagonale)

A\B 01234567890123456
A=16 ................\
A=15 .........P.....\.
A=14 ..............\..
A=13 ........P....\...
A=12 ............\....
A=11 ...........\.....
A=10 ......P...\......
A= 9 .........\.....P.
A= 8 ........\....P...
A= 7 ....P..\.........
A= 6 ......\...P......
A= 5 ...P.\...........
A= 4 ....\..P.........
A= 3 ...\.P...........
A= 2 .P\..............
A= 1 .\P..............
A= 0 P................

Les P-positions s'alignent sur des droites de pente phi et 1/phi !

Interpretation de la visualisation

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.

// Strategie optimale au Wythoff : depuis une N-position, trouver un coup gagnant
// (ramener a une P-position). Trois types de coups : tas A seul, tas B seul, diagonale.
static (int a, int b)? WythoffWinningMove(int a, int b, double phi)
{
    if (IsWythoffPPosition(a, b, phi)) return null;
    // Type 1 : retirer de A seul
    for (int newA = a - 1; newA >= 0; newA--)
        if (IsWythoffPPosition(newA, b, phi)) return (newA, b);
    // Type 2 : retirer de B seul
    for (int newB = b - 1; newB >= 0; newB--)
        if (IsWythoffPPosition(a, newB, phi)) return (a, newB);
    // Type 3 : retirer le meme nombre des deux (diagonale)
    for (int k = 1; k <= Math.Min(a, b); k++)
        if (IsWythoffPPosition(a - k, b - k, phi)) return (a - k, b - k);
    return null;
}

var examples = new[] { (5, 8), (7, 11), (3, 5), (10, 15) };
Console.WriteLine("Strategie optimale au Wythoff");
Console.WriteLine(new string('=', 50));
foreach (var (a, b) in examples)
{
    string posType = IsWythoffPPosition(a, b, PHI) ? "P" : "N";
    var move = WythoffWinningMove(a, b, PHI);
    string moveStr = move.HasValue ? $"-> ({move.Value.a}, {move.Value.b})" : "Position perdante";
    Console.WriteLine($"({a}, {b}) [{posType}]: {moveStr}");
}

Strategie optimale au Wythoff
==================================================
(5, 8) [N]: -> (5, 3)
(7, 11) [N]: -> (7, 4)
(3, 5) [P]: Position perdante
(10, 15) [N]: -> (9, 15)

Exercice : Generation et verification des P-positions de Wythoff

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.

Indice : Les P-positions suivent les sequences de Beatty avec le nombre d’or.
Étape 1 : Generer les 15 premières P-positions.
Étape 2 : Verifier chaque position avec is_wythoff_p_position.
Étape 3 : Pour les N-positions (10,15), (8,12), trouver le coup gagnant.

// EXERCICE : Generation et verification des P-positions de Wythoff.
// TODO etudiant : generer les P-positions via WythoffPPositions, les verifier avec
// IsWythoffPPosition, puis trouver un coup gagnant depuis des N-positions donnees.
Console.WriteLine("Exercice a completer : generation et verification Wythoff");
Console.WriteLine("Etape 1 : var pPos = WythoffPPositions(15, PHI);");
Console.WriteLine("Etape 2 : bool allVerified = pPos.All(p => IsWythoffPPosition(p.a, p.b, PHI));");
Console.WriteLine("Etape 3 : pour (10,15) et (8,12), appel WythoffWinningMove(...)");
// Indice : les P-positions suivent les sequences de Beatty avec le nombre d'or.
// Votre code ici :
object resultWythoff = null;  // TODO etudiant : dict { p_positions, all_verified, winning_moves }
Console.WriteLine($"Resultat : {(resultWythoff == null ? "(a completer)" : resultWythoff)}");

Exercice a completer : generation et verification Wythoff
Etape 1 : var pPos = WythoffPPositions(15, PHI);
Etape 2 : bool allVerified = pPos.All(p => IsWythoffPPosition(p.a, p.b, PHI));
Etape 3 : pour (10,15) et (8,12), appel WythoffWinningMove(...)
Resultat : (a completer)

3. Jeux multi-composantes

Le 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.

// Jeux multi-composantes : theoreme de Sprague-Grundy.
// G(J1 + J2 + ... + Jk) = G(J1) XOR G(J2) XOR ... XOR G(Jk).
public class CompositeGame
{
    public List<(HashSet<int> moves, int size)> Games { get; }
    public List<Dictionary<int, int>> Memos { get; }
    public CompositeGame(List<(HashSet<int>, int)> games)
    {
        Games = games.Select(g => (g.Item1, g.Item2)).ToList();
        Memos = games.Select(_ => new Dictionary<int, int>()).ToList();
    }
    public int Grundy(int component, int size)
    {
        var moves = Games[component].moves;
        return GrundySubtraction(size, moves, Memos[component]);
    }
    public int TotalGrundy(List<int> sizes)
    {
        int g = 0;
        for (int i = 0; i < sizes.Count; i++) g ^= Grundy(i, sizes[i]);
        return g;
    }
    public string PositionType(List<int> sizes) => TotalGrundy(sizes) == 0 ? "P" : "N";
    public (int component, int newSize)? FindWinningMove(List<int> sizes)
    {
        if (TotalGrundy(sizes) == 0) return null;
        for (int i = 0; i < Games.Count; i++)
        {
            int target = 0;
            for (int j = 0; j < sizes.Count; j++) if (j != i) target ^= Grundy(j, sizes[j]);
            for (int newSize = sizes[i] - 1; newSize >= 0; newSize--)
            {
                // Garde legalite : newSize doit etre atteignable depuis sizes[i]
                // par un coup de moves (sinon Grundy(n) n'a aucun sens physique).
                if (!Games[i].moves.Contains(sizes[i] - newSize)) continue;
                if (Grundy(i, newSize) == target) return (i, newSize);
            }
        }
        return null;
    }
}

var composite = new CompositeGame(new List<(HashSet<int>, int)>
{
    (new HashSet<int> { 1, 2 }, 7),      // Composante 0
    (new HashSet<int> { 1, 3, 4 }, 5),   // Composante 1
    (new HashSet<int> { 2, 3 }, 6),      // Composante 2
});

var sizes = new List<int> { 7, 5, 6 };
Console.WriteLine("Jeu composite : 3 jeux de soustraction");
Console.WriteLine(new string('=', 50));
for (int i = 0; i < sizes.Count; i++)
{
    string ms = "{" + string.Join(", ", composite.Games[i].moves.OrderBy(x => x)) + "}";
    Console.WriteLine($"Composante {i}: S({ms}) avec {sizes[i]} jetons -> G={composite.Grundy(i, sizes[i])}");
}
Console.WriteLine();
Console.WriteLine($"Grundy total: {composite.TotalGrundy(sizes)}");
Console.WriteLine($"Position: {composite.PositionType(sizes)}");
var move = composite.FindWinningMove(sizes);
if (move.HasValue)
{
    var (ci, ns) = move.Value;
    Console.WriteLine();
    Console.WriteLine($"Coup gagnant: Composante {ci}, reduire de {sizes[ci]} a {ns}");
    var newSizes = sizes.ToList();
    newSizes[ci] = ns;
    Console.WriteLine($"Nouvelle position: [{string.Join(", ", newSizes)}] -> G={composite.TotalGrundy(newSizes)}");
}

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=0

Exercice : Analyse d’un jeu composite a trois composantes

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.

Indice : Utiliser CompositeGame avec différentes combinaisons de moves.
Étape 1 : Définir 3 composantes avec des moves différents de l’exemple.
Étape 2 : Calculer les Grundy individuels et le total.
Étape 3 : Si N-position, trouver le coup gagnant et verifier que le nouveau Grundy = 0.

// EXERCICE : Analyse d'un jeu composite a trois composantes (S({1,2,3}), S({2,4}), S({1,5})).
// TODO etudiant : construire le CompositeGame, calculer Grundy individuels + total, type, coup gagnant.
Console.WriteLine("Exercice a completer : jeu composite a trois composantes");
Console.WriteLine("Etape 1 : var g = new CompositeGame(new() { (new HashSet<int>{1,2,3}, ...), ... });");
Console.WriteLine("Etape 2 : calculer Grundy individuels et le total (TotalGrundy)");
Console.WriteLine("Etape 3 : si N-position, FindWinningMove et verifier nouveau Grundy = 0");
// Indice : le Grundy total est le XOR des Grundy individuels (Sprague-Grundy).
// Votre code ici :
object resultComp = null;  // TODO etudiant : dict { component_grundys, total_grundy, position_type, winning_move }
Console.WriteLine($"Resultat : {(resultComp == null ? "(a completer)" : resultComp)}");

Exercice a completer : jeu composite a trois composantes
Etape 1 : var g = new CompositeGame(new() { (new HashSet<int>{1,2,3}, ...), ... });
Etape 2 : calculer Grundy individuels et le total (TotalGrundy)
Etape 3 : si N-position, FindWinningMove et verifier nouveau Grundy = 0
Resultat : (a completer)

4. Visualisation interactive

Creons une visualisation des valeurs de Grundy pour mieux comprendre leur structure.

#load "../Probas/Infer/SvgChartHelper.cs"
// Visualisation comparee des valeurs de Grundy (matplotlib subplots -> barres ASCII compactes).
var gamesToCompare = new Dictionary<string, HashSet<int>>
{
    ["Fibonacci-like"] = new HashSet<int> { 1, 2 },
    ["Classique"]      = new HashSet<int> { 1, 3, 4 },
    ["Impair seulement"] = new HashSet<int> { 1, 3, 5 },
    ["Pair seulement"]   = new HashSet<int> { 2, 4, 6 },
};
int maxN = 24;
var grundyRows = new List<(string Name, List<int> Values)>();
foreach (var kv in gamesToCompare)
{
    var memo = new Dictionary<int, int>();
    var values = Enumerable.Range(0, maxN).Select(n => GrundySubtraction(n, kv.Value, memo)).ToList();
    var (pre, period, _) = FindPeriodicity(kv.Value, maxN: 200);
    string ms = "{" + string.Join(",", kv.Value.OrderBy(x => x)) + "}";
    string perStr = period > 0 ? $"periode={period}" : "periode=?";
    Console.WriteLine($"S({ms}) {kv.Key} [{perStr}] ; P-positions (G=0): " + string.Join(",", Enumerable.Range(0, maxN).Where(n => values[n] == 0)));
    grundyRows.Add((kv.Key, values));
}

// Heatmap SVG : valeurs de Grundy par variante (ligne) x position N (colonne).
// Les bandes de couleur repetees = periodicite (caractere distinctif du solveur combinatoire).
// (rendu SVG inline via SvgChartHelper.Heatmap, technique C548-L2)
SvgChartHelper.Heatmap(
    "Valeurs de Grundy : periodicite des jeux de soustraction (G=0 = P/perdante)",
    Enumerable.Range(0, maxN).Select(n => n.ToString()).ToArray(),
    grundyRows.Select(r => r.Name).ToArray(),
    grundyRows.Select(r => r.Values.Select(v => (double)v).ToArray()).ToArray())

S({1,2}) Fibonacci-like [periode=3] ; P-positions (G=0): 0,3,6,9,12,15,18,21
S({1,3,4}) Classique [periode=7] ; P-positions (G=0): 0,2,7,9,14,16,21,23
S({1,3,5}) Impair seulement [periode=2] ; P-positions (G=0): 0,2,4,6,8,10,12,14,16,18,20,22
S({2,4,6}) Pair seulement [periode=8] ; P-positions (G=0): 0,1,8,9,16,17

5. Jeu de Chomp

Le jeu de Chomp est un jeu partizan (contrairement a Nim qui est impartial) :

Une tablette de chocolat rectangulaire \(m \times n\)
A chaque tour, on mange un carre et tous les carres en haut et a droite
Le carre en bas a gauche (0,0) est empoisonne - celui qui le mange perd

Theoreme de Gale (1974)

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 !

// Jeu de Chomp (partizan) : theoreme de Gale (strategy stealing) = 1er joueur gagne
// pour m,n >= 2, mais strategie non-constructive (NP-difficile). Analyse exacte petites tablettes.
// Position = hauteurs des colonnes (ex. (3,3,3) = tablette 3x3). (1,) = carre poison seul = perdant.
static List<int[]> ChompMoves(int[] position)
{
    var moves = new List<int[]>();
    int cols = position.Length;
    for (int col = 0; col < cols; col++)
    {
        for (int row = 1; row <= position[col]; row++)
        {
            var newPos = (int[])position.Clone();
            for (int c = col; c < cols; c++) newPos[c] = Math.Min(newPos[c], row - 1);
            var list = newPos.ToList();
            while (list.Count > 0 && list[list.Count - 1] == 0) list.RemoveAt(list.Count - 1);
            if (list.Count == 0) continue;
            moves.Add(list.ToArray());
        }
    }
    return moves;
}

// Memoisation par cle texte (Bug #13 : int[] = ref-equality, on serialize en string).
var chompMemo = new Dictionary<string, bool>();
string PosKey(int[] p) => string.Join(",", p);
bool ChompIsLosing(int[] position)
{
    if (position.Length == 0) return true;
    if (position.Length == 1 && position[0] == 1) return true;
    var key = PosKey(position);
    if (chompMemo.TryGetValue(key, out var v)) return v;
    bool losing = true;
    foreach (var mv in ChompMoves(position))
    {
        if (ChompIsLosing(mv)) { losing = false; break; }
    }
    chompMemo[key] = losing;
    return losing;
}

Console.WriteLine("Analyse du jeu de Chomp 3x3");
Console.WriteLine(new string('=', 40));
int[] initial = { 3, 3, 3 };
Console.WriteLine($"Position initiale: ({string.Join(", ", initial)})");
Console.WriteLine($"Type: {(ChompIsLosing(initial) ? "P (perdante)" : "N (gagnante)")}");
Console.WriteLine();
Console.WriteLine("Coups depuis la position initiale (8 premiers) :");
int shown = 0;
foreach (var mv in ChompMoves(initial))
{
    if (shown >= 8) break;
    string status = ChompIsLosing(mv) ? "P" : "N";
    Console.WriteLine($"  ({string.Join(", ", mv)}) [{status}]");
    shown++;
}

Analyse du jeu de Chomp 3x3
========================================
Position initiale: (3, 3, 3)
Type: N (gagnante)

Coups depuis la position initiale (8 premiers) :
  (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]

Interpretation des résultats

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_losing utilise la memoisation (@lru_cache) car le nombre de positions croit exponentiellement avec la taille de la tablette.

// Visualisation ASCII d'une position de Chomp (X = poison (0,0), # = chocolat).
static void VisualizeChomp(int[] position, string title = "Chomp")
{
    Console.WriteLine(title);
    Console.WriteLine($"Position: ({string.Join(", ", position)})");
    int maxH = position.Length > 0 ? position.Max() : 1;
    for (int row = maxH; row >= 1; row--)
    {
        Console.Write("  ");
        for (int col = 0; col < position.Length; col++)
        {
            if (row <= position[col]) Console.Write(row == 1 && col == 0 ? "X " : "# ");
            else Console.Write("  ");
        }
        Console.WriteLine();
    }
    Console.WriteLine("  (X = poison (0,0), # = chocolat)");
    Console.WriteLine();
}

VisualizeChomp(new[] { 3, 3, 3 }, "Position initiale 3x3");
VisualizeChomp(new[] { 2, 2, 1 }, "Apres un coup");
VisualizeChomp(new[] { 1 }, "Position finale (perdante)");

Position initiale 3x3
Position: (3, 3, 3)
  # # # 
  # # # 
  X # # 
  (X = poison (0,0), # = chocolat)

Apres un coup
Position: (2, 2, 1)
  # #   
  X # # 
  (X = poison (0,0), # = chocolat)

Position finale (perdante)
Position: (1)
  X 
  (X = poison (0,0), # = chocolat)

Exercices

Exercice 1 : Periode de S({1, 2, 4, 8})

Trouvez la periode et la pre-periode du jeu de soustraction S({1, 2, 4, 8}).

Exercice 2 : Wythoff generalise

Dans le Wythoff (k), on peut retirer jusqu’a k fois le même nombre des deux tas. Implementez l’analyse pour k=2.

Exercice 3 : Simulation de Chomp

Implementez un joueur optimal pour Chomp 4x4 et jouez contre lui.

// EXERCICE 1 : Periode du jeu de soustraction S({1, 2, 4, 8}).
// TODO etudiant : utiliser FindPeriodicity pour analyser S({1,2,4,8}).
Console.WriteLine("Exercice a completer : periode de S({1, 2, 4, 8})");
Console.WriteLine("Etape 1 : var moves = new HashSet<int> { 1, 2, 4, 8 };");
Console.WriteLine("Etape 2 : var (pre, period, seq) = FindPeriodicity(moves, maxN: 200);");
Console.WriteLine("Etape 3 : afficher pre, period, et les 20 premiers termes");
Console.WriteLine("Etape 4 : interpreter - quelles positions sont perdantes (Grundy = 0) ?");
// Indice : les puissances de 2 donnent une structure particuliere (periodicite courte).
// Votre code ici :
Console.WriteLine("(a completer : jeux combinatoires)");

Exercice a completer : periode de S({1, 2, 4, 8})
Etape 1 : var moves = new HashSet<int> { 1, 2, 4, 8 };
Etape 2 : var (pre, period, seq) = FindPeriodicity(moves, maxN: 200);
Etape 3 : afficher pre, period, et les 20 premiers termes
Etape 4 : interpreter - quelles positions sont perdantes (Grundy = 0) ?
(a completer : jeux combinatoires)

Resume et perspectives

Ce 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.

Resume

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

Ressources

Conway, J.H. On Numbers and Games (2001)
Berlekamp, E., Conway, J., Guy, R. Winning Ways (2001)
Sprague-Grundy Theorem (Wikipedia)

Navigation : << 8-CombinatorialGames | Index | 8b-Lean-CombinatorialGames

Retour au sommet