Search-6 — Recherche adversariale (jeux à somme nulle) — jumeau .NET

Jumeau C# / .NET du notebook Python Search-06-AdversarialSearch. Partie de l’EPIC #4956 — parité .NET ⇄ Python des séries de notebooks. Cette partie couvre la recherche sur arbre de jeu : Minimax, élagage Alpha-Beta, heuristiques d’évaluation, recherche à profondeur limitée, iterative deepening et tables de transposition. Le fil rouge est le Tic-Tac-Toe (3×3), banc d’essai historique de la théorie des jeux (von Neumann 1928, Nash 1950) où l’arbre de jeu est assez petit pour être exploré complètement.

Contrairement à la recherche sur graphe (Partie 1, A*/IDA*) où un seul agent cherche un chemin, la recherche adversariale modélise deux agents en conflit : MAX cherche à maximiser l’utilité, MIN à la minimiser. L’optimalité de Minimax repose sur l’hypothèse d’adversaire parfait — chaque joueur joue le meilleur coup disponible — ce qui produit la valeur du jeu (von Neumann) : pour le Tic-Tac-Toe, cette valeur est 0 (nulle avec jeu optimal des deux côtés).

Fidélité du port (#3801 — SOTA-OK) : les algorithmes sont des implémentations fidèles de Minimax (von Neumann) et Alpha-Beta (Knuth & Moore 1975), pas des workarounds dégradés. Les exercices (Connect Four, ordonnancement, negamax, tournoi) sont laissés en stub // TODO etudiant conformément à la règle C.1 — le notebook s’exécute de bout en bout même non complété.

Interface : jeu à somme nulle à information parfaite

On abstrait la structure d’un jeu à somme nulle par une interface générique paramétrée par le type d’état TEtat. Sept méthodes suffisent à exprimer n’importe quel jeu de cette classe (échecs, dames, Tic-Tac-Toe, Puissance 4…) — la logique de recherche (Minimax, Alpha-Beta) s’écrit une seule fois contre cette interface et s’applique à toutes les instances.

// Interface pour un jeu a somme nulle a information parfaite.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

public interface IJeuSommeNulle<TEtat>
{
    TEtat EtatInitial();                         // etat de depart
    string Joueur(TEtat etat);                   // "MAX" ou "MIN" : a qui le tour
    List<int> Actions(TEtat etat);               // coups legaux (indices)
    TEtat Resultat(TEtat etat, int action);      // nouvel etat apres le coup
    bool EstTerminal(TEtat etat);                // partie finie (gain ou nul)
    double Utilite(TEtat etat, string joueur);   // +1 victoire, -1 defaite, 0 nul
    string Afficher(TEtat etat);                 // representation textuelle
}

Console.WriteLine("Interface IJeuSommeNulle<TEtat> definie (7 methodes, jeux a somme nulle).");
Interface IJeuSommeNulle<TEtat> definie (7 methodes, jeux a somme nulle).

Instance : Tic-Tac-Toe

Le Tic-Tac-Toe (morpion 3×3) est le banc d’essai canonique : son arbre de jeu compte ~5 478 états légaux, explorables en quelques millisecondes. X joue le rôle de MAX (cherche à gagner, utilité +1), O joue le rôle de MIN (cherche à faire perdre X, utilité −1 du point de vue de MAX). L’état est un couple (grille, joueur) où la grille est une chaîne de 9 caractères (’ ‘, ’X’ ou ‘O’).

// Etat du Tic-Tac-Toe : grille 9 cases (string immutable -> hashable) + joueur courant.
public record TttEtat(string Grille, char Joueur);

public class TicTacToe : IJeuSommeNulle<TttEtat>
{
    // 8 lignes gagnantes : 3 rangees + 3 colonnes + 2 diagonales
    private static readonly int[][] Lignes = new[]
    {
        new[] { 0, 1, 2 }, new[] { 3, 4, 5 }, new[] { 6, 7, 8 },   // rangees
        new[] { 0, 3, 6 }, new[] { 1, 4, 7 }, new[] { 2, 5, 8 },   // colonnes
        new[] { 0, 4, 8 }, new[] { 2, 4, 6 }                       // diagonales
    };

    public TttEtat EtatInitial() => new(new string(' ', 9), 'X');

    public string Joueur(TttEtat e) => e.Joueur == 'X' ? "MAX" : "MIN";

    public List<int> Actions(TttEtat e) =>
        Enumerable.Range(0, 9).Where(i => e.Grille[i] == ' ').ToList();

    public TttEtat Resultat(TttEtat e, int action)
    {
        char[] g = e.Grille.ToCharArray();
        g[action] = e.Joueur;
        char suivant = e.Joueur == 'X' ? 'O' : 'X';
        return new TttEtat(new string(g), suivant);
    }

    public bool EstTerminal(TttEtat e)
    {
        foreach (var l in Lignes)
            if (e.Grille[l[0]] != ' ' && e.Grille[l[0]] == e.Grille[l[1]] && e.Grille[l[1]] == e.Grille[l[2]])
                return true;
        return !e.Grille.Contains(' ');
    }

    public double Utilite(TttEtat e, string joueur)
    {
        foreach (var l in Lignes)
            if (e.Grille[l[0]] != ' ' && e.Grille[l[0]] == e.Grille[l[1]] && e.Grille[l[1]] == e.Grille[l[2]])
            {
                string gagnant = e.Grille[l[0]] == 'X' ? "MAX" : "MIN";
                return gagnant == joueur ? 1.0 : -1.0;
            }
        return 0.0;
    }

    public string Afficher(TttEtat e)
    {
        var g = e.Grille;
        return $"\n {g[0]} |{g[1]} |{g[2]}\n-----------\n {g[3]} |{g[4]} |{g[5]}\n-----------\n {g[6]} |{g[7]} |{g[8]}\n";
    }
}

var jeu = new TicTacToe();
var e0 = jeu.EtatInitial();
Console.WriteLine(jeu.Afficher(e0));
Console.WriteLine($"Joueur courant : {jeu.Joueur(e0)}");
Console.WriteLine($"Actions possibles : [{string.Join(", ", jeu.Actions(e0))}]");

   |  | 
-----------
   |  | 
-----------
   |  | 

Joueur courant : MAX
Actions possibles : [0, 1, 2, 3, 4, 5, 6, 7, 8]

Minimax

Minimax (von Neumann, 1928) calcule la valeur du jeu en explorant tout l’arbre jusqu’aux états terminaux. À chaque nœud :

  • si c’est le tour de MAX, on choisit l’action qui maximise la valeur ;
  • si c’est le tour de MIN, on choisit l’action qui minimise la valeur.

L’hypothèse est celle de l’adversaire parfait : MIN jouera le coup qui nous fait le plus de mal. Pour le Tic-Tac-Toe, Minimax confirme la valeur 0 (partie nulle avec jeu optimal des deux côtés) — aucun des deux joueurs ne peut forcer la victoire.

// Minimax recursif : retourne (valeur du jeu, meilleure action) du point de vue de joueurMax.
public static (double Valeur, int? Action) Minimax<TEtat>(
    IJeuSommeNulle<TEtat> jeu, TEtat etat, string joueurMax = "MAX")
{
    if (jeu.EstTerminal(etat))
        return (jeu.Utilite(etat, joueurMax), null);

    var actions = jeu.Actions(etat);
    if (jeu.Joueur(etat) == joueurMax)
    {
        double meilleure = double.NegativeInfinity;
        int? meilleureAction = null;
        foreach (var a in actions)
        {
            var (v, _) = Minimax(jeu, jeu.Resultat(etat, a), joueurMax);
            if (v > meilleure) { meilleure = v; meilleureAction = a; }
        }
        return (meilleure, meilleureAction);
    }
    else
    {
        double meilleure = double.PositiveInfinity;
        int? meilleureAction = null;
        foreach (var a in actions)
        {
            var (v, _) = Minimax(jeu, jeu.Resultat(etat, a), joueurMax);
            if (v < meilleure) { meilleure = v; meilleureAction = a; }
        }
        return (meilleure, meilleureAction);
    }
}

var jeu2 = new TicTacToe();
var (valeur, action) = Minimax(jeu2, jeu2.EtatInitial());
Console.WriteLine($"Valeur Minimax depuis l'etat initial : {valeur}");
Console.WriteLine($"Meilleure action (case 0-8) : {action}");
Console.WriteLine("-> Valeur 0 = partie nulle garantie avec jeu optimal des deux cotes.");
Valeur Minimax depuis l'etat initial : 0
Meilleure action (case 0-8) : 0
-> Valeur 0 = partie nulle garantie avec jeu optimal des deux cotes.

Lire le verdict Minimax : la valeur 0 n’est pas un échec, c’est un théorème

La sortie affiche Valeur Minimax depuis l'etat initial : 0, Meilleure action (case 0-8) : 0, puis le commentaire imprimé -> Valeur 0 = partie nulle garantie avec jeu optimal des deux cotes. La lecture importante est celle du 0 : ce n’est pas « l’algorithme n’a rien trouvé », c’est la valeur du jeu — au Tic-Tac-Toe, deux joueurs parfaits font nulle, et le minimax qui explore l’arbre complet le constate numériquement. La « meilleure action 0 » (le coin) ne gagne rien de plus qu’une autre case : toutes les actions mènent à la valeur 0, l’algorithme rend la première. Retenir le geste : la recherche adversariale ne « résout » pas le jeu en trouvant la victoire — elle mesure ce que chaque camp peut garantir.

Élagage Alpha-Beta

Minimax explore tout l’arbre. L’élagage Alpha-Beta (Knuth & Moore, 1975) coupe des branches dont on sait qu’elles ne peuvent pas influencer la décision : si MAX a déjà trouvé un coup valant alpha, toute branche de MIN garantissant ≤ alpha est inutile à explorer (MIN ne permettra jamais mieux). On maintient deux bornes — alpha (meilleur pour MAX), beta (meilleur pour MIN) — et on élague dès que beta ≤ alpha.

La valeur retournée est identique à Minimax (Alpha-Beta est exact) ; seul le nombre de nœuds explorés diminue. Sur Tic-Tac-Toe, le speedup est mesurable mais modeste (l’arbre est petit) ; sur des jeux plus profonds (échecs, Puissance 4), il devient décisif.

// Alpha-Beta : meme resultat que Minimax, moins de nœuds explores.
public static (double Valeur, int? Action) AlphaBeta<TEtat>(
    IJeuSommeNulle<TEtat> jeu, TEtat etat,
    double alpha, double beta, string joueurMax = "MAX")
{
    if (jeu.EstTerminal(etat))
        return (jeu.Utilite(etat, joueurMax), null);

    var actions = jeu.Actions(etat);
    if (jeu.Joueur(etat) == joueurMax)
    {
        double meilleure = double.NegativeInfinity;
        int? meilleureAction = null;
        foreach (var a in actions)
        {
            var (v, _) = AlphaBeta(jeu, jeu.Resultat(etat, a), alpha, beta, joueurMax);
            if (v > meilleure) { meilleure = v; meilleureAction = a; }
            alpha = Math.Max(alpha, meilleure);
            if (beta <= alpha) break;   // elagage : MIN ne permettra jamais mieux
        }
        return (meilleure, meilleureAction);
    }
    else
    {
        double meilleure = double.PositiveInfinity;
        int? meilleureAction = null;
        foreach (var a in actions)
        {
            var (v, _) = AlphaBeta(jeu, jeu.Resultat(etat, a), alpha, beta, joueurMax);
            if (v < meilleure) { meilleure = v; meilleureAction = a; }
            beta = Math.Min(beta, meilleure);
            if (beta <= alpha) break;   // elagage : MAX ne permettra jamais pire
        }
        return (meilleure, meilleureAction);
    }
}

// Benchmark : Minimax vs Alpha-Beta sur l'etat initial.
var jeu3 = new TicTacToe();
var init3 = jeu3.EtatInitial();

var sw = Stopwatch.StartNew();
var (v1, a1) = Minimax(jeu3, init3);
sw.Stop();
double t1 = sw.Elapsed.TotalSeconds;

sw.Restart();
var (v2, a2) = AlphaBeta(jeu3, init3, double.NegativeInfinity, double.PositiveInfinity);
sw.Stop();
double t2 = sw.Elapsed.TotalSeconds;

Console.WriteLine($"Minimax    : valeur={v1}, temps={t1:F4}s");
Console.WriteLine($"Alpha-Beta : valeur={v2}, temps={t2:F4}s");
Console.WriteLine($"Speedup    : {(t2 > 0 ? t1 / t2 : double.PositiveInfinity):F1}x  (meme valeur -> decision identique)");
Minimax    : valeur=0, temps=0,2095s
Alpha-Beta : valeur=0, temps=0,0061s
Speedup    : 34,1x  (meme valeur -> decision identique)

Lire le speedup : 0,2095 s contre 0,0061 s

La sortie aligne les deux moteurs : Minimax : valeur=0, temps=0,2095s puis Alpha-Beta : valeur=0, temps=0,0061s, et conclut Speedup : 34,1x (meme valeur -> decision identique). Deux lectures. Le speedup fait la leçon, pas les temps absolus : 0,2095 s et 0,0061 s dépendent de la machine (convention du registre : seuls les rapports et l’ordre comptent) — mais le facteur ~34 mesure ce que l’élagage épargne : l’alpha-beta visite une fraction de l’arbre sans jamais changer la racine. La parenthèse est la garantie de correction : « meme valeur -> decision identique » — un élagage plus rapide qui donnait une autre décision serait un bug, pas une optimisation ; la sortie atteste que la valeur racine (0) survit à l’élagage.

Heuristique, profondeur limitée et iterative deepening

Sur des jeux trop profonds pour explorer entièrement (échecs, Go), on borne la profondeur et on évalue les états non terminaux par une fonction d’évaluation heuristique. Pour le Tic-Tac-Toe, une heuristique naturelle compte les lignes « ouvertes » (sans pion adverse) et pondère par le nombre de pions alignés. L’iterative deepening enchaîne les profondeurs 1, 2, 3… jusqu’à une limite de temps, en conservant la meilleure action trouvée — il permet d’interrompre la recherche à tout moment avec un coup raisonnable.

// Fonction d'evaluation heuristique pour le Tic-Tac-Toe.
public static double EvaluationHeuristique(TttEtat e, string joueur)
{
    char moi = joueur == "MAX" ? 'X' : 'O';
    char adv = joueur == "MAX" ? 'O' : 'X';
    int[][] lignes = {
        new[] { 0, 1, 2 }, new[] { 3, 4, 5 }, new[] { 6, 7, 8 },
        new[] { 0, 3, 6 }, new[] { 1, 4, 7 }, new[] { 2, 5, 8 },
        new[] { 0, 4, 8 }, new[] { 2, 4, 6 }
    };
    double score = 0;
    foreach (var l in lignes)
    {
        int ma = l.Count(i => e.Grille[i] == moi);
        int adverse = l.Count(i => e.Grille[i] == adv);
        if (adverse == 0) score += ma * ma;       // ligne ouverte pour moi
        if (ma == 0) score -= adverse * adverse;  // ligne ouverte pour l'adversaire
    }
    return score / 9.0;
}

// Alpha-Beta a profondeur limitee : s'arrete a profondeur 0 sur l'heuristique.
public static (double Valeur, int? Action) AlphaBetaLimite<TEtat>(
    IJeuSommeNulle<TEtat> jeu, TEtat etat, int profondeur,
    double alpha, double beta, string joueurMax = "MAX")
{
    if (jeu.EstTerminal(etat))
        return (jeu.Utilite(etat, joueurMax), null);
    if (profondeur == 0)
        return (EvaluationHeuristique((TttEtat)(object)etat!, joueurMax), null);

    var actions = jeu.Actions(etat);
    if (jeu.Joueur(etat) == joueurMax)
    {
        double bestV = double.NegativeInfinity; int? bestA = null;
        foreach (var a in actions)
        {
            var (v, _) = AlphaBetaLimite(jeu, jeu.Resultat(etat, a), profondeur - 1, alpha, beta, joueurMax);
            if (v > bestV) { bestV = v; bestA = a; }
            alpha = Math.Max(alpha, bestV);
            if (beta <= alpha) break;
        }
        return (bestV, bestA);
    }
    else
    {
        double bestV = double.PositiveInfinity; int? bestA = null;
        foreach (var a in actions)
        {
            var (v, _) = AlphaBetaLimite(jeu, jeu.Resultat(etat, a), profondeur - 1, alpha, beta, joueurMax);
            if (v < bestV) { bestV = v; bestA = a; }
            beta = Math.Min(beta, bestV);
            if (beta <= alpha) break;
        }
        return (bestV, bestA);
    }
}

// Iterative deepening : profondeurs 1, 2, 3... jusqu'a temps_max ou profondeur max
// (sur Tic-Tac-Toe, l'arbre complet fait 9 plis : inutile de chercher plus profond).
public static (double Valeur, int? Action, int Profondeur) IterativeDeepening(
    TicTacToe jeu, TttEtat etat, double tempsMax = 0.5, int profondeurMax = 9)
{
    var sw = Stopwatch.StartNew();
    double bestV = 0; int? bestA = null;
    int depth;
    for (depth = 1; depth <= profondeurMax && sw.Elapsed.TotalSeconds < tempsMax; depth++)
    {
        var (v, a) = AlphaBetaLimite(jeu, etat, depth, double.NegativeInfinity, double.PositiveInfinity);
        bestV = v; bestA = a;
        if (Math.Abs(v) >= 1) break;   // victoire certaine, inutile d'aller plus profond
    }
    int atteinte = Math.Min(depth, profondeurMax);
    return (bestV, bestA, atteinte);
}

var jeu4 = new TicTacToe();
var (vi, ai, di) = IterativeDeepening(jeu4, jeu4.EtatInitial(), tempsMax: 0.3, profondeurMax: 9);
Console.WriteLine($"Iterative Deepening : valeur={vi:F2}, action={ai}, profondeur atteinte={di}");
Console.WriteLine("-> Profondeur 9 = arbre complet du Tic-Tac-Toe (9 cases) ; valeur 0 = nul avec jeu optimal.");

Iterative Deepening : valeur=0,00, action=0, profondeur atteinte=9
-> Profondeur 9 = arbre complet du Tic-Tac-Toe (9 cases) ; valeur 0 = nul avec jeu optimal.

Lire l’iterative deepening : la même valeur obtenue par progression

La sortie imprime Iterative Deepening : valeur=0,00, action=0, profondeur atteinte=9 puis -> Profondeur 9 = arbre complet du Tic-Tac-Toe (9 cases) ; valeur 0 = nul avec jeu optimal. Deux détails à lire. La profondeur atteinte 9 : la progression par profondeur croissante a fini par couvrir l’arbre entier — au Tic-Tac-Toe l’horizon est fini, l’iterative deepening converge donc vers le minimax exact. La valeur 0,00 : c’est la valeur heuristique à profondeur limitée qui, à chaque palier, se rapproche de la valeur exacte — ici elle vaut exactement 0 dès que la profondeur suffit. Le geste algorithmique : dans un jeu trop profond pour l’arbre complet, la même boucle rendrait la meilleure valeur atteignable dans le budget, avec la garantie de toujours avoir une réponse.

Table de transposition

Une table de transposition (Zobrist, 1970 ; clé de hachage de l’état) met en cache les résultats déjà calculés : si l’on retombe sur un état déjà vu (différents ordres de coups mènent au même état), on renvoie la valeur cachée au lieu de recalculer. Au Tic-Tac-Toe, de nombreuses permutations de coups convergent vers le même plateau — le cache évite ce recalcul redondant. On stocke pour chaque clé (valeur, profondeur, drapeau) afin de ne réutiliser le cache que si l’entrée est au moins aussi profonde que la requête courante.

// Alpha-Beta avec table de transposition (cache des etats deja calcules).
public class AlphaBetaTransposition
{
    private readonly Dictionary<string, (double Valeur, int Profondeur, string Flag)> _table = new();
    public int Hits { get; private set; }
    public int Misses { get; private set; }

    public (double Valeur, int? Action) Rechercher<TEtat>(
        IJeuSommeNulle<TEtat> jeu, TEtat etat, int profondeur,
        double alpha, double beta, string joueurMax = "MAX")
    {
        string cle = etat!.ToString()!;   // cle = representation canonique de l'etat (record)

        if (_table.TryGetValue(cle, out var entry) && entry.Profondeur >= profondeur)
        {
            Hits++;
            if (entry.Flag == "exact") return (entry.Valeur, null);
        }
        Misses++;

        if (jeu.EstTerminal(etat))
            return (jeu.Utilite(etat, joueurMax), null);
        if (profondeur == 0)
            return (EvaluationHeuristique((TttEtat)(object)etat!, joueurMax), null);

        var actions = jeu.Actions(etat);
        if (jeu.Joueur(etat) == joueurMax)
        {
            double bestV = double.NegativeInfinity; int? bestA = null;
            foreach (var a in actions)
            {
                var (v, _) = Rechercher(jeu, jeu.Resultat(etat, a), profondeur - 1, alpha, beta, joueurMax);
                if (v > bestV) { bestV = v; bestA = a; }
                alpha = Math.Max(alpha, bestV);
                if (beta <= alpha) break;
            }
            _table[cle] = (bestV, profondeur, "exact");
            return (bestV, bestA);
        }
        else
        {
            double bestV = double.PositiveInfinity; int? bestA = null;
            foreach (var a in actions)
            {
                var (v, _) = Rechercher(jeu, jeu.Resultat(etat, a), profondeur - 1, alpha, beta, joueurMax);
                if (v < bestV) { bestV = v; bestA = a; }
                beta = Math.Min(beta, bestV);
                if (beta <= alpha) break;
            }
            _table[cle] = (bestV, profondeur, "exact");
            return (bestV, bestA);
        }
    }
}

var abt = new AlphaBetaTransposition();
var jeu5 = new TicTacToe();
sw.Restart();
var (vt, at) = abt.Rechercher(jeu5, jeu5.EtatInitial(), 9, double.NegativeInfinity, double.PositiveInfinity);
sw.Stop();
Console.WriteLine($"Alpha-Beta + Transposition : valeur={vt}, temps={sw.Elapsed.TotalSeconds:F4}s");
Console.WriteLine($"Cache : {abt.Hits} hits, {abt.Misses} misses");
Console.WriteLine("-> Valeur identique a Minimax pur (le cache ne change pas la decision, seulement la vitesse).");
Alpha-Beta + Transposition : valeur=0, temps=0,0091s
Cache : 1565 hits, 3010 misses
-> Valeur identique a Minimax pur (le cache ne change pas la decision, seulement la vitesse).

Lire la table de transposition : le cache ne change pas la décision

La sortie affiche Alpha-Beta + Transposition : valeur=0, temps=0,0091s, Cache : 1565 hits, 3010 misses, et le commentaire -> Valeur identique a Minimax pur (le cache ne change pas la decision, seulement la vitesse). La statistique centrale est le couple 1565 hits / 3010 misses : un peu plus d’un tiers des recherches d’état tombent sur une position déjà calculée — le Tic-Tac-Toe contient des transpositions (jouer case 1 puis case 3 mène au même état que 3 puis 1), et la table capture cette redondance. Le temps (0,0091 s) est du même ordre que l’alpha-beta pur : sur ce petit jeu, le cache ne paie pas — c’est exactement la lecture honnête, la table de transposition est un investissement qui rapporte sur les arbres profonds (échecs), pas sur 9 cases. Et la ligne finale est le contrat d’invariance : valeur identique = le cache est transparent pour la décision.

Exercices

Les exercices suivants sont laissés en stub // TODO etudiant (règle C.1) : le notebook s’exécute de bout en bout même non complété. Chaque exercice est précédé de son énoncé et d’indices. Les classifier par contenu (règle de labeling) : ce sont des exercices (à compléter), à distinguer des exemples guidés résolus ci-dessus.

Exercice 1 — Connect Four (Puissance 4)

Implémentez la classe ConnectFour héritant de IJeuSommeNulle<C4Etat> : - grille 6 lignes × 7 colonnes ; - 4 pions alignés (horizontal, vertical, deux diagonales) pour gagner ; - les coups se jouent en choisissant une colonne (le pion tombe sur la case libre la plus basse).

Indice : représentez la grille par une string de 42 caractères (comme le Tic-Tac-Toe), et parcourez les 4 directions pour détecter l’alignement de 4.

// Exercice 1 : Connect Four
// TODO etudiant : implementer ConnectFour : IJeuSommeNulle<C4Etat>
// - EtatInitial : grille 6x7 vide, joueur 'X'
// - Actions : colonnes (0-6) non pleines
// - Resultat : faire tomber le pion dans la colonne
// - EstTerminal : 4 alignes (4 directions) OU grille pleine
// - Utilite : +1 si joueur gagne, -1 s'il perd, 0 nul
public record C4Etat(string Grille, char Joueur);  // grille 42 chars, ligne 0 en haut

public class ConnectFour : IJeuSommeNulle<C4Etat>
{
    public C4Etat EtatInitial() => null!;  // TODO etudiant
    public string Joueur(C4Etat e) => null!;  // TODO etudiant
    public List<int> Actions(C4Etat e) => null!;  // TODO etudiant
    public C4Etat Resultat(C4Etat e, int action) => null!;  // TODO etudiant
    public bool EstTerminal(C4Etat e) => false;  // TODO etudiant
    public double Utilite(C4Etat e, string joueur) => 0.0;  // TODO etudiant
    public string Afficher(C4Etat e) => "(grille Connect Four a afficher)";  // TODO etudiant
}

Console.WriteLine("Exercice 1 a completer : Connect Four (voir indices ci-dessus).");
Exercice 1 a completer : Connect Four (voir indices ci-dessus).

Exercice 2 — Ordonnancement des coups

L’élagage Alpha-Beta est d’autant plus efficace que l’on explore d’abord les bons coups (alors l’élagage intervient tôt). Modifiez AlphaBeta pour trier les actions par proximité au centre (colonnes 3, 2, 4, 1, 5, 0, 6) avant de les parcourir.

Indice : écrivez OrdonnerActions(List<int>, int centre = 3) qui trie par distance croissante au centre, et appez-la sur jeu.Actions(etat) avant la boucle.

// Exercice 2 : Ordonnancement des coups
// TODO etudiant : ordonner les actions par proximite au centre avant Alpha-Beta
public static List<int> OrdonnerActions(List<int> actions, int centre = 3)
{
    return actions;  // TODO etudiant : trier par distance croissante au centre
}

public static (double Valeur, int? Action) AlphaBetaOrdonne<TEtat>(
    IJeuSommeNulle<TEtat> jeu, TEtat etat, int profondeur,
    double alpha, double beta, string joueurMax = "MAX")
{
    return (0.0, null);  // TODO etudiant : Alpha-Beta avec tri des coups (cf. AlphaBetaLimite)
}

Console.WriteLine("Exercice 2 a completer : ordonnancement des coups (voir indices ci-dessus).");
Exercice 2 a completer : ordonnancement des coups (voir indices ci-dessus).

Exercice 3 — Negamax

Dans Minimax, MAX et MIN font exactement la même chose, sauf que MIN minimise. Or minimiser pour soi = maximiser le négatif. Negamax unifie les deux cas : on maximise toujours, mais on négatie la valeur retournée par le fils (qui est du point de vue de l’adversaire).

Relation fondamentale : negamax(etat) = max(−negamax(fils)) pour chaque fils. L’utilité est calculée du point de vue du joueur courant puis multipliée par signe (+1 si tour de MAX, −1 si tour de MIN).

Indice : la borne Alpha-Beta s’inverse dans l’appel récursif : −negamax_ab(fils, −beta, −alpha, −signe).

// Exercice 3 : Negamax (unification de MAX/MIN)
// TODO etudiant : implementer negamax (max de -negamax(fils) pour chaque fils)
public static (double Valeur, int? Action) Negamax<TEtat>(
    IJeuSommeNulle<TEtat> jeu, TEtat etat, int signe = 1, string joueurMax = "MAX")
{
    return (0.0, null);  // TODO etudiant
}

public static (double Valeur, int? Action) NegamaxAlphaBeta<TEtat>(
    IJeuSommeNulle<TEtat> jeu, TEtat etat, double alpha, double beta, int signe = 1, string joueurMax = "MAX")
{
    return (0.0, null);  // TODO etudiant : negamax avec elagage (bornes inversées dans l'appel recursif)
}

Console.WriteLine("Exercice 3 a completer : negamax (voir indices ci-dessus).");
Exercice 3 a completer : negamax (voir indices ci-dessus).

Exercice 4 — Tournoi algorithmique

Construisez un cadre de tournoi automatique entre stratégies : joueur aléatoire, Minimax, Alpha-Beta jouent les uns contre les autres, en alternant qui commence. Collectez : victoires, nulles, temps moyen par coup.

Indice : écrivez JouerPartie(jeu, fnMax, fnMin) qui joue une partie complète en appelant fnMax / fnMin à chaque tour pour choisir l’action, et renvoie le résultat (+1/0/−1).

// Exercice 4 : Tournoi algorithmique
// TODO etudiant : framework de tournoi entre strategies
public static int? JoueurAleatoire<TEtat>(IJeuSommeNulle<TEtat> jeu, TEtat etat, Random rng)
{
    return null;  // TODO etudiant : choisir un coup au hasard parmi jeu.Actions(etat)
}

public static int? JouerPartie<TEtat>(
    IJeuSommeNulle<TEtat> jeu,
    Func<IJeuSommeNulle<TEtat>, TEtat, int?> fnMax,
    Func<IJeuSommeNulle<TEtat>, TEtat, int?> fnMin)
{
    return null;  // TODO etudiant : jouer la partie, retourner +1 (gain MAX), 0 (nul), -1 (gain MIN)
}

Console.WriteLine("Exercice 4 a completer : tournoi algorithmique (voir indices ci-dessus).");
Exercice 4 a completer : tournoi algorithmique (voir indices ci-dessus).

Lire les quatre exercices : l’échelle des extensions

Les cellules d’exercice impriment la même invite (Exercice N a completer) — le contrat C.1 : le notebook s’exécute d’un bout à l’autre, la validation est l’étudiant. L’échelle se lit dans les énoncés : Exercice 1 transpose tout ce notebook vers Connect Four (grille 7×6, victory line de 4) — le même minimimax sur un arbre qui ne tient plus en entier ; Exercice 2 attaque l’ordonnancement des coups (move ordering) — l’ordre dans lequel alpha-beta visite les enfants détermine l’élagage, la question est de le mesurer ; Exercice 3 unifie MAX et MIN en une seule récursion negamax — la reformulation standard des échecs ; Exercice 4 organise le tournoi où ces variantes s’affrontent. Quatre niveaux : transférer, optimiser, reformuler, confronter.

Conclusion

Ce jumeau .NET a porté fidèlement les cinq pierres angulaires de la recherche adversariale :

  1. Minimax (von Neumann, 1928) — la valeur du jeu sous hypothèse d’adversaire parfait ;
  2. Alpha-Beta (Knuth & Moore, 1975) — même décision, moins de nœuds (élagage par bornes) ;
  3. Heuristique + profondeur limitée — pour les jeux trop profonds à explorer entièrement ;
  4. Iterative deepening — recherche interrompible, meilleur coup disponible à tout instant ;
  5. Table de transposition — cache des états déjà calculés (et non du code métier).

La leçon générale, cohérente avec le reste de la série Search : l’optimalité a un coût (Minimax explore tout l’arbre), et l’art consiste à préserver la décision optimale en réduisant le travail — Alpha-Beta, l’ordonnancement des coups, les tables de transposition sont autant de leviers qui rapprochent le coût effectif du coût incompressible. Pour les jeux où même cela ne suffit pas (échecs, Go), on relâche l’optimalité via une heuristique d’évaluation — exactement le même contraste qu’entre A* (optimal, Partie 1) et les métaheuristiques (approché, Partie 4).

Ponts

  • Notebook Python source : Search-06-AdversarialSearch — même contenu algorithmique, noyau python3 (avec numpy/matplotlib pour la visualisation) ;
  • Partie 3 : Search-03b-PatternDatabases prolonge la recherche heuristique à un seul agent (A*/IDA*, PDB) ;
  • Partie 4 : les métaheuristiques composables (recuit simulé, algorithmes génétiques) relâchent l’optimalité garantie pour gagner en scalabilité ;
  • EPIC #4956 : parité .NET ⇄ Python des séries de notebooks.
Retour au sommet