// Exemple résolu : Connect-4 (6x7) -- le cas discriminant où Minimax s'essouffle.
// On implémente le jeu (IJeuSommeNulle), un Minimax depth-limité avec heuristique,
// puis on benchmark Minimax(depth) vs MCTS(itérations) sur l'état initial.
// --- État du jeu ---
public sealed class EtatC4 { public char[] Grille = new char[42]; public char Joueur = 'X'; public int Coups = 0; }
// --- Jeu Connect-4 (6 lignes x 7 colonnes, gravité) ---
public sealed class ConnectFour : IJeuSommeNulle<EtatC4>
{
public const int NB_LIGNES = 6, NB_COLONNES = 7;
// Toutes les fenêtres de 4 cases alignées (horiz, vert, 2 diagonales) -- précalculées.
public static readonly int[][] Fenetres4 = BuildFenetres();
private static int[][] BuildFenetres()
{
var f = new List<int[]>();
for (int r = 0; r < NB_LIGNES; r++) for (int c = 0; c <= NB_COLONNES - 4; c++)
f.Add(new[]{r*NB_COLONNES+c, r*NB_COLONNES+c+1, r*NB_COLONNES+c+2, r*NB_COLONNES+c+3});
for (int c = 0; c < NB_COLONNES; c++) for (int r = 0; r <= NB_LIGNES - 4; r++)
f.Add(new[]{r*NB_COLONNES+c, (r+1)*NB_COLONNES+c, (r+2)*NB_COLONNES+c, (r+3)*NB_COLONNES+c});
for (int r = 0; r <= NB_LIGNES - 4; r++) for (int c = 0; c <= NB_COLONNES - 4; c++)
f.Add(new[]{r*NB_COLONNES+c, (r+1)*NB_COLONNES+c+1, (r+2)*NB_COLONNES+c+2, (r+3)*NB_COLONNES+c+3});
for (int r = 3; r < NB_LIGNES; r++) for (int c = 0; c <= NB_COLONNES - 4; c++)
f.Add(new[]{r*NB_COLONNES+c, (r-1)*NB_COLONNES+c+1, (r-2)*NB_COLONNES+c+2, (r-3)*NB_COLONNES+c+3});
return f.ToArray();
}
private static bool A4Aligne(char[] g, char j)
{ foreach (var f in Fenetres4) if (g[f[0]]==j && g[f[1]]==j && g[f[2]]==j && g[f[3]]==j) return true; return false; }
public EtatC4 EtatInitial() => new EtatC4();
public string Joueur(EtatC4 e) => e.Joueur == 'X' ? "MAX" : "MIN";
public List<int> Actions(EtatC4 e) { var a = new List<int>(); for (int c = 0; c < NB_COLONNES; c++) if (e.Grille[c] == '\0') a.Add(c); return a; }
public EtatC4 Resultat(EtatC4 e, int col)
{
var n = new EtatC4 { Joueur = e.Joueur == 'X' ? 'O' : 'X', Coups = e.Coups + 1 };
Array.Copy(e.Grille, n.Grille, 42);
for (int r = NB_LIGNES - 1; r >= 0; r--)
{ int idx = r*NB_COLONNES + col; if (n.Grille[idx] == '\0') { n.Grille[idx] = e.Joueur; break; } }
return n;
}
public bool EstTerminal(EtatC4 e) => e.Coups == 42 || A4Aligne(e.Grille, e.Joueur == 'X' ? 'O' : 'X');
public double Utilite(EtatC4 e, string joueur)
{
char gagnant = e.Joueur == 'X' ? 'O' : 'X'; // le joueur qui vient de jouer
if (!A4Aligne(e.Grille, gagnant)) return 0.0;
char moi = joueur == "MAX" ? 'X' : 'O';
return gagnant == moi ? 1.0 : -1.0;
}
}
// --- Minimax depth-limité (le Connect-4 est trop profond pour l'exact) ---
public static class C4Minimax
{
public static long NbNoeuds = 0;
public static (double Valeur, int? Action) DepthLimite(IJeuSommeNulle<EtatC4> jeu, EtatC4 e, int depth, string joueurMax = "MAX")
{
NbNoeuds++;
if (jeu.EstTerminal(e) || depth == 0) return (Heuristique(e, joueurMax), null);
var acts = jeu.Actions(e);
if (jeu.Joueur(e) == joueurMax)
{
double bv = double.NegativeInfinity; int? ba = null;
foreach (var a in acts) { var (v, _) = DepthLimite(jeu, jeu.Resultat(e, a), depth - 1, joueurMax); if (v > bv) { bv = v; ba = a; } }
return (bv, ba);
}
else
{
double bv = double.PositiveInfinity; int? ba = null;
foreach (var a in acts) { var (v, _) = DepthLimite(jeu, jeu.Resultat(e, a), depth - 1, joueurMax); if (v < bv) { bv = v; ba = a; } }
return (bv, ba);
}
}
// Heuristique : différence de menaces (3 pions alignés avec la 4e case vide).
private static double Heuristique(EtatC4 e, string joueur)
{
char moi = joueur == "MAX" ? 'X' : 'O', adv = joueur == "MAX" ? 'O' : 'X';
return CompteMenaces3(e.Grille, moi) - CompteMenaces3(e.Grille, adv);
}
private static double CompteMenaces3(char[] g, char j)
{
int n = 0;
foreach (var f in ConnectFour.Fenetres4)
{
int c = 0; bool bloque = false;
foreach (var i in f) { if (g[i] == j) c++; else if (g[i] != '\0') bloque = true; }
if (!bloque && c == 3) n++;
}
return n;
}
}
// --- Benchmark : Minimax depth-limité vs MCTS sur Connect-4 ---
var jeuC4 = new ConnectFour();
Console.WriteLine($"Connect-4 : {ConnectFour.NB_LIGNES}x{ConnectFour.NB_COLONNES}, " +
$"facteur de branchement racine = {jeuC4.Actions(jeuC4.EtatInitial()).Count}, " +
$"~4,5e12 positions légales (Tromp) ; arbre de jeu ~10^21 (Allis 1988) -- Minimax exact inenvisageable.");
Console.WriteLine();
Console.WriteLine($"{"Algorithme",-22}{"Nœuds/iters",14}{"Temps (s)",11}{"Coup",6}");
Console.WriteLine(new string('-', 55));
var sw = Stopwatch.StartNew();
foreach (int d in new[] { 4, 6, 8 }) // depth 10 = ~330 s, mesuré hors-ligne (voir plus haut)
{
C4Minimax.NbNoeuds = 0;
sw.Restart();
var (v, a) = C4Minimax.DepthLimite(jeuC4, jeuC4.EtatInitial(), d);
sw.Stop();
Console.WriteLine($"{"Minimax depth="+d,-22}{C4Minimax.NbNoeuds,14:N0}{sw.Elapsed.TotalSeconds,11:F2}{a,6}");
}
Console.WriteLine($"{"Minimax depth=10 (mesure)",-22}{314_060_245,14:N0}{330.18,11:F2}{"-",6}");
Console.WriteLine();
foreach (int it in new[] { 1000, 5000, 10000, 50000 })
{
var mcts = new MCTS<EtatC4>(jeuC4, seed: 42);
sw.Restart();
var (action, valeur) = mcts.Recherche(jeuC4.EtatInitial(), it);
sw.Stop();
Console.WriteLine($"{"MCTS iter="+it,-22}{it,14:N0}{sw.Elapsed.TotalSeconds,11:F2}{action,6}");
}