GameTheory-17 (C#) : Multi-Agent Reinforcement Learning — Self-Play, FP, NFSP, PSRO

Twin C# (.NET Interactive / from-scratch) du notebook Python GameTheory-17-MultiAgent-RL-Python (numpy + OpenSpiel).

Le Multi-Agent Reinforcement Learning (MARL) étend le RL classique au cas où plusieurs agents apprennent simultanément. La difficulté centrale : la politique optimale d’un agent dépend de la politique de l’autre — qui évolue aussi. Ce notebook présente les algorithmes fondateurs du MARL sur des jeux matriciels :

  1. Self-Play naif : chaque joueur joue la meilleure réponse à la stratégie courante de l’autre. Illustre pourquoi ça diverge (cycle).
  2. Fictitious Play (FP) : jouer la meilleure réponse à la fréquence empirique historique de l’adversaire. Converge vers Nash sur certains jeux.
  3. Exploitabilité : mesure de distance à un équilibre (somme des gains de meilleure réponse des deux joueurs).
  4. Neural Fictitious Self-Play (NFSP) — version simplifiée table-based (Q-learning + stratégie moyenne, sans réseau de neurones).
  5. Policy-Space Response Oracles (PSRO) : maintien d’une population de stratégies + équilibre de Nash sur le méta-jeu.

Parité : le twin Python utilise numpy (noyau portable) + OpenSpiel (pyspiel, section 6) + décrit NFSP/AlphaZero neuronaux. Ce twin C# couvre l’intégralité du noyau table-based portable (Self-Play, FP, NFSP simplifié, PSRO) en C# from-scratch (0 NuGet). Les composants exigeant un framework neuronal (AlphaZero = MCTS + réseaux) ou une lib C++ externe (OpenSpiel/pyspiel) sont documentés comme INTRINSIC / RECOVERABLE-MACHINE (verdict SOTA section 8).

0. Environnement

Aucune dépendance externe : tout est implémenté from-scratch en C# (BCL only). La comparaison finale utilise un tracé ASCII (substitut documenté de matplotlib).

using System;
using System.Linq;
using System.Collections.Generic;

Console.WriteLine("GT-17 Multi-Agent RL (C# twin) - environnement pret.");
GT-17 Multi-Agent RL (C# twin) - environnement pret.

1. Défis du Multi-Agent RL

En RL single-agent, l’agent apprend une politique optimale dans un environnement stationnaire (les règles ne changent pas). En MARL, l’environnement de chaque agent inclut les autres agents qui apprennent — donc il est non-stationnaire.

Défi Description
Non-stationnarité La politique optimale change quand l’adversaire apprend
Équilibre vs optimum On cherche un Nash, pas un maximum global
Coordination Plusieurs optima coordonnés (jeux de coordination)
Exploration jointe Les deux agents doivent explorer simultanément

La solution clé : les algorithmes de self-play, où un agent (ou une population) joue contre lui-même pour découvrir des stratégies d’équilibre.

2. Jeu matriciel : la brique de base

Un jeu matriciel à somme nulle à 2 joueurs : une matrice de gains A où A[i,j] = gain du joueur 1 si P1 joue l’action i et P2 l’action j. Le gain de P2 = -A[i,j] (somme nulle). Les stratégies sont des distributions de probabilité sur les actions (stratégies mixtes).

// Jeu matriciel a 2 joueurs, somme nulle (P2 = -P1)
class MatrixGame {
    public double[,] A;  // matrice de gains P1
    public string Name;
    public int N1 => A.GetLength(0);  // actions P1
    public int N2 => A.GetLength(1);  // actions P2
    public MatrixGame(double[,] a, string name="Game") { A=a; Name=name; }

    // Gain espere pour strategies mixtes s1 (P1), s2 (P2)
    public double ExpectedPayoffP1(double[] s1, double[] s2) {
        double sum = 0;
        for (int i=0;i<N1;i++) for (int j=0;j<N2;j++) sum += s1[i]*A[i,j]*s2[j];
        return sum;
    }

    // Meilleure reponse (action pure) de P1 a la strategie s2 de P2
    public int BestResponseP1(double[] s2) {
        int best=0; double bestVal=double.NegativeInfinity;
        for (int i=0;i<N1;i++) {
            double v=0; for (int j=0;j<N2;j++) v += A[i,j]*s2[j];
            if (v>bestVal) { bestVal=v; best=i; }
        }
        return best;
    }

    // Meilleure reponse de P2 a s1 (P2 minimise le gain P1 => maximise -A^T)
    public int BestResponseP2(double[] s1) {
        int best=0; double bestVal=double.PositiveInfinity;  // P2 minimise le gain de P1
        for (int j=0;j<N2;j++) {
            double v=0; for (int i=0;i<N1;i++) v += s1[i]*A[i,j];
            if (v<bestVal) { bestVal=v; best=j; }
        }
        return best;
    }
}

// Jeux canoniques
MatrixGame RPS() {
    // Rock/Paper/Scissors : gain +1 si gagne, -1 si perd, 0 sinon
    return new MatrixGame(new double[,]{{0,-1,1},{1,0,-1},{-1,1,0}}, "RPS");
}
MatrixGame MatchingPennies() {
    // P1 veut matcher, P2 veut eviter. A[i,j] = +1 si i==j sinon -1
    return new MatrixGame(new double[,]{{1,-1},{-1,1}}, "MatchingPennies");
}

var rps = RPS();
var mp = MatchingPennies();
Console.WriteLine("RPS: " + rps.N1 + "x" + rps.N2 + " actions");
Console.WriteLine("MatchingPennies: " + mp.N1 + "x" + mp.N2 + " actions");
var uniform = new double[]{1.0/3,1.0/3,1.0/3};
Console.WriteLine("RPS uniforme vs uniforme : gain P1 = " + rps.ExpectedPayoffP1(uniform,uniform).ToString("F4") + " (=0 a lequilibre)");
RPS: 3x3 actions
MatchingPennies: 2x2 actions
RPS uniforme vs uniforme : gain P1 = 0,0000 (=0 a lequilibre)

3. Self-Play naif : pourquoi ça diverge

Dans le self-play naif, chaque joueur joue la meilleure réponse à la stratégie courante de l’adversaire, puis met à jour sa stratégie par moyenne mobile. Sur Roche-Papier-Ciseaux, cela cycle indéfiniment (Roche → Papier → Ciseaux → Roche…) sans converger.

class NaiveSelfPlay {
    MatrixGame G; double Lr;
    double[] s1, s2;
    public List<double> ExploitHistory = new();
    public NaiveSelfPlay(MatrixGame g, double lr=0.1) {
        G=g; Lr=lr;
        s1 = Enumerable.Repeat(1.0/g.N1, g.N1).ToArray();
        s2 = Enumerable.Repeat(1.0/g.N2, g.N2).ToArray();
    }
    public void Step() {
        int br1 = G.BestResponseP1(s2);
        int br2 = G.BestResponseP2(s1);
        // Mise a jour graduelle vers la BR
        for (int i=0;i<s1.Length;i++) s1[i] = (1-Lr)*s1[i] + (i==br1? Lr:0);
        for (int j=0;j<s2.Length;j++) s2[j] = (1-Lr)*s2[j] + (j==br2? Lr:0);
    }
    public double[] S1 => s1; public double[] S2 => s2;
}

// Demo : self-play naif sur RPS
var sp = new NaiveSelfPlay(rps, 0.3);
double Exploit() {
    // exploitabilite = (gain BR P1 vs s2) + (gain BR P2 vs s1) a somme nulle
    var br1vec = new double[rps.N1]; br1vec[rps.BestResponseP1(sp.S2)] = 1;
    var br2vec = new double[rps.N2]; br2vec[rps.BestResponseP2(sp.S1)] = 1;
    double g1 = rps.ExpectedPayoffP1(br1vec, sp.S2) - rps.ExpectedPayoffP1(sp.S1, sp.S2);
    double g2 = -(rps.ExpectedPayoffP1(sp.S1, br2vec) - rps.ExpectedPayoffP1(sp.S1, sp.S2));
    return g1 + g2;
}
Console.WriteLine("Self-Play naif sur RPS (montre le cycle) :");
Console.WriteLine("iter  exploit.  s1[0] s1[1] s1[2]");
for (int t=0;t<8;t++) {
    for (int k=0;k<5;k++) sp.Step();
    Console.WriteLine(t*5+5 + "     " + Exploit().ToString("F3") + "   " + sp.S1[0].ToString("F2") + "   " + sp.S1[1].ToString("F2") + "   " + sp.S1[2].ToString("F2"));
}
Console.WriteLine("\nObserve : la strategie oscille, ne converge pas (cycle R->P->S)." );
Self-Play naif sur RPS (montre le cycle) :
iter  exploit.  s1[0] s1[1] s1[2]
5     0,520   0,13   0,31   0,57
10     0,424   0,20   0,41   0,40
15     0,591   0,28   0,58   0,14
20     0,413   0,40   0,40   0,20
25     0,590   0,58   0,14   0,28
30     0,413   0,40   0,20   0,40
35     0,590   0,14   0,28   0,58
40     0,413   0,20   0,40   0,40

Observe : la strategie oscille, ne converge pas (cycle R->P->S).

4. Fictitious Play : converger vers Nash

Fictitious Play (Brown 1951) corrige le self-play naif : au lieu de répondre à la stratégie instantanée, chaque joueur répond à la fréquence empirique (moyenne historique) des actions de l’adversaire. Sur les jeux à somme nulle 2 joueurs, FP converge vers l’équilibre de Nash (Robinson 1951).

class FictitiousPlay {
    MatrixGame G;
    double[] counts1, counts2;  // compteurs d actions (Laplace smoothing init=1)
    public List<double> ExploitHistory = new();
    public FictitiousPlay(MatrixGame g) {
        G=g;
        counts1 = Enumerable.Repeat(1.0, g.N1).ToArray();
        counts2 = Enumerable.Repeat(1.0, g.N2).ToArray();
    }
    public double[] AvgStrategy1 { get {
        double s=counts1.Sum(); return counts1.Select(c=>c/s).ToArray();
    } }
    public double[] AvgStrategy2 { get {
        double s=counts2.Sum(); return counts2.Select(c=>c/s).ToArray();
    } }
    public void Step() {
        var avg1 = AvgStrategy1; var avg2 = AvgStrategy2;
        int br1 = G.BestResponseP1(avg2);
        int br2 = G.BestResponseP2(avg1);
        counts1[br1]++; counts2[br2]++;
    }
    public double Exploitability() {
        var s1=AvgStrategy1; var s2=AvgStrategy2;
        double baseline = G.ExpectedPayoffP1(s1,s2);
        var br1vec=new double[G.N1]; br1vec[G.BestResponseP1(s2)]=1;
        var br2vec=new double[G.N2]; br2vec[G.BestResponseP2(s1)]=1;
        double gain1 = G.ExpectedPayoffP1(br1vec,s2) - baseline;
        double gain2 = baseline - G.ExpectedPayoffP1(s1,br2vec);  // gain de BR P2
        return gain1 + gain2;
    }
}

// FP sur Matching Pennies (equilibre = (0.5, 0.5) pour les deux)
var fp = new FictitiousPlay(mp);
Console.WriteLine("Fictitious Play sur Matching Pennies (equilibre cible = 0.5, 0.5) :");
Console.WriteLine("iter  exploit.  P1 avg      P2 avg");
for (int t=0;t<6;t++) {
    for (int k=0;k<200;k++) { fp.Step(); fp.ExploitHistory.Add(fp.Exploitability()); }
    var a1=fp.AvgStrategy1; var a2=fp.AvgStrategy2;
    Console.WriteLine((t+1)*200 + "   " + fp.Exploitability().ToString("F4") + "   (" + a1[0].ToString("F3") + "," + a1[1].ToString("F3") + ")  (" + a2[0].ToString("F3") + "," + a2[1].ToString("F3") + ")");
}
Console.WriteLine("\nConvergence vers (0.5,0.5) confirmee (Robinson 1951)." );
Fictitious Play sur Matching Pennies (equilibre cible = 0.5, 0.5) :
iter  exploit.  P1 avg      P2 avg
200   0,0990   (0,475,0,525)  (0,475,0,525)
400   0,0697   (0,473,0,527)  (0,493,0,507)
600   0,0598   (0,525,0,475)  (0,495,0,505)
800   0,0499   (0,488,0,512)  (0,488,0,512)
1000   0,0439   (0,483,0,517)  (0,505,0,495)
1200   0,0399   (0,490,0,510)  (0,510,0,490)

Convergence vers (0.5,0.5) confirmee (Robinson 1951).

5. Exploitabilité : mesurer la distance à Nash

L’exploitabilité d’un profil de stratégie (s1, s2) = combien chaque joueur gagnerait en déviant vers sa meilleure réponse. À l’équilibre de Nash d’un jeu à somme nulle, l’exploitabilité = 0 (personne ne veut dévier).

exploit(s1,s2) = [gain BR_P1 vs s2 - gain(s1,s2)] + [gain(s1,s2) - gain(s1 vs BR_P2)]

Les deux termes mesurent les gains de déviation unilatérale. Une stratégie d’équilibre minimise l’exploitabilité.

static double ComputeExploitability(MatrixGame g, double[] s1, double[] s2) {
    double baseline = g.ExpectedPayoffP1(s1, s2);
    var br1vec = new double[g.N1]; br1vec[g.BestResponseP1(s2)] = 1;
    var br2vec = new double[g.N2]; br2vec[g.BestResponseP2(s1)] = 1;
    double gain1 = g.ExpectedPayoffP1(br1vec, s2) - baseline;  // P1 peut gagner +gain1
    double gain2 = baseline - g.ExpectedPayoffP1(s1, br2vec);  // P2 peut gagner +gain2
    return gain1 + gain2;
}

// RPS : uniforme (equilibre) vs biaisee (non-equilibre)
var uni3 = new double[]{1.0/3,1.0/3,1.0/3};
var biased = new double[]{0.5,0.3,0.2};
Console.WriteLine("RPS uniforme vs uniforme : exploitabilite = " + ComputeExploitability(rps,uni3,uni3).ToString("F4") + " (equilibre, ~0)");
Console.WriteLine("RPS biaisee (0.5/0.3/0.2) vs biaisee : exploitabilite = " + ComputeExploitability(rps,biased,biased).ToString("F4") + " (exploitable !)");
Console.WriteLine("Une strategie biaisee est exploitable : ladversaire joue la BR (ici toujours Papier) et gagne." );
RPS uniforme vs uniforme : exploitabilite = 0,0000 (equilibre, ~0)
RPS biaisee (0.5/0.3/0.2) vs biaisee : exploitabilite = 0,6000 (exploitable !)
Une strategie biaisee est exploitable : ladversaire joue la BR (ici toujours Papier) et gagne.

6. Neural Fictitious Self-Play (NFSP) — version table-based

Le NFSP (Heinrich & Silver 2016) combine RL (apprendre une meilleure réponse via Q-learning) et Supervised Learning (mémoriser la stratégie moyenne dans un réseau). La version originale utilise des réseaux de neurones ; ici nous utilisons des tables Q (Q-learning tabulaire) — suffisantes pour les jeux matriciels à petit nombre d’actions. Chaque agent (i) met à jour ses Q-values vers la meilleure réponse (oracle) et (ii) accumule dans une mémoire (moyenne cumulative) l’action apprise (greedy sur Q). L’exploitabilité est évaluée sur cette mémoire — l’analogue NFSP de la fréquence empirique de FP.

Caveat honnête (G.1) : contrairement à FP (dont la BR est exacte et qui converge vers Nash, Robinson 1951), ici la BR est apprise (argmax de Q). Dans l’environnement non-stationnaire du self-play, cette BR apprise cycle, et la mémoire cumulée ne converge pas vers Nash — l’exploitabilité plafonne vers ~0.41 sur RPS. C’est précisément la difficulté que le vrai NFSP adresse par l’approximation neuronale, l’expérience replay et le jeu eta-mélangé. La version tabulaire illustrée ici met en évidence pourquoi ces mécanismes sont nécessaires.

class SimplifiedNFSP {
    MatrixGame G; double RlLr;
    double[] Q1, Q2;                 // Q-values = meilleure reponse APPRISE (RL)
    double[] counts1, counts2;       // memoire SL : moyenne CUMULATIVE des actions gloutonnes
    public List<double> ExploitHistory = new();
    public SimplifiedNFSP(MatrixGame g, double rlLr=0.1) {
        G=g; RlLr=rlLr;
        Q1 = new double[g.N1]; Q2 = new double[g.N2];
        counts1 = Enumerable.Repeat(1.0, g.N1).ToArray();  // Laplace smoothing
        counts2 = Enumerable.Repeat(1.0, g.N2).ToArray();
    }
    // Strategie evaluee = la MEMOIRE (moyenne cumulative), analogue NFSP de la frequence empirique FP
    public double[] Avg1 { get { double s=counts1.Sum(); return counts1.Select(c=>c/s).ToArray(); } }
    public double[] Avg2 { get { double s=counts2.Sum(); return counts2.Select(c=>c/s).ToArray(); } }
    public int GreedyP1() { int b=0; for (int i=1;i<Q1.Length;i++) if (Q1[i]>Q1[b]) b=i; return b; }
    public int GreedyP2() { int b=0; for (int j=1;j<Q2.Length;j++) if (Q2[j]<Q2[b]) b=j; return b; }  // P2 minimise
    public void Step() {
        var s1=Avg1; var s2=Avg2;  // chaque joueur joue sa memoire
        int a1 = G.BestResponseP1(s2);  // cible RL : vraie meilleure reponse (oracle)
        int a2 = G.BestResponseP2(s1);
        // Mise a jour Q (RL) : Q[a] vers le gain espere de laction
        double r1=0; for (int j=0;j<G.N2;j++) r1 += G.A[a1,j]*s2[j];
        Q1[a1] += RlLr*(r1 - Q1[a1]);
        double r2=0; for (int i=0;i<G.N1;i++) r2 += G.A[i,a2]*s1[i];
        Q2[a2] += RlLr*(r2 - Q2[a2]);
        // Memoire SL : on accumule laction APPRISE (greedy sur Q), pas loracle.
        // C est l ECART cles vs FP : NFSP moyenne sa BRappris, pas la vraie BR.
        counts1[GreedyP1()]++; counts2[GreedyP2()]++;
    }
    public double Exploitability() => ComputeExploitability(G, Avg1, Avg2);
}

var nfsp = new SimplifiedNFSP(rps, rlLr:0.3);
Console.WriteLine("NFSP (table-based) sur RPS : exploitabilite de la memoire (moyenne cumulative)");
Console.WriteLine("iter  exploit.  Q1 approx  memoire P1");
for (int t=0;t<6;t++) {
    for (int k=0;k<200;k++) { nfsp.Step(); }
    var a1=nfsp.Avg1;
    Console.WriteLine((t+1)*200 + "   " + nfsp.Exploitability().ToString("F4") + "   ("
        + nfsp.GreedyP1() + ")   (" + a1[0].ToString("F3") + "," + a1[1].ToString("F3") + "," + a1[2].ToString("F3") + ")");
}
Console.WriteLine("\nObservation honnete : la memoire PLAFONNE a ~0.41, ne converge PAS vers Nash." );
Console.WriteLine("La BR apprise (greedy sur Q) CYCLE dans cet env non-stationnaire : la moyenne");
Console.WriteLine("cumulee neprouve pas la convergence. C est lecart cles vs FP (BR exacte -> converge).");
Console.WriteLine("Le vrai NFSP a besoin de RN + experience replay + jeu eta-melange pour stabiliser.");
NFSP (table-based) sur RPS : exploitabilite de la memoire (moyenne cumulative)
iter  exploit.  Q1 approx  memoire P1
200   0,4138   (0)   (0,212,0,291,0,498)
400   0,4119   (0)   (0,501,0,146,0,352)
600   0,4113   (1)   (0,459,0,287,0,254)
800   0,4110   (1)   (0,396,0,413,0,191)
1000   0,4108   (1)   (0,358,0,490,0,153)
1200   0,4123   (2)   (0,332,0,538,0,131)

Observation honnete : la memoire PLAFONNE a ~0.41, ne converge PAS vers Nash.
La BR apprise (greedy sur Q) CYCLE dans cet env non-stationnaire : la moyenne
cumulee neprouve pas la convergence. C est lecart cles vs FP (BR exacte -> converge).
Le vrai NFSP a besoin de RN + experience replay + jeu eta-melange pour stabiliser.

7. PSRO : Policy-Space Response Oracles

PSRO (Lanctot et al. 2017) maintient une population de stratégies pour chaque joueur, et calcule à chaque tour un méta-jeu (matrice de gains entre toutes les stratégies de la population), puis l’équilibre de Nash du méta-jeu (méta-Nash). On ajoute ensuite à la population la meilleure réponse au méta-Nash de l’adversaire. Cela élargit progressivement le pool de stratégies jusqu’à convergence.

class PSRO {
    MatrixGame G;
    public List<double[]> Pop1 = new(), Pop2 = new();
    public List<double> ExploitHistory = new();
    public PSRO(MatrixGame g) {
        G=g;
        Pop1.Add(Enumerable.Repeat(1.0/g.N1, g.N1).ToArray());
        Pop2.Add(Enumerable.Repeat(1.0/g.N2, g.N2).ToArray());
    }
    // Meta-jeu : payoff[i,j] = gain espere de Pop1[i] vs Pop2[j]
    double MetaPayoff(int i, int j) => G.ExpectedPayoffP1(Pop1[i], Pop2[j]);
    // Meta-Nash sur meta-jeu 2x2 (uniforme ici ; un vrai solveur LP donnerait le Nash exact)
    (double[] m1, double[] m2) MetaNash() {
        // Pour simplicite : strategie uniforme sur la population courante
        // (un PSRO complet resout le meta-jeu par LP/programmation lineaire)
        var m1 = Enumerable.Repeat(1.0/Pop1.Count, Pop1.Count).ToArray();
        var m2 = Enumerable.Repeat(1.0/Pop2.Count, Pop2.Count).ToArray();
        return (m1, m2);
    }
    // Strategie mixte de ladversaire (combinaison meta-Nash de sa population)
    double[] MixedStrategy2(double[] m2) {
        var s = new double[G.N2];
        for (int j=0;j<Pop2.Count;j++) for (int a=0;a<G.N2;a++) s[a] += m2[j]*Pop2[j][a];
        return s;
    }
    double[] MixedStrategy1(double[] m1) {
        var s = new double[G.N1];
        for (int i=0;i<Pop1.Count;i++) for (int a=0;a<G.N1;a++) s[a] += m1[i]*Pop1[i][a];
        return s;
    }
    public void Step() {
        var (m1,m2) = MetaNash();
        // IMPORTANT : calculer les strategies mixtes AVANT d ajouter a la population,
        // car m1/m2 ont la longueur courante de la population.
        var opp2 = MixedStrategy2(m2);  // strategie mixte de P2 vue par P1
        var opp1 = MixedStrategy1(m1);  // strategie mixte de P1 vue par P2
        int br1 = G.BestResponseP1(opp2);
        int br2 = G.BestResponseP2(opp1);
        var br1vec = new double[G.N1]; br1vec[br1]=1;
        var br2vec = new double[G.N2]; br2vec[br2]=1;
        Pop1.Add(br1vec);
        Pop2.Add(br2vec);
        // Exploitabilite de la meta-strategie uniforme
        ExploitHistory.Add(ComputeExploitability(G, opp1, opp2));
    }
}

var psro = new PSRO(rps);
Console.WriteLine("PSRO sur RPS (croissance de la population) :");
Console.WriteLine("round  pop_size  exploit.");
for (int t=0;t<6;t++) {
    psro.Step();
    Console.WriteLine(t+1 + "      " + psro.Pop1.Count + "         " + psro.ExploitHistory.Last().ToString("F4"));
}
Console.WriteLine("La population grandit ; chaque round ajoute une meilleure reponse au meta-Nash." );
PSRO sur RPS (croissance de la population) :
round  pop_size  exploit.
1      2         0,0000
2      3         1,0000
3      4         0,6667
4      5         0,5000
5      6         0,8000
6      7         0,6667
La population grandit ; chaque round ajoute une meilleure reponse au meta-Nash.

8. Verdict SOTA : ce qui est portable et ce qui ne l’est pas

Le twin Python utilise, au-delà du noyau numpy (porté ici en C#) : - OpenSpiel (pyspiel) : lib C++ de DeepMind pour les jeux extensifs (Kuhn Poker, etc.). Pont .NET démontré via PythonNet (annexe S10) – la taxonomie bucket-3 (#10382) avait omis l’axe PythonNet (.NET -> Python.Runtime -> pyspiel -> OpenSpiel C++, même axe que SemanticKernel-09 et que le moteur QuantConnect/Lean). Le pont est RECOVERABLE-LOCAL : pythonnet (NuGet) + open_spiel (pip) s’installent sur la machine du worker (règle F) et le branchement est mesuré en annexe S10 (load_game('kuhn_poker') + rollout réel exécuté depuis C#). Le from-scratch C# (sections 3-7) reste la contrepartie pédagogique : le pont est en plus, jamais à la place (mandat #10382). L’axe « lib-différente » (Gambit CLI, #10442) reste ouvert pour l’équilibre de Nash mais le pont PythonNet est plus direct pour OpenSpiel-la-lib. - NFSP / AlphaZero neuronaux : réseaux de neurones (PyTorch/TensorFlow) + MCTS. Le noyau .NET n’a pas d’équivalent unifié de PyTorch pour l’entraînement RL à grande échelle → INTRINSIC pour la version neurale complète.

Ce twin couvre donc le noyau pédagogique portable (Self-Play, FP, exploitabilité, NFSP table-based, PSRO méta-jeu) en C# from-scratch – qui est la partie algorithmiquement instructive. Les composants industriels neuronaux (AlphaZero) restent la référence Python ; OpenSpiel-la-lib est désormais atteignable depuis C# (annexe S10).

9. Comparaison des 4 méthodes sur RPS

Comparons l’évolution de l’exploitabilité pour Self-Play naif, FP, NFSP et PSRO sur Roche-Papier-Ciseaux. Une méthode converge vers Nash si son exploitabilité décroît vers 0.

// Comparaison : courbes d'exploitabilite (SVG inline) - Self-Play naif vs FP vs NFSP vs PSRO sur RPS.
// Prong-A (#3801) : remplace le dump texte Console.WriteLine par un vrai rendu (desormais SVG
// statique zero-CDN, rend sur GitHub/nbviewer/offline). Dynamique inchangee (meme computation,
// meme graine) : FP -> 0 (Robinson 1951), Self-Play naif oscille (cycle),
// NFSP chute puis plafonne (version tabulaire non stationnaire).
// PSRO (meta-Nash uniforme) oscille comme Self-Play : sans solveur LP exact sur le
// meta-jeu, l'exploitabilite ne converge pas vers 0 (la population grandit mais
// la strategie uniforme sur la population n'atteint pas Nash).
// Helper canon SvgChartHelper.cs (#6942 MERGED) ; Overlay multi-series (#6958 MERGED) pour les
// 4 courbes partageant l'axe X numerique "iteration". Cf #6927 / #3801.
#load "../Probas/Infer/SvgChartHelper.cs"

int N = 300;
var spC = new NaiveSelfPlay(rps, 0.3);
var fpC = new FictitiousPlay(rps);
var nfspC = new SimplifiedNFSP(rps, rlLr:0.3);
var psroC = new PSRO(rps);
double[] spE = new double[N/10], fpE = new double[N/10], nfspE = new double[N/10], psroE = new double[N/10];
for (int t=0;t<N;t++) {
    spC.Step();
    fpC.Step(); fpC.ExploitHistory.Add(fpC.Exploitability());
    nfspC.Step();
    psroC.Step();
    if (t%10==0) {
        int idx=t/10;
        var s1=spC.S1; var s2=spC.S2;
        spE[idx]=ComputeExploitability(rps,s1,s2);
        fpE[idx]=fpC.Exploitability();
        nfspE[idx]=nfspC.Exploitability();
        psroE[idx]=psroC.ExploitHistory[idx*10];
    }
}

// Axe x = iteration (0..290 par pas de 10)
int M = spE.Length;
double[] xs = Enumerable.Range(0, M).Select(i => (double)(i*10)).ToArray();

SvgChartHelper.Overlay(
    "Exploitabilite (RPS) - convergence vs cycles",
    "iteration", "exploitabilite",
    new[] {
        new SvgSeries("Self-Play naif", xs, spE, TraceStyle.LineMarkers, "#C44E52"),
        new SvgSeries("Fictitious Play", xs, fpE, TraceStyle.LineMarkers, "#4C72B0"),
        new SvgSeries("NFSP (tabulaire)", xs, nfspE, TraceStyle.LineMarkers, "#55A868"),
        new SvgSeries("PSRO", xs, psroE, TraceStyle.LineMarkers, "#8172B3"),
    })
Exploitabilite (RPS) - convergence vs cycles-0.0360.1320.30.4680.636072.5145217.5290iterationexploitabiliteSelf-Play naifFictitious PlayNFSP (tabulaire)PSRO

Conclusion

Méthode Principe Convergence RPS Statut twin C#
Self-Play naif BR vs stratégie courante Cycle (diverge) SOTA-OK (section 3)
Fictitious Play BR vs fréquence empirique Converge (Robinson 1951) SOTA-OK (section 4)
Exploitabilité Somme des gains de déviation = 0 à Nash SOTA-OK (section 5)
NFSP (table-based) Q-learning + mémoire moyenne Plafonne ~0.41 (ne converge pas) SOTA-OK (section 6, caveat G.1)
PSRO Population + méta-Nash Croissance pool SOTA-OK (section 7)
OpenSpiel (pyspiel) Lib C++ jeux extensifs — SOTA-OK (pont PythonNet S10)
AlphaZero neuronal MCTS + NN (PyTorch/TF) — INTRINSIC

Lecons clés : 1. Non-stationnarité : en MARL, l’environnement change parce que l’adversaire apprend. Les algorithmes doivent viser un équilibre, non un optimum. 2. Self-play naif cycle : répondre à la stratégie instantanée crée des cycles (R→P→S). Fictitious Play stabilise en répondant à la moyenne. 3. Exploitabilité = métrique de Nash : elle mesure combien on perdrait face à un adversaire qui nous connaît. 0 = Nash. 4. PSRO élargit le pool : au lieu d’une seule stratégie, on maintient une population et on joue un Nash sur le méta-jeu — plus robuste. 5. NFSP = RL + SL : la combinaison Q-learning (BR) + mémoire (stratégie moyenne) imite le jeu humain (exploiter + rester imprévisible).

Parité avec le twin Python : le noyau algorithmique portable (sections 2-7) est couvert à l’identique. OpenSpiel (jeux extensifs C++) est désormais atteignable depuis C# via le pont PythonNet (annexe S10) ; seul AlphaZero neuronal (PyTorch/TF + MCTS) reste INTRINSIC (section 8), conformément à la discipline SOTA (#3801).

Verdict lib-vs-lib #10382/#10459 (bucket-3, RECOVERABLE-LOCAL pour OpenSpiel) : la parité nativement atteignable couvre le noyau table-based portable (Self-Play, FP, exploitabilité, NFSP, PSRO). Côté Python, l’écosystème OpenSpiel (pyspiel — librairie C++ de DeepMind) fournit fictitious_play, exploitability, rl_environment, les jeux extensifs (Kuhn/Leduc Poker) et les références AlphaZero. Cet écosystème est désormais atteignable depuis C# via le pont PythonNet (annexe S10) – la taxonomie bucket-3 (#10382) avait omis cet axe (.NET -> Python.Runtime -> pyspiel -> C++), corrigé par #10459. Le pont est démontré : load_game('kuhn_poker') + rollout réel exécuté depuis C# avec sortie committée. Le from-scratch C# reste la contrepartie pédagogique (niveau semantic) – le pont est en plus, jamais à la place (mandat #10382). Reste INTRINSIC : NFSP/AlphaZero neuronaux (PyTorch/TF + MCTS, pas d’équivalent .NET unifié pour le RL neuronal à grande échelle). L’axe « lib-différente » (Gambit CLI, #10442) reste ouvert pour l’équilibre de Nash.

Exercices

Completez les squelettes ci-dessous (result = null // TODO).

// Exercice 1 : Calculer lexploitabilite de la strategie (0.5, 0.3, 0.2) sur RPS.
// Indice : utiliser ComputeExploitability(rps, biased, biased).
object exo1Result = null;  // TODO etudiant : double attendu
Console.WriteLine(exo1Result == null ? "Exercice a completer" : exo1Result);
Exercice a completer
// Exercice 2 : Faire converger Fictitious Play sur Matching Pennies et verifier (0.5,0.5).
// Indice : instancier FictitiousPlay(mp), Step() x1000, lire AvgStrategy1.
object exo2Result = null;  // TODO etudiant : double[] attendu
Console.WriteLine(exo2Result == null ? "Exercice a completer" : exo2Result);
Exercice a completer
// Exercice 3 : Ajouter une 4eme action a RPS (R-P-C-Lizard, facon Big Bang) et
// relancer FP. La convergence tient-elle ? ( conjecture : oui pour somme nulle 2-j ).
object exo3Result = null;  // TODO etudiant : string/bool verdict attendu
Console.WriteLine(exo3Result == null ? "Exercice a completer" : exo3Result);
Exercice a completer

10. Annexe : Pont .NET vers OpenSpiel via PythonNet (#10459)

La section 8 requalifie le verdict SOTA d’OpenSpiel d’INTRINSIC en RECOVERABLE-LOCAL : un pont direct existe, il est installable et mesurable. Cette annexe démontre le branchement effectif – la parité lib-vs-lib visée par le mandat #10382, axe PythonNet omis de la taxonomie bucket-3 et corrigé par #10459.

Chaîne d’interopérabilité : C# (.NET 9) -> pythonnet (Python.Runtime) -> pyspiel -> OpenSpiel C++. C’est le même axe que le notebook SemanticKernel-09 (CLR interop Python<->.NET) et que l’architecture du moteur de backtesting QuantConnect/Lean. Aucun port .NET natif n’est requis : pythonnet s’installe par NuGet, open_spiel par pip (règle F).

La cellule ci-dessous charge le vrai moteur OpenSpiel depuis C# et exécute un rollout réel sur Kuhn poker (jeu extensif non couvert par le from-scratch sections 2-7). La sortie committée est la preuve que le pont est vivant.

Rejouabilité : la cellule pointe vers CPython via la variable d’environnement PYTHONNET_PYDLL (défaut sous Windows : C:\Python313\python313.dll, le CPython 3.13 du worker où open_spiel est pip-installé). Sans cette variable ni ce fichier, elle interroge le premier interpréteur (python3, puis python) qui importe pyspiel, et en reprend la bibliothèque et le sys.path : sous Linux et macOS, pip install open_spiel suffit, environnement virtuel compris. PYTHONNET_PYDLL reste le moyen de désigner un autre CPython.

#r "nuget: pythonnet,3.0.5"
using System;
using System.Linq;
using System.Collections.Generic;
using Python.Runtime;

// Pont .NET -> CPython -> pyspiel -> OpenSpiel C++ (annexe S10, #10459).
// pythonnet (NuGet) embarque Python.Runtime ; on pointe vers le CPython 3.13
// ou open_spiel est installe (pip install open_spiel), puis on initialise le runtime.
// PYTHONNET_PYDLL (env) permet de pointer un autre CPython ; defaut = CPython 3.13 du worker.
// Repli portable (Linux, macOS, ou Windows sans le CPython ci-dessus) : le premier
// interpreteur (python3, puis python) qui importe le module fournit sa bibliotheque
// partagee, son prefixe et son sys.path, environnement virtuel compris.
static void InitPythonFromInterpreter(string module)
{
    const string probe =
        "import importlib, json, os, sys, sysconfig\n" +
        "importlib.import_module(sys.argv[1])\n" +
        "v = sysconfig.get_config_var; lib = v('LIBDIR') or ''; mm = sys.version_info[:2]\n" +
        "c = [os.path.join(lib, n) for n in (v('INSTSONAME'), v('LDLIBRARY')) if n]\n" +
        "c += [os.path.join(d, 'libpython%d.%d.dylib' % mm) for d in (lib, os.path.join(sys.base_prefix, 'lib'))]\n" +
        "c.append(os.path.join(sys.base_prefix, 'python%d%d.dll' % mm))\n" +
        "dll = next((p for p in c if os.path.isfile(p)), '')\n" +
        "print(json.dumps({'dll': dll, 'home': sys.base_prefix, 'path': [p for p in sys.path if p]}))\n";
    foreach (var exe in new[] { "python3", "python" })
    {
        try
        {
            var psi = new System.Diagnostics.ProcessStartInfo(exe)
            { RedirectStandardOutput = true, RedirectStandardError = true, UseShellExecute = false };
            foreach (var arg in new[] { "-c", probe, module }) psi.ArgumentList.Add(arg);
            using var p = System.Diagnostics.Process.Start(psi);
            var stderr = p.StandardError.ReadToEndAsync();
            string json = p.StandardOutput.ReadToEnd();
            p.WaitForExit();
            if (p.ExitCode != 0) continue;
            var info = System.Text.Json.JsonDocument.Parse(json).RootElement;
            string dll = info.GetProperty("dll").GetString();
            if (string.IsNullOrEmpty(dll)) continue;
            Runtime.PythonDLL = dll;
            PythonEngine.PythonHome = info.GetProperty("home").GetString();
            PythonEngine.Initialize();
            using (Py.GIL())
            {
                var path = info.GetProperty("path").EnumerateArray()
                    .Select(e => (PyObject)new PyString(e.GetString())).ToArray();
                Py.Import("sys").SetAttr("path", new PyList(path));
            }
            return;
        }
        catch (System.ComponentModel.Win32Exception) { }   // interpreteur absent du PATH
    }
    throw new System.IO.FileNotFoundException(
        $"Aucun CPython n'importe {module} : l'installer (pip install), ou definir PYTHONNET_PYDLL.");
}

var pyDll = Environment.GetEnvironmentVariable("PYTHONNET_PYDLL") ?? @"C:\Python313\python313.dll";
if (System.IO.File.Exists(pyDll)) { Runtime.PythonDLL = pyDll; PythonEngine.Initialize(); }
else InitPythonFromInterpreter("pyspiel");
Console.WriteLine($"Runtime Python : {PythonEngine.Version}");

// Invoque le vrai moteur OpenSpiel (le meme pyspiel que le twin Python cellule 16).
using (Py.GIL())
{
    dynamic pyspiel = Py.Import("pyspiel");
    dynamic game = pyspiel.load_game("kuhn_poker");
    Console.WriteLine($"load_game('kuhn_poker') : joueurs={game.num_players()}, " +
                      $"actions={game.num_distinct_actions()}, longueur_max={game.max_game_length()}");

    // Rollout reel : un episode de Kuhn poker (jeu extensif a information incomplete),
    // joue aleatoirement. Kuhn poker est somme nulle 2 joueurs -> returns = [+g, -g].
    dynamic state = game.new_initial_state();
    var rng = new Random(7);
    int steps = 0;
    while (!(bool)state.is_terminal() && steps < 50)
    {
        if ((bool)state.is_chance_node())
        {
            // Noeud hasard : distribue une carte parmi les outcomes possibles.
            dynamic outs = state.chance_outcomes();
            state.apply_action((int)outs[0][0]);
        }
        else
        {
            // Noeud de decision : action legale aleatoire.
            var legal = new List<int>();
            foreach (var a in state.legal_actions()) legal.Add((int)a);
            state.apply_action(legal[rng.Next(legal.Count)]);
        }
        steps++;
    }
    var rets = new List<double>();
    foreach (var r in state.returns()) rets.Add((double)r);
    Console.WriteLine($"Rollout : {steps} etapes, gains=[{string.Join(", ", rets)}]");
}
Console.WriteLine("PONT .NET -> OpenSpiel : OK");
Installed Packages
  • pythonnet, 3.0.5
Runtime Python : 3.11.15 (main, Mar  3 2026, 09:26:23) [GCC 13.3.0]
load_game('kuhn_poker') : joueurs=2, actions=2, longueur_max=3
Rollout : 5 etapes, gains=[-2, 2]
PONT .NET -> OpenSpiel : OK
Retour au sommet