L'étude des jeux : attracteurs et minmax

(Sens direct) Pour $s\in A$ : par récurrence sur l'ordre d'entrée dans $A$. Si $s\in S_1$, le coup témoin mène dans $A$ « plus ancien » ; si $s\in S_2$, tout coup de $J_2$ mène dans $A$ plus ancien — dans les deux cas la partie progresse vers $F_1$ et l'atteint (l'ordre d'entrée décroît strictement : un variant, chapitre 10 !). (Réciproque) Pour $s\notin A$ : montrons que $J_2$ peut éviter $A$ pour toujours. Si $s\in S_1$ : aucun successeur de $s$ n'est dans $A$ (sinon la règle 2 y aurait mis $s$) — où que joue $J_1$, on reste hors de $A$. Si $s\in S_2$ : un successeur au moins est hors de $A$ (sinon règle 3) — $J_2$ le choisit. Rester hors de $A$, c'est ne jamais toucher $F_1$ : $s$ n'est pas gagnante. $\square$ (La preuve est constructive deux fois : elle fabrique la stratégie gagnante de $J_1$ et la stratégie d'évitement de $J_2$ — hors de l'attracteur, c'est l'adversaire qui détient la recette.)

$S_1=\{(t,J_1)\}$, $S_2=\{(t,J_2)\}$ pour $t=\mathrm{0..9}$, plus les finals $(10,J_2)\in F_1$ et $(10,J_1)\in F_2$. À rebours : $(9,J_1)$ et $(8,J_1)$ gagnantes (dire $10$) ; $(7,J_1)$ : les coups mènent à $(8,J_2)$ ou $(9,J_2)$… il faut d'abord traiter $J_2$ : $(9,J_2)$ et $(8,J_2)$ sont perdantes pour $J_1$ ? Non — raisonnons en « gagnant pour le joueur au trait » : depuis $8$ ou $9$, le joueur au trait dit $10$ et gagne ; depuis $7$, tout coup ($8$ ou $9$) donne le trait à l'adversaire en position gagnante : $7$ est perdante pour le trait. Puis $6,5$ gagnantes (jouer vers $7$), $4$ perdante, $3,2$ gagnantes, $1$ perdante, $0$ gagnante. Les perdantes au trait : $\{1,4,7\}$ — les totaux $\equiv 1(\mathrm{mod}3)$. $J_1$ part de $0$ : gagnante — stratégie : dire $1$, puis $4$, puis $7$, puis $10$ (compléter chaque coup adverse à $3$). (Le « gagnant pour le joueur au trait » est le bon référentiel des jeux symétriques : il divise les états par deux et révèle l'arithmétique — l'attracteur du cours fait le même calcul, mécaniquement, en gardant les deux joueurs distincts.)

Départ : $A=\{f\}$. Tour 1 : $e\in S_1$ a son successeur $f\in A$ — entre, témoin $e\to f$. Tour 2 : $d\in S_2$ : successeurs $e\in A$ mais $g\notin A$ — $J_2$ peut fuir vers $g$ : $d$ n'entre pas. $b\in S_2$ : successeurs $c,e$ — $e\in A$, $c\notin A$ : n'entre pas. $c\in S_1$ : successeur $d\notin A$ : n'entre pas. $a\in S_1$ : successeurs $b,d\notin A$ : n'entre pas. Stabilité : $A=\{f,e\}$. Positions gagnantes de $J_1$ : $e$ seule (avec $f$, déjà gagné) ; stratégie : depuis $e$, aller en $f$. Pour $a$ : non gagnante pour $J_1$ — et la preuve du cours dit mieux : $J_2$ possède une stratégie d'évitement (depuis $b$, jouer $c$ ; depuis $d$, jouer $g$) ; comme $g\in F_2$, on vérifierait par l'attracteur de $J_2$ que $a$ est en fait gagnante pour $J_2$ ($a\to d$ forcé d'y passer ? non : $a$ choisit $b$ ou $d$ — calcul : ${\mathrm{Attr}}_2(\{g\})$ : $d\in S_2$ a $g\in A_2$ — entre ; $c\in S_1$ : son unique successeur $d\in A_2$ — entre ; $b\in S_2$ : successeurs $c\in A_2$, $e\notin$ — n'entre pas ; $a\in S_1$ : $d\in A_2$ mais $a$ choisit : $a$ est de $J_1$, il faut tous ? Non — règle de $J_2$ inversée : pour ${\mathrm{Attr}}_2$, les états de $S_1$ exigent tous les successeurs : $b\notin A_2$ — $a$ n'entre pas). Bilan : $a$ n'est gagnante pour personne — match nul par évitements croisés : $J_1$ joue $a\to b$ (fuyant $d$), $J_2$ répond $b\to c$ (fuyant $e$), $c\to d$ forcé, $d\to g$… non : $d\in A_2$ donne la victoire à $J_2$ — recompte : depuis $c$, l'unique coup est $d$, où $J_2$ joue $g$ et gagne. Donc $J_1$ doit éviter $c$ : depuis $b$, c'est $J_2$ qui choisit $c$ ! La partie $a\to b\to c\to d\to g$ est forcée par $J_2$ : $a$ est gagnante pour $J_2$ — l'erreur était dans la règle : pour ${\mathrm{Attr}}_2$, un état de $S_2$ entre avec un successeur dans $A_2$ : $b$ entre (via $c$) ; puis $a$ ($S_1$, tous ses successeurs $b,d\in A_2$) entre. ${\mathrm{Attr}}_2=\{g,d,c,b,a\}$. (L'exercice, déroulé honnêtement avec sa fausse piste, enseigne l'essentiel : les rôles un/tous s'échangent quand on change de joueur, et l'intuition se trompe vite — c'est précisément pourquoi on calcule.)

(a) Le joueur au trait devant $n$ allumettes gagne si et seulement si $n\not\equiv 0(\mathrm{mod}4)$ ; stratégie : prendre $n\mathrm{mod}4$ (ramener à un multiple de $4$), puis compléter chaque prise adverse à $4$. (b) $n=21\equiv 1$ : gagnant, prendre $1$. $n=24\equiv 0$ : perdant — face à un adversaire parfait, aucun premier coup ne sauve ; en pratique on joue n'importe quoi et l'on guette la faute. $n=30\equiv 2$ : gagnant, prendre $2$. (c) Même architecture avec le module $k+1$ : positions perdantes $=$ multiples de $k+1$, stratégie « compléter à $k+1$ » — la preuve du cours se recopie mot pour mot. (Les jeux de soustraction sont l'arithmétique modulaire déguisée en jeu de société ; mais la morale algorithmique vaut plus que la formule : l'attracteur trouve aussi la réponse des variantes sans formule — interdire de prendre $2$, autoriser $\{1,3,4\}$… — où l'arithmétique élégante n'existe plus, exercice 22 de la banque.)

n = 21
S1 = {(r, 1) for r in range(n + 1)}
S2 = {(r, 2) for r in range(n + 1)}
succ = {}
for r in range(n + 1):
    for j, autre in ((1, 2), (2, 1)):
        succ[(r, j)] = [(r - p, autre) for p in (1, 2, 3) if p <= r]
# finals : (0, 1) -> J2 a pris la dernière ; (0, 2) -> J1 a gagné
A, strategie = attracteur(S1, S2, succ, {(0, 2)})

assert all(((r, 1) in A) == (r % 4 != 0) for r in range(n + 1))     # (a)
assert all(strategie[(r, 1)][0] % 4 == 0                            # (b)
           for r in range(1, n + 1) if r % 4 != 0)

Les deux assertions passent : le calcul retrouve la théorie — $11$ positions gagnantes au trait sur $\mathrm{0..21}$ pour $J_1$ côté $r\not\equiv 0$, et chaque coup témoin laisse un multiple de $4$. (Remarquer la symétrie : $(r,2)\in A$ exactement pour $r\equiv 0(\mathrm{mod}4)$ — les positions où $J_2$, au trait, est piégé ; l'arène double chaque position par le trait, et l'attracteur gère cette comptabilité sans qu'on y pense. Le banc théorie-contre-calcul est la validation reine des jeux : une formule et un algorithme génériques qui se confirment l'un l'autre, chapitre 1.)

import random
def jouer(n, coup_J1, coup_J2):
    r, j = n, 1
    while r > 0:
        p = coup_J1(r) if j == 1 else coup_J2(r)
        r, j = r - p, 3 - j
    return 3 - j                      # qui vient de prendre la dernière a gagné

parfait = lambda r: r % 4 if r % 4 != 0 else random.randint(1, min(3, r))
hasard  = lambda r: random.randint(1, min(3, r))
# 1000 parties depuis 21 : parfait (J1) contre hasard -> 1000 victoires J1
# parfait contre parfait depuis 21 -> J1 gagne toujours (21 non multiple de 4)
# depuis 24 : parfait contre parfait -> J2 gagne toujours ;
#             parfait (J1) contre hasard -> J1 gagne   99 % des parties !

Depuis $21$ : $1000/1000$ pour $J_1$ contre le hasard et contre le parfait — c'est la définition même de la stratégie gagnante, vérifiée expérimentalement : le « pour tout adversaire » ne souffre aucune exception. Depuis $24$ (position perdante) : contre le parfait, $J_1$ perd toujours ; contre le hasard, il gagne presque toujours ($\approx 99\%$) — car il suffit d'une faute adverse (ne pas compléter à $4$, probabilité $2/3$ par tour de l'éviter... au contraire : le hasard ne joue le bon coup qu'une fois sur trois) pour que $J_1$ récupère une position gagnante et ne la lâche plus. (La leçon dépasse le jeu : une position « perdante » ne l'est que contre la perfection — d'où la stratégie pratique des programmes en position difficile : jouer le coup qui maximise les chances de faute adverse, un critère que l'attracteur ignore et que les heuristiques, elles, savent encoder.)

Les finals deviennent : $(9,\cdot )$ nuls (personne ne gagne), $(10,J_2)\in F_1$, $(10,J_1)\in F_2$. Du point de vue du joueur au trait devant le total $t$ : depuis $8$, dire $10$ gagne (le nul de $9$ est un choix qu'on écarte) ; depuis $7$, les coups mènent à $8$ (adversaire gagnant) ou $9$ (nul) — la défaite est évitable mais pas la victoire : $7$ est nulle avec le bon jeu. Depuis $6$ : aller à $7$ (nulle pour l'adversaire au trait) ou $8$ (gagnante pour lui) — au mieux nul : $6$ nulle. Depuis $5$ : $6$ ou $7$, toutes deux nulles au trait adverse — $5$ nulle. Le calcul des attracteurs confirme et complète : $\mathrm{Attr}$ du joueur au trait $=\{8\}$ (et $10$) seulement — toute la zone $\mathrm{0..7}$ est nulle, car l'adversaire peut toujours dévier vers le refuge $9$. Verdict : depuis $0$, match nul — la règle du $9$ a tué le jeu : la zone nulle, une fois créée, contamine tout l'amont (chaque joueur préfère le refuge à la défaite). (C'est le mécanisme profond des grands jeux nuls — dames, morpion : il suffit d'un refuge accessible de partout pour que la perfection des deux côtés s'y réfugie ; les trois zones ne sont pas symétriques, le nul est contagieux.)

Position : $\times$ au centre (case $5$), $\circ$ au coin $1$. Lignes gagnables : une ligne l'est pour $\times$ si elle ne contient pas de $\circ$ (et réciproquement). Comptons après chaque coup de $\times$ (profondeur $1$ : on évalue directement, sans réponse adverse) : coin opposé ($9$) : $\times$ tient $5$ et $9$ — lignes sans $\circ$ contenant $\times$… l'heuristique du cours compte toutes les lignes gagnables : pour $\times$ : les $8$ lignes moins celles touchant $\circ$ ($3$ lignes passent par le coin $1$) $=5$ ; pour $\circ$ : $8$ moins les lignes touchant $\times$ ($4$ par le centre, $3$ par le coin $9$, moins la diagonale commune comptée deux fois : $6$) $=2$ — note $5-2=3$. Bord ($2$) : lignes de $\times$ : toujours $5$ ; lignes de $\circ$ : un bord n'appartient qu'à deux lignes (sa rangée et sa colonne), et le bord $2$ partage la colonne $2$-$5$-$8$ avec le centre : $8-(4+2-1)=3$ — note $5-3=2$. Coin ($3$) : trois lignes par un coin, la diagonale $3$-$5$-$7$ commune avec le centre : $8-(4+3-1)=2$ — note $3$, comme le coin $9$. La profondeur $1$ départage donc le bord (note $2$) des deux coins (note $3$) — mais laisse les deux coins à égalité entre eux : elle voit la géométrie statique, pas la menace, et c'est sur cette égalité coin/coin que porte la leçon : à profondeur $2$, le coup au coin $9$ révèle sa valeur (il crée une double attaque potentielle sur la diagonale) tandis qu'apparaissent les répliques de $\circ$. (L'expérience type du minmax : chaque profondeur supplémentaire « voit » un coup d'avance — les tactiques à $k$ coups exigent la profondeur $k$, et une heuristique fine ne remplace qu'imparfaitement un coup de calcul ; d'où la course à la profondeur de tous les programmes de jeu.)

def valeur(grille: tuple, memo: dict) -> int:
    if grille in memo:
        return memo[grille]
    g = gagnant(grille)                    # 'X', 'O' ou None
    if g == "X": v = 1
    elif g == "O": v = -1
    elif " " not in grille: v = 0          # plein sans gagnant : nul
    else:
        trait = "X" if grille.count("X") == grille.count("O") else "O"
        suites = [valeur(grille[:i] + (trait,) + grille[i+1:], memo)
                  for i in range(9) if grille[i] == " "]
        v = max(suites) if trait == "X" else min(suites)
    memo[grille] = v
    return v

memo = {}
v0 = valeur((" ",) * 9, memo)
assert v0 == 0                             # (a) le morpion parfait est NUL
# (b) len(memo) = 5478 positions atteignables distinctes

(a) Valeur $0$ : le morpion est un match nul — aucun des deux ne peut forcer la victoire, théorème calculé en une seconde. (b) $5478$ positions distinctes mémorisées ; sans mémoïsation, l'arbre déroule chaque partie : plusieurs centaines de milliers d'appels (le chevauchement vient des transpositions — des ordres de coups différents menant à la même grille) : la table de transposition des programmes d'échecs est exactement cette mémoïsation, en plus musclé. (c) En réévaluant les neuf premiers coups : tous donnent $0$ — face à la perfection, tout premier coup annule ; mais contre un adversaire faillible ils ne se valent pas (le centre crée quatre menaces, le bord deux), ce que la valeur exacte ne mesure pas. (Le minmax exact à mémo est l'attracteur, calculé en profondeur d'abord plutôt qu'à rebours — comparer les deux codes du chapitre est un exercice de structure : mêmes états, même trichotomie, deux ordres de parcours ; et le morpion est le plus grand jeu qu'on résoudra dans ce livre — le suivant de la liste, le puissance 4, a $4,5\cdot 10^{12}$ positions et fut un exploit de 1988.)

(a) Cible $21$ : le joueur au trait à $t$ gagne s'il peut atteindre $21$ ou laisser l'adversaire à une position perdante ; le calcul (attracteur ou la formule des jeux de soustraction transposée) donne : perdantes au trait $=$ les $t\equiv 21(\mathrm{mod}4)$, soit $t\equiv 1(\mathrm{mod}4)$ — depuis $0$, le premier joueur gagne en jouant vers $1$ ? Non : il doit laisser $\equiv 1$ : depuis $0$ jouer $+1\to 1$ ✓ — premier joueur théoriquement gagnant. (b) Mesures : à profondeur $1$, l'heuristique pousse à jouer $+3$ systématiquement (avancer le total) — un jeu naïf qu'un adversaire de profondeur $2$ punit dès la fin de partie (il voit la victoire adverse un coup à l'avance et l'évite quand c'est possible) ; profondeur $4$ bat profondeur $1$ et $2$ depuis toute position gagnante : la profondeur compense largement la médiocrité de $h$, car près de la fin, les feuilles de l'arbre sont des positions finales, évaluées exactement ($\pm 1$) — l'heuristique n'est consultée que loin du but. (c) Le jeu entier dure au plus $21$ coups, mais la perfection arrive bien avant la profondeur $21$ : dès que l'horizon atteint la prochaine position perdante adverse (distance $\le 4$), le minmax voit la mécanique des multiples et ne la lâche plus — en pratique, profondeur $4$ joue parfaitement depuis les positions gagnantes. (C'est la loi générale : la qualité d'un minmax $=$ exactitude près des finals $+$ heuristique au-delà de l'horizon ; allonger l'horizon convertit du jugement en calcul — et le coût explose en $b^p$ (chapitre 6, l'arbre à $b$ branches), d'où l'élagage alpha-bêta des programmes réels, qui gagne de la profondeur à coût égal sans changer le résultat.)

Modélisation : état $=$ (ensemble des cases libres, joueur au trait) ; coups : poser un domino $2\times 1$ vertical ($J_1$) ou horizontal ($J_2$) sur deux cases libres ; finals : le joueur au trait sans coup légal a perdu — c'est un jeu d'accessibilité où $F_1=\{$états de $S_2$ sans successeur$\}$ et symétriquement : la défaite par blocage se code en « atteindre les états où l'adversaire est paralysé ». Taille : $2^{16}$ ensembles de cases $\times 2$ traits $=131072$ états majorants — largement dans les cordes du calcul exact : minmax mémoïsé (ou attracteur, équivalent). Verdict mesuré : sur le $4\times 4$, le calcul rend la victoire au premier joueur (le vertical) avec un jeu parfait — environ $2400$ positions atteignables mémorisées (le majorant brut $2^{17}\approx 131000$ est très pessimiste), une poignée de secondes. Heuristique pour les grands plateaux : compter les coups disponibles de chaque joueur — $h=(\text{emplacements verticaux libres})-(\text{horizontaux libres})$ — la « mobilité », transposition directe de l'idée des lignes ouvertes du morpion ; mieux : compter les coups sûrs (les emplacements qu'aucun domino adverse ne peut détruire), l'heuristique des joueurs experts. Validation : le banc théorie-pratique de l'exercice 5 (l'IA exacte ne perd jamais depuis une position gagnante) et le tournoi des profondeurs de l'exercice 9 pour la version heuristique. (Le dossier rejoue toute la chaîne du semestre — modéliser (chapitre 12), résoudre exactement quand l'espace d'états le permet (attracteur, mémoïsation : chapitres 13 et 18), dégrader avec lucidité sinon (heuristique, profondeur : chapitre 14 et ce chapitre), valider au banc (chapitre 1) : quatre réflexes, un seul métier — et c'est sur cette boucle complète que le livre vous laisse.)