GameTheory-13 : Jeux a Information Imparfaite et CFR (C#)

Navigation : << 12-Reputation | Index | 14-DifferentialGames >>

Twin C# (.NET Interactive) de GameTheory-13-ImperfectInfo-CFR-Python.ipynb — marathon #4956 (parite .NET <-> Python).

La théorie des jeux a information complète (échecs, poker vu par Dieu) se résout par minimax ou induction a rebours. Mais le poker est a information imparfaite : chaque joueur connait sa carte cachée, pas celle de l’adversaire. L’algorithme de référence pour ces jeux est CFR (Counterfactual Regret Minimization, Zinkevich et al. 2007) — c’est lui qui a permis de résoudre le Heads-Up Limit Texas Hold’em (Bowling et al. 2015). La stratégie moyenne produite par CFR converge vers un équilibre de Nash.

Plan pédagogique

Kuhn Poker — le plus petit jeu de poker réaliste (3 cartes, 2 actions)
Regret et Regret Matching — minimiser le regret cumule (demo Pierre-Feuille-Ciseaux)
CFR Vanilla — récursion contrefactuelle sur l’arbre de jeu
CFR+ — variante avec regrets ecretes (Tammelin 2014)
Convergence — la stratégie moyenne converge vers Nash
Exercices

Parite #4956 : la version Python déroule un solveur CFR from-scratch (§3-4) ET le compare a OpenSpiel (librarie Google DeepMind, boite noire). Ce twin C# (BCL .NET 9, 0 NuGet) traduit le solveur from-scratch (le coeur pédagogique — récursion contrefactuelle, regret matching, accumulation de stratégie moyenne) ; la comparaison OpenSpiel (Python-only, pas d’equivalent C# du même niveau) devient une note documentee honnete (RECOVERABLE-MACHINE) : le from-scratch CFR solver EST la substance.

1. Kuhn Poker : notre jeu de référence

Le Kuhn Poker (Kuhn 1950) est le plus petit poker a information imparfaite encore non-trivial. Trois cartes (Jack=0, Queen=1, King=2), deux joueurs, ante de 1. Chaque joueur reçoit une carte, le joueur 1 ouvre (passe ou mise), etc. Les historiques terminaux sont pp (check-check : abattage), pbp (check-bet-fold), pbb (check-bet-call : abattage), bp (bet-fold), bb (bet-call : abattage).

Un information set (infoset) = carte du joueur + historique visible. Deux situations dans le même infoset sont indistinguables pour le joueur (c’est la cle de l’information imparfaite).

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

static void Show(string s) { s.Display(); }

// Kuhn Poker : 3 cartes (J=0, Q=1, K=2), 2 actions (Pass=0, Bet=1).
public static class Kuhn
{
    public const int PASS = 0;
    public const int BET = 1;
    public const int NUM_ACTIONS = 2;
    public static readonly string[] CardName = { "J", "Q", "K" };

    public static bool IsTerminal(string history)
        => history == "pp" || history == "pbp" || history == "pbb"
           || history == "bp" || history == "bb";

    // Payoff du joueur courant a un etat terminal. cards = [card0, card1].
    public static double GetPayoff(string history, int[] cards)
    {
        bool p1Higher = cards[0] > cards[1];
        return history switch
        {
            "pp"  => p1Higher ? 1 : -1,     // check-check : abattage (pot=2, net +-1)
            "pbp" => -1,                    // check-bet-fold : J1 perd l'ante
            "pbb" => p1Higher ? 2 : -2,     // check-bet-call : abattage (pot=4, net +-2)
            "bp"  => 1,                     // bet-fold : J1 gagne l'ante
            "bb"  => p1Higher ? 2 : -2,     // bet-call : abattage (pot=4, net +-2)
            _ => 0
        };
    }

    public static string GetInfoSet(string history, int card)
        => CardName[card] + history;

    public static int GetCurrentPlayer(string history)
        => history.Length % 2;   // 0 = J1, 1 = J2 (alternance)
}

// Tests du modele de jeu.
$"Tests Kuhn Poker :".Display();
$"'pp' terminal ? {Kuhn.IsTerminal("pp")}  |  'p' terminal ? {Kuhn.IsTerminal("p")}".Display();
$"Payoff 'bb' avec K vs J  : {Kuhn.GetPayoff("bb", new[]{ 2, 0 })}   (attendu +2)".Display();
$"Payoff 'bp' (bet-fold)   : {Kuhn.GetPayoff("bp", new[]{ 0, 2 })}   (attendu +1)".Display();
$"Payoff 'pp' avec Q vs J  : {Kuhn.GetPayoff("pp", new[]{ 1, 0 })}   (attendu +1)".Display();
$"Infoset J2 avec Q apres 'p' : {Kuhn.GetInfoSet("p", 1)}   (attendu 'Qp')".Display();

Tests Kuhn Poker :

'pp' terminal ? True  |  'p' terminal ? False

Payoff 'bb' avec K vs J  : 2   (attendu +2)

Payoff 'bp' (bet-fold)   : 1   (attendu +1)

Payoff 'pp' avec Q vs J  : 1   (attendu +1)

Infoset J2 avec Q apres 'p' : Qp   (attendu 'Qp')

Lecture chiffree — le banc de tests du moteur Kuhn. Cinq lignes verifient chacune une piece du moteur avant tout entrainement : 'pp' terminal ? True mais 'p' terminal ? False — un pass de J1 laisse le coup vivre, deux passes closent l’abattage ; Payoff 'bb' avec K vs J : 2 (attendu +2) — mise contre mise, le King ramasse les deux mises ; Payoff 'bp' (bet-fold) : 1 (attendu +1) — le fold ne cede qu’une mise ; Payoff 'pp' avec Q vs J : 1 (attendu +1) — l’abattage au check vaut une mise ; et Infoset J2 avec Q apres 'p' : Qp — la etiquette d’information se construit carte + historique. Chaque attendu affirme une regle du jeu : la cellule suivante peut batir le regret matching sur ce socle, sachant que les payoffs et les infosets du solveur sont exacts.

2. Regret et Regret Matching

Le regret d’avoir joue l’action \(a\) au lieu de la stratégie \(\sigma\) est la différence d’utilité : \(R(a) = u(a) - \sum_b \sigma(b) u(b)\). On accumule ces regrets au fil des itérations, et la stratégie courante est proportionnelle aux regrets positifs cumules :

\[\sigma(a) = \frac{\max(0, R_{sum}(a))}{\sum_b \max(0, R_{sum}(b))}\]

(quand tous les regrets sont <= 0, stratégie uniforme.) Théorème : le regret matching sur un jeu a somme nulle converge vers l’équilibre de Nash.

#nullable enable
// Regret Matching pour un agent (N actions).
public class RegretMatcher
{
    public int NumActions;
    public double[] RegretSum;
    public double[] StrategySum;

    public RegretMatcher(int numActions)
    {
        NumActions = numActions;
        RegretSum = new double[numActions];
        StrategySum = new double[numActions];
    }

    // Strategie courante : proportionnelle aux regrets positifs cumules.
    public double[] GetStrategy()
    {
        var s = new double[NumActions];
        double norm = 0;
        for (int a = 0; a < NumActions; a++)
        {
            s[a] = Math.Max(0, RegretSum[a]);
            norm += s[a];
        }
        if (norm > 0)
            for (int a = 0; a < NumActions; a++) s[a] /= norm;
        else
            for (int a = 0; a < NumActions; a++) s[a] = 1.0 / NumActions;   // uniforme
        return s;
    }

    // Strategie moyenne (converge vers Nash en jeu a somme nulle).
    public double[] GetAverageStrategy()
    {
        var s = new double[NumActions];
        double norm = StrategySum.Sum();
        if (norm > 0)
            for (int a = 0; a < NumActions; a++) s[a] = StrategySum[a] / norm;
        else
            for (int a = 0; a < NumActions; a++) s[a] = 1.0 / NumActions;
        return s;
    }

    // Mise a jour : actionUtilities[a] = utilite observee de l'action a.
    public void Update(double[] actionUtilities, double reachProb = 1.0)
    {
        var strategy = GetStrategy();
        double expected = 0;
        for (int a = 0; a < NumActions; a++) expected += strategy[a] * actionUtilities[a];
        for (int a = 0; a < NumActions; a++)
            RegretSum[a] += actionUtilities[a] - expected;   // regret = u(a) - u(sigma)
        for (int a = 0; a < NumActions; a++)
            StrategySum[a] += reachProb * strategy[a];
    }
}

// Demonstration : regret matching sur Pierre-Feuille-Ciseaux, face a un adversaire qui joue toujours Pierre.
var rps = new RegretMatcher(3);   // 0=Pierre, 1=Feuille, 2=Ciseaux
var utilVsRock = new double[] { 0.0, 1.0, -1.0 };   // Pierre=0, Feuille=+1, Ciseaux=-1
for (int t = 0; t < 1000; t++) rps.Update(utilVsRock);
var avg = rps.GetAverageStrategy();
$"Regret Matching vs adversaire 'toujours Pierre' (1000 iter) :".Display();
$"  Pierre={avg[0]:F3}  Feuille={avg[1]:F3}  Ciseaux={avg[2]:F3}".Display();
$"  -> Converge vers Feuille (meilleure reponse pure a 'toujours Pierre'). Attendu (0.000, 1.000, 0.000).".Display();

Regret Matching vs adversaire 'toujours Pierre' (1000 iter) :

  Pierre=0,000  Feuille=0,999  Ciseaux=0,000

  -> Converge vers Feuille (meilleure reponse pure a 'toujours Pierre'). Attendu (0.000, 1.000, 0.000).

Lecture chiffree — le regret matching trouve la meilleure reponse pure. Face a un adversaire fige sur ‘toujours Pierre’ pendant 1000 iterations, la strategie apprise tombe a Pierre=0,000 Feuille=0,999 Ciseaux=0,000, contre l’attendu (0.000, 1.000, 0.000). Deux choses dans ces trois nombres : la masse se concentre entierement sur Feuille, la seule action a regret positif contre un adversaire qui ne joue que Pierre ; et le 0,999 — pas tout a fait 1,000 — rappelle que le regret matching ne produit jamais une pure exacte en temps fini : les regrets s’accumulent, la strategie s’approche sans toucher la borne. C’est le meme mecanisme que CFR va boucler contrefactuellement sur les 12 infosets du Kuhn Poker.

3. CFR Vanilla : la récursion contrefactuelle

CFR applique le regret matching a chaque information set de l’arbre de jeu, en parcourant récursivement toutes les attributions de cartes. L’idee cle est la reach probability contrefactuelle : on met a jour le regret d’un infoset seulement avec la probabilité d’atteindre ce noeud sans tenir compte du joueur courant (puisqu’on veut évaluer ce qui se passerait si CE joueur jouait differemment, toute chose égale par ailleurs).

cfr(history, cards, reach_probs):
  si terminal : retourner le payoff
  player = joueur courant ; infoset = carte[player] + history
  strategy = regret_matching(infoset)
  pour chaque action a :
     child_util = cfr(history + a, cards, reach * strategy[a] pour player)
     node_util += strategy[a] * child_util
  pour chaque action a :
     regret = child_util[player] - node_util[player]
     regret_sum[infoset][a] += reach_probs[opponent] * regret   # contrefactuel
  strategy_sum[infoset] += reach_probs[player] * strategy
  retourner node_util

Théorème (Zinkevich 2007) : la stratégie moyenne issue de strategy_sum converge vers un epsilon-équilibre de Nash quand le nombre d’itérations croit.

#nullable enable
// Solveur CFR vanilla pour Kuhn Poker. Stocke regret_sum et strategy_sum par infoset.
public class CFRSolver
{
    public Dictionary<string, double[]> RegretSum = new();
    public Dictionary<string, double[]> StrategySum = new();
    public int Iterations = 0;

    protected virtual double[] GetRegret(string infoset)
    {
        if (!RegretSum.ContainsKey(infoset)) RegretSum[infoset] = new double[Kuhn.NUM_ACTIONS];
        return RegretSum[infoset];
    }

    public double[] GetStrategy(string infoset)
    {
        var regrets = GetRegret(infoset);
        var s = new double[Kuhn.NUM_ACTIONS];
        double norm = 0;
        for (int a = 0; a < Kuhn.NUM_ACTIONS; a++) { s[a] = Math.Max(0, regrets[a]); norm += s[a]; }
        if (norm > 0)
            for (int a = 0; a < Kuhn.NUM_ACTIONS; a++) s[a] /= norm;
        else
            for (int a = 0; a < Kuhn.NUM_ACTIONS; a++) s[a] = 1.0 / Kuhn.NUM_ACTIONS;
        return s;
    }

    public double[] GetAverageStrategy(string infoset)
    {
        if (!StrategySum.ContainsKey(infoset)) return Enumerable.Repeat(1.0 / Kuhn.NUM_ACTIONS, Kuhn.NUM_ACTIONS).ToArray();
        var ss = StrategySum[infoset];
        double norm = ss.Sum();
        var s = new double[Kuhn.NUM_ACTIONS];
        if (norm > 0) for (int a = 0; a < Kuhn.NUM_ACTIONS; a++) s[a] = ss[a] / norm;
        else for (int a = 0; a < Kuhn.NUM_ACTIONS; a++) s[a] = 1.0 / Kuhn.NUM_ACTIONS;
        return s;
    }

    // Recursion CFR principale. Retourne [util_J0, util_J1].
    public virtual double[] Cfr(string history, int[] cards, double[] reach)
    {
        if (Kuhn.IsTerminal(history))
        {
            double p = Kuhn.GetPayoff(history, cards);   // payoff de J1
            return new double[] { p, -p };
        }
        int player = Kuhn.GetCurrentPlayer(history);
        int opponent = 1 - player;
        string infoset = Kuhn.GetInfoSet(history, cards[player]);
        var strategy = GetStrategy(infoset);

        var childUtil = new double[Kuhn.NUM_ACTIONS][];
        double[] nodeUtil = { 0, 0 };
        for (int a = 0; a < Kuhn.NUM_ACTIONS; a++)
        {
            char ac = a == Kuhn.PASS ? 'p' : 'b';
            var newReach = (double[])reach.Clone();
            newReach[player] *= strategy[a];
            childUtil[a] = Cfr(history + ac, cards, newReach);
            nodeUtil[0] += strategy[a] * childUtil[a][0];
            nodeUtil[1] += strategy[a] * childUtil[a][1];
        }

        // Mise a jour contrefactuelle : regret pondere par reach de l'adversaire.
        double cfReach = reach[opponent];
        var rs = GetRegret(infoset);
        for (int a = 0; a < Kuhn.NUM_ACTIONS; a++)
        {
            double regret = childUtil[a][player] - nodeUtil[player];
            rs[a] += cfReach * regret;
        }

        // Accumulation de la strategie (ponderee par reach du joueur courant).
        if (!StrategySum.ContainsKey(infoset)) StrategySum[infoset] = new double[Kuhn.NUM_ACTIONS];
        var ss = StrategySum[infoset];
        for (int a = 0; a < Kuhn.NUM_ACTIONS; a++) ss[a] += reach[player] * strategy[a];

        return nodeUtil;
    }

    // Toutes les distributions de cartes (J1, J2) avec 3 cartes distinctes.
    static readonly int[][] CardPermutations = {
        new[]{0,1}, new[]{0,2}, new[]{1,0}, new[]{1,2}, new[]{2,0}, new[]{2,1}
    };

    public virtual double Train(int iterations)
    {
        double totalAvg = 0;
        for (int i = 0; i < iterations; i++)
        {
            double totalUtil = 0;
            foreach (var cards in CardPermutations)
                totalUtil += Cfr("", cards, new double[]{ 1.0, 1.0 })[0];
            totalAvg += totalUtil / CardPermutations.Length;
            Iterations++;
        }
        return totalAvg / iterations;
    }
}

"Solveur CFR vanilla (Kuhn Poker) pret.".Display();

Solveur CFR vanilla (Kuhn Poker) pret.

3.1 Entrainement et valeur du jeu

On entraine CFR sur un grand nombre d’itérations. La valeur du jeu (utilité moyenne par coup pour J1) converge vers la valeur de Nash : Kuhn (1950) a demontre que cette valeur vaut \(-1/18 \approx -0{,}0556\) pour le joueur 1 (leger desavantage du premier joueur).

var solver = new CFRSolver();
int N = 20000;
double gameValue = solver.Train(N);
$"Entrainement CFR vanilla sur Kuhn Poker ({N} iterations).".Display();
$"Valeur du jeu pour J1 = {gameValue:F4}    (valeur de Nash theorique = {-1.0/18.0:F4})".Display();
$"Iterations executees : {solver.Iterations}".Display();

Entrainement CFR vanilla sur Kuhn Poker (20000 iterations).

Valeur du jeu pour J1 = -0,0565    (valeur de Nash theorique = -0,0556)

Iterations executees : 20000

Lecture chiffree — la valeur approchee a 9 dix-milliemes. Apres 20000 iterations, la sortie mesure Valeur du jeu pour J1 = -0,0565 contre la reference valeur de Nash theorique = -0,0556 (\(-1/18\)). L’ecart vaut \(|{-0{,}0565} - (-0{,}0556)| = 0{,}0009\) : CFR n’atteint pas Nash, il l’approche — a moins d’un millieme d’utilite par coup. Deux lectures utiles de ce seul nombre : le signe negatif confirme le leger desavantage du premier joueur pose par Kuhn (1950) ; et la taille de l’ecart servira d’etalon a la section suivante, ou CFR+ sera mesure sur le meme criterium.

3.2 Stratégies apprises (stratégie moyenne)

La stratégie moyenne converge vers un équilibre de Nash. Pour Kuhn Poker, on s’attend notamment a : le joueur avec le King mise presque toujours ; avec Jack face a une mise, il se couche (King bat Jack a l’abattage) ; les melanges (bluffs avec Jack, value bets avec King) emergent dans les infosets intermediaires.

// Afficher la strategie moyenne de chaque infoset (triee par carte puis historique).
var sb = new StringBuilder();
sb.AppendLine("Strategies Nash apprises par CFR (format : [Pass, Bet]) :");
sb.AppendLine($"{"Infoset",-8} {"Pass",-8} {"Bet",-8}  interpretation");
sb.AppendLine(new string('-', 52));
// Toutes les infosets non-terminales : carte dans {J,Q,K}, historique dans {"", "p", "b", "pb"}.
string[] histories = { "", "p", "pb", "b" };
foreach (var card in new[]{ 0, 1, 2 })
  foreach (var h in histories)
  {
      // ne pas lister les situations impossibles/terminales.
      if (Kuhn.IsTerminal(h)) continue;
      // "pb" n'est atteignable que pour J1 (J1 a passe, J2 a mise) ; "b" que pour J2 (J1 a mise).
      // On garde tout pour simplicite — la strategie d'un infoset jamais atteint reste uniforme.
      string infoset = Kuhn.GetInfoSet(h, card);
      var strat = solver.GetAverageStrategy(infoset);
      string readout = infoset switch
      {
          "K"  => "King : value bet",
          "Jpb" => "Jack face a mise : fold (King bat Jack)",
          _ => ""
      };
      sb.AppendLine($"{infoset,-8} {strat[0],-8:F3} {strat[1],-8:F3}  {readout}");
  }
Show(sb.ToString());

// Verifier deux resultats canoniques.
double[] kStrat = solver.GetAverageStrategy("K");
double[] jpbStrat = solver.GetAverageStrategy("Jpb");
$"Verification : King mise (bet) avec proba ~ {kStrat[1]:F3} (Nash : King value-bet, proba >= 1/3 ; Kuhn 1950 donne une famille d'equilibres).".Display();
$"Verification : Jack face a mise se couche (pass) avec proba ~ {jpbStrat[0]:F3} (Nash : Jack fold face a bet, attendu ~ 1.0).".Display();

Strategies Nash apprises par CFR (format : [Pass, Bet]) :
Infoset  Pass     Bet       interpretation
----------------------------------------------------
J        0,779    0,221     
Jp       0,667    0,333     
Jpb      1,000    0,000     Jack face a mise : fold (King bat Jack)
Jb       1,000    0,000     
Q        1,000    0,000     
Qp       1,000    0,000     
Qpb      0,439    0,561     
Qb       0,659    0,341     
K        0,339    0,661     King : value bet
Kp       0,000    1,000     
Kpb      0,000    1,000     
Kb       0,000    1,000

Verification : King mise (bet) avec proba ~ 0,661 (Nash : King value-bet, proba >= 1/3 ; Kuhn 1950 donne une famille d'equilibres).

Verification : Jack face a mise se couche (pass) avec proba ~ 1,000 (Nash : Jack fold face a bet, attendu ~ 1.0).

Lecture chiffree — la structure de la table des 12 infosets. Trois blocs se lisent carte par carte. Les trois lignes du King sont identiques : Kp, Kpb et Kb affichent toutes 0,000 1,000 — le King mise dans chaque position, la value bet n’a pas d’exception. La Dame a l’oppose ne mise jamais en premier : Q et Qp a 1,000 0,000, et ses mixtes n’apparaissent qu’apres mise adverse (Qpb 0,439 0,561, Qb 0,659 0,341). Le Jack joue les deux tableaux : Jpb 1,000 0,000 (le fold face a mise, signe deja dans la sortie), mais J 0,779 0,221 — un bluf environ une fois sur cinq — et surtout Jp 0,667 0,333, pile deux tiers / un tiers. Les lignes pures et les mixtes se repartissent exactement comme la famille d’equilibres de Kuhn 1950 le predit : strategies pures aux extremites (King mise, Jack passe face a mise), mixtures au milieu, ou le bluff du Jack equilibre la value bet du King.

4. Variante CFR+ (Tammelin 2014)

CFR+ accelere la convergence avec deux modifications : 1. Regrets ecretes : on maintient regret_sum[a] = max(0, regret_sum[a] + cf_reach * regret) (les regrets negatifs sont immediatement remis a zero). 2. Accumulation ponderee : la stratégie est accumulee avec un poids croissant w = t+1 (itérations recentes privilegiees).

CFR+ a ete l’algorithme cle de la resolution du Heads-Up Limit Texas Hold’em (Bowling 2015).

#nullable enable
// CFR+ : variant avec regrets ecretes (Tammelin 2014).
public class CFRPlusSolver : CFRSolver
{
    protected override double[] GetRegret(string infoset)
    {
        if (!RegretSum.ContainsKey(infoset)) RegretSum[infoset] = new double[Kuhn.NUM_ACTIONS];
        return RegretSum[infoset];
    }

    public override double[] Cfr(string history, int[] cards, double[] reach)
    {
        if (Kuhn.IsTerminal(history))
        {
            double p = Kuhn.GetPayoff(history, cards);
            return new double[] { p, -p };
        }
        int player = Kuhn.GetCurrentPlayer(history);
        int opponent = 1 - player;
        string infoset = Kuhn.GetInfoSet(history, cards[player]);
        var strategy = GetStrategy(infoset);

        var childUtil = new double[Kuhn.NUM_ACTIONS][];
        double[] nodeUtil = { 0, 0 };
        for (int a = 0; a < Kuhn.NUM_ACTIONS; a++)
        {
            char ac = a == Kuhn.PASS ? 'p' : 'b';
            var newReach = (double[])reach.Clone();
            newReach[player] *= strategy[a];
            childUtil[a] = Cfr(history + ac, cards, newReach);
            nodeUtil[0] += strategy[a] * childUtil[a][0];
            nodeUtil[1] += strategy[a] * childUtil[a][1];
        }

        // CFR+ : (1) regrets ecretes a chaque mise a jour.
        double cfReach = reach[opponent];
        var rs = GetRegret(infoset);
        for (int a = 0; a < Kuhn.NUM_ACTIONS; a++)
        {
            double regret = childUtil[a][player] - nodeUtil[player];
            rs[a] = Math.Max(0, rs[a] + cfReach * regret);
        }

        // CFR+ : (2) strategie accumulee avec poids croissant w = iterations+1.
        if (!StrategySum.ContainsKey(infoset)) StrategySum[infoset] = new double[Kuhn.NUM_ACTIONS];
        double w = Iterations + 1;
        var ss = StrategySum[infoset];
        for (int a = 0; a < Kuhn.NUM_ACTIONS; a++) ss[a] += w * reach[player] * strategy[a];

        return nodeUtil;
    }
}

var solverPlus = new CFRPlusSolver();
double gvPlus = solverPlus.Train(N);
$"Entrainement CFR+ sur Kuhn Poker ({N} iterations).".Display();
$"Valeur du jeu (CFR+) pour J1 = {gvPlus:F4}    (Nash = {-1.0/18.0:F4})".Display();
$"Convergence CFR vs CFR+ : |valeur - (-1/18)|  vanilla={Math.Abs(gameValue - (-1.0/18.0)):F4}  CFR+={Math.Abs(gvPlus - (-1.0/18.0)):F4}  (CFR+ converge generalement plus vite)".Display();

Entrainement CFR+ sur Kuhn Poker (20000 iterations).

Valeur du jeu (CFR+) pour J1 = -0,0572    (Nash = -0,0556)

Convergence CFR vs CFR+ : |valeur - (-1/18)|  vanilla=0,0009  CFR+=0,0016  (CFR+ converge generalement plus vite)

Lecture chiffree — ce run inverse l’attendu de CFR+. La derniere ligne de la sortie mesure les deux ecarts a Nash : vanilla=0,0009 CFR+=0,0016. Sur CE run de 20000 iterations, le vanilla est deux fois plus proche de \(-1/18\) que CFR+ (-0,0565 contre -0,0572), alors que la parenthese de la sortie meme rappelle que CFR+ converge generalement plus vite. Aucune contradiction : la superiorite de CFR+ est un enonce asymptotique et en moyenne, pas une garantie run par run — ici un seul tirage par variante, sans moyenne sur seeds ni variance affichee. La lecon methodologique vaut pour toutes les cellules de ce notebook : une comparaison d’algorithmes sur un run unique est une indication, jamais un verdict — c’est exactement le multi-seed que les exercices de evaluation exigent ailleurs dans le depot.

5. Visualisation de la convergence

On re-entraine CFR pour quelques paliers d’itérations et on trace la valeur du jeu : elle doit converger vers \(-1/18\). Courbe ASCII (axe horizontal = itérations en echelle log, axe vertical = valeur pour J1).

// Courbe ASCII : valeur du jeu vs iterations (CFR vanilla).
int[] checkpoints = { 10, 30, 100, 300, 1000, 3000, 10000, 30000 };
var pts = new List<(int iter, double val)>();
foreach (var cp in checkpoints)
{
    var s = new CFRSolver();
    double v = s.Train(cp);
    pts.Add((cp, v));
}

double vmin = pts.Min(p => p.val), vmax = pts.Max(p => p.val);
double nash = -1.0 / 18.0;
// elargir un peu l'echelle pour inclure la ligne de Nash.
vmin = Math.Min(vmin, nash) - 0.01; vmax = Math.Max(vmax, nash) + 0.01;
int H = 14, W = 50;
var canvas = new char[H, W];
for (int r = 0; r < H; r++) for (int c = 0; c < W; c++) canvas[r, c] = ' ';

// ligne de Nash (pointille).
int nashCol = -1;
for (int c = 0; c < W; c++)
{
    double frac = (double)c / (W - 1);
    int iter = (int)Math.Round(checkpoints[0] + frac * (checkpoints[^1] - checkpoints[0]));
    // place la colonne la plus proche de Nash sur l'axe vertical
}
// determiner la ligne correspondant a 'nash' sur l'axe vertical
int RowFor(double v) => H - 1 - (int)Math.Round((v - vmin) / (vmax - vmin) * (H - 1));
int nashRow = RowFor(nash);
for (int c = 0; c < W; c++) if (c % 2 == 0) canvas[nashRow, c] = '-';

// points CFR.
for (int i = 0; i < pts.Count; i++)
{
    int c = (int)Math.Round((double)i / (pts.Count - 1) * (W - 1));
    int r = RowFor(pts[i].val);
    if (r >= 0 && r < H && c >= 0 && c < W) canvas[r, c] = '*';
}

var sb2 = new StringBuilder();
sb2.AppendLine($"Convergence CFR : valeur du jeu (J1) vs iterations (ligne '- -' = Nash = {nash:F4})");
for (int r = 0; r < H; r++)
{
    var line = new StringBuilder();
    for (int c = 0; c < W; c++) line.Append(canvas[r, c]);
    double v = vmax - (double)r / (H - 1) * (vmax - vmin);
    sb2.AppendLine($"{v,7:F3} |{line}");
}
sb2.AppendLine($"        +{new string('-', W)}");
sb2.AppendLine($"         iter: {checkpoints[0]} ... {checkpoints[^1]} (log-scale approx)");
Show(sb2.ToString());
$"Convergence constatee : la valeur du jeu se rapproche de la ligne de Nash ({nash:F4}) a mesure que les iterations augmentent.".Display();

Convergence CFR : valeur du jeu (J1) vs iterations (ligne '- -' = Nash = -0,0556)
 -0,009 |                                                  
 -0,016 |*                                                 
 -0,023 |                                                  
 -0,029 |                                                  
 -0,036 |                                                  
 -0,043 |                                                  
 -0,050 |                                                  
 -0,057 |- - - - - - - * - - - - - - * - - -*- - - * - - -*
 -0,064 |                     *                            
 -0,071 |                                                  
 -0,078 |                                                  
 -0,084 |                                                  
 -0,091 |       *                                          
 -0,098 |                                                  
        +--------------------------------------------------
         iter: 10 ... 30000 (log-scale approx)

Convergence constatee : la valeur du jeu se rapproche de la ligne de Nash (-0,0556) a mesure que les iterations augmentent.

Lecture chiffree — oscillation puis plateau sur la ligne de Nash. Les huit paliers (10, 30, 100 … 30000 iterations) dessinent trois regimes. Le depart est trop optimiste : iter 10 vaut -0,016, bien au-dessus de Nash. Le creux suit : iter 30 plonge a -0,091, plus pessimiste que la cible. Le retour : iter 100 remonte a -0,064, puis les cinq derniers paliers — 300 a 30000 — tiennent tous la ligne -0,057, celle ou le tracé place les tirets de Nash. La convergence n’est pas monotone : la valeur traverse la cible en oscillant avant de s’y coller, et la ligne finale -0,057 contre -0,0556 attendu rappelle qu’a convergence affichee il reste l’ecart constant de ~0,0009 mesure plus haut.

6. Exercices

Convention C.1 : les stubs s’executent sans erreur (jamais throw). Remplir le corps, re-exécuter, verifier.

Exercice 1 — Leduc Poker (generalisation a 2 tours)

Implementer un solveur CFR pour Leduc Poker (6 cartes : 3 rangs x 2 couleurs, 2 tours de mise). C’est le deuxième benchmark canonique du poker a information imparfaite après Kuhn.

Indice : etendre le modèle de jeu (historique plus long, plus d’actions legales), garder la récursion CFR identique.

#nullable enable
// Exercice 1 : Leduc Poker (2 tours, 6 cartes). Generalisation de CFR.
// TODO etudiant : modeliser Leduc + lancer CFR.
static double SolveLeduc()
{
    // Indice : nouvelle classe Leduc avec IsTerminal/GetPayoff/GetInfoSet etendus,
    //          reutiliser CFRSolver en parametrant le jeu.
    return 0.0;   // TODO etudiant
}

"Exercice a completer".Display();

Exercice a completer

Exercice 2 — Exploitabilite (best-response)

Coder le calcul de l’exploitabilite d’une stratégie : \(\mathrm{expl}(\sigma) = \frac{1}{2}(\mathrm{BR}_1(\sigma_2) + \mathrm{BR}_2(\sigma_1)) - v(\mathrm{Nash})\), ou \(\mathrm{BR}\) est la meilleure reponse. Une stratégie proche de Nash a une exploitabilite proche de 0.

Indice : calculer la meilleure reponse d’un joueur face a la stratégie fixee de l’autre, par programmation dynamique sur l’arbre de jeu.

#nullable enable
// Exercice 2 : exploitabilite d'une strategie CFR.
// TODO etudiant : best-response de chaque joueur, puis moyenne.
static double Exploitability(CFRSolver solver)
{
    // Indice : BR de J1 face a strategy(J2), BR de J2 face a strategy(J1), moyenne - valeur Nash.
    return 0.0;   // TODO etudiant
}

"Exercice a completer".Display();

Exercice a completer

Exercice 3 — External Sampling MCCFR

Les variantes Monte Carlo CFR echantillonnent les actions plutot que de tout parcourir. Implementer External Sampling : on echantillonne les actions de l’adversaire et du hasard, on explore exhaustivement celles du joueur courant.

Indice : dans la récursion, tirer une seule action pour l’adversaire (au lieu de sommer), garder l’exploration complète pour le joueur courant.

#nullable enable
// Exercice 3 : External Sampling MCCFR.
// TODO etudiant : recursion avec echantillonnage des actions adverses.
static double ExternalSamplingCfr()
{
    // Indice : Random.NextDouble pour tirer l'action adverse selon sa strategie courante.
    return 0.0;   // TODO etudiant
}

"Exercice a completer".Display();

Exercice a completer

Conclusion

Ce que vous avez appris

Information imparfaite — contrairement aux jeux d’échecs, le joueur ne connait pas tout l’etat ; les information sets regroupent les situations indistinguables.
Regret Matching — stratégie proportionnelle aux regrets positifs cumules ; converge vers Nash en jeu a somme nulle (demo Pierre-Feuille-Ciseaux).
CFR (Zinkevich 2007) — regret matching applique a chaque infoset via une récursion contrefactuelle (reach probability de l’adversaire). La stratégie moyenne converge vers un epsilon-Nash.
CFR+ (Tammelin 2014) — variant a regrets ecretes qui a permis de résoudre le Heads-Up Limit Texas Hold’em (Bowling 2015).
Valeur du jeu — Kuhn Poker : \(-1/18\) pour J1 (leger desavantage du premier joueur), retrouve par CFR.

Pont avec la version Python

La version Python (GameTheory-13-ImperfectInfo-CFR-Python.ipynb) déroule le même solveur CFR from-scratch (§3-4) et le compare a OpenSpiel (Google DeepMind). Ce twin C# traduit le coeur from-scratch (BCL .NET 9, 0 NuGet) — les internes (récursion contrefactuelle, reach probabilities, accumulation de stratégie moyenne) sont visibles. La comparaison OpenSpiel (Python-only) est desormais RECOVERABLE-LOCAL (reclassification #10459) : la taxonomie bucket-3 (#10382) avait omis l’axe PythonNet (.NET -> Python.Runtime -> pyspiel -> OpenSpiel C++, meme axe que SemanticKernel-09 et que le moteur QuantConnect/Lean). Le pont est démontré et mesuré en annexe §7 (CFR + exploitabilité executés depuis C#) – pythonnet (NuGet) + open_spiel (pip) s’installent sur la machine du worker (regle F). Le from-scratch C# reste la contrepartie legitime (niveau semantic) ; le pont est en plus, jamais a la place (mandat #10382). La ou le Python delegue a OpenSpiel : la ou le Python delegue a OpenSpiel (cellules 28-33 : openspiel_cfr, exploitability, benchmark Leduc), le C# rend visible la mecanique de la recursion contrefactuelle et du regret matching que la lib encapsule.

Parite #4956

Twin de parite legitime (Prong B, niveau semantic) : les deux langages deroulent le solveur CFR from-scratch. La ou Python s’appuie sur OpenSpiel pour la comparaison SOTA (pont PythonNet desormais branche depuis C#, cf. annexe §7 et verdict RECOVERABLE-LOCAL ci-dessus), le C# rend visible la mecanique de la récursion contrefactuelle. Le notebook GameTheory-09-BackwardInduction-Python couvre l’induction a rebours en information complète (point de contraste).

Marathon #4956 (parite .NET <-> Python).

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

La conclusion ci-dessus 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 sur le coeur meme du sujet de ce notebook – le solveur CFR et l’exploitabilité – 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), que l’architecture du moteur de backtesting QuantConnect/Lean, et que l’annexe S10 de GameTheory-17-MultiAgent-RL-CSharp. Aucun port .NET natif n’est requis : pythonnet s’installe par NuGet, open_spiel par pip (règle F).

La cellule ci-dessous invoque le vrai solveur CFR d’OpenSpiel (pyspiel.CFRSolver) sur Kuhn poker depuis C#, itère 100 fois, puis mesure l’exploitabilité de la stratégie moyenne (pyspiel.exploitability) – le même concept que l’Exercice 2 et que la convergence démontrée section 5. 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 Python.Runtime;

// Pont .NET -> CPython -> pyspiel -> OpenSpiel C++ (annexe CFR, #10459).
// pythonnet (NuGet) embarque Python.Runtime ; PYTHONNET_PYDLL (env) pointe vers
// le CPython 3.13 ou open_spiel est installe (pip install open_spiel), defaut 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 solveur CFR d'OpenSpiel (Zinkevich 2007) -- le meme algorithme que le from-scratch section 3.
using (Py.GIL())
{
    dynamic pyspiel = Py.Import("pyspiel");
    dynamic game = pyspiel.load_game("kuhn_poker");
    dynamic cfr = pyspiel.CFRSolver(game);
    for (int i = 0; i < 100; i++) cfr.evaluate_and_update_policy();
    dynamic policy = cfr.average_policy();
    // Exploitabilite de la strategie moyenne (best-response) -- le concept de l'Exercice 2.
    double expl = (double)pyspiel.exploitability(game, policy);
    Console.WriteLine($"CFR(kuhn_poker, 100 iters) : exploitabilite = {expl.ToString("F6", System.Globalization.CultureInfo.InvariantCulture)} (converge vers 0 = Nash)");
}
Console.WriteLine("PONT .NET -> OpenSpiel CFR : OK");

Installed Packages

pythonnet, 3.0.5

Runtime Python : 3.11.15 (main, Mar  3 2026, 09:26:23) [GCC 13.3.0]
CFR(kuhn_poker, 100 iters) : exploitabilite = 0.008226 (converge vers 0 = Nash)
PONT .NET -> OpenSpiel CFR : OK

Retour au sommet