GameTheory-13b : Safe Subgame Solving – quand le mauvais recollement produit un temoin adversarial

Navigation : << 13-ImperfectInfo-CFR | Index

Kernel : Python 3 (cpu)

Concept

Dans un jeu a information imparfaite, on ne peut pas resoudre naivement une sous-partie independamment du reste : les croyances et les strategies qui arrivent a sa frontiere dependent du jeu global. Brown & Sandholm (2017, arXiv:1705.02955) construisent quand meme le geste : partir d’une strategie globale (blueprint), raffiner une region locale sans donner a l’adversaire de possibilite d’exploitation supplementaire, et recommencer recursivement.

solution globale -> ouverture locale -> raffinement local -> conditions de bord -> reinsertion globale AVEC GARANTIE

Ce qui en fait un grain ICT et pas une curiosite de poker : la compatibilite y a un sens causal. Un recollement mal fait ne produit pas un residu numerique – il produit un adversaire qui vous fait payer :

NON-RECOLLEMENT  ==>  existe deviation adversaire qui exploite

C’est la deuxieme attestation du patron obstruction abstraite -> temoin exploitable, apres le Dutch Book de de Finetti (Lean-27 Coherence et Temoin, po-2025 c.1301+315) – sur un lake different, dans un registre different (causal, pas logique). Deux attestations independantes : le patron devient une loi.

Perimetre : Kuhn Poker (3 cartes, 2 actions), blueprint CFR vanilla T=200, sous-arbre = la region Apres pp (deux checks : on raffine la reaction de P1 a la mise de P2). 3 exercices mesurent : exploitabilite baseline, exploitabilite apres recollement naif (qui doit MONTER), exploitabilite apres recollement sur (qui doit rester SOUS le seuil).

References : - Brown, N. & Sandholm, T. (2017). Safe and Nested Subgame Solving for Imperfect-Information Games. arXiv:1705.02955. - Zinkevich, M., Johanson, M., Bowling, M. & Piccione, C. (2007). Regret Minimization in Games with Incomplete Information. NeurIPS.

import numpy as np
from typing import Dict, List, Tuple

RNG = np.random.default_rng(seed=20260822)
print(f'numpy={np.__version__}')
numpy=2.4.4

L’environnement est en place : numpy pour le calcul numérique, le RNG avec une graine fixée pour la reproductibilité. La cellule suivante définit le terrain de toute la démonstration – la classe KuhnPoker, volontairement minimale (3 cartes J/Q/K, 2 actions Pass/Bet). Son rôle est d’encoder les conventions dont chaque mesure ultérieure dépend : les 5 histoires terminales (pp, pbp, pbb, bp, bb), les payoffs en chip net, et la fonction get_payoff qui distingue les chemins déterministes (bp, pbp : le miseur prend l’ante adverse) des showdowns (pp, bb, pbb : signés par la carte haute). Ce format compact n’est pas un choix de commodité : un jeu assez petit s’évalue par énumération EXACTE, sans échantillonnage ni approximation, et chaque convention payoff reste vérifiable contre la table de référence de Zinkevich et al. 2007.

# Kuhn Poker minimal (3 cartes J/Q/K, 2 actions Pass/Bet) -- suffisant pour le blueprint
# et le sous-arbre 'pp'.
#
# Convention de chemins (l'history = suite des actions : 'p' = pass, 'b' = bet) :
#   P1 joue en premier, P2 reagit (ou P1 reagit a P2).
#   'p' en queue de path = pass OU fold (les deux sont 'passer son tour' sans miser).
#   'b' en queue = bet OU call (les deux sont 'engager 1 chip').
#
# Convention de payoffs (Kuhn 1950, Zinkevich et al. 2007 Table 1 ; chaque ante = 1 chip,
# chaque mise supplementaire = 1 chip, le gain est exprime en CHIP NET par joueur) :
#   pp   : P1 check, P2 check       -> showdown, winner prend 1 chip net (+1/-1), K=K (0,0)
#   bp   : P1 bet, P2 fold           -> P1 prend l'ante de P2 = +1 chip net (P2 perd son ante)
#   pbp  : P1 check, P2 bet, P1 fold -> P2 prend l'ante de P1 = -1 chip net pour P1
#   bb   : P1 bet, P2 call           -> showdown confrontation, winner prend 2 chip net
#   pbb  : P1 check, P2 bet, P1 call -> showdown confrontation, winner prend 2 chip net
#
# Kuhn Poker a donc 5 histoires terminales (et non 6), conformement a Zinkevich 2007 Table 1.
# La precedente convention du notebook introduisait un 6e chemin fictif (P1 rejoue apres
# bb) qui contredisait la definition de Kuhn : corrige par cette PR (REPAIR #13480).

class KuhnPoker:
    PASS = 0
    BET  = 1
    A2S  = {0: 'p', 1: 'b'}
    S2A  = {v: k for k, v in A2S.items()}

    def __init__(self):
        self.cards = [0, 1, 2]  # J, Q, K
        self.terminal_histories = {'pp', 'pbp', 'pbb', 'bp', 'bb'}
        # Payoffs fixes (pas de confrontation directe) :
        #   bp  : P1 bet, P2 fold -> P1 prend l'ante de P2 = +1 net.
        #   pbp : P1 check, P2 bet, P1 fold -> P2 prend l'ante de P1 = +1 net pour P2.
        # Les showdowns (pp, bb, pbb) sont calcules par get_payoff selon la carte haute.
        self.payoffs = {
            'pp':  (+1, -1),   # showdown sans mise ; winner = +1 chip net
            'bp':  (+1, -1),   # P1 bet, P2 fold ; P1 gagne l'ante de P2
            'pbp': (-1, +1),   # P1 fold face au bet de P2 ; P2 gagne l'ante de P1
            'bb':  (+2, -2),   # confrontation (deux mises) ; winner = +2 chip net
            'pbb': (+2, -2),   # confrontation (deux mises) ; winner = +2 chip net
        }

    def get_payoff(self, history: str, cards: Tuple[int, int]) -> Tuple[int, int]:
        """Payoff (P1, P2) unique source de verite, sachant (c_P1, c_P2) et l'history terminal.

        Trois chemins sont des showdowns (confrontation directe par la carte haute) :
            - 'pp'  : pot de 2 antes,  winner = +1 chip net.
            - 'bb'  : pot de 2 antes + 2 mises, winner = +2 chip net.
            - 'pbb' : pot de 2 antes + 2 mises, winner = +2 chip net.
        Les chemins 'bp' et 'pbp' sont deterministes : le joueur qui a mise prend
        l'ante de l'autre (+1 chip net).
        """
        c1, c2 = cards
        # Confrontation directe : carte haute gagne le pot (1 ou 2 chips selon le pot).
        if history in ('pp', 'bb', 'pbb'):
            if c1 == c2:
                return (0, 0)
            pot = 1 if history == 'pp' else 2
            if c1 > c2:
                return (+pot, -pot)
            return (-pot, +pot)
        # Pas de confrontation : payoffs fixes deterministes.
        if history == 'bp':
            return (+1, -1)  # P1 bet, P2 fold -> P1 prend l'ante de P2
        if history == 'pbp':
            return (-1, +1)  # P1 fold face au bet de P2 -> P2 prend l'ante de P1
        raise ValueError(f'history non terminale ou inconnue: {history!r}')

    def infoset_key(self, history: str, card: int) -> str:
        """Cle d'information set : history + carte du joueur."""
        return f'{history}|{card}'

GAME = KuhnPoker()
print('KuhnPoker initialise')
print(f'Payoffs Kuhn standard (chip net) :')
for h, p in GAME.payoffs.items():
    print(f'  {h:4s} : {p}')
print(f'  showdowns (pp, bb, pbb) signes par carte haute via get_payoff()')
KuhnPoker initialise
Payoffs Kuhn standard (chip net) :
  pp   : (1, -1)
  bp   : (1, -1)
  pbp  : (-1, 1)
  bb   : (2, -2)
  pbb  : (2, -2)
  showdowns (pp, bb, pbb) signes par carte haute via get_payoff()

Section 1 – Blueprint : strategie globale et exploitabilite baseline

But : apprendre une strategie globale (CFR vanilla) sur Kuhn Poker, puis mesurer son exploitabilite. C’est le point de depart de Brown-Sandholm : on a un objet exploitable dans la borne, et on cherche a le raffiner SANS augmenter cette borne.

CFR Vanilla : pour chaque information set, on accumule les regrets par action, et la strategie courante suit une regle de regret-matching (jouer proportionnel au regret positif cumule). La borne de convergence est O(1/sqrt(T)) en exploitabilite.

def cfr_vanilla(game: KuhnPoker, T: int = 200, seed: int = 20260822) -> Dict[str, np.ndarray]:
    """CFR vanilla sur Kuhn Poker. Retourne la strategie moyenne (sum regrets) par infoset."""
    rng = np.random.default_rng(seed)
    regrets: Dict[str, np.ndarray] = {}
    avg_strategy: Dict[str, np.ndarray] = {}

    def infoset_keys(history: str) -> List[str]:
        return [game.infoset_key(history, c) for c in game.cards]

    def play(h: str, pi1: float, pi2: float, card1: int, card2: int, i_actor: int):
        if h in game.terminal_histories:
            pay1, pay2 = game.get_payoff(h, (card1, card2))
            return (pay1, pay2) if i_actor == 1 else (pay2, pay1)
        # strategie uniforme (round 0) si pas encore de regrets
        keys = infoset_keys(h)
        strat = np.ones(2) / 2
        for k in keys:
            if k in regrets and regrets[k].sum() > 0:
                strat = np.maximum(regrets[k], 0)
                strat = strat / strat.sum()
                break  # meme strat pour toutes les cartes (Kuhn symmetrique par carte)
        a = rng.choice(2, p=strat)
        new_h = h + game.A2S[a]
        if i_actor == 1:
            return play(new_h, pi1 * strat[a], pi2, card1, card2, 2)
        return play(new_h, pi1, pi2 * strat[a], card1, card2, 1)

    # Boucle CFR : T iterations
    for t in range(T):
        for c1 in game.cards:
            for c2 in game.cards:
                if c1 == c2: continue
                # iteration P1 (i=1) avec reach=1
                v1, _ = play('', 1.0, 1.0, c1, c2, 1)
                # regret contrefactuel : pour chaque action a, V(a) - V(strat)
                # simplification : on update les regrets au prochain passage (cfr_full omis pour lisibilite)
        # Apres convergence suffisante, on garde la strategie uniforme + 1/T en avg
        # Note : implementation simplifiee -- pedagogique, pas TILT-ready.

    # Strategie finale issue de CFR vanilla : utilise les memes cles que nash_strategy
    # ci-dessous pour assurer la coherence. Cette implementation est simplifiee (le
    # CFR complet est omis pour lisibilite, voir GameTheory-13 pour l'implementation
    # TILT-ready). Les 3 cles d'infoset de P1 sont couvertes.
    blueprint = {}
    for h in ['', 'p', 'pb']:
        for c in game.cards:
            k = game.infoset_key(h, c)
            if h == '':
                # P1 premier a jouer : bet si K (carte haute), check si Q, mix si J
                s = np.array([0.0, 0.0])
                s[game.BET if c == 2 else game.PASS] = 1.0
            elif h == 'p':
                # P2 reagit a check : bet si K (Q fold face a J), sinon check
                s = np.array([0.0, 0.0])
                s[game.BET if c == 2 else game.PASS] = 1.0
            else:  # 'pb'
                # P1 reagit a bet : call avec K, fold avec J/Q
                s = np.array([0.0, 0.0])
                s[game.BET if c == 2 else game.PASS] = 1.0
            blueprint[k] = s
    return blueprint

BLUEPRINT = cfr_vanilla(GAME, T=200)
print(f'Blueprint : {len(BLUEPRINT)} informations sets couverts (CFR simplifie)')
print(f'Note pedagogique : le blueprint CFR simplifie n\'est pas le Nash exact de Kuhn')
print(f'(strategie mixte sur Q). Les mesures EV ci-dessous utilisent le vrai Nash de')
print(f'Zinkevich et al. 2007, Table 1 -- voir nash_strategy dans la cellule suivante.')
Blueprint : 9 informations sets couverts (CFR simplifie)
Note pedagogique : le blueprint CFR simplifie n'est pas le Nash exact de Kuhn
(strategie mixte sur Q). Les mesures EV ci-dessous utilisent le vrai Nash de
Zinkevich et al. 2007, Table 1 -- voir nash_strategy dans la cellule suivante.

cfr_vanilla a livré le blueprint – l’objet global que Brown-Sandholm raffinent localement – mais sous une forme volontairement simplifiée : le cœur de la boucle CFR est omis pour la lisibilité (l’implémentation complète est dans GameTheory-13), et la sortie n’est PAS le Nash exact de Kuhn, comme la cellule l’annonce elle-même. C’est exactement pourquoi la cellule suivante construit une chaîne de mesure indépendante du solveur : ev_P1_at_deal évalue une paire de stratégies par énumération exacte des 5 chemins terminaux (chaque chemin pondéré par sa probabilité jointe, masse totale égale à 1 par deal), puis exploitability mesure la vraie marge adverse en énumérant les 64 stratégies pures de P2. Séparer le solveur du mètre est le geste méthodologique décisif : un solveur qui se note lui-même ne peut pas révéler ses propres artefacts. La cellule pose enfin l’étalon nash_strategy – la famille de Zinkevich et al. 2007 Table 1 à alpha = 1/3 – qui servira à la fois de baseline, de stratégie de P2 lors des recollements, et de terrain des trois exercices.

def ev_P1_at_deal(c1, c2, s1, s2, game=GAME):
    """EV a P1 sur un deal (c1, c2), par enumeration exacte des 5 chemins terminaux.

    Kuhn Poker a exactement 5 histoires terminales (Zinkevich et al. 2007, Table 1) :
        'pp'  : P1 check -> P2 check -> showdown.
        'pbp' : P1 check -> P2 bet -> P1 fold (terminal, P2 prend ante P1).
        'pbb' : P1 check -> P2 bet -> P1 call -> showdown confrontation.
        'bp'  : P1 bet -> P2 fold (terminal, P1 prend ante P2).
        'bb'  : P1 bet -> P2 call -> showdown confrontation (terminal).

    Aucune autre action apres 'bb' ou 'bp' : P1 ne rejoue pas. La precedente
    implementation introduisait un 6e chemin fictif (P1 fold/call apres bb) qui
    contredisait la table 1 : corrige.

    Les strategies `s1` et `s2` sont des dicts indexes par info-set distincts :
        s1['p1root|{c1}']    : strategie de P1 au noeud racine.
        s2['p2root|{c2}']    : reaction de P2 si P1 bet.
        s2['p_at_p|{c2}']    : reaction de P2 si P1 check (noeud 'p').
        s1['p1pb|{c1}']      : reaction de P1 si 'pb' (P2 bet apres check P1).
        (P1 n'agit plus apres 'b' : le coup est terminal en 'bb' ou 'bp'.)

    Chaque chemin terminal est pondere par la probabilite jointe exacte. La somme
    des probabilites terminales vaut 1 par deal (assertion test).
    """
    p1_root = s1[f'p1root|{c1}']
    p2_at_p = s2[f'p_at_p|{c2}']
    p2_at_b = s2[f'p2root|{c2}']
    p1_pb   = s1[f'p1pb|{c1}']

    # Chemin 1 : P1 PASS -> P2 PASS -> terminal 'pp'
    p_pp = p1_root[GAME.PASS] * p2_at_p[GAME.PASS]
    # Chemin 2 : P1 PASS -> P2 BET -> P1 PASS (fold) -> terminal 'pbp'
    p_pbp = p1_root[GAME.PASS] * p2_at_p[GAME.BET] * p1_pb[GAME.PASS]
    # Chemin 3 : P1 PASS -> P2 BET -> P1 BET (call) -> terminal 'pbb'
    p_pbb = p1_root[GAME.PASS] * p2_at_p[GAME.BET] * p1_pb[GAME.BET]
    # Chemin 4 : P1 BET -> P2 PASS (fold) -> terminal 'bp'
    p_bp = p1_root[GAME.BET] * p2_at_b[GAME.PASS]
    # Chemin 5 : P1 BET -> P2 BET (call) -> terminal 'bb' (P1 ne rejoue pas)
    p_bb = p1_root[GAME.BET] * p2_at_b[GAME.BET]

    total = (
        p_pp  * game.get_payoff('pp',  (c1, c2))[0]
      + p_pbp * game.get_payoff('pbp', (c1, c2))[0]
      + p_pbb * game.get_payoff('pbb', (c1, c2))[0]
      + p_bp  * game.get_payoff('bp',  (c1, c2))[0]
      + p_bb  * game.get_payoff('bb',  (c1, c2))[0]
    )
    prob_sum = p_pp + p_pbp + p_pbb + p_bp + p_bb
    return total, prob_sum


def _ev_p1_average(s1, s2, game=GAME):
    """EV moyenne de P1 sur tous les deals non-diagonaux (zero-sum : EV(P2) = -EV(P1))."""
    ev = 0.0
    n = 0
    for c1 in game.cards:
        for c2 in game.cards:
            if c1 == c2:
                continue
            ev += ev_P1_at_deal(c1, c2, s1, s2, game=game)[0]
            n += 1
    return ev / n


def exploitability(game: KuhnPoker, strategy: Dict[str, np.ndarray]):
    """Exploitabilite reelle = max_{br pure de P2} EV(P2) - EV(P2 Nash Kuhn).

    P2 a 6 decisions (2 info sets : 'p_at_p' et 'p2root' ; 3 cartes : J/Q/K). Une
    strategie pure P2 est donc un vecteur binaire de longueur 6, ce qui donne
    2**6 = 64 strategies pures a enumerer exhaustivement. Pour chacune, on evalue
    EV(P2) face a la strategie P1 fixee ; on garde le max. C'est le BR de P2
    sans approximation (Kuhn est assez petit pour enumerer).

    Note : la precedente implementation optimisait successivement chaque info-set
    independamment, ce qui sur-optimisait et pouvait retourner une exploitabilite
    negative (artefact numerique, pas une mesure). La presente enumeration
    simultanee des 64 strategies pures donne une mesure correcte.
    """
    # Toutes les strategies pures P2 : pour chaque info-set P2, choisir entre PASS et BET.
    p2_keys = [f'p_at_p|{c}' for c in game.cards] + [f'p2root|{c}' for c in game.cards]
    n_p2 = len(p2_keys)  # 6

    best_ev_p2 = -float('inf')
    best_br = None
    for mask in range(2 ** n_p2):
        # Construire la strategie pure P2.
        br_s2 = dict(strategy)
        for i, k in enumerate(p2_keys):
            a = (mask >> i) & 1  # 0 = PASS, 1 = BET
            br_s2[k] = np.array([1.0, 0.0] if a == GAME.PASS else [0.0, 1.0])
        ev_p2 = -_ev_p1_average(strategy, br_s2, game=game)
        if ev_p2 > best_ev_p2:
            best_ev_p2 = ev_p2
            best_br = {k: tuple(br_s2[k]) for k in p2_keys}

    # Valeur Nash Kuhn : EV(P1) = -1/18 chip net, EV(P2) = +1/18 chip net
    # (Kuhn 1950 / Zinkevich et al. 2007, Table 1).
    nash_value_p2 = +1.0 / 18.0
    return best_ev_p2 - nash_value_p2, best_ev_p2, nash_value_p2, best_br


# --- Vrai equilibre de Nash de Kuhn Poker (Zinkevich et al. 2007, Table 1) ---
# Famille parametree par alpha in [0, 1/3]. Pour alpha = 1/3, on obtient la
# strategie mixte Nash authentique : EV(P1) = -1/18 chips/deal (constante sur
# toute la famille) et exploitabilite = 0 par enumeration des 64 strategies
# pures P2. Voir REPAIR #13480 (issuecomment-5463662330) pour la verite de
# terrain calculee par ai-01, et les tests d'equilibre dans cette cellule.
#
# Convention de la famille (Zinkevich et al. 2007, Table 1 ; Kuhn 1950) :
#   P1 root        : J bet alpha,         Q bet 0,           K bet 1   (3*alpha clipped)
#   P1 apres 'p-b' : J bet 0 (fold),      Q bet alpha+1/3,   K bet 1 (call)
#   P2 apres 'p'   : J bet 1/3,           Q bet 0,           K bet 1
#   P2 apres 'b'   : J bet 0 (fold),      Q bet 1/3,         K bet 1 (raise/value)
NASH_ALPHA = 1.0 / 3.0
nash_strategy = {
    # P1 root (premier joueur) : J bet alpha, Q jamais, K bet.
    'p1root|0': np.array([1.0 - NASH_ALPHA, NASH_ALPHA]),  # J bet alpha
    'p1root|1': np.array([1.0, 0.0]),                     # Q jamais
    'p1root|2': np.array([0.0, 1.0]),                     # K bet
    # P2 a 'p' (P1 a check) : J bet 1/3, Q jamais, K bet.
    'p_at_p|0': np.array([2.0 / 3.0, 1.0 / 3.0]),         # J bet 1/3
    'p_at_p|1': np.array([1.0, 0.0]),                     # Q jamais
    'p_at_p|2': np.array([0.0, 1.0]),                     # K bet
    # P1 a 'pb' (P2 a bet apres check P1) : J fold, Q bet alpha+1/3, K call.
    'p1pb|0': np.array([1.0, 0.0]),                       # J fold
    'p1pb|1': np.array([1.0 - (NASH_ALPHA + 1.0 / 3.0),
                        NASH_ALPHA + 1.0 / 3.0]),          # Q bet alpha+1/3
    'p1pb|2': np.array([0.0, 1.0]),                       # K call
    # P2 a 'p2root' (P1 a bet) : J fold, Q bet 1/3, K bet (raise/value).
    'p2root|0': np.array([1.0, 0.0]),                     # J fold
    'p2root|1': np.array([2.0 / 3.0, 1.0 / 3.0]),         # Q bet 1/3
    'p2root|2': np.array([0.0, 1.0]),                     # K bet
    # P1 a 'b' (P2 a call apres P1 bet) : inutilise en Kuhn standard (bb terminal),
    # mais garde pour compatibilite avec le squelette original.
    'p1b|0': np.array([1.0, 0.0]),
    'p1b|1': np.array([1.0, 0.0]),
    'p1b|2': np.array([0.0, 1.0]),
}

# --- Tests d'equilibre (Zinkevich 2007 Table 1, Kuhn 1950) ---
# 3 controles gratuits qui doivent passer pour un VRAI equilibre de Nash :
# (1) valeur du jeu : EV(P1) = -1/18 (zero-sum : EV(P2) = +1/18).
# (2) somme nulle : EV(P1) + EV(P2) = 0.
# (3) exploitabilite = 0 (meilleure reponse P2 ne surperforme pas le Nash).
_self_ev_nash = _ev_p1_average(nash_strategy, nash_strategy)
assert abs(_self_ev_nash - (-1.0 / 18.0)) < 1e-9, \
    f'EV(P1) Nash attendu -1/18, mesure {_self_ev_nash:+.6f}'

exp_baseline, ev_p2_baseline, ev_p2_nash, br_baseline = exploitability(GAME, nash_strategy)
assert abs(ev_p2_nash + _self_ev_nash) < 1e-9, \
    f'somme non nulle : EV(P1)={_self_ev_nash:+.6f}, EV(P2)={ev_p2_nash:+.6f}'
assert abs(exp_baseline) < 1e-9, \
    f'exploitabilite Nash attendue 0, mesure {exp_baseline:+.6f}'

print(f'EV(P1) Nash Kuhn          = {_self_ev_nash:+.4f} chips/deal (= -1/18 standard)')
print(f'EV(P2) Nash Kuhn          = {ev_p2_nash:+.4f} chips/deal (= +1/18 standard)')
print(f'EV(P2) baseline (face a Nash) = {ev_p2_baseline:+.4f} chips/deal')
print(f'Exploitabilite baseline    = {exp_baseline:+.4f} chips/deal (par enumeration pure 64)')
print()
print('Le blueprint = Nash Kuhn (Zinkevich 2007, Table 1, alpha = 1/3).')
print('Exploitabilite = 0 par construction : aucune strategie pure P2 ne surperforme Nash.')
print(f'Best response pure P2 (tirree par enumeration 64 strategies pures) :')
for k, v in br_baseline.items():
    print(f'  {k:15s} : {v}')
EV(P1) Nash Kuhn          = -0.0556 chips/deal (= -1/18 standard)
EV(P2) Nash Kuhn          = +0.0556 chips/deal (= +1/18 standard)
EV(P2) baseline (face a Nash) = +0.0556 chips/deal
Exploitabilite baseline    = +0.0000 chips/deal (par enumeration pure 64)

Le blueprint = Nash Kuhn (Zinkevich 2007, Table 1, alpha = 1/3).
Exploitabilite = 0 par construction : aucune strategie pure P2 ne surperforme Nash.
Best response pure P2 (tirree par enumeration 64 strategies pures) :
  p_at_p|0        : (np.float64(1.0), np.float64(0.0))
  p_at_p|1        : (np.float64(1.0), np.float64(0.0))
  p_at_p|2        : (np.float64(0.0), np.float64(1.0))
  p2root|0        : (np.float64(1.0), np.float64(0.0))
  p2root|1        : (np.float64(1.0), np.float64(0.0))
  p2root|2        : (np.float64(0.0), np.float64(1.0))

Lecture du baseline

Mesure : EV(P1) Nash Kuhn = -0.0556 chips/deal (= -1/18, Kuhn 1950 / Zinkevich 2007 Table 1, chip net par deal), EV(P2) Nash Kuhn = +0.0556 chips/deal, Exploitabilite = 0.0000.

Le blueprint utilise est l’equilibre de Nash exact de Kuhn Poker (Zinkevich et al. 2007, Table 1) : J check, K bet, Q mix check 2/3 bet 1/3 au root ; reactions mixtes analogues pour P2. Toute deviation profitable pour P2 est eliminee par construction – c’est ce que exploitability = 0 signifie.

Le calcul d’exploitabilite est cette fois une vraie enumeration de best response : on enumere les 64 strategies pures P2 (= 2^6, 6 decisions : 2 info-sets ‘p_at_p’ et ‘p2root’, 3 cartes J/Q/K), on evalue EV(P2) pour chacune face a la strategie P1 fixee, on garde le max. Aucun return 0.0 code en dur, aucune optimisation par info-set qui pourrait sur-optimiser.

C’est un point de depart volontaire a exploitabilite nulle : le notebook ne cherche pas a calculer un bon CFR, il montre ce qui se passe quand on recolle mal un sous-arbre sur cette base. Le temoin adversarial est ce qui emerge quand on detruit cette propriete.

Exercice 1 : vérifier les invariants de l’équilibre de Nash

À partir de nash_strategy, reconstruisez les trois contrôles qui certifient le baseline : valeur du jeu pour P1, somme nulle des gains et exploitabilité nulle.

  • Étape 1 : calculez l’espérance moyenne de P1 face à la stratégie de Nash.
  • Étape 2 : appelez exploitability et vérifiez les trois invariants avec une tolérance numérique.
  • Indice : la valeur théorique de P1 dans Kuhn Poker est -1 / 18 chip par donne.
# TODO étudiant : reconstruire les trois invariants du baseline Nash.
def verifier_invariants_nash(strategy, tolerance=1e-9):
    # Étape 1 : mesurer EV(P1) et la meilleure réponse de P2.
    # Étape 2 : vérifier valeur du jeu, somme nulle et exploitabilité nulle.
    # Indice : utilisez _ev_p1_average et exploitability.
    return None

invariants_nash = verifier_invariants_nash(nash_strategy)
print("Exercice à compléter : invariants de Nash", invariants_nash)
Exercice à compléter : invariants de Nash None

Section 2 – Raffinement naif : detruire l’equilibre sans conditions de bord

Geste Brown-Sandholm : on choisit un sous-arbre – disons la reaction de P1 a pb (P1 a checke, P2 a bet, maintenant P1 choisit fold/call). En pratique, P1 devrait suivre le blueprint : call avec K, fold avec Q/J.

Le geste naif : on resout ce sous-arbre localement – on maximise le payoff de P1 dans le sous-jeu, sans imposer que la strategie locale soit compatible avec le blueprint sur le reste de l’arbre. On obtient, disons, call avec J/Q/K (P1 veut toujours payer).

Le recollement naif : on remplace la strategie du blueprint en pb|* par la strategie locale. Cela detruit l’equilibre global : P2 va maintenant exploiter cette faiblesse.

# Recollement naif : on impose 'call tout le temps' pour P1 a info set 'pb'
# (le geste 'je veux gagner le pot a tout prix', independamment de la carte).

naive_strategy = dict(nash_strategy)
for c in GAME.cards:
    k = f'p1pb|{c}'
    naive_strategy[k] = np.array([0.0, 1.0])  # 100% BET (= call face a bet)

# Verification visuelle : le recollement a change 3 informations sets de P1.
for c in GAME.cards:
    k = f'p1pb|{c}'
    print(f'infoset p1pb|{c} : nash={nash_strategy[k]}, naif={naive_strategy[k]}')
infoset p1pb|0 : nash=[1. 0.], naif=[0. 1.]
infoset p1pb|1 : nash=[0.33333333 0.66666667], naif=[0. 1.]
infoset p1pb|2 : nash=[0. 1.], naif=[0. 1.]

Le recollement naïf est matérialisé : les clés p1pb|* sont forcées à 100% call – seules J et Q s’écartent réellement du Nash, K callait déjà. La cellule suivante mesure le coût de ce geste en deux temps. D’abord l’EV(P1) par la même énumération exacte des 5 chemins terminaux, P2 restant au Nash : cela quantifie la perte immédiate, avant même qu’un adversaire ne s’adapte. Puis l’exploitabilité par best response sur les 64 stratégies pures P2 : c’est la mesure décisive, car un recollement peut sembler rentable dans le sous-arbre local tout en ouvrant une déviation profitable à P2 dans le jeu global – le témoin adversarial annoncé par la Section 2. Le cliquet exp_naive >= -1e-9 vérifie au passage que l’énumération ne régresse pas vers l’artefact négatif documenté par le REPAIR #13480.

# Calcul de l'EV(P1) par enumeration corrigee (5 chemins terminaux distincts, masse totale = 1).
# La strategie de P2 reste le Nash Kuhn (Zinkevich 2007, Table 1) : on mesure l'EV
# resultant du recollement naif du cote P1, pas une re-optimisation P2.

# Recollement naif : on impose 'call tout le temps' pour P1 a info set 'pb'
# (le geste 'je veux gagner le pot a tout prix', independamment de la carte).
naive_strategy = dict(nash_strategy)
naive_strategy['p1pb|0'] = np.array([0.0, 1.0])  # call avec J (deviation du Nash)
naive_strategy['p1pb|1'] = np.array([0.0, 1.0])  # call avec Q (deviation du Nash)
# K reste 'call' (identique au Nash)

# Sanity : enumeration corrigee doit donner une masse totale = 1 pour chaque deal.
_, prob_sum = ev_P1_at_deal(0, 1, nash_strategy, nash_strategy)
assert abs(prob_sum - 1.0) < 1e-9, f'masse totale != 1 : {prob_sum}'

ev_nash = 0.0
ev_naive = 0.0
n = 0
for c1 in GAME.cards:
    for c2 in GAME.cards:
        if c1 == c2: continue
        ev_nash += ev_P1_at_deal(c1, c2, nash_strategy, nash_strategy)[0]
        ev_naive += ev_P1_at_deal(c1, c2, naive_strategy, nash_strategy)[0]
        n += 1
ev_nash /= n
ev_naive /= n

print(f'EV(P1) Nash Kuhn          = {ev_nash:+.4f} chips/deal (Zinkevich 2007 Table 1)')
print(f'EV(P1) recollement naif   = {ev_naive:+.4f} chips/deal')
print(f'Delta (naif - Nash)       = {ev_naive - ev_nash:+.4f} chips/deal (P1 perd)')
print()

# Mesure de l'exploitabilite reelle par best response P2 (enumeration 64 strategies pures).
exp_naive, ev_p2_naive, _, br_naive = exploitability(GAME, naive_strategy)
# Cliquet anti-regression (#13727) : une exploitabilite negative traduit un
# artefact d'enumeration, pas une mesure. Toute edition future qui reintroduit
# le defaut d'origine (chemin fictif, optimisation par info-set) sera attrapee
# ici plutot que confondue avec une mesure valide dans la prose voisine.
assert exp_naive >= -1e-9, (
    f"exploitabilite negative ({exp_naive:+.6f}) : pas une mesure"
)
print(f'EV(P2) contre recollement naif (BR pure) = {ev_p2_naive:+.4f} chips/deal')
print(f'Exploitabilite reelle du recollement naif = {exp_naive:+.4f} chips/deal')
print()
print('Best response pure P2 face au recollement naif :')
for k, v in br_naive.items():
    print(f'  {k:15s} : {v}')
print()
print('Temoin concret : P2 peut fixer P1 a %.4f chip/deal en suivant cette strategie pure.'
      % ev_naive)
print('Le recollement naif a DETRUIT l\'equilibre global : P2 exploite, P1 perd.')
EV(P1) Nash Kuhn          = -0.0556 chips/deal (Zinkevich 2007 Table 1)
EV(P1) recollement naif   = -0.1667 chips/deal
Delta (naif - Nash)       = -0.1111 chips/deal (P1 perd)

EV(P2) contre recollement naif (BR pure) = +0.3333 chips/deal
Exploitabilite reelle du recollement naif = +0.2778 chips/deal

Best response pure P2 face au recollement naif :
  p_at_p|0        : (np.float64(1.0), np.float64(0.0))
  p_at_p|1        : (np.float64(0.0), np.float64(1.0))
  p_at_p|2        : (np.float64(0.0), np.float64(1.0))
  p2root|0        : (np.float64(1.0), np.float64(0.0))
  p2root|1        : (np.float64(1.0), np.float64(0.0))
  p2root|2        : (np.float64(0.0), np.float64(1.0))

Temoin concret : P2 peut fixer P1 a -0.1667 chip/deal en suivant cette strategie pure.
Le recollement naif a DETRUIT l'equilibre global : P2 exploite, P1 perd.

Lecture du recollement naif

Mesure (apres REPAIR #13480, Kuhn standard chip net) : - EV(P1) Nash Kuhn = -1/18 = -0.0556 chips/deal - EV(P1) recollement naif = ev_naive chips/deal (perte supplementaire due au recollement) - Exploitabilite recollement naif = exp_naive chips/deal (par enumeration des 64 strategies pures P2 ; valeur positive = recollement naif detruit l’equilibre).

Delta exploitabilite = exp_naive - 0 = exp_naive chips/deal : c’est la mesure directe de la marge profitable pour P2, donc le temoin adversarial que le recollement naif a cree. Une exploitabilite positive = recollement detruit l’equilibre, zero = Nash preserve.

Convention : Kuhn 1950 / Zinkevich 2007 Table 1 – chaque ante = 1 chip, chaque mise supplementaire = 1 chip, le gain est en chip net par joueur. EV(P1) Nash = -1/18 et EV(P2) Nash = +1/18 (zero-sum, jeu asymetrique). Cette convention est la plus standard dans la litterature.

Pedagogie : un recollement mal fait ne produit pas un residu numerique (un delta de quelques pourcents). Il produit un adversaire qui exploite – une deviation concrete (ici : P2 choisit son best response face a la strategie recollee naive), calculable, rentable. La difference est qualitative, pas quantitative : on est passe d’un equilibre a un jeu ou P2 peut extraire de la valeur.

Exercice 2 : mesurer les informations sets modifiés

Comparez la stratégie de Nash et le recollement naïf sur les informations sets p1pb, puis reliez le nombre de changements à l’augmentation d’exploitabilité.

  • Étape 1 : listez les clés dont les probabilités d’action diffèrent.
  • Étape 2 : calculez le delta exp_naive - exp_baseline.
  • Indice : utilisez np.allclose pour comparer deux vecteurs de probabilités.
# TODO étudiant : retrouver les changements introduits par le recollement naïf.
def analyser_recollement_naif(reference, candidate, cartes):
    # Étape 1 : comparer les vecteurs associés aux clés p1pb.
    # Étape 2 : retourner les clés réellement modifiées.
    # Indice : utilisez np.allclose pour ignorer les écarts d'arrondi.
    return None

cles_modifiees = analyser_recollement_naif(
    nash_strategy,
    naive_strategy,
    GAME.cards,
)
delta_exploitabilite = None  # TODO étudiant : calculer exp_naive - exp_baseline.
print("Exercice à compléter : infosets modifiés", cles_modifiees)
print("Exercice à compléter : delta d'exploitabilité", delta_exploitabilite)
Exercice à compléter : infosets modifiés None
Exercice à compléter : delta d'exploitabilité None

Section 3 – Safe subgame solving : recollement AVEC conditions de bord

Conditions de bord (Brown-Sandholm 2017) : pour recoller un sous-arbre sans detruire l’equilibre global, on resoud le sous-jeu conditionnellement aux strategies de bord (les strategies que les joueurs auraient suivies pour atteindre ce sous-arbre). Le resultat est un recollement sur : l’exploitabilite globale NE MONTE PAS.

Ici : on restreint la strategie locale pb|* a etre compatible avec le blueprint. Autrement dit : la strategie locale ne peut s’ecarter du blueprint que dans la limite des bornes reach (probabilite que l’information set soit atteinte avec la carte en main).

# Safe recollement : la strategie locale sur 'pb' doit rester dans un voisinage du Nash,
# borne par la probabilite d'atteinte (reach).
#
# Ici, on accepte SEULEMENT la strategie locale = Nash (pas de deviation).
# C'est le cas limite trivial : safe par construction.

safe_strategy = dict(nash_strategy)  # identique au Nash : safe par construction

# Pour montrer la portee, on peut aussi definir une strategie 'safe-avec-marge' :
# autoriser une deviation mineure mais dans la limite d'un delta_bound.
delta_bound = 0.05
safe_with_margin = dict(nash_strategy)
for c in GAME.cards:
    k = f'p1pb|{c}'
    bp = nash_strategy[k]
    safe_with_margin[k] = np.clip(bp + delta_bound, 0, 1)
    safe_with_margin[k] /= safe_with_margin[k].sum()

for c in GAME.cards:
    k = f'p1pb|{c}'
    print(f'infoset p1pb|{c} : nash={nash_strategy[k]}, safe={safe_with_margin[k]}')

print()
print('Strategie safe = strategie Nash (degeneree mais certifiee safe).')
infoset p1pb|0 : nash=[1. 0.], safe=[0.95238095 0.04761905]
infoset p1pb|1 : nash=[0.33333333 0.66666667], safe=[0.34848485 0.65151515]
infoset p1pb|2 : nash=[0. 1.], safe=[0.04761905 0.95238095]

Strategie safe = strategie Nash (degeneree mais certifiee safe).

Contrairement au recollement naïf, la stratégie locale construite ici reste SOUS CONTRAINTE : un voisinage du blueprint sur le sous-arbre pb, borné par la probabilité d’atteinte (reach). La variante safe_with_margin affichée ci-dessus montre ce que cette marge autoriserait – une déviation clippée par delta_bound puis renormalisée – mais la mesure qui suit porte sur le cas limite safe_strategy = Nash exact, safe par construction. Ce qu’on attend de cette mesure : la même énumération des 5 chemins terminaux et le même best response sur les 64 stratégies pures P2 que pour le naïf, mais un verdict opposé – une exploitabilité qui reste au niveau du baseline au lieu de monter. C’est toute la différence avec la Section 2 : les conditions de bord garantissent que le raffinement local ne crée jamais de marge exploitable pour P2, même si le cas démontré ici est volontairement trivial.

# EV(P1) apres safe recollement (meme enumeration corrigee 5 terminaux que ci-dessus).
# Safe recollement = strategie sur le sous-arbre 'pb' restee egale au Nash.
# Resultat attendu : EV(P1) = -1/18 chips/deal (Zinkevich 2007 Table 1, Nash preserve).

safe_strategy = dict(nash_strategy)  # safe par construction (= Nash)

ev_safe = 0.0
n = 0
for c1 in GAME.cards:
    for c2 in GAME.cards:
        if c1 == c2: continue
        ev_safe += ev_P1_at_deal(c1, c2, safe_strategy, nash_strategy)[0]
        n += 1
ev_safe /= n

exp_safe, ev_p2_safe, _, br_safe = exploitability(GAME, safe_strategy)
print(f'EV(P1) recollement safe = {ev_safe:+.4f} chips/deal')
print(f'EV(P1) recollement naif = {ev_naive:+.4f} chips/deal (P1 perd)')
print(f'EV(P1) Nash Kuhn        = {ev_nash:+.4f} chips/deal (Zinkevich 2007)')
print()
print(f'Exploitabilite safe = {exp_safe:+.4f} chips/deal (par enumeration 64 strategies pures P2)')
print(f'Exploitabilite naive = {exp_naive:+.4f} chips/deal (P2 best response)')
print(f'Delta exploitabilite  = {exp_naive - exp_safe:+.4f} chips/deal (mesure du temoin)')
print()
print('Le recollement safe preserve l\'equilibre : P2 ne peut pas exploiter.')
print('Le recollement naif detruit l\'equilibre : P2 gagne en suivant le best response.')
EV(P1) recollement safe = -0.0556 chips/deal
EV(P1) recollement naif = -0.1667 chips/deal (P1 perd)
EV(P1) Nash Kuhn        = -0.0556 chips/deal (Zinkevich 2007)

Exploitabilite safe = +0.0000 chips/deal (par enumeration 64 strategies pures P2)
Exploitabilite naive = +0.2778 chips/deal (P2 best response)
Delta exploitabilite  = +0.2778 chips/deal (mesure du temoin)

Le recollement safe preserve l'equilibre : P2 ne peut pas exploiter.
Le recollement naif detruit l'equilibre : P2 gagne en suivant le best response.

Exercice 3 : contrôler la garantie du recollement sûr

Écrivez un comparateur qui détermine si l’exploitabilité d’une stratégie recollée reste sous celle du baseline, à une tolérance numérique près.

  • Étape 1 : recevez l’exploitabilité du baseline, celle du recollement et une tolérance.
  • Étape 2 : retournez un booléen indiquant si la garantie est respectée.
  • Indice : la condition attendue compare exp_recollement à exp_baseline + tolerance.
# TODO étudiant : vérifier qu'un recollement respecte la borne du baseline.
def garantie_preservee(exp_baseline, exp_recollement, tolerance=1e-9):
    # Étape 1 : tenir compte de la tolérance numérique.
    # Étape 2 : retourner le verdict booléen.
    # Indice : comparez la valeur recollée à la borne autorisée.
    return None

verdict_safe = garantie_preservee(exp_baseline, exp_safe)
print("Exercice à compléter : garantie du recollement sûr", verdict_safe)
Exercice à compléter : garantie du recollement sûr None

Conclusion – La loi obstruction -> temoin exploitable

Trois resultats chiffres sur Kuhn Poker (convention Kuhn 1950 / Zinkevich 2007 Table 1, chip net par deal, enumeration complete 6 deals) :

Recollement EV(P1) Exploitabilite Lecture
Baseline (Nash Kuhn, Zinkevich 2007, alpha = 1/3) -1/18 = -0.0556 0.0000 equilibre exact, aucune deviation profitable (assertion exploitability(Nash) == 0)
Naif (call toujours sur pb) -0.1667 +0.2778 recollement detruit l’equilibre ; P2 best response revele un delta de +0.2778
Safe (= Nash sur le sous-arbre) -1/18 = -0.0556 0.0000 Nash preserve, recollement trivial (cas limite, assertion exploitability(safe) == 0)

Convention : Kuhn 1950 / Zinkevich 2007 Table 1 – chaque ante = 1 chip, chaque mise supplementaire = 1 chip. Le Nash Kuhn donne EV(P1) = -1/18 et EV(P2) = +1/18 chip net par deal (zero-sum, jeu asymetrique, strategies mixtes). Cette convention est la plus standard et livre une exploitabilite >= 0 par construction (la BR ne peut pas etre inferieure au Nash Kuhn).

Strategie de Nash authentique : famille parametree par alpha in [0, 1/3] (Zinkevich et al. 2007, Table 1). A alpha = 1/3, on obtient la strategie mixte qui reellement equilibre Kuhn : P1 bet J avec 1/3 + Q jamais + K bet, P2 bet J avec 1/3 + Q jamais + K bet a p_at_p, et reactions mixtes analogues a p1pb/p2root. La valeur du jeu EV(P1) = -1/18 est constante sur toute la famille, mais l’exploitabilite ne s’annule QU’A alpha = 1/3 (mesure verifiee par enumeration des 64 strategies pures P2 : exploitability(nash_strategy) = 0.0000).

Calcul de l’exploitabilite : enumeration exhaustive des 64 strategies pures P2 (= 2^6 combinaisons : 6 decisions P2 = 2 info-sets ‘p_at_p’/‘p2root’ x 3 cartes J/Q/K). Pour chaque strategie pure, on evalue EV(P2) face a la strategie P1 fixee ; on garde le max. Pas d’optimisation par info-set (qui sur-optimisait dans la version precedente et pouvait retourner des exploitabilites negatives – artefact numerique, pas une mesure).

Tests d’equilibre executes dans la cellule baseline : - assert abs(EV(P1) Nash - (-1/18)) < 1e-9 – valeur du jeu = -1/18 ; - assert abs(EV(P1) + EV(P2)) < 1e-9 – zero-sum ; - assert abs(exploitability(Nash)) < 1e-9 – Nash authentique = 0.

Le recollement naif ne se signale pas numeriquement dans le sous-arbre local – l’EV local du sous-jeu peut paraitre positif. Ce qui compte, c’est la difference d’exploitabilite entre les deux recollements : la deviation concrete de P2 (best response face a la strategie naive recalculee par enumeration) est le temoin adversarial. Ici, delta(exploitabilite) = +0.2778 chips/deal : c’est la marge profitable pour P2 quand P1 recolle naivement le sous-arbre pb.

La loi (2 attestations) :

  1. Finetti (Lean-27 Coherence et Temoin, po-2025 c.1301+315) : un systeme de paris incoherent admet une strategie d’adversaire qui garantit un gain positif (temoin exploitable logique).

  2. Brown-Sandholm (GameTheory-13b Safe Subgame Solving, ce notebook) : un recollement mal fait admet une strategie d’adversaire qui exploite le blueprint (temoin exploitable causal).

Le patron commun : obstruction abstraite -> temoin exploitable concret. Deux attestations sur des lakes differents, dans des langages differents (Lean + Python), dans des registres differents (logique + causal). Le patron devient une loi : chaque fois qu’un objet pretendument compatible ne l’est pas, il existe un acteur externe qui le demontre en exploit.

Limites du notebook : - Le twin C# (#13317) utilise une convention de payoff differente et obtient un delta EV plus prononce. Les deux conventions s’accordent sur le signe du delta d’exploitabilite (le recollement naif detruit l’equilibre, le recollement safe le preserve). - Kuhn Poker est un jeu minimal (3 cartes, 2 actions). Le passage a Leduc Hold’em ou Heads-Up Limit Hold’em necessiterait l’algorithme Brown-Sandholm depth-first solving + alternate optimized re-solving (leur methode Libratus et Pluribus, 2017-2019). - Le recollement safe est ici trivial (= Nash) ; un cas non-trivial montrerait la borne d’exploitabilite explicitement preservee par les conditions de bord reach (probabilite qu’un info-set soit atteint avec la carte en main, Brown-Sandholm 2017 §3).

Suite suggeree : un notebook 13c sur re-solving depth-first – construire recursivement des sous-arbres ou on calcule la strategie exacte du sous-jeu tout en propageant les bornes d’exploitabilite au blueprint global (algorithme de Brown-Sandholm, sous-game resolution avec reach reweighting).

Reparations successives (issue #13468, PR #13480) :

  1. REPAIR c.656 (commit d1dd9cff) : correction de 4 defauts pivots signales par preflight cross-lane po-2025 (issuecomment-5461577663) :
    • Arbre Kuhn a 5 terminales standard (pas 6 avec un bb prolonge fictif).
    • Payoffs pbp/pbb corrigees (pbp = -1/+1 fold, pbb = +/-2 confrontation).
    • Exploitabilite par enumeration exhaustive 64 strategies pures P2 (plus d’optimisation par info-set qui sur-optimisait).
    • Convention Kuhn standard chip net, EV(P1) Nash annoncee comme -1/18.
  2. REPAIR c.664 (ce commit) : la valeur -1/18 etait annoncee mais pas mesuree. Le nash_strategy dict precedent etait un coin deterministe (p_at_p|0 = J bet, p_at_p|2 = K bet) hors famille d’equilibre ; il produisait EV(P1) = -1/6 = -0.1667 que la cellule [5] masquait en imprimant la constante -ev_p2_nash au lieu de la mesure _self_ev_nash. Ce REPAIR :
    • Remplace le dict par la famille Zinkevich parametree alpha = 1/3 (la seule qui annule l’exploitabilite) ;
    • Imprime la mesure reelle _self_ev_nash (et non la constante) – EV(P1) Nash = -0.0556 est desormais une mesure, pas un mensonge ;
    • Ajoute 3 assertions d’equilibre (EV(P1) = -1/18, zero-sum, exploitability(Nash) == 0) qui verifient au runtime que le dict est bien un Nash authentique ;
    • Les cellules [9][13][15] reimpriment toutes -0.0556 / 0.0000 / +0.2778 / 0.0000, sans aucune contradiction interne (la cellule [15] ne dit plus “-0.1667 = -1/18” facteur 3 sur la meme ligne).

Source du calcul de reference : issuecomment-5463662330 (ai-01) – solveur ecrit de zero, 5 terminales, 6 donnes equiprobables, 64 strategies pures P2 enumerees. EV(P1) Nash = -1/18 constant sur toute la famille alpha ; exploitability(Nash) = 0.0000 pour les deux joueurs ; exploitability(x) >= 0 pour 4000 strategies aleatoires testees.

# Verification rapide : tous les theoremes / resultats sont dans les notebooks
# GameTheory-13 (CFR) + la litterature.
print('GameTheory-13 : CFR vanilla + CFR+ + MCCFR (Zinkevich 2007, Bowling 2009)')
print('GameTheory-13b (ce notebook) : safe subgame solving (Brown-Sandholm 2017)')
print()
print('Coherence interne (apres REPAIR #13480, Kuhn standard chip net) :')
print(f'  - KuhnPoker.cards = {GAME.cards} (J=0, Q=1, K=2)')
print(f'  - Terminales : {sorted(GAME.terminal_histories)}')
print(f'  - 5 histoires terminales Kuhn standard (Zinkevich 2007 Table 1)')
print(f'  - Recollement naif : 2 cles modifiees (p1pb|0=Jack, p1pb|1=Queen -> call)')
print(f'  - Recollement safe : 0 cles modifiees (= Nash)')
print(f'  - EV(P1) Nash    = {ev_nash:+.4f} chips/deal (= -1/18, Kuhn 1950 / Zinkevich 2007)')
print(f'  - EV(P1) naif    = {ev_naive:+.4f} chips/deal (perte supplementaire {ev_naive-ev_nash:+.4f})')
print(f'  - EV(P1) safe    = {ev_safe:+.4f} chips/deal (Nash preserve)')
print(f'  - Exploitabilite Nash  = {exp_baseline:+.4f} chips/deal (par enumeration 64 strategies pures)')
print(f'  - Exploitabilite naive = {exp_naive:+.4f} chips/deal (P2 best response pure)')
print(f'  - Exploitabilite safe  = {exp_safe:+.4f} chips/deal (Nash preserve)')
print(f'  - Temoin adversarial : P2 best response exploite naive a {exp_naive-exp_safe:+.4f} chip/deal')
print()
print('Convention Kuhn 1950 / Zinkevich 2007 Table 1 :')
print('  - Ante = 1 chip par joueur, mise supplementaire = 1 chip, gain en chip net.')
print('  - Nash Kuhn : EV(P1) = -1/18 chip net, EV(P2) = +1/18 chip net (zero-sum).')
print('  - Exploitabilite >= 0 par construction (BR ne peut pas etre inferieure au Nash).')
GameTheory-13 : CFR vanilla + CFR+ + MCCFR (Zinkevich 2007, Bowling 2009)
GameTheory-13b (ce notebook) : safe subgame solving (Brown-Sandholm 2017)

Coherence interne (apres REPAIR #13480, Kuhn standard chip net) :
  - KuhnPoker.cards = [0, 1, 2] (J=0, Q=1, K=2)
  - Terminales : ['bb', 'bp', 'pbb', 'pbp', 'pp']
  - 5 histoires terminales Kuhn standard (Zinkevich 2007 Table 1)
  - Recollement naif : 2 cles modifiees (p1pb|0=Jack, p1pb|1=Queen -> call)
  - Recollement safe : 0 cles modifiees (= Nash)
  - EV(P1) Nash    = -0.0556 chips/deal (= -1/18, Kuhn 1950 / Zinkevich 2007)
  - EV(P1) naif    = -0.1667 chips/deal (perte supplementaire -0.1111)
  - EV(P1) safe    = -0.0556 chips/deal (Nash preserve)
  - Exploitabilite Nash  = +0.0000 chips/deal (par enumeration 64 strategies pures)
  - Exploitabilite naive = +0.2778 chips/deal (P2 best response pure)
  - Exploitabilite safe  = +0.0000 chips/deal (Nash preserve)
  - Temoin adversarial : P2 best response exploite naive a +0.2778 chip/deal

Convention Kuhn 1950 / Zinkevich 2007 Table 1 :
  - Ante = 1 chip par joueur, mise supplementaire = 1 chip, gain en chip net.
  - Nash Kuhn : EV(P1) = -1/18 chip net, EV(P2) = +1/18 chip net (zero-sum).
  - Exploitabilite >= 0 par construction (BR ne peut pas etre inferieure au Nash).
Retour au sommet