Minimax e alpha-beta

L’algoritmo che assume l’avversario peggiore possibile e poi, su quell’assunzione, calcola la mossa ottima — scheletro di ogni AI di gioco da Shannon ad AlphaZero, e cornice di adversarial training, GAN, red teaming.

Perché questo capitolo

Quando Deep Blue sconfigge Kasparov nel 1997, sotto al cofano gira un algoritmo che Claude Shannon aveva descritto in un paper del 1950, costruito sopra un teorema che John von Neumann aveva dimostrato nel 1928. Quando AlphaZero, nel 2018, rimpiazza vent’anni di chess engine ingegnerizzati a mano e impara a giocare in quattro ore di self-play partendo da zero, la struttura del suo motore decisionale è ancora ricognoscibile come parente del minimax: un albero di gioco, una valutazione alle foglie, una propagazione di valori verso la radice. Il dettaglio di chi espande quali nodi e di come si valuta una foglia è cambiato radicalmente; lo scheletro no.

Capire minimax serve per tre ragioni. La prima è storica: senza minimax non si capisce nulla della prima metà della storia dell’AI, dove “intelligenza artificiale” e “programma che gioca a scacchi” erano quasi sinonimi. La seconda è algoritmica: alpha-beta pruning è l’esempio paradigmatico di ottimizzazione che mantiene la correttezza dell’algoritmo originale potando l’esplorazione, e la sua dimostrazione di correttezza (Knuth-Moore 1975) è uno dei classici dell’analisi degli algoritmi. La terza è contemporanea: il framework $min_x max_y f(x, y)$ ricompare ovunque nell’AI moderna — come loss di GAN, come obiettivo di adversarial training, come schema concettuale del red teaming di LLM, come fondamento di MCTS in AlphaGo/AlphaZero, come Yao’s principle nell’analisi di algoritmi randomizzati. Chi non ha familiarità col minimax originale legge queste applicazioni come notazione esoterica; chi l’ha studiato le riconosce come variazioni su un tema.

Questo capitolo richiama il teorema minimax di von Neumann (già introdotto in Zero-sum, non-zero-sum), dedica il grosso dello spazio all’algoritmo minimax su alberi di gioco, sviluppa alpha-beta pruning con la sua analisi, descrive l’evoluzione storica fino a MCTS e AlphaZero, e collega il minimax alle sue manifestazioni in ML moderno.

Contesto

Il capitolo siede nella Parte sulla teoria dei giochi, dopo Cos’è un gioco in senso tecnico, Zero-sum, non-zero-sum e L’equilibrio di Nash. Quei capitoli hanno fissato il vocabolario (gioco, strategia, payoff, somma zero, equilibrio) e enunciato il teorema minimax di von Neumann come caso particolare dell’equilibrio di Nash in zero-sum a due giocatori. Qui il fuoco si sposta dal teorema all’algoritmo: come si calcola, in pratica, la mossa “minimax” in un gioco a informazione perfetta sequenziale come scacchi, dama, go. Il teorema dice che esiste un valore del gioco; l’algoritmo dice come avvicinarlo, e dove si rompe quando il gioco è troppo grande per essere risolto esattamente.

I personaggi principali, in ordine di apparizione:

John von Neumann (matematico ungherese-statunitense, 1903-1957): nel 1928, su Mathematische Annalen, dimostra il teorema minimax per zero-sum a due giocatori. Nel 1944, con Oskar Morgenstern, pubblica Theory of Games and Economic Behavior, fondazione della disciplina.
Alan Turing (matematico britannico, 1912-1954) e David Champernowne (economista britannico, 1912-2000): nel 1948 descrivono “Turochamp”, il primo algoritmo minimax per scacchi su carta. Turing lo eseguirà a mano nel 1952, perdendo contro un collega ma producendo la prima partita di un programma di scacchi documentata.
Claude Shannon (matematico statunitense, 1916-2001): nel 1950, in “Programming a Computer for Playing Chess” sul Philosophical Magazine, formalizza il framework completo: minimax, evaluation function alle foglie, distinzione tra Type A (esplorazione full-width a profondità fissa) e Type B (selettiva), stima del numero di posizioni di scacchi (10^120, “numero di Shannon”). Paper fondativo dell’AI di gioco.
Arthur Samuel (informatico statunitense, 1901-1990): nel 1959 pubblica “Some Studies in Machine Learning Using the Game of Checkers”, in cui un programma di dama impara i pesi della propria evaluation function via self-play. Origine pratica del termine “machine learning”.
John McCarthy (informatico statunitense, 1927-2011): cita per primo l’idea di alpha-beta nel 1956 al workshop di Dartmouth; viene poi sviluppata operativamente in vari progetti negli anni ‘60.
Donald Knuth (informatico statunitense, 1938) e Ronald Moore: nel 1975, in “An Analysis of Alpha-Beta Pruning” su Artificial Intelligence, danno la prima analisi formale rigorosa: dimostrano correttezza, calcolano complessità con perfect ordering ( $O(b^(d/2))$ ).
Albert Zobrist (informatico statunitense): nel 1969 introduce lo Zobrist hashing per indicizzare posizioni in transposition tables.
Rémi Coulom (informatico francese): nel 2006, in “Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search”, introduce MCTS nel programma di Go Crazy Stone. Conia il termine.
Levente Kocsis e Csaba Szepesvári (informatici ungheresi): nello stesso 2006 propongono UCT (Upper Confidence bounds applied to Trees) — l’applicazione di UCB1 alla selection di MCTS — dando garanzie asintotiche.
David Silver e il team DeepMind: nel 2016 con AlphaGo, nel 2017 con AlphaGo Zero, nel 2018 con AlphaZero, integrano MCTS con policy e value network apprese via self-play e battono i top human player a Go, scacchi, shogi.
Ian Goodfellow (informatico statunitense, 1985): nel 2014, in “Generative Adversarial Nets”, formula il training di GAN come minimax differenziabile $min_G max_D V(D, G)$ .

Sullo sfondo, due distinzioni di classe di affermazione che useremo costantemente:

TEOREMA: minimax di von Neumann (esistenza del valore in zero-sum); correttezza di alpha-beta (Knuth-Moore 1975).
FILIAZIONE: la linea minimax → alpha-beta → minimax + handcrafted eval (Deep Blue) → MCTS (Coulom) → MCTS + learned net (AlphaGo) → AlphaZero. Questa è discendenza storica documentata, non analogia: ogni passo cita e modifica il precedente.
ANALOGIA: minimax classico ↔ GAN, ↔ adversarial training, ↔ red teaming. Stesso schema concettuale min max, ma differenze tecniche importanti che marcheremo.

L’intuizione, due angoli

Primo angolo: assumi l’avversario peggiore

Sei davanti a una scacchiera. Devi scegliere una mossa. Come decidi?

Una strategia: per ogni tua mossa candidata, immagina l’avversario che ti risponde nel modo peggiore per te. Il “valore” di quella mossa, dal tuo punto di vista, è quello che resterà sul tavolo dopo la sua risposta peggiore. Tra le tue mosse, scegli quella il cui valore così calcolato è massimo. È l’idea del minimax in due parole: massimizza, sapendo che l’altro minimizza.

Si applica ricorsivamente. Per valutare cosa farebbe l’avversario, devi metterti nei suoi panni e applicare lo stesso ragionamento — solo che lì lui massimizza il proprio payoff, che in zero-sum significa minimizzare il tuo. E così via fino a una posizione terminale (vittoria, sconfitta, patta) dove il valore è ovvio.

Il vantaggio epistemico di questo approccio: garantisce un floor. Se gioco minimax, il payoff che ottengo contro un avversario qualsiasi è almeno quello che ottengo contro l’avversario ottimo, perché un avversario sub-ottimo gioca move che il min ha scartato. Il teorema minimax di von Neumann (richiamato da Zero-sum, non-zero-sum) garantisce che in zero-sum questo floor è anche, in strategie miste, il ceiling dell’avversario: la security strategy per uno è anche la migliore mossa contro un avversario altrettanto razionale. In zero-sum, paranoia e razionalità coincidono.

Secondo angolo: ricorsione su un albero

Cambia lente. Il gioco è un albero. La radice è la posizione corrente. Ogni nodo ha figli — le mosse legali da quella posizione. I nodi si alternano per “chi muove”: MAX (tu) e MIN (avversario). Le foglie sono posizioni terminali con un payoff numerico (per esempio +1 vittoria, 0 patta, -1 sconfitta dal punto di vista di MAX).

Definiamo il valore minimax V(n) di un nodo n:

se n è foglia: V(n) = utility(n)
se n è MAX: V(n) = max over children c di V(c)
se n è MIN: V(n) = min over children c di V(c)

V(radice) è il valore del gioco assumendo entrambi giochino ottimamente. La mossa ottima per MAX è quella che porta al figlio con V massimo.

Questa lente è operativa: traduce direttamente in pseudocodice ricorsivo. È la lente giusta per pensare a complessità, profondità, pruning. Ed è la lente che cambia di meno passando da Shannon ad AlphaZero: l’albero c’è sempre, è il meccanismo di esplorazione e valutazione che evolve.

Terzo angolo (opzionale): equilibrio in un gioco esteso

Per chi ha digerito Nash: minimax in un albero è un equilibrio di Nash subgame-perfect (Selten 1965) del gioco esteso a informazione perfetta. Backward induction su nodi MAX/MIN produce esattamente la strategia di equilibrio. In zero-sum a informazione perfetta non servono strategie miste alla radice: c’è sempre un equilibrio in pure (Zermelo 1913 lo aveva già osservato per scacchi). Questo è il motivo per cui l’algoritmo minimax non randomizza: non gli serve.

La meccanica

Pseudocodice base

La ricorsione minimax in versione esplicita MAX/MIN:

def minimax(node, depth, maximizing):
    if depth == 0 or terminal(node):
        return eval(node)
    if maximizing:
        v = -float('inf')
        for child in successors(node):
            v = max(v, minimax(child, depth - 1, False))
        return v
    else:
        v = +float('inf')
        for child in successors(node):
            v = min(v, minimax(child, depth - 1, True))
        return v

Tre osservazioni:

depth permette di fermare la ricerca a una profondità prestabilita. Necessario perché l’albero completo ha dimensione esponenziale.
eval(node) è la evaluation function: quando ci si ferma su una foglia non terminale, stima il valore minimax. È il cuore “intelligente” del programma.
Costo: $O(b^d)$ chiamate, dove b è il branching factor medio e d la profondità. Memoria $O(d)$ (DFS, lo stack). Per scacchi, $b ≈ 35$ . Per go, $b ≈ 250$ .

Negamax: stesso algoritmo, codice più asciutto

In zero-sum, utility per MIN è -utility(MAX). Possiamo eliminare il branch MAX/MIN:

def negamax(node, depth, color):
    if depth == 0 or terminal(node):
        return color * eval(node)
    v = -float('inf')
    for child in successors(node):
        v = max(v, -negamax(child, depth - 1, -color))
    return v

color è +1 per MAX, -1 per MIN, e si alterna a ogni livello. Risultato identico, codice più compatto. Knuth-Moore presentano alpha-beta in versione negamax. Nel resto del capitolo terremo la versione esplicita perché didatticamente più chiara.

Alpha-beta pruning

L’osservazione: durante la DFS, possiamo scartare interi sottoalberi se sappiamo già che il loro valore non influenzerà la decisione alla radice.

Manteniamo due bound lungo il path radice-nodo corrente:

alpha: il miglior valore già garantito a MAX su questo path (lower bound del valore radice dal punto di vista di MAX).
beta: il miglior valore già garantito a MIN su questo path (upper bound).

Invariante: $alpha <= V(radice) <= beta$ . Se durante l’esplorazione di un nodo $alpha >= beta$ , possiamo potare gli altri figli (cutoff).

def alphabeta(node, depth, alpha, beta, maximizing):
    if depth == 0 or terminal(node):
        return eval(node)
    if maximizing:
        v = -float('inf')
        for child in successors(node):
            v = max(v, alphabeta(child, depth - 1, alpha, beta, False))
            alpha = max(alpha, v)
            if alpha >= beta:
                break          # beta cutoff
        return v
    else:
        v = +float('inf')
        for child in successors(node):
            v = min(v, alphabeta(child, depth - 1, alpha, beta, True))
            beta = min(beta, v)
            if alpha >= beta:
                break          # alpha cutoff
        return v

Chiamata iniziale: alphabeta(root, D, -inf, +inf, True).

minimax tree with alpha-beta pruning, branches cut shown crossed out, alpha and beta bounds annotated at each node

TEOREMA (Knuth-Moore 1975)

alphabeta(root, D, -inf, +inf, True) ritorna lo stesso valore di minimax(root, D, True). Cioè il pruning non altera la correttezza.

L’idea della prova: per induzione sulla profondità, ogni nodo che alpha-beta poterebbe ha la proprietà che il suo contributo al valore della radice è già fissato dai bound. Un nodo MIN già con $v <= alpha$ non può migliorare la situazione di MAX (che ha già alpha), quindi MAX preferirà la mossa che ha portato ad alpha. Esplorare gli altri figli di MIN può solo abbassare ulteriormente v, irrilevante. Specularmente per cutoff alpha.

Complessità con perfect ordering

Se ad ogni nodo i figli vengono esaminati in ordine ottimale (best move first), il numero di foglie esplorate è $O(b^(d/2))$ — cioè raddoppia la profondità raggiungibile rispetto al minimax non potato. Questo è il celebre risultato $sqrt(b)$ di Knuth-Moore.

Intuizione: nel minimax pieno, ogni livello moltiplica per b. Con perfect ordering, alpha-beta esplora completamente solo metà dei livelli (i “PV nodes” o principal variation), gli altri livelli vengono scanditi solo per confermare il valore — un solo figlio per nodo. Risultato: $b * 1 * b * 1 * ... = b^(d/2)$ .

In pratica l’ordering perfetto non si conosce a priori, ma si stima con euristiche. Con random ordering Knuth-Moore mostrano che il guadagno medio resta sostanziale, attorno a $O(b^(3d/4))$ .

Move ordering

Ottenere ordering vicino al perfetto è la priorità dell’engine moderno:

Killer heuristic (Akl-Newborn 1977): a parità di profondità nell’albero, le mosse che hanno causato un cutoff in altri rami spesso lo causeranno anche qui. Si tengono 1-2 “killer moves” per livello.
History heuristic (Schaeffer 1989): score globale (from, to) che cresce ogni volta che la mossa causa un cutoff, decresce con il tempo. Generalizzazione robusta del killer.
MVV-LVA (Most Valuable Victim, Least Valuable Aggressor): per le catture, ordina prima quelle in cui un pezzo piccolo cattura un pezzo grosso. Spesso ottime.
PV move dalla iterazione precedente: in iterative deepening, la best move trovata a depth d-1 è quasi sempre ottima a depth d.

Transposition table

Posizioni raggiungibili da percorsi diversi (transposition) sono frequenti — cambiare l’ordine di due mosse innocue porta allo stesso stato. Un albero diventa di fatto un DAG. Una hash table indicizzata da una hash della posizione memorizza:

valore trovato
profondità della ricerca che l’ha calcolato
tipo di bound: EXACT, LOWER (alpha cutoff: il valore vero è ≥), UPPER (beta cutoff: il valore vero è ≤)
best move per ordering futuro

Lookup all’inizio di ogni chiamata: se la posizione è già stata cercata a profondità sufficiente, si riusa il valore (con cura sui bound per non rompere alpha-beta).

L’indice è la Zobrist hash (Zobrist 1969). Per ogni coppia (piece, square) si pre-genera un numero random a 64 bit. La hash di una posizione è XOR di tutti i contributi presenti. Aggiornamento incrementale a costo costante: una mossa = XOR-out vecchio (piece, from), XOR-in (piece, to), XOR-out eventuale catturato. Conflitti rari, ma possibili: i bug da hash collision sono un classico problema dei chess engine.

Iterative deepening

Anziché ricercare a profondità fissa D da subito, si cerca a depth 1, poi 2, poi 3, e così via finché c’è tempo. Apparentemente è uno spreco — si rifà lavoro dei livelli bassi — ma:

la transposition table riusa quasi tutto il lavoro precedente
il move ordering migliora drasticamente: la best move a depth d-1 diventa la prima provata a depth d, e di solito resta best, dando perfect ordering al primo nodo
supporta time control: si può interrompere a tempo e ritornare la best move della depth completata
i livelli profondi dominano in costo, quindi rifare i livelli bassi è quasi gratis ( $b^d$ cresce molto più di $b + b^2 + ... + b^(d-1)$ )

Heuristic evaluation function

Quando la ricorsione si ferma a profondità D su una foglia non terminale, serve un valore numerico. La evaluation function $eval: position -> R$ lo fornisce. Componenti tipiche per gli scacchi (Shannon 1950 le elenca quasi tutte):

eval = w1 * (white_material - black_material)
     + w2 * (white_mobility - black_mobility)
     + w3 * king_safety_diff
     + w4 * pawn_structure_diff
     + w5 * center_control_diff
     + ...

Storicamente i pesi $w_i$ erano hand-tuned dall’autore dell’engine, spesso dopo migliaia di partite di test. Samuel 1959 li imparava da self-play con regole TD-like (precorritore di TD-learning di Sutton). Negli anni 2000, alcuni engine hanno automatizzato la tuning con metodi tipo Texel (gradient descent sulla logistic loss tra valutazione predetta e risultato della partita). Stockfish nel 2020 ha integrato NNUE (Efficiently Updatable Neural Network, Nasu 2018), una piccola rete neurale come eval, mantenendo alpha-beta classico per la search. AlphaZero ha sostituito sia eval che style di search (vedi sotto).

Quiescence search

Fermarsi a depth D esatta crea l’horizon effect: se al nodo terminale c’è una cattura pendente, l’eval registra material count senza considerare che alla mossa dopo (oltre l’orizzonte) un pezzo è perduto. Soluzione: quando si raggiunge la depth limit, si entra in quiescence search, una sotto-ricerca che espande solo catture (e check, eventualmente) finché la posizione è “tranquilla”. Solo allora si valuta. Costo aggiuntivo modesto, miglioramento drammatico della qualità di gioco.

Richiamo: il teorema minimax di von Neumann

Per chiudere la meccanica, un richiamo. In un gioco a somma zero a due giocatori finito, in strategie miste, vale (TEOREMA, von Neumann 1928):

max_{σ_1} min_{σ_2} u_1(σ_1, σ_2) = min_{σ_2} max_{σ_1} u_1(σ_1, σ_2) = v

v è il valore del gioco. L’ordine di mossa non conta: chiunque sa giocare maximin si garantisce v. In giochi a informazione perfetta sequenziali questo si rafforza in un risultato classico (Zermelo 1913): esiste una strategia ottima in pure, e l’algoritmo minimax la trova per backward induction. Nei giochi non a informazione perfetta servono strategie miste; lì l’algoritmo standard non è minimax bensì CFR — Counterfactual Regret Minimization (Zinkevich et al. 2007), che però è fuori scope qui.

Esempi

Esempio 1: minimax esaustivo a mano su tic-tac-toe mid-game

Consideriamo la posizione (X muove; X è MAX, +1 = X vince, -1 = O vince, 0 = patta):

 X | O | X
-----------
   | O |
-----------
   |   |

Mosse di X: 4 caselle vuote (1, 6, 7, 8, 9 in numerazione 1-9 con 1=alto-sinistra, …, 9=basso-destra; ignoriamo le occupate). Per ciascuna analizziamo l’albero.

X gioca 8 (basso-centro): blocca il “tre in colonna” di O sulla seconda colonna.

 X | O | X
-----------
   | O |
-----------
   | X |

Ora tocca a O (MIN). O ha 5 caselle vuote: 4, 6, 7, 9. (Considero 4 mosse, eliminando 9 simmetrico a 7 per brevità manuale.)

O gioca 4 (sinistra-centro): ora X muove, posizione

 X | O | X
-----------
 O | O |
-----------
   | X |

O minaccia 6 (per 4-5-6 no, 5 è suo; per 4-7 no). In realtà O minaccia di chiudere la riga centrale 4-5-6. X deve giocare 6. Dopo X-6:

 X | O | X
-----------
 O | O | X
-----------
   | X |

X ha colonna 3 (3-6) ma serve anche 9. Tocca O. O gioca 7 (per chiudere 1-4-7? 1 è X. Per chiudere 7-5-3? 3 è X). O non ha minacce immediate; gioca difensivamente 9 per bloccare diagonale 3-5-7? 3 è X, 5 è O. Diagonale 3-5-7 mista → no minaccia. Strategicamente la posizione è patta forzata: a mano si vede che le caselle restanti 7, 9 portano comunque a 0. Valore: 0.

O gioca 6 (destra-centro): minaccia chiudere riga 2 (4-5-6)? no, 4 è vuoto. Minaccia colonna 3 (3-6-9)? 3 è X. La sua mossa più forte è 6 per attaccare la riga 2 con la coppia 5-6, richiede ancora 4. X risponde 4 (blocca riga 2 e crea proprie minacce). La continuazione si chiude in patta. Valore: 0.
O gioca 7 (basso-sinistra): minaccia diagonale 3-5-7 (3 è X), no. Minaccia colonna 1 (1-4-7, 1 è X), no. Mossa neutra. X gioca 9 per minaccia diagonale 3-5-7 no, 1-5-9 (1 X, 5 O), no. X gioca 4 attaccando riga 2 (X1, ?, X3? no, riga 2 è 4-5-6). Patta forzata. Valore: 0.
O gioca 9 (basso-destra): simmetrico a 7. Patta. Valore: 0.

min su risposte di O = 0. Quindi V(X gioca 8) = 0.

X gioca 7 (basso-sinistra): ora minaccia la colonna 1 (1-4-7, 1 X, 4 vuoto, 7 X). O deve bloccare 4. Ma O ha anche la propria minaccia: la colonna 2 (2-5-8, 2 O, 5 O, 8 vuoto), una mossa O su 8 vincerebbe. O gioca 8 (vince sua minaccia, ignorando la nostra). Dopo O-8: O ha tris in colonna 2. X perde. Valore: -1.

X gioca 9 (basso-destra): minaccia diagonale 1-5-9? 5 è O. Minaccia colonna 3 (3-6-9, 3 X, 6 vuoto, 9 X). O deve bloccare 6. Ma anche qui O minaccia 8 per chiudere colonna 2. O gioca 8 → vince. Valore: -1.

X gioca 6 (destra-centro): minaccia colonna 3 (3-6-9, 3 X, 6 X, 9 vuoto): mossa successiva su 9 vince. O deve bloccare 9. Ma O ha la sua minaccia su 8. O gioca 8 → vince. Valore: -1.

X gioca 4 (sinistra-centro): minaccia riga 2 (4-5-6, 5 O), niente. Minaccia colonna 1 (1-4-7, 1 X, 4 X, 7 vuoto). O blocca? No, O gioca 8 e vince. Valore: -1.

max su mosse di X = max(0, -1, -1, -1, -1) = 0. L’unica mossa che salva la patta è X-8. Senza minimax, una scelta naïve “io creo le mie minacce” porta X a perdere.

Questo conto a mano rende concreto cosa fa minimax: identifica la sola mossa che resiste alla risposta peggiore, anche quando sembra meno aggressiva.

Esempio 2: implementazione tic-tac-toe con alpha-beta

Tic-tac-toe è abbastanza piccolo (5478 stati distinti) per essere risolto esattamente. Ecco un’implementazione compatta in Python:

WIN_LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]

def winner(b):
    for (i, j, k) in WIN_LINES:
        if b[i] != '.' and b[i] == b[j] == b[k]:
            return b[i]
    return None

def terminal(b):
    return winner(b) is not None or '.' not in b

def utility(b):
    w = winner(b)
    return 1 if w == 'X' else -1 if w == 'O' else 0

def alphabeta(b, alpha, beta, max_player):
    if terminal(b):
        return utility(b), None
    best_move = None
    if max_player:
        v = -2
        for i in range(9):
            if b[i] == '.':
                nb = b[:i] + 'X' + b[i+1:]
                vc, _ = alphabeta(nb, alpha, beta, False)
                if vc > v:
                    v, best_move = vc, i
                alpha = max(alpha, v)
                if alpha >= beta:
                    break
        return v, best_move
    else:
        v = 2
        for i in range(9):
            if b[i] == '.':
                nb = b[:i] + 'O' + b[i+1:]
                vc, _ = alphabeta(nb, alpha, beta, True)
                if vc < v:
                    v, best_move = vc, i
                beta = min(beta, v)
                if alpha >= beta:
                    break
        return v, best_move

# uso: dalla posizione iniziale, X muove
v, m = alphabeta('.' * 9, -2, 2, True)
print(v, m)   # 0, 0 -- patta forzata, X gioca in alto-sinistra

Trenta righe scarse, e abbiamo un giocatore di tic-tac-toe ottimo. Su una macchina moderna gira in meno di un secondo. Cambiando utility e successori, lo stesso scheletro vale per dama (con depth limit + eval), connect-4, gomoku, breakthrough.

Esempio 3: Deep Blue vs AlphaZero — due modi opposti di costruire un motore di scacchi

Confrontiamo due programmi che hanno entrambi raggiunto il top mondiale, separati da vent’anni e da una filosofia opposta.

Deep Blue (1997, IBM). Hardware dedicato: 30 PowerPC + 480 chip VLSI custom per la generazione di mosse e la valutazione. Velocità: 100-200 milioni di posizioni al secondo. Algoritmo: alpha-beta + iterative deepening + transposition table + extensions selettive (singular extensions, check extensions, recapture extensions). Evaluation function: circa 8000 feature hand-engineered, con pesi tarati da grandmaster e da auto-play. Profondità tipica: 12-14 ply nominali, fino a 30-40 con extensions. Apertura: book di milioni di partite umane. Endgame: tablebase a 5-pezzi. Risultato: batte Garry Kasparov 3.5-2.5 nel maggio 1997, primo match a tempo regolamentare contro un campione del mondo in carica.

AlphaZero (2018, DeepMind). Hardware: 5000 TPU di prima generazione per il training, 16 TPU per la partita. Algoritmo: MCTS guidato da una rete neurale residuale che produce due output — una policy $p(a|s)$ (distribuzione sulle mosse) e un value $v(s) ∈ [-1, 1]$ (stima del payoff atteso). Niente alpha-beta. Niente transposition table esplicita. Niente eval hand-coded — la value head è l’eval. Niente apertura book — la policy net incorpora pattern di apertura impliciti dal self-play. Niente knowledge umana scacchistica oltre alle regole del gioco. Training: 700.000 step di gradient descent su dati generati da self-play di una versione precedente del modello. Tempo totale di training: 9 ore per scacchi. Profondità tipica al play: ~80.000 simulazioni MCTS per mossa, tipicamente ~10 ply ma estese fortemente in linee critiche. Risultato: batte Stockfish 8 (engine alpha-beta tradizionale di top livello al 2017) 28 vittorie, 0 sconfitte, 72 patte su 100 partite con time control match.

Cosa è cambiato (FILIAZIONE):

componente	Deep Blue	AlphaZero
albero di gioco	sì	sì
esplorazione	full-width (alpha-beta)	selettiva (MCTS guidato da policy)
pruning	alpha-beta + extensions	implicito via prior policy
evaluation alle foglie	hand-engineered, ~8000 feature	rete neurale value head
apertura	opening book umano	implicito nella policy
dominio knowledge	grandmaster consultants	nessuna oltre regole
training	feature engineering manuale	self-play + gradient descent

L’osservazione strutturale: lo scheletro è lo stesso. Si esplora un albero, si valutano foglie, si propagano valori verso la radice scegliendo la mossa migliore. Alpha-beta in Deep Blue e MCTS-PUCT in AlphaZero sono due strategie diverse di esplorazione dello stesso oggetto matematico. Quello che cambia è chi sceglie di guardare dove (full-width vs selective via policy), e come si valuta una posizione non terminale (handcrafted vs learned). FILIAZIONE: AlphaZero discende, storicamente e tecnicamente, dal minimax di Shannon-Knuth, attraverso MCTS di Coulom-Kocsis-Szepesvári; ANALOGIA: AlphaZero non è minimax (la sua ricerca non è full-width né puntualmente min/max), ma ne mantiene lo scheletro concettuale.

flowchart LR
  subgraph DeepBlue["Deep Blue (1997)"]
    DB1[Posizione] --> DB2[Alpha-Beta search<br/>+ Iterative Deepening<br/>+ Transposition Table]
    DB2 --> DB3[Eval handcrafted<br/>~8000 feature]
    DB3 --> DB2
    DB2 --> DB4[Mossa migliore]
  end
  subgraph AlphaZero["AlphaZero (2018)"]
    AZ1[Posizione] --> AZ2[MCTS<br/>+ PUCT selection<br/>+ Dirichlet noise]
    AZ2 --> AZ3[Policy/Value net<br/>residual NN]
    AZ3 --> AZ2
    AZ2 --> AZ4[Mossa migliore]
    AZ5[Self-play] --> AZ6[Gradient descent] --> AZ3
  end

Figura 3 — pipeline a confronto Deep Blue (alpha-beta + iterative deepening + transposition table + eval handcrafted) vs AlphaZero (MCTS + PUCT + policy/value net + self-play)

Applicazioni pratiche

Game AI

Tutto il filone classico chess/checkers/othello/connect-4 vive su minimax + alpha-beta. Stockfish, il più forte engine open-source di scacchi, è alpha-beta + NNUE. Komodo, Houdini, Leela (Lc0, MCTS+net come AlphaZero) compongono il top contemporaneo. In Go il regno è di MCTS+nets (KataGo, Leela Zero). In poker invece il framework è altro (CFR), che è discendente concettuale ma non algoritmico.

Adversarial training

PGD (Madry et al. 2018) formula la difesa contro adversarial examples come problema di sella:

min_θ E_(x, y) [max_{δ : ||δ|| <= ε} L(f_θ(x + δ), y)]

L’inner max trova la perturbazione peggiore entro un budget ε; l’outer min addestra il modello a essere robusto a questa perturbazione. È minimax stocastico differenziabile. ANALOGIA solida: stesso schema min max, ma differenze importanti:

l’inner max è approssimato da gradient ascent proiettato (PGD), non risolto esattamente
entrambi gli “attori” condividono i gradienti del modello, non sono indipendenti
non c’è “valore del gioco” in senso teorico, solo equilibrio del training

GAN (Goodfellow 2014)

min_G max_D V(D, G) = E_x [log D(x)] + E_z [log(1 - D(G(z)))]

Generator e discriminator giocano un gioco a somma zero (concettuale; in pratica si usano loss non-saturating per training stability). All’equilibrio teorico il discriminator è 1/2 ovunque e il generator riproduce la distribuzione dei dati. ANALOGIA con minimax classico, ma:

il problema è continuo, non discreto
gradient descent simultaneo non è best-response dynamics; può ciclare attorno all’equilibrio invece di convergere (Mertikopoulos et al. 2018)
in pratica, GAN training usa una sequenza di approssimazioni che non corrispondono né a minimax né a Nash classico, e gli equilibri trovati sono spesso “instabili” o “mode-collapsed”

Si veda gan (in preparazione) per il dettaglio.

Red teaming e jailbreak di LLM

Un attacker cerca prompt che inducono un modello allineato a produrre output indesiderato; un defender (modello + classificatori) cerca di rifiutare. Strutturalmente è minimax: $max_attacker min_defender$ di una utility “harmfulness”. Differenze rispetto al minimax classico:

spazio degli attacchi enorme e discreto (sequenze di token)
utility mal definita (cos’è “harmful” varia con politiche, contesti, giurisdizioni)
il defender non ha gradiente diretto sull’attacker, e viceversa solo se black-box queries sono ammesse
iterativo, asimmetrico, con discontinuità (un singolo prompt rotto può sbloccare un’intera famiglia di output)

Vedi red-teaming (in preparazione) e jailbreak (in preparazione).

Robust optimization / Distributionally robust learning

$min_θ max_{P in U} E_P [L(θ, X)]$ , dove U è un set di distribuzioni “ammissibili”. L’apprendimento minimizza il worst-case su un’incertezza distribuzionale. Tipicamente U è una palla di Wasserstein o KL attorno alla distribuzione empirica. Schema minimax stocastico applicato all’incertezza, non a un avversario in senso letterale.

Yao’s principle

Yao (1977) usa il teorema minimax di von Neumann per analizzare algoritmi randomizzati: la complessità del miglior algoritmo randomizzato sul peggior input vale come la complessità del miglior algoritmo deterministico sulla peggior distribuzione di input. È minimax fuori dal contesto di gioco — un esempio della pervasività dello schema.

Tree-of-Thoughts in LLM reasoning

Yao et al. (2023) propongono di esplorare ragionamenti LLM come albero, con valutazione dei nodi via il modello stesso. È cugino di MCTS sui token, e parente lontano del minimax. Vedi tree-of-thoughts (in preparazione).

Dove si rompe

Esponenziale resta esponenziale

Anche con perfect ordering, alpha-beta è $O(b^(d/2))$ . Per scacchi ( $b ≈ 35$ ) raddoppiare la profondità da 14 a 28 richiede $b^7 ≈ 64.000$ volte il compute, irrealistico anche con hardware Deep Blue. Per Go ( $b ≈ 250$ ) anche b^(d/2) è proibitivo: 50 ply richiederebbero $250^25 ≈ 10^60$ operazioni. È il motivo per cui Go è rimasto inaccessibile al minimax classico per cinquant’anni e ha richiesto MCTS + nets.

Heuristic eval è il vero bottleneck

In giochi posizionali complessi (Go, ma anche scacchi posizionali e shogi) i fattori che determinano una “buona” posizione sono numerosi, sottili, dipendenti dal contesto. Hand-engineering produce eval mediocri. Per Go, decenni di tentativi non hanno prodotto eval comparabile a giocatori dilettanti seri. La rete neurale di AlphaGo/AlphaZero è la risposta: eval imparata da self-play. Lezione generale: in alpha-beta la qualità dell’eval domina la qualità del giocatore quando la depth è già “abbastanza”.

Informazione perfetta richiesta

Il framework minimax/alpha-beta assume ogni giocatore conosca lo stato completo del gioco. Cade in poker (carte private), bridge (mani nascoste), kriegspiel (scacchi alla cieca), Stratego (pezzi nascosti). In quei domini si lavora con information sets — gruppi di stati indistinguibili — e algoritmi diversi: CFR, Counterfactual Regret Minimization (Zinkevich et al. 2007), ha portato Libratus (Brown-Sandholm 2017) e Pluribus (2019) a battere i top pro di poker heads-up e 6-max no-limit hold’em rispettivamente. CFR converge a un equilibrio di Nash approssimato in giochi a somma zero a informazione imperfetta, ma non è minimax in senso ricorsivo classico.

Avversario perfettamente razionale

Minimax assume MIN giochi ottimamente. Contro umani imperfetti, modellare gli errori avversari (“opponent modeling”) batte il minimax puro. Nel poker il concetto è centrale (exploitative vs game-theoretic optimal play). Nei scacchi è meno critico al top livello, ma negli engine “anti-human” (programmi che simulano un avversario umano debole per allenare studenti) è esplicito. La generalizzazione si chiama Bayes-Nash equilibrium con priori sull’avversario, lontano dal minimax pulito.

No stocasticità nativa

Backgammon ha dadi: dopo la mossa di MAX, il dado decide quali mosse di MIN siano possibili. Il modello standard è expectimax: l’albero alterna nodi MAX, MIN e CHANCE (i lanci di dado), e ai nodi CHANCE si fa il valore atteso sui figli pesati per probabilità.

V(chance) = sum_outcome p(outcome) * V(child_outcome)

TD-Gammon (Tesauro 1995) combinò expectimax con una rete neurale come eval, addestrata via TD-learning su milioni di partite di self-play. Ottenne livello di top campione mondiale. Storicamente è il precursore concettuale di AlphaGo/AlphaZero — vedi TD-Gammon.

L’inner max negli adversarial training non è ottimo

PGD approssima $max_δ L(θ, x+δ, y)$ con gradient ascent locale proiettato. Non è il vero max. Conseguenza: l’outer min sta ottimizzando un surrogato. La “robustezza” garantita è quindi solo robustezza contro PGD, non contro attaccanti più forti. Per garanzie certificate servono strumenti aggiuntivi (interval bound propagation, randomized smoothing, certified defenses Wong-Kolter 2018), che però sono lontani dal minimax classico.

Red teaming senza utility ben definita

Nei contesti di alignment, l’utility “harmfulness” è soggettiva e contestuale. Il minimax min defender max attacker harmfulness si scontra con: cosa misura harmfulness esattamente? Categorizzato a mano? Da un classificatore (che a sua volta è imperfetto)? Il framework formale è instabile. In pratica si usano cicli iterativi di red team / blue team con metriche operative (success rate degli attacchi noti, rate di rifiuti su test set), non equilibri minimax in senso stretto.

Gradient descent simultaneo non converge a Nash

Anche in giochi semplici come zero-sum bilineare, $min_x max_y x^T A y$ con gradient descent simultaneo non converge: oscilla attorno al saddle point (Mertikopoulos et al. 2018, Daskalakis et al. 2018). Il GAN training eredita questo problema. Servono algoritmi diversi (extra-gradient, optimistic mirror descent, follow-the-regularized-leader) per garantire convergenza. La conseguenza pratica è che “minimax loss” in deep learning non implica automaticamente un equilibrio raggiungibile.

Equilibri multipli e general-sum

Minimax assume zero-sum. In general-sum (somma non costante) non c’è “il” valore del gioco; possono esistere molti equilibri di Nash con payoff diversi, e la nozione di “best response all’avversario peggiore” diventa o conservativa o malposta. Vedi L’equilibrio di Nash per il quadro.

Collegamenti

Cos’è un gioco in senso tecnico — vocabolario di base che minimax presuppone (gioco, strategia, payoff).
Zero-sum, non-zero-sum — il teorema minimax di von Neumann nasce qui; minimax algorithm presuppone zero-sum.
L’equilibrio di Nash — minimax è caso particolare di Nash (zero-sum 2-player); la backward induction su nodi MAX/MIN produce un equilibrio subgame-perfect del gioco esteso.
TD-Gammon — expectimax + rete neurale, primo grande successo di RL+NN, antesignano concettuale di AlphaZero.
Deep Blue 1997 — il caso d’uso paradigmatico dell’alpha-beta industriale.
AlphaGo 2016 — la transizione da minimax-style ad MCTS guidato da nets.
monte-carlo-tree-search (in preparazione, Parte VI) — la trattazione dedicata di MCTS, UCT, e varianti.
self-play (in preparazione) — il meccanismo di apprendimento in AlphaZero, che chiude il loop minimax/RL.
gan (in preparazione) — minimax differenziabile, con caveat di convergenza.
adversarial-examples (in preparazione) — l’inner max di PGD, dove minimax incontra robust ML.
jailbreak (in preparazione), red-teaming (in preparazione) — minimax come schema concettuale per security di LLM.
tree-of-thoughts (in preparazione) — search-based reasoning negli LLM, parente di MCTS sui token.

Per andare oltre

Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4ª ed.), capitolo 5 “Adversarial Search and Games”. Trattazione moderna completa di minimax, alpha-beta, MCTS, expectimax, giochi a informazione imperfetta. Punto di partenza accademico standard.
Knuth, D. E., & Moore, R. W. (1975). “An Analysis of Alpha-Beta Pruning”. Artificial Intelligence, 6(4), 293-326. Il paper fondativo dell’analisi formale di alpha-beta. Da leggere per capire perché $O(b^(d/2))$ non è magia.
Shannon, C. E. (1950). “Programming a Computer for Playing Chess”. Philosophical Magazine, 41(314), 256-275. Cinque pagine che fondano l’AI di gioco. Si legge in mezz’ora e contiene già metà delle idee dei cinquant’anni successivi.
Silver, D., et al. (2018). “A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play”. Science, 362(6419), 1140-1144. AlphaZero. Mostra come MCTS + policy/value net + self-play sostituiscano l’intero stack alpha-beta + handcrafted eval.
Coulom, R. (2006). “Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search”. Computers and Games. Il paper che introduce MCTS. Elegante e compatto, base per tutta la letteratura successiva su tree search non-minimax.