[Search-07] Recyclage d'un stash : variante misere du Nim et minimax memoise — livrer ou refuser

[myia-ai-01]

Constat

Un stash ancien de la machine ai-01, recycle dans le cadre de jsboige/roo-extensions#3827 (ancre refs/stash-archive/ai01/coursia/22-2026-04-21, commit 57bdd86c39, 21/04/2026), porte deux contenus pedagogiques absents de main pour Search/Part1-Foundations/Search-07-MCTS-And-Beyond.ipynb :

1. La variante misere du Nim (le joueur qui prend la derniere allumette perd). main porte la variante normale (« Le joueur qui prend la derniere allumette GAGNE ») ; la misere n'y apparait pas (grep -ci misere = 0 sur le notebook). Le stash l'accompagne d'une interpretation : les positions perdantes basculent de n % 4 == 0 a n % 4 == 1, et MCTS redecouvre la solution d'un jeu resolu sans la surpasser.
2. Un minimax memoise (_minimax_memo) qui enumere les actions optimales d'une position, utilise par l'analyse de convergence de l'exemple 7. Absent de main (grep -c _minimax_memo = 0).

Le reste de l'ancre est deja sur main sous une autre forme : le correctif de signe MCTS (#7876, convention negamax) et les exemples 6 et 7 (#8994, #9202).

L'ancre n'existe que dans le depot local d'ai-01 (aucune ref refs/stash-archive/* sur origin). Les trois cellules utiles sont donc recopiees ci-dessous, telles qu'elles sont dans l'ancre, pour qu'une lane d'une autre machine puisse trancher.

Ce qui est demande

Une decision de la lane qui porte la serie Search, ecrite ici :

• livrer : integrer la variante misere et/ou le minimax memoise dans Search-07 par une PR (notebook re-execute avec ses sorties, C.1/C.2, ligne Grain:), en adaptant les cellules au code actuel du notebook (le moteur MCTS de main a change de convention de signe depuis le stash) ;
• ou refuser par ecrit, avec le motif (par exemple : la variante normale suffit a l'objectif pedagogique, ou la misere ferait doublon avec un autre notebook).

Les deux sorties ferment cette issue. Reporter la decision en une ligne sur jsboige/roo-extensions#3827, qui attend ce verdict pour son recompte final.

Contenu de l'ancre (a lire, pas a copier tel quel)

Cellule de code n° 25 de l'ancre

# Exemple resolu 7 : Analyse de convergence MCTS
# Mesure comment MCTS converge vers l'action Minimax optimale avec le nombre
# d'iterations.
#
# On utilise une position ou le signal est tres fort : X a deux alignements
# sur la ligne du haut (cases 0 et 1), O au centre. X doit JOUER LA CASE 2
# pour gagner immediatement ; toute autre action rate la victoire. Le signal
# est maximal car les rollouts depuis la case 2 retournent +1 systematiquement
# (victoire triviale), alors que les autres donnent un melange.


def _minimax_memo(jeu, etat, joueur_max='MAX', _cache={}):
    """Minimax avec memoisation (cle : (etat, joueur_max)). Permet d'enumerer
    rapidement les actions optimales de n'importe quelle position."""
    key = (etat, joueur_max)
    if key in _cache:
        return _cache[key]
    if jeu.est_terminal(etat):
        _cache[key] = (jeu.utilite(etat, joueur_max), None)
        return _cache[key]
    actions = jeu.actions(etat)
    if jeu.joueur(etat) == joueur_max:
        best = (float('-inf'), None)
        for a in actions:
            v, _ = _minimax_memo(jeu, jeu.resultat(etat, a), joueur_max)
            if v > best[0]:
                best = (v, a)
    else:
        best = (float('+inf'), None)
        for a in actions:
            v, _ = _minimax_memo(jeu, jeu.resultat(etat, a), joueur_max)
            if v < best[0]:
                best = (v, a)
    _cache[key] = best
    return best


def analyser_convergence(jeu, etat, iterations_list, repetitions=30, seed=0):
    """Pour chaque taille d'iterations, repete MCTS et collecte :
    - taux_optimal_%  : % de fois ou MCTS choisit une action Minimax-optimale
    - valeur_moyenne  : valeur MCTS moyenne (devrait converger vers Minimax)
    - temps_moyen_s   : temps moyen d'une recherche

    Chaque repetition utilise une graine RNG distincte derivee de `seed` pour
    rendre l'analyse reproductible tout en exposant la variance naturelle de MCTS.
    """
    v_opt, _ = _minimax_memo(jeu, etat)
    actions_optimales = set()
    for a in jeu.actions(etat):
        v_a, _ = _minimax_memo(jeu, jeu.resultat(etat, a))
        if v_a == v_opt:
            actions_optimales.add(a)

    donnees = []
    for n_iter in iterations_list:
        succes = 0
        valeurs, temps = [], []
        for rep in range(repetitions):
            random.seed(seed * 10_000 + rep)
            mcts = MCTS(jeu)
            t0 = time.time()
            action, valeur = mcts.recherche(etat, iterations=n_iter)
            temps.append(time.time() - t0)
            valeurs.append(valeur)
            if action in actions_optimales:
                succes += 1
        donnees.append({
            'iterations': n_iter,
            'taux_optimal_%': round(100.0 * succes / repetitions, 1),
            'valeur_moyenne': round(float(np.mean(valeurs)), 4),
            'temps_moyen_s': round(float(np.mean(temps)), 4),
        })
    return pd.DataFrame(donnees), v_opt, actions_optimales


def tracer_convergence(df, v_ref, actions_opt, n_actions_total,
                       titre="TicTacToe (X a 2-en-ligne top, doit jouer la case 2)"):
    """Trois sous-graphiques : taux d'action optimale, valeur moyenne, temps."""
    fig, axes = plt.subplots(1, 3, figsize=(15, 4.2))

    axes[0].plot(df['iterations'], df['taux_optimal_%'], 'o-',
                 color='tab:blue', linewidth=2, markersize=7)
    axes[0].axhline(100.0, color='grey', linestyle='--', alpha=0.5)
    taux_random = 100.0 * len(actions_opt) / n_actions_total
    axes[0].axhline(taux_random, color='tab:red', linestyle=':', alpha=0.7,
                    label=f'Choix uniforme ({taux_random:.0f}%)')
    axes[0].set_xlabel('Iterations MCTS (log)')
    axes[0].set_ylabel("Taux d'action optimale (%)")
    axes[0].set_xscale('log')
    axes[0].set_ylim(-5, 105)
    axes[0].set_title(f"Actions optimales : {sorted(actions_opt)}")
    axes[0].grid(alpha=0.3, which='both')
    axes[0].legend(loc='lower right')

    axes[1].plot(df['iterations'], df['valeur_moyenne'], 's-',
                 color='tab:orange', linewidth=2, markersize=7)
    axes[1].axhline(v_ref, color='tab:red', linestyle='--', alpha=0.7,
                    label=f'Minimax = {v_ref}')
    axes[1].set_xlabel('Iterations MCTS (log)')
    axes[1].set_ylabel("Valeur MCTS estimee")
    axes[1].set_xscale('log')
    axes[1].set_title("Valeur estimee vs reference")
    axes[1].grid(alpha=0.3, which='both')
    axes[1].legend()

    axes[2].plot(df['iterations'], df['temps_moyen_s'], '^-',
                 color='tab:green', linewidth=2, markersize=7)
    axes[2].set_xlabel('Iterations MCTS (log)')
    axes[2].set_ylabel("Temps moyen (s, log)")
    axes[2].set_xscale('log')
    axes[2].set_yscale('log')
    axes[2].set_title("Temps de calcul (echelle log-log)")
    axes[2].grid(alpha=0.3, which='both')

    plt.suptitle(f'Convergence de MCTS sur {titre}', y=1.02, fontsize=13)
    plt.tight_layout()
    plt.show()


# --- Execution : X a deux alignements sur la ligne du haut, doit jouer la case 2 ---
jeu = TicTacToe()
# Grille 3x3 :  X | X | .
#               . | O | .
#               . | . | .
# X a jouer. L'action gagnante est la case 2 (complete la ligne 0).
grille = ('X', 'X', ' ',
          ' ', 'O', ' ',
          ' ', ' ', ' ')
etat_depart = (grille, 'X')

iterations_list = [10, 30, 100, 300, 1000]
df_conv, v_ref, actions_opt = analyser_convergence(
    jeu, etat_depart, iterations_list, repetitions=30, seed=42)

print("Etat de depart : X a deux cases alignees en haut (0 et 1), O au centre.")
print(f"Actions possibles pour X : {sorted(jeu.actions(etat_depart))}")
print(f"Valeur Minimax optimale  : {v_ref}  (X peut gagner immediatement)")
print(f"Action(s) optimale(s)    : {sorted(actions_opt)}  <- completer la ligne 0")
print(f"Baseline aleatoire       : {100.0 / len(jeu.actions(etat_depart)):.0f}%")
print()
display(df_conv)
tracer_convergence(df_conv, v_ref, actions_opt,
                   n_actions_total=len(jeu.actions(etat_depart)))

Cellule de code n° 28 de l'ancre

# Exemple resolu 6 : MCTS sur le jeu de Nim (misere, 1-3)
# Regles :
#  - on part de N allumettes
#  - chaque joueur prend 1, 2 ou 3 allumettes
#  - le joueur qui prend la DERNIERE allumette PERD (version misere)
#
# Theorie : les P-positions (perdantes pour le joueur qui doit jouer) sont
#           n = 1, 5, 9, 13, ... c-a-d n % 4 == 1.
# Strategie optimale : laisser a l'adversaire un n tel que n % 4 == 1.
#                      Si on est deja dans une P-position, tout coup perd -
#                      on joue 1 par convention et on espere une erreur.


class NimGame(JeuSommeNulle):
    """Jeu de Nim misere : N allumettes, prendre 1-3, le dernier PERD."""

    def __init__(self, n_allumettes: int = 15):
        self.n_init = n_allumettes

    def etat_initial(self):
        # (n_restantes, joueur_courant)
        return (self.n_init, 'MAX')

    def joueur(self, etat):
        return etat[1]

    def actions(self, etat):
        n, _ = etat
        return [k for k in (1, 2, 3) if k <= n]

    def resultat(self, etat, action):
        n, j = etat
        prochain = 'MIN' if j == 'MAX' else 'MAX'
        return (n - action, prochain)

    def est_terminal(self, etat):
        return etat[0] == 0

    def utilite(self, etat, joueur):
        # Convention : le joueur courant a l'etat terminal n'a pas pris la
        # derniere allumette (c'est l'adversaire qui vient de la prendre).
        # Donc en misere, le joueur courant GAGNE.
        n, courant = etat
        assert n == 0, "utilite n'est defini que sur un etat terminal"
        return 1.0 if joueur == courant else -1.0


def strategie_optimale_nim(etat):
    """Strategie optimale pour le Nim misere (1-3) :
    laisser a l'adversaire n ≡ 1 (mod 4).

    - Si prise = (n - 1) % 4 > 0, on la joue (on atteint une P-position).
    - Sinon on est deja dans une P-position (n ≡ 1 mod 4) : on joue 1 par defaut.
    """
    n, _ = etat
    if n == 1:
        return 1  # coup force, on perdra
    prise = (n - 1) % 4
    return prise if prise > 0 else 1


# --- Verification de NimGame : une partie manuelle ---
jeu = NimGame(n_allumettes=5)
e = jeu.etat_initial()
assert e == (5, 'MAX') and jeu.actions(e) == [1, 2, 3]
# MAX joue optimal : depuis 5 (P-position pour MAX) il perdra. Prend 1 -> (4, MIN)
# MIN joue optimal : depuis 4 laisse 1 a MAX -> prend 3 -> (1, MAX)
# MAX force de prendre 1 -> (0, MIN) terminal. MAX a pris la derniere -> MAX perd.
e1 = jeu.resultat(e,  strategie_optimale_nim(e))         # (4, MIN)
e2 = jeu.resultat(e1, strategie_optimale_nim(e1))        # (1, MAX)
e3 = jeu.resultat(e2, strategie_optimale_nim(e2))        # (0, MIN)
assert jeu.est_terminal(e3)
assert jeu.utilite(e3, 'MAX') == -1.0, "MAX a pris la derniere => MAX perd"
assert jeu.utilite(e3, 'MIN') ==  1.0
print("NimGame verifie sur partie manuelle depuis n=5 : MAX perd (P-position pour MAX).")
print()


# --- MCTS vs strategie optimale ---
def jouer_nim(n_init: int, iterations_mcts: int, mcts_commence: bool) -> str:
    """Joue une partie NimGame(n_init) : MCTS contre la strategie optimale.
    Retourne 'MCTS' ou 'OPT' selon le gagnant."""
    jeu = NimGame(n_init)
    mcts = MCTS(jeu)
    etat = jeu.etat_initial()
    mcts_joueur = 'MAX' if mcts_commence else 'MIN'
    while not jeu.est_terminal(etat):
        if etat[1] == mcts_joueur:
            action, _ = mcts.recherche(etat, iterations=iterations_mcts)
        else:
            action = strategie_optimale_nim(etat)
        etat = jeu.resultat(etat, action)
    # Le joueur courant (non-preneur de la derniere) gagne en misere
    gagnant_role = etat[1]
    return 'MCTS' if gagnant_role == mcts_joueur else 'OPT'


random.seed(123)
parties = 10
tailles = [7, 9, 11, 13]    # 9 et 13 sont P-positions (perdantes si MCTS commence)
iterations_a_tester = [50, 500]

rows = []
for n_init in tailles:
    p_pos = (n_init % 4 == 1)
    for mcts_iter in iterations_a_tester:
        wins_mcts_first = sum(
            1 for _ in range(parties)
            if jouer_nim(n_init, mcts_iter, mcts_commence=True) == 'MCTS'
        )
        rows.append({
            'n_init': n_init,
            'type': 'P-position (MCTS commence -> doit perdre)' if p_pos
                    else 'W-position (MCTS commence -> doit gagner)',
            'mcts_iter': mcts_iter,
            f'MCTS wins / {parties}': wins_mcts_first,
        })

df_nim = pd.DataFrame(rows)
print("Benchmark : MCTS (joueur MAX qui commence) vs strategie optimale (joueur MIN)")
print("=" * 72)
display(df_nim)

Cellule markdown n° 29 de l'ancre

### Interpretation : MCTS face a une strategie optimale sur Nim

**Ce qu'on attend theoriquement**

Les P-positions du Nim misere (1-3) sont `{1, 5, 9, 13, 17, ...}` soit `n ≡ 1 (mod 4)`. Un joueur dans une P-position perd contre un adversaire parfait, quel que soit son choix. Un joueur dans une W-position gagne s'il joue `(n-1) % 4` allumettes.

| `n_init` | type | MCTS qui commence | resultat attendu (vs OPT parfait) |
| :------: | :--- | :---------------- | :-------------------------------- |
| 7  | W | MAX | MCTS gagne s'il joue bien (prendre 2 -> laisse 5) |
| 9  | **P** | MAX | MCTS **perd** quel que soit son coup |
| 11 | W | MAX | MCTS gagne s'il joue bien (prendre 2 -> laisse 9) |
| 13 | **P** | MAX | MCTS **perd** quel que soit son coup |

**Lecture du tableau**

- Sur les **P-positions** (9, 13), MCTS ne peut pas gagner : la colonne "MCTS wins" doit etre proche de 0, quelle que soit la taille des iterations. C'est la confirmation empirique d'un theoreme de theorie des jeux, pas une faiblesse de MCTS.
- Sur les **W-positions** (7, 11), MCTS doit converger vers 100 % de victoires quand on augmente les iterations. Avec 50 iterations, il peut encore se tromper ; avec 500, il joue typiquement parfaitement.
- Si vous voyez MCTS gagner une partie en P-position, c'est que **l'adversaire a du cafouiller** -- or ici `strategie_optimale_nim` ne cafouille pas, donc 0 victoires en P-position est le seul resultat correct.

**Lecons a tirer**

1. **Un jeu fini a information complete et sans chance est mathematiquement resolu** : connaitre les P-positions donne la reponse exacte. MCTS redecouvre cette solution empiriquement, il ne la surpasse pas.
2. **La qualite de MCTS borde par le plafond du jeu** : sur un jeu resolu, aucun nombre d'iterations ne sauve une position perdue. Cela rappelle que MCTS est un **outil d'estimation**, pas une source de magie combinatoire.
3. **Dans un tournoi reel** (humains, bots imparfaits), MCTS peut gagner depuis une P-position car l'adversaire finit par jouer un coup sous-optimal. C'est pourquoi les moteurs d'echecs modernes (Stockfish, Leela) combinent une evaluation tactique forte *et* des rollouts MCTS pour capitaliser sur les erreurs adverses.
4. **Misere vs normal** : prendre le temps de verifier quelle convention de gain s'applique. La meme regle de prise avec la convention "le dernier gagne" donnerait les P-positions `{0, 4, 8, ...}` (multiples de 4) -- d'ou l'erreur repandue dans les enonces classiques.

Critere de sortie

• PR mergee qui porte le contenu retenu, ou refus motive poste ici ;
• une ligne de verdict sur [CLAUDE-AI-01] Recyclage des stashes ancrés — 77 ancres / 8 dépôts (suite #3147) roo-extensions#3827.

See jsboige/roo-extensions#3827

[jsboige]

Grain: DEEP/notebook-python — lane myia-po-2025:CoursIA — prev: DEEP/notebook-python #17960
[CLAIMED] lane myia-po-2025:CoursIA — comparer le Nim normal et misère dans Search-07 avec mesure MCTS, après contrôle du notebook actuel ; paths: MyIA.AI.Notebooks/Search/Part1-Foundations/Search-07-MCTS-And-Beyond.ipynb

[jsboige]

Décision : livrer la variante misère et un témoin minimax adapté au code actuel dans la PR #17967 (commit f647610). Papermill a exécuté 16/16 cellules sans erreur ; le minimax de convergence du stash, distinct de cette comparaison et dépendant d’un cache partagé/convention de signe, n’est pas repris dans cette PR. Le critère de sortie « PR mergée » reste à satisfaire.

[jsboige]

[CLAIMED-AMEND] lane myia-po-2025:CoursIA -- paths: MyIA.AI.Notebooks/Search/Part1-Foundations/Search-07-MCTS-And-Beyond.ipynb, scripts/notebook_tools/twin_pairs.d/search-07-mcts-and-beyond.yaml, scripts/notebook_tools/twin_pairs.d/search-07-mcts-and-beyond/** -- attestation de la variante misère Python-only : le jumeau C# conserve le Nim normal et le pont OpenSpiel, sans prétendre à une équivalence de contenu totale.

[jsboige]

[CLAIMED] lane myia-po-2027:CoursIA — décision + livraison : variante misère Nim (classe + benchmark vs stratégie optimale + interprétation) et minimax mémoisé (analyse de convergence), adaptés au moteur MCTS negamax actuel, notebook re-exécuté

[jsboige]

Décision de la lane : LIVRER — PR #17991 ouverte (tête 5e2a9db). Les deux contenus sont intégrés : variante misère (exemple résolu + benchmark vs stratégie optimale : 0/10 sur les P-positions 9 et 13, 10/10 sur les W-positions à 500 itérations — la théorie confirmée empiriquement) et minimax mémoïsé (ensemble des actions optimales + baseline choix uniforme dans l'analyse de convergence). Cellules adaptées au moteur negamax actuel ; pyspiel 2.0.2 installé (règle F) pour la re-exécution complète. Verdict déposé sur jsboige/roo-extensions#3827.

[jsboige]

[INFO] candidate-delivered — la livraison demandée est sur main : PR #17967 (lane myia-po-2025:CoursIA, MERGÉE 2026-09-26T19:14Z) porte la variante misère du Nim avec témoin minimax exact (valeur_misere lru_cache, contrôle n = 1 à 16). Verdict « LIVRER » déposé sur jsboige/roo-extensions#3827 (c.5849257647). Un complément est en cours sur PR #17991 (cellule d'analyse de convergence : minimax mémoïsé, ensemble d'actions optimales, baseline uniforme) — partie du stash que #17967 n'a pas couverte. Fermeture réservée au coordinateur.

[jsboige]

[CLAIMED] lane myia-po-2023:CoursIA — Lot D #18140 : dossier de fermeture [CLOSURE PREFLIGHT] sur cette issue.

[jsboige]

[CLOSURE PREFLIGHT]
schema: 1
lane: myia-po-2023:CoursIA
issue: 17937
verdict: CLOSE
acceptance:

• decision ecrite (livrer ou refuser) -> LIVRER decide par deux lanes : c.15:22Z (po-2025) et c.19:37Z (po-2027, PR feat(search,#17937): Search-07 -- analyse de convergence par minimax memoise (complement #17967) #17991 fermee sans merge -- livraison parallele devancee)
• livraison sur main de la variante misere et du temoin minimax adapte -> commit d2575da (PR feat(search): comparer Nim normal et misère avec témoin minimax #17967 MERGED 26/09 19:14Z) sur Search-07-MCTS-And-Beyond.ipynb : misere x20 occurrences, minimax x14, verifie grep firsthand sur main ; [INFO] candidate-delivered c.19:54Z trace la ou la livraison est passee (reponse au drapeau du lot : feat(search): comparer Nim normal et misère avec témoin minimax #17967, pas feat(search,#17937): Search-07 -- analyse de convergence par minimax memoise (complement #17967) #17991)
• report de la decision sur [CLAUDE-AI-01] Recyclage des stashes ancrés — 77 ancres / 8 dépôts (suite #3147) roo-extensions#3827 -> commentaire du 2026-09-26T15:22:52Z sur cette issue : Verdict Search-07 / CoursIA [Search-07] Recyclage d'un stash : variante misere du Nim et minimax memoise — livrer ou refuser #17937 : variante misere + minimax exact adaptes livres en PR feat(search): comparer Nim normal et misère avec témoin minimax #17967
  residue: none
  open-prs: 0
  comments-reviewed: 7
  [/CLOSURE PREFLIGHT]

-- Dossier tiers (lane myia-po-2023:CoursIA), verification firsthand sur main + dans jsboige/roo-extensions#3827.

[jsboige]

Note gate : le dossier ci-dessus ne peut pas rendre CLOSE tant que #18142 (fix organ cross-repo) n'est pas merge -- scripts/check_closure_dossier.py crashe sur les references croisées roo-extensions#3827 -> CoursIA #17937 (reproduit : UNKNOWN, GraphQL Could not resolve to a PullRequest with the number of 17937). C est exactement le sujet de #18142, dont le dossier READY est pose. Le dossier de fond reste valable ; ai-01 peut arbitrer sur la substance ou attendre le merge du fix.

[jsboige]

[CLOSURE PREFLIGHT]
schema: 1
lane: myia-po-2023:CoursIA
issue: 17937
verdict: CLOSE
acceptance:

• decision ecrite (livrer ou refuser) -> LIVRER decide par deux lanes : c.15:22Z (po-2025) et c.19:37Z (po-2027, PR 17991 fermee sans merge -- livraison parallele devancee)
• livraison sur main de la variante misere et du temoin minimax adapte -> commit d2575da (PR feat(search): comparer Nim normal et misère avec témoin minimax #17967 MERGED 26/09 19:14Z) sur Search-07-MCTS-And-Beyond.ipynb : misere x20 occurrences, minimax x14, verifie grep firsthand sur main ; [INFO] candidate-delivered c.19:54Z trace la ou la livraison est passee (reponse au drapeau du lot : feat(search): comparer Nim normal et misère avec témoin minimax #17967, pas 17991)
• report de la decision sur jsboige/roo-extensions3827 -> commentaire du 2026-09-26T15:22:52Z sur cette issue : Verdict Search-07 / CoursIA 17937 : variante misere + minimax exact adaptes livres en PR feat(search): comparer Nim normal et misère avec témoin minimax #17967
  residue: none
  open-prs: 0
  comments-reviewed: 9
  [/CLOSURE PREFLIGHT]

-- Dossier tiers (lane myia-po-2023:CoursIA), verification firsthand sur main + dans jsboige/roo-extensions3827.

[myia-ai-01]

Décision : livrer. #17967 (MERGED) a apporté la variante misère du Nim et le témoin minimax dans Search-07-MCTS-And-Beyond.ipynb (vérifié sur main). La décision est aussi reportée sur jsboige/roo-extensions#3827.

Fermée sur le dossier tiers [CLOSURE PREFLIGHT] (gate check_closure_dossier.py : CLOSE), après une lecture de la PR livrante et une vérification ponctuelle sur main par ai-01. Aucune PR ouverte ne référence cette issue.