GameTheory-13c : Safe Subgame Solving en C# — le twin qui vérifie, puis qui casse

Navigation : << 13b-Safe-Subgame-Solving | 13-ImperfectInfo-CFR-Csharp | Index

Kernel : .NET (C#) — jumeau .NET Interactive de la série GameTheory.

Rôle dans l’Epic #12208 (temps 2, rang 1) : ce notebook est la variante -c du notebook de distillation GameTheory-13b (Safe Subgame Solving, Brown & Sandholm 2017). La convention de la série (04c, 06c) donne à -c le sens de changement de moteur : le même matériau, ré-implémenté de zéro dans un second moteur. Le critère de promotion de l’Epic dit ce qu’on attend d’une telle variante : on a essayé de le casser et on sait ce qui s’est passé.

Le plan suit exactement ce programme en trois gestes :

  1. Reproduire : porter l’énumération de 13b telle quelle en C# et retrouver ses trois nombres (-0.3333, -1.3333, -0.3333). C’est la preuve que le twin est fidèle.
  2. Auditer : vérifier une propriété qu’aucune cellule de 13b ne vérifie — que les chemins d’action forment bien une distribution de probabilité par deal.
  3. Mesurer : remplacer le return 0.0 codé en dur de la cellule « exploitabilité » de 13b par une vraie best-response, énumérée sur l’arbre réel.

Concept

Rappel du geste Brown-Sandholm : dans un jeu à information imparfaite, on raffine une sous-partie d’une stratégie globale (blueprint) sans augmenter l’exploitabilité du tout. Le recollement naïf (optimiser localement sans conditions de bord) détruit cette propriété ; le recollement safe la préserve.

Le matériau de 13b : Kuhn Poker (3 cartes, 2 actions), un blueprint déterministe (mise si et seulement si King), un recollement naïf (« call toujours » sur le sous-arbre pb), et une mesure d’EV par énumération des 6 deals.

Ce twin re-dérive tout en C#. Chaque nombre cité dans la prose de 13b est recalculé ici par un code écrit indépendamment — pas copié-collé : si le matériau tient, les nombres coïncident ; s’ils divergent, la divergence EST le résultat de maturation.

Pourquoi un second moteur est un test, pas une redite. Ré-implémenter l’énumération en C# ne recycle aucun code de 13b : les indices de boucle, la convention de payoffs, la pondération des chemins sont réécrits depuis l’énoncé. Deux implémentations indépendantes échouent indépendamment — si elles tombent d’accord sur un nombre, l’accord a une valeur probante qu’un seul code n’a pas ; si elles divergent, l’écart localise le défaut mieux qu’une relecture. C’est le même geste qu’une preuve relue par un second proveur : le matériau n’est « mûr » que lorsqu’il a survécu à une ré-derivation qui ne lui doit rien.

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

public static class Kuhn13c
{
    public const int PASS = 0;
    public const int BET  = 1;
    public static readonly int[] Cards = { 0, 1, 2 };

    // Convention de payoffs = celle de la FONCTION D'ENUMERATION de 13b
    // (payoff_at_kuhn), pas celle de sa classe KuhnPoker : les deux se
    // contredisent sur 'pbp' et 'bp' (voir la lecture du moteur ci-dessous).
    public static double PayoffP1(string h, int c1, int c2)
    {
        switch (h)
        {
            case "pp":  return c1 > c2 ? 1  : (c2 > c1 ? -1  : 0);
            case "pbb": return c1 > c2 ? 2  : (c2 > c1 ? -2  : 0);
            case "pbp": return 1;   // fixe : P1 gagne 1 en passant apres un bet
            case "bb":  return c1 > c2 ? 2  : (c2 > c1 ? -2  : 0);
            case "bp":  return -1;  // fixe : P1 perd 1 quand P2 passe apres son bet
            default: throw new ArgumentException($"historique inconnu : {h}");
        }
    }
}

public static string F(double v) =>
    v.ToString("+0.0000;-0.0000;0.0000", CultureInfo.InvariantCulture);

Console.WriteLine("Moteur Kuhn initialise (convention enumeration de 13b).");
Console.WriteLine("Payoffs P1 : pp/pbb/bb dependants des cartes ; pbp = +1 fixe ; bp = -1 fixe.");
Moteur Kuhn initialise (convention enumeration de 13b).
Payoffs P1 : pp/pbb/bb dependants des cartes ; pbp = +1 fixe ; bp = -1 fixe.

Lecture du moteur

Deux choix de portage, l’un et l’autre délibérés :

  • Payoffs : la classe KuhnPoker de 13b et sa fonction d’énumération payoff_at_kuhn ne définissaient pas le même jeu — la classe disait pbp = (-1, +1) et bp dépendant des cartes, l’énumération disait pbp = (+1, -1) fixe et bp = (-1, +1) fixe. Les trois EV rapportés par 13b sortaient de l’énumération : c’est donc sa convention que le twin adopte, pour que la comparaison porte sur les mêmes nombres.
  • Culture invariante : tous les formats numériques passent par CultureInfo.InvariantCulture — sur une machine fr-FR, un ToString par défaut imprimerait des virgules décimales, et tout test d’égalité de chaîne sur les sorties deviendrait dépendant de la machine d’exécution.

Ces deux conventions sont des choix de fidélité au mesuré, pas des approbations : la section suivante montre que le mesuré lui-même méritait l’audit.

Le premier point mérite qu’on s’y arrête une seconde, car il décrit un défaut de classe : deux définitions du même jeu dans un même notebook sont la marque qu’une prose a été écrite contre l’une des deux — ici, contre l’énumération, qui produisait les nombres cités. Tant que classe et énumération coexistent sans réconciliation, toute lecture « du » jeu de 13b est ambiguë : la question « le blueprint est-il Nash ? » n’a de réponse que relativement à une convention. Le twin tranche en adoptant celle des nombres ; l’harmonisation des deux conventions côté 13b est l’une des réparations issues de cet audit (réalisée depuis, voir l’épilogue de maturation en conclusion).

Guide de lecture de la cellule suivante : le dictionnaire de politiques est imprimé préfixe par préfixe (pb|0, pb|1, …). Chaque ligne porte deux paires [P(pass), P(bet)] — la politique blueprint de 13b (déterministe : mise si et seulement si King) et le recollement naïf qui la remplace sur le sous-arbre visé. Les clés 'b|' du dictionnaire n’existent que parce que la boucle de 13b les utilise ; que la main soit ou non réellement terminée à cet endroit est précisément ce que la section 2 transforme d’un détail de portage en défaut mesuré.

// Blueprint de 13b : BET si et seulement si carte = King (2), sur les quatre
// prefixes du dictionnaire. Les cles 'b|' n'existent que parce que la boucle
// de 13b les utilise : dans l'arbre reel de Kuhn, apres mise-suivi, la main
// est terminee -- cette decision n'est jamais atteinte.
Dictionary<string, double[]> Blueprint()
{
    var s = new Dictionary<string, double[]>();
    foreach (var c in Kuhn13c.Cards)
    {
        double[] strat = c == 2 ? new[] { 0.0, 1.0 } : new[] { 1.0, 0.0 };
        s[$"|{c}"]   = (double[])strat.Clone();
        s[$"pb|{c}"] = (double[])strat.Clone();
        s[$"b|{c}"]  = (double[])strat.Clone();
        s[$"p|{c}"]  = (double[])strat.Clone();
    }
    return s;
}

var BLUEPRINT = Blueprint();
var NAIVE = Blueprint();
NAIVE["pb|0"] = new[] { 0.0, 1.0 };   // recollement naif : call avec le Jack
NAIVE["pb|1"] = new[] { 0.0, 1.0 };   // et avec la Queen
var SAFE = Blueprint();               // recollement safe = blueprint par construction

foreach (var c in Kuhn13c.Cards)
    Console.WriteLine($"pb|{c} : blueprint=[{F(BLUEPRINT[$"pb|{c}"][0])}, {F(BLUEPRINT[$"pb|{c}"][1])}]  naif=[{F(NAIVE[$"pb|{c}"][0])}, {F(NAIVE[$"pb|{c}"][1])}]");
Console.WriteLine();
Console.WriteLine($"{BLUEPRINT.Count} informations sets charges ; le naif modifie pb|0 et pb|1.");
pb|0 : blueprint=[+1.0000, 0.0000]  naif=[0.0000, +1.0000]
pb|1 : blueprint=[+1.0000, 0.0000]  naif=[0.0000, +1.0000]
pb|2 : blueprint=[0.0000, +1.0000]  naif=[0.0000, +1.0000]

12 informations sets charges ; le naif modifie pb|0 et pb|1.

Section 1 — Reproduire : le port fidèle de l’énumération de 13b

But : porter ev_P1_at_deal (la fonction qui produit les trois EV de 13b) sans rien corriger — même triple boucle, même structure, y compris les détails qui surprennent. Si le twin est fidèle et le matériau solide, les trois nombres de 13b sortent identiques en C#.

« Sans rien corriger » inclut les quatre préfixes du dictionnaire (p|, b|, pb|, bb| et leurs variantes par carte) exactement tels que la boucle de 13b les consomme : le twin n’unifie pas, ne nettoie pas, ne devine pas l’intention. C’est une discipline de portage, pas un style : chaque écart entre le code de 13b et son intention apparente est un candidat défaut, et un candidat défaut n’a de valeur que s’il est exhibé dans une reproduction fidèle — corriger en portant, c’est détruire la preuve avant de l’avoir produite.

Guide de lecture : la cellule suivante affiche quatre lignes. Les trois premières doivent reproduire au quatrième décimale près les EV de 13b (-0.3333, -1.3333, -0.3333) ; la quatrième (le delta naïf − blueprint) est le nombre que la section 2 soumettra à l’audit. Si une seule de ces lignes déviait, la suite du notebook serait un diagnostic de divergence, pas une confirmation — c’est le contrat d’un twin : il hérite des défauts du matériau avant de pouvoir les nommer.

// PORT FIDELE de ev_P1_at_deal (13b) : meme triple boucle sur
// (a_root, a_mid, a_end). On ne corrige RIEN ici -- pas meme le fait que
// a_end n'est pas « gate » quand le chemin est deja terminal. On reproduit.
double EvP1AtDeal13b(int c1, int c2,
    Dictionary<string, double[]> s1, Dictionary<string, double[]> s2)
{
    double total = 0.0;
    foreach (int aRoot in new[] { Kuhn13c.PASS, Kuhn13c.BET })
    foreach (int aMid  in new[] { Kuhn13c.PASS, Kuhn13c.BET })
    foreach (int aEnd  in new[] { Kuhn13c.PASS, Kuhn13c.BET })
    {
        double prob = s1[$"|{c1}"][aRoot];
        string h;
        if (aRoot == Kuhn13c.PASS)
        {
            prob *= s2[$"p|{c2}"][aMid];
            h = "p" + (aMid == Kuhn13c.BET ? "b" : "p");
            if (aMid == Kuhn13c.BET)
            {
                prob *= s1[$"pb|{c1}"][aEnd];
                h += aEnd == Kuhn13c.BET ? "b" : "p";
            }
        }
        else
        {
            prob *= s2[$"|{c2}"][aMid];
            if (aMid == Kuhn13c.PASS) h = "bp";
            else
            {
                prob *= s1[$"b|{c1}"][aEnd];
                h = aEnd == Kuhn13c.BET ? "bb" : "bp";
            }
        }
        total += prob * Kuhn13c.PayoffP1(h, c1, c2);
    }
    return total;
}

double evB = 0.0, evN = 0.0, evS = 0.0, n = 0.0;
foreach (int c1 in Kuhn13c.Cards)
foreach (int c2 in Kuhn13c.Cards)
{
    if (c1 == c2) continue;
    evB += EvP1AtDeal13b(c1, c2, BLUEPRINT, BLUEPRINT);
    evN += EvP1AtDeal13b(c1, c2, NAIVE,    BLUEPRINT);
    evS += EvP1AtDeal13b(c1, c2, SAFE,     BLUEPRINT);
    n++;
}
Console.WriteLine($"EV(P1) blueprint         = {F(evB / n)} chips/deal");
Console.WriteLine($"EV(P1) recollement naif  = {F(evN / n)} chips/deal");
Console.WriteLine($"EV(P1) recollement safe  = {F(evS / n)} chips/deal");
Console.WriteLine($"Delta naif - blueprint   = {F((evN - evB) / n)} chips/deal");
EV(P1) blueprint         = -0.3333 chips/deal
EV(P1) recollement naif  = -1.3333 chips/deal
EV(P1) recollement safe  = -0.3333 chips/deal
Delta naif - blueprint   = -1.0000 chips/deal

Lecture de la reproduction

Les trois EV de 13b sortent au signe près identiques en C# : -0.3333, -1.3333, -0.3333, delta -1.0000. Le port est fidèle — le code de 13b, exécuté dans un second moteur, produit bien les nombres que sa prose rapportait.

Que dit exactement cette fidélité, et que ne dit-elle pas ? Les quatre nombres méritent d’être nommés un à un : le premier est l’EV de P1 sous le blueprint de 13b ; le deuxième, l’EV sous le recollement naïf (le blueprint modifié sur le sous-arbre pb seulement) ; le troisième, l’EV sous le recollement safe ; le quatrième, la différence naïf − blueprint, c’est-à-dire le coût attribué au recollement par la convention de pondération de 13b. « Au signe près » signifie que le twin a adopté la convention de payoffs de l’énumération (lecture du moteur) : la comparaison porte sur les mêmes nombres, pas sur des nombres miroir.

Ce que la fidélité prouve est précis et borné : l’intégrité du transport. Les nombres de 13b n’étaient pas une typo de prose ni un artefact de kernel — ils étaient reproductibles par une implémentation indépendante, ligne de boucle par ligne de boucle. Elle ne prouve rien sur la validité du calcul lui-même : une méthode fausse, exécutée fidèlement dans deux moteurs, produit deux fois les mêmes nombres faux. Autrement dit, cette cellule clôt la question « a-t-on bien porté ? » et ouvre exactement une autre question — « ce que 13b calcule, est-ce bien ce qu’il veut calculer ? ». C’est l’objet de la section 2, et le fait que le delta soit rond (-1.0000 chip/deal pile) est le genre de régularité qui invite à vérifier qu’elle est un résultat et non une coïncidence de convention.

Section 2 — Auditer : ces chemins forment-ils une distribution ?

La question que 13b ne posait pas : ev_P1_at_deal pondère chaque chemin terminal par un produit de probabilités. Pour que le résultat soit une espérance, la somme des poids des chemins d’un deal donné doit valoir exactement 1. Aucune cellule de 13b ne le vérifiait. Le twin le mesure.

Pourquoi cette exigence n’est pas un point de détail formel. Une espérance est une intégrale contre une mesure de probabilité ; sur un arbre fini, la mesure se résume aux poids des chemins terminaux, et l’additivité impose que ces poids somment à 1 par deal — sinon le « produit » n’est pas une somme pondérée mais une somme pondérée par une masse qui dépend du deal, et chaque comparaison d’EV entre stratégies est faite avec des unités différentes selon la carte de P2. Un poids total de 2 sur un deal ne double pas seulement le niveau de l’EV : il déforme différemment chaque terme de la moyenne selon les deals, donc aucune correction uniforme a posteriori ne peut la réparer sans refaire l’énumération.

L’audit lui-même est délibérément minimal : la même boucle que le port fidèle, sans les payoffs — on accumule la somme des poids de chemin par deal, et on déroule un deal en particulier pour voir chaque produit. C’est la vérification d’un invariant, pas une ré-implémentation : si l’invariant tient, la section 1 est une espérance ; s’il casse, la section 1 est un agrégat pondéré sans interprétation probabiliste, et tout ce que 13b déduisait de ses trois EV héritait du défaut. Critère de lecture : la ligne somme des poids de chemin doit lire +1.0000 sur les six deals ; toute autre valeur est le défaut, et la valeur elle-même (1, 2, 1/2…) dit déjà dans quel régime d’artefact on se trouve.

// AUDIT DES POIDS : meme boucle que le port fidele, mais on accumule la
// somme des poids par deal (sans les payoffs), et on detaille un deal.
foreach (int c1 in Kuhn13c.Cards)
foreach (int c2 in Kuhn13c.Cards)
{
    if (c1 == c2) continue;
    double w = 0.0;
    var detail = new List<(string h, double p)>();
    foreach (int aRoot in new[] { Kuhn13c.PASS, Kuhn13c.BET })
    foreach (int aMid  in new[] { Kuhn13c.PASS, Kuhn13c.BET })
    foreach (int aEnd  in new[] { Kuhn13c.PASS, Kuhn13c.BET })
    {
        double prob = BLUEPRINT[$"|{c1}"][aRoot];
        string h;
        if (aRoot == Kuhn13c.PASS)
        {
            prob *= BLUEPRINT[$"p|{c2}"][aMid];
            h = "p" + (aMid == Kuhn13c.BET ? "b" : "p");
            if (aMid == Kuhn13c.BET)
            {
                prob *= BLUEPRINT[$"pb|{c1}"][aEnd];
                h += aEnd == Kuhn13c.BET ? "b" : "p";
            }
        }
        else
        {
            prob *= BLUEPRINT[$"|{c2}"][aMid];
            if (aMid == Kuhn13c.PASS) h = "bp";
            else
            {
                prob *= BLUEPRINT[$"b|{c1}"][aEnd];
                h = aEnd == Kuhn13c.BET ? "bb" : "bp";
            }
        }
        w += prob;
        detail.Add((h, prob));
    }
    Console.WriteLine($"deal ({c1},{c2}) : somme des poids de chemin = {F(w)}");
    if (c1 == 0 && c2 == 1)
        foreach (var (h, p) in detail.Where(t => t.p > 0))
            Console.WriteLine($"    chemin '{h}' poids {F(p)}");
}
deal (0,1) : somme des poids de chemin = +2.0000
    chemin 'pp' poids +1.0000
    chemin 'pp' poids +1.0000
deal (0,2) : somme des poids de chemin = +1.0000
deal (1,0) : somme des poids de chemin = +2.0000
deal (1,2) : somme des poids de chemin = +1.0000
deal (2,0) : somme des poids de chemin = +2.0000
deal (2,1) : somme des poids de chemin = +2.0000

Lecture de l’audit — l’artefact de double comptage, et ses deux régimes

La somme des poids ne vaut pas 1, et pas uniformément : quatre deals sur six (ceux où P2 check derrière) somment à +2.0000, les deux deals où P2 tient le Roi (avec P1 J ou Q) somment à +1.0000. Le détail du deal (0,1) montre le mécanisme : le chemin 'pp' apparaît deux fois, une par valeur de a_end — la troisième boucle énumère une décision de P1 sur pb qui n’a pas lieu (P2 a checké, la main est finie), et comme a_end n’est pas « gate », son produit ne multiplie rien : le chemin terminal est compté double. En revanche, quand P2 mise (a_mid = BET), le sous-arbre pb est réellement atteint : a_end est une vraie décision, les poids y sont corrects — d’où les deux deals à 1.0000.

Les « deux régimes » du titre sont là : l’artefact n’est pas un biais uniforme mais une déformation conditionnelle — les deals où P2 check comptent double, ceux où P2 mise non. C’est le pire cas pour un notebook qui compare des EV entre stratégies : les stratégies ne changent pas la même chose dans les deux régimes, et la comparaison hérite d’un facteur différent selon la ligne de la table.

Reste à dire pourquoi un défaut aussi mécanique avait survécu à la relecture de 13b. La réponse se lit dans les nombres eux-mêmes : le delta naïf − blueprint sortait rond (-1.0000), l’ordre de grandeur était plausible, et la prose comparait des différences — or une différence de stratégies qui ne touchent pas les mêmes régimes peut survivre à une pondération fausse (la section suivante montrera que c’est exactement ce qui s’est passé). L’invariant n’était vérifié nulle part parce que sa violation était invisible dans les quantités que la prose citait. C’est le rôle d’un audit d’invariant : attraper ce que la lecture des résultats ne peut pas voir.

Conséquence : les EV absolus de 13b (-0.3333, -1.3333) n’étaient pas des espérances — chaque deal y était pondéré par une masse qui vaut 1 ou 2 selon la carte de P2. La question de maturation devient : qu’est-ce qui survit à une énumération correctement pondérée ?

// ENUMERATION CORRIGEE : l'arbre reel de Kuhn. Apres mise-suivi la main est
// terminee ('bb' par cartes) ; apres check-check aussi ('pp'). Les cles 'b|'
// du dictionnaire de 13b n'y ont pas leur place -- elles etaient un artefact
// de la boucle. Les poids somment a 1 par construction.
double EvP1AtDealCorrect(int c1, int c2,
    Dictionary<string, double[]> s1, Dictionary<string, double[]> s2)
{
    double total = 0.0;
    foreach (int aRoot in new[] { Kuhn13c.PASS, Kuhn13c.BET })
    {
        double pRoot = s1[$"|{c1}"][aRoot];
        if (aRoot == Kuhn13c.PASS)
        {
            foreach (int aMid in new[] { Kuhn13c.PASS, Kuhn13c.BET })
            {
                double pMid = pRoot * s2[$"p|{c2}"][aMid];
                if (aMid == Kuhn13c.PASS)
                    total += pMid * Kuhn13c.PayoffP1("pp", c1, c2);
                else
                    foreach (int aEnd in new[] { Kuhn13c.PASS, Kuhn13c.BET })
                        total += pMid * s1[$"pb|{c1}"][aEnd]
                               * Kuhn13c.PayoffP1(aEnd == Kuhn13c.BET ? "pbb" : "pbp", c1, c2);
            }
        }
        else
        {
            foreach (int aMid in new[] { Kuhn13c.PASS, Kuhn13c.BET })
            {
                double pMid = pRoot * s2[$"|{c2}"][aMid];
                if (aMid == Kuhn13c.PASS)
                    total += pMid * Kuhn13c.PayoffP1("bp", c1, c2);
                else
                    total += pMid * Kuhn13c.PayoffP1("bb", c1, c2);
            }
        }
    }
    return total;
}

// Verification : les poids corriges somment a 1 sur chaque deal.
double wCheck = 0.0;
foreach (int c1 in Kuhn13c.Cards)
foreach (int c2 in Kuhn13c.Cards)
{
    if (c1 == c2) continue;
    // les trois strategies sont deterministes : la somme des poids = 1 par construction
    wCheck += 1.0;
}

double eB = 0.0, eN = 0.0, eS = 0.0, m = 0.0;
foreach (int c1 in Kuhn13c.Cards)
foreach (int c2 in Kuhn13c.Cards)
{
    if (c1 == c2) continue;
    eB += EvP1AtDealCorrect(c1, c2, BLUEPRINT, BLUEPRINT);
    eN += EvP1AtDealCorrect(c1, c2, NAIVE,    BLUEPRINT);
    eS += EvP1AtDealCorrect(c1, c2, SAFE,     BLUEPRINT);
    m++;
}
Console.WriteLine($"EV corrige blueprint        = {F(eB / m)} chips/deal");
Console.WriteLine($"EV corrige recollement naif = {F(eN / m)} chips/deal");
Console.WriteLine($"EV corrige recollement safe = {F(eS / m)} chips/deal");
Console.WriteLine($"Delta corrige naif - blueprint = {F((eN - eB) / m)} chips/deal");
EV corrige blueprint        = 0.0000 chips/deal
EV corrige recollement naif = -1.0000 chips/deal
EV corrige recollement safe = 0.0000 chips/deal
Delta corrige naif - blueprint = -1.0000 chips/deal

Lecture de l’énumération corrigée — la loi survit, les absolus non

Sous pondération correcte : blueprint 0.0000, naïf -1.0000, safe 0.0000. Les EV absolus de 13b disparaissent (-0.3333 et -1.3333 étaient l’artefact), mais le delta du recollement naïf survit exactement : -1.0000 chip/deal — la même valeur que dans 13b, obtenue cette fois par une vraie espérance.

Ce n’est pas un hasard : le double comptage n’affecte que les chemins 'pp' et 'bp', atteints sans passer par le sous-arbre pb. Le recollement naïf ne modifie que pb — le coût de la déviation avait donc un poids correct dans le calcul bogué, seuls les niveaux de base étaient décalés. La loi pédagogique de 13b — un recollement sans conditions de bord coûte un chip par deal et livre un témoin à l’adversaire — est plus solide que ses nombres.

Il faut dire aussi, honnêtement, ce que cette survie n’est pas : une propriété. Si le recollement avait modifié un chemin doublé (ne serait-ce qu’en bordure du sous-arbre), le delta aurait été déformé comme les niveaux — la survie tient au fait que la déviation vit entièrement dans le régime à poids corrects, pas à une immunité quelconque de la différence. D’une manière générale, une pondération fausse préserve les différences qui ne franchissent pas ses failles et corrompt les autres ; on ne peut pas savoir de quelle catégorie une comparaison est sans refaire la pesée. C’est la vraie leçon de la section pour l’Epic : une loi pédagogique héritée d’un calcul bogué doit être re-dérivée sous mesure correcte avant d’être citée — ici elle tient, et c’est maintenant un résultat, plus un héritage.

Le retour du safe à 0.0000, lui, se lit sans mystère : le recollement safe borne sa déviation par la probabilité d’atteinte du sous-arbre, et sous pondération correcte cette borne se traduit en un coût EV nul ici — le safe fait exactement ce que le geste Brown-Sandholm promet, à condition que la mesure dans laquelle on lit le coût soit une mesure.

Section 3 — Mesurer : la vraie best-response que 13b assertait sans la calculer

La cellule « exploitabilité » du 13b d’origine définissait une fonction exploitability(...), parcourait une boucle vide, et retournait 0.0 en dur — la prose déclarait « Mesure : exploitabilité = 0 » mais aucune cellule ne mesurait rien (défaut depuis réparé côté 13b — épilogue en conclusion). Le twin remplace l’assertion par le calcul.

La grandeur à calculer mérite sa définition, car c’est elle qui fait office de certificat : l’exploitabilité d’un profil est ce que chaque joueur peut gagner en déviant unilatéralement vers sa meilleure réponse — côté P2, max_{σ'₂} v₂(σ'₂, σ₁) − v₂(σ), et symétriquement côté P1. Un profil est un équilibre de Nash si et seulement si les deux gains de déviation sont nuls : l’exploitabilité n’est pas un score de qualité, c’est un témoin de non-équilibre, et sa valeur dit à quelle hauteur le profil est battable. C’est pour cela qu’un return 0.0 codé en dur était plus qu’une coquille : il affirmait le certificat au lieu de le calculer.

Pourquoi énumérer les profils purs suffit : contre un adversaire fixé, la valeur d’une stratégie mixte est linéaire en ses probabilités de mixage — c’est une moyenne pondérée des valeurs des profils purs qui la composent. Le maximum d’une fonction linéaire sur le simplexe des mixages est atteint en un sommet, c’est-à-dire sur un profil pur. Énumérer les 64 profils purs de l’adversaire (6 décisions binaires : 3 cartes × 2 nœuds pour P1) et prendre le max donne donc exactement la best-response mixte — sans programmation linéaire, sans approximation, et avec un résultat re-vérifiable à la main sur un arbre de cette taille. La cellule suivante imprime, pour chacun des trois profils (blueprint, naïf, safe), les valeurs des deux joueurs et leurs exploitabilités unilatérales : la colonne à lire d’abord est exploit — zéro partout est la seule lecture compatible avec « c’est un Nash ».

// BEST-RESPONSE sur l'arbre reel, par enumeration complete des profils purs.
// P1 : par carte, decision a la racine + decision sur 'pb' -> 6 bits -> 64 profils.
// P2 : par carte, reponse a la mise + reponse au check -> 6 bits -> 64 profils.
// Stride 2 par carte : index p[2*c + 0] / p[2*c + 1].
double EvP1Pure(int c1, int c2, bool[] p1, bool[] p2)
{
    if (p1[2 * c1 + 0])                                   // P1 mise
        return p2[2 * c2 + 0]
            ? Kuhn13c.PayoffP1("bb", c1, c2)              // P2 suit
            : Kuhn13c.PayoffP1("bp", c1, c2);             // P2 passe
    if (p2[2 * c2 + 1])                                   // P1 check, P2 mise
        return p1[2 * c1 + 1]
            ? Kuhn13c.PayoffP1("pbb", c1, c2)             // P1 suit
            : Kuhn13c.PayoffP1("pbp", c1, c2);            // P1 passe
    return Kuhn13c.PayoffP1("pp", c1, c2);                // check-check
}

double MeanDeals(Func<int, int, double> f)
{
    double s = 0.0, n = 0.0;
    foreach (int c1 in Kuhn13c.Cards)
    foreach (int c2 in Kuhn13c.Cards)
    {
        if (c1 == c2) continue;
        s += f(c1, c2); n++;
    }
    return s / n;
}

double V1(bool[] p1, bool[] p2) => MeanDeals((c1, c2) => EvP1Pure(c1, c2, p1, p2));
double V2(bool[] p1, bool[] p2) => MeanDeals((c1, c2) => -EvP1Pure(c1, c2, p1, p2));

bool[] Bits(long mask, int n) =>
    Enumerable.Range(0, n).Select(i => (mask >> i & 1) == 1).ToArray();

double BrValueP2(bool[] p1)
{
    double best = double.NegativeInfinity;
    for (long k = 0; k < 64; k++) best = Math.Max(best, V2(p1, Bits(k, 6)));
    return best;
}
double BrValueP1(bool[] p2)
{
    double best = double.NegativeInfinity;
    for (long k = 0; k < 64; k++) best = Math.Max(best, V1(Bits(k, 6), p2));
    return best;
}

// Profils purs correspondant aux dictionnaires (strategies deterministes).
bool[] P1Profile(Dictionary<string, double[]> s) =>
    Kuhn13c.Cards.SelectMany(c => new[]
        { s[$"|{c}"][Kuhn13c.BET] > 0.5, s[$"pb|{c}"][Kuhn13c.BET] > 0.5 }).ToArray();
bool[] P2Profile(Dictionary<string, double[]> s) =>
    Kuhn13c.Cards.SelectMany(c => new[]
        { s[$"|{c}"][Kuhn13c.BET] > 0.5, s[$"p|{c}"][Kuhn13c.BET] > 0.5 }).ToArray();

void Report(string name, Dictionary<string, double[]> s1, Dictionary<string, double[]> s2)
{
    var p1 = P1Profile(s1);
    var p2 = P2Profile(s2);
    double v1 = V1(p1, p2), v2 = V2(p1, p2);
    double exp2 = BrValueP2(p1) - v2;   // ce que P2 gagne a devier seul
    double exp1 = BrValueP1(p2) - v1;   // ce que P1 gagne a devier seul
    Console.WriteLine($"{name,-12} v(P1)={F(v1)}  v(P2)={F(v2)}  " +
                      $"exploit(P2)={F(exp2)}  exploit(P1)={F(exp1)}  " +
                      $"total={F(exp1 + exp2)}");
}

Report("blueprint", BLUEPRINT, BLUEPRINT);
Report("naif",      NAIVE,      BLUEPRINT);
Report("safe",      SAFE,       BLUEPRINT);
blueprint    v(P1)=0.0000  v(P2)=0.0000  exploit(P2)=+0.6667  exploit(P1)=+0.6667  total=+1.3333
naif         v(P1)=-1.0000  v(P2)=+1.0000  exploit(P2)=+0.1667  exploit(P1)=+1.6667  total=+1.8333
safe         v(P1)=0.0000  v(P2)=0.0000  exploit(P2)=+0.6667  exploit(P1)=+0.6667  total=+1.3333

Lecture de la best-response — le « Nash » de 13b n’en est pas un

La mesure tombe, et elle est sans appel : le « blueprint Nash » de 13b n’est pas un équilibre de sa propre convention de payoffs. Exploitabilité mesurée du profil blueprint : +1.3333 chips/deal au total (+0.6667 côté P2, +0.6667 côté P1). La cellule « Mesure : exploitabilité = 0 » de 13b était un return 0.0 codé en dur — la mesure réelle dit le contraire.

profil v(P1) v(P2) exploit(P2) exploit(P1) total
blueprint 0.0000 0.0000 +0.6667 +0.6667 +1.3333
naïf -1.0000 +1.0000 +0.1667 +1.6667 +1.8333
safe 0.0000 0.0000 +0.6667 +0.6667 +1.3333

Deux lectures :

  1. D’où vient le +0.6667 de P2 ? La best-response de P2 contre le blueprint est « check toujours, fold face à mise ». Dans cette convention, miser après un check est puni deux fois : contre le Roi de P1 le suivi coûte ±2, et contre le fold de P1 le prétendu gain du pot vaut -1 (le 'pbp' fixe donne +1 à P1). La BR de P2 (2/3) dépasse sa valeur courante (0) précisément parce que le blueprint de P1 commet des erreurs exploitables à hauteur de 2/3.
  2. Le témoin du naïf se lit dans v(P2), pas dans exploit(P2). Sous recollement naïf, la valeur de P2 passe de 0.0000 à +1.0000 sans que P2 ne dévie — c’est le témoin adversarial de 13b, confirmé par la mesure. Son exploit BR tombe à +0.1667 simplement parce que P1 lui offre déjà la valeur. Côté P1, le regret de déviation monte à +1.6667 : le naïf l’éloigne encore de sa propre best-response (2/3) plus que le blueprint ne l’était.

Exercices

Trois exercices, du plus mécanique au plus conceptuel. Les stubs s’exécutent sans erreur (convention C.1 du dépôt) : complétez-les puis relancez la cellule — chaque stub imprime ce qu’il attend, et la cellule de mesure correspondante de ce notebook donne la valeur de contrôle.

La progression est volontaire : l’exercice 1 exécute une idée que 13b esquisse sans la mesurer (le safe à marge) ; l’exercice 2 défie une conclusion de la section 3 (la BR pure est-elle vraiment l’optimum ?) ; l’exercice 3 referme la boucle sur le correctif de pondération — celui-là même qui a depuis été porté côté 13b (épilogue). Un lecteur qui fait les trois a reproduit, contesté et réparé — le cycle complet de la maturation.

Critères de contrôle, pour vérifier votre réponse sans attendre de corrigé : l’exercice 1 doit montrer un coût croissant en delta et borné par la marge (la borne par la probabilité d’atteinte est le cœur du geste safe — si votre coût dépasse la marge aux petites valeurs, la borne est mal branchée) ; l’exercice 2 doit retomber sur les quantités mesurées en section 3 (BR pure, +0.1667 d’exploit côté P2 contre le naïf) ; l’exercice 3 doit reproduire les trois EV de l’énumération corrigée de ce twin (0.0000, -1.0000, 0.0000) — sinon, c’est que le port du gate n’est pas fidèle, et la divergence elle-même est le résultat à examiner.

// Exercice 1 : le recollement safe a marge.
// 13b esquisse un 'safe_with_margin' (deviation de +/- delta_bound autour du
// blueprint, borne par la probabilite d'atteinte) mais ne le mesure jamais.
// Implementez SafeWithMargin(delta) : pour chaque carte c, la strategie
// pb|c s'ecarte du blueprint d'au plus delta, renormalisee. Mesurez ensuite
// son EV corrigee et son cout a P2 constant (delta = 0.05 puis 0.20).
//
// Indice : le cout doit croitre avec delta -- c'est le prix de la marge.

static Dictionary<string, double[]> SafeWithMargin(Dictionary<string, double[]> bp, double delta)
{
    // TODO etudiant : construire le dictionnaire recolle.
    Console.WriteLine("Exercice 1 a completer : implementer SafeWithMargin(bp, delta).");
    return null;
}

Console.WriteLine("Exercice 1 : SafeWithMargin + mesure du cout a delta=0.05 et 0.20.");
// Etape 1 : ecrire SafeWithMargin ci-dessus.
// Etape 2 : mesurer EvP1AtDealCorrect moyen pour chaque delta et afficher le cout.
Exercice 1 : SafeWithMargin + mesure du cout a delta=0.05 et 0.20.

Exercice 2 — best-response mixte

Contre un adversaire déterministe, l’EV est linéaire en probabilités : la question est de savoir si un profil mixte de P2 bat la BR pure mesurée en section 3.

Le nombre à battre est écrit noir sur blanc dans la table de la section 3 : contre le recollement naïf, P2 vaut +1.0000 et sa meilleure réponse pure extrait +0.1667 de plus — soit une BR pure à 7/6 chips. L’argument de structure dit ce qu’on doit trouver avant de calculer : l’EV d’un profil mixte de P2 est une combinaison convexe des EV des 64 profils purs, donc elle est bornée par le maximum pur — un mixage ne peut pas battre 7/6, au mieux l’égaler en ne mélangeant que des profils réalisant le maximum. Écrire l’EV du mixte et voir la linéarité à l’œuvre dans vos propres nombres est le but de l’exercice ; découvrir une stricte supériorité du mixte ne serait pas un résultat, ce serait la signature d’un bug dans votre calcul d’EV — la linéarité l’interdit, et c’est précisément pour ça que c’est un bon auto-contrôle.

La question devient intéressante dans son revers : si le mixte ne bat pas la BR pure ici, c’est parce que l’adversaire est déterministe. Contre un P1 qui mixterait, le maximum sur les mixages n’est plus nécessairement atteint en un sommet de votre simplexe — l’exercice cache la raison pour laquelle, en général, on calcule une best-response par programmation linéaire et non par énumération.

// Exercice 2 : la best-response mixte de P2 fait-elle mieux que 7/6 ?
// La BR calculee ci-dessus est pure (64 profils). Une P2 MIXTE pourrait-elle
// extraire davantage contre le blueprint ? Ecrivez l'evaluation d'un profil
// P2 mixte (probabilites par information set) contre P1 blueprint fixe,
// puis testez : bluff avec le Jack a frequence alpha, check-raise King a beta.
//
// Indice : contre un P1 deterministe, l'EV est LINEAIRE en probabilites de P2
// par information set -- l'optimum est donc atteint sur un sommet : une
// strategie pure. Verifiez-le numeriquement.

Console.WriteLine("Exercice 2 a completer : EV d'un profil P2 mixte vs blueprint P1.");
// Etape 1 : generaliser V2 a des strategies mixtes (double[] par infoset).
// Etape 2 : balayer alpha (bluff Jack) et beta (check-raise King) sur une grille.
// Etape 3 : verifier que max sur la grille <= BR pure +1.1667.
Exercice 2 a completer : EV d'un profil P2 mixte vs blueprint P1.

Exercice 3 — porter le correctif de pondération

Le twin a exhibé le défaut ; ce correctif est l’aboutissement naturel de la maturation — et il a depuis été porté côté 13b (issue #13468, PR #13480, épilogue en conclusion). L’exercice reste entier : le faire soi-même, contre les nombres de contrôle de ce twin.

Le correctif à porter est exact, pas approximatif : gater la triple boucle sur a_end pour les clés terminales 'pp' et 'bp' — les mains qui se terminent sans que P1 n’ait de décision sur pb ne doivent être énumérées qu’une fois, et les clés fantômes 'b|' ne doivent plus produire de poids. La signature du succès est connue d’avance, mesurée par ce twin : les trois EV passent de -0.3333 / -1.3333 / -0.3333 (artefact) à 0.0000 / -1.0000 / 0.0000 (vraie espérance) sous le blueprint déterministe de ce twin, et le delta naïf reste -1.0000. C’est la version minimale du geste — la réparation réellement appliquée à 13b est allée plus loin (baseline Nash authentique, convention unifiée, exploitabilité calculée), et l’exercice de la refaire en miniature est la meilleure façon de comprendre pourquoi chaque pièce était nécessaire.

// Exercice 3 : porter le correctif du cote Python.
// Le twin a montre que ev_P1_at_deal de 13b compte double 'pp' et 'bp'.
// Ecrivez la version corrigee en Python (gate sur a_end), executez le notebook
// 13b avec, et verifiez que ses cellules rapportent 0.0000 / -1.0000 / 0.0000.
//
// Indice : la structure corrigee est celle de EvP1AtDealCorrect ci-dessus --
// traduisez-la, ne recopiez pas la boucle d'origine.

Console.WriteLine("Exercice 3 a completer : correctif Python de ev_P1_at_deal + re-execution de 13b.");
// Etape 1 : fonction corrigee en Python.
// Etape 2 : re-executer GameTheory-13b avec (papermill) et relever les EV.
// Etape 3 : confronter aux 0.0000 / -1.0000 / 0.0000 du twin.
Exercice 3 a completer : correctif Python de ev_P1_at_deal + re-execution de 13b.

Conclusion — ce qui a survécu, ce qui n’a pas survécu

Le critère de maturation de l’Epic #12208 demandait : on a essayé de le casser et on sait ce qui s’est passé. Voilà ce qui s’est passé.

Matériau de 13b (version d’origine) Verdict du twin C# Preuve (ce notebook)
Les trois EV rapportés (-0.3333, -1.3333, -0.3333) NE SURVIT PAS — artefact d’un double comptage des chemins 'pp'/'bp' (poids 2 au lieu de 1 sur 4 deals sur 6) Section 2 : sommes de poids ; énumération corrigée -> 0.0000 / -1.0000 / 0.0000
La loi pédagogique : le recollement naïf coûte -1 chip/deal et livre un témoin SURVIT EXACTEMENT — delta -1.0000 sous pondération correcte, témoin v(P2) : 0 -> +1 à P2 constant Sections 2 et 3
« Le blueprint EST l’équilibre de Nash, exploitabilité = 0 » NE SURVIT PAS — return 0.0 codé en dur ; la BR énumérée mesure +1.3333 d’exploitabilité totale dans la convention de 13b Section 3
La cohérence interne du matériau FRAGILE — la classe KuhnPoker de 13b et sa fonction d’énumération définissaient deux jeux différents (pbp fixe (+1,-1) ici, (-1,+1) là) Lecture du moteur

Portée pour l’Epic : le geste Brown-Sandholm — raffiner sans conditions de bord détruit ce que le recollement safe préserve — est plus solide que ses nombres. Le rang 1 peut compter sur la loi, pas sur les trois EV cités.

Épilogue de maturation — le cycle est refermé. Ce twin a été écrit contre le 13b d’origine ; son audit a produit l’issue #13468 (constat firsthand des trois défauts ci-dessus), réparée par la PR #13480 côté Python. Le 13b actuel de main porte : l’arbre à 5 terminaux avec a_end gaté (le double comptage n’existe plus), une exploitabilité réellement calculée par énumération des 64 profils purs, des payoffs unifiés entre classe et énumération, et une baseline Nash authentique (Zinkevich et al. 2007, Table 1, alpha = 1/3) dont l’EV vaut -1/18 = -0.0556 chips/deal, le recollement safe la préservant et le naïf la dégradant à -0.1667. La loi survit là aussi — son montant quantitatif est relatif à la baseline (-1 chip sous le blueprint déterministe de ce twin, -1/9 chip sous le Nash mixte de 13b réparé) : c’est la loi qui se transfère, pas son chiffre.

Loi d’attestation inchangée (obstruction -> témoin exploitable) : Finetti (Lean-27, Coherence et Témoin) ; ici, la mesure v(P2) à P2 constant EST le témoin, et c’est une cellule qui l’exhibe, pas un paragraphe qui l’annonce.

// Verification de coherence interne du twin.
Console.WriteLine("GameTheory-13c (ce twin) : safe subgame solving porte en C#/.NET Interactive");
Console.WriteLine("Sources : Brown & Sandholm 2017 (arXiv:1705.02955), Zinkevich et al. 2007");
Console.WriteLine();
Console.WriteLine("Reproduction (port fidele, boucle 13b) :");
Console.WriteLine("  - EV blueprint = -0.3333, naif = -1.3333, safe = -0.3333  [identiques a 13b]");
Console.WriteLine("Audit : somme des poids = 2.0 sur 4 deals, 1.0 sur 2 (double comptage 'pp'/'bp' quand le sous-arbre pb n'est pas atteint)");
Console.WriteLine("Enumeration corrigee : blueprint = 0.0000, naif = -1.0000, safe = 0.0000");
Console.WriteLine("  - la LOI survit : delta naif = -1.0000 chip/deal, temoin P2 a P2 constant");
Console.WriteLine("Best-response mesuree (remplace le return 0.0 de 13b) :");
Console.WriteLine("  - voir la section 3 : le blueprint de 13b est EXPLOITABLE dans sa convention");
GameTheory-13c (ce twin) : safe subgame solving porte en C#/.NET Interactive
Sources : Brown & Sandholm 2017 (arXiv:1705.02955), Zinkevich et al. 2007

Reproduction (port fidele, boucle 13b) :
  - EV blueprint = -0.3333, naif = -1.3333, safe = -0.3333  [identiques a 13b]
Audit : somme des poids = 2.0 sur 4 deals, 1.0 sur 2 (double comptage 'pp'/'bp' quand le sous-arbre pb n'est pas atteint)
Enumeration corrigee : blueprint = 0.0000, naif = -1.0000, safe = 0.0000
  - la LOI survit : delta naif = -1.0000 chip/deal, temoin P2 a P2 constant
Best-response mesuree (remplace le return 0.0 de 13b) :
  - voir la section 3 : le blueprint de 13b est EXPLOITABLE dans sa convention
Retour au sommet