Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search

Un gioco come problema di ricerca, l’albero di gioco, il minimax, la potatura alfa-beta, le funzioni di valutazione e MCTS — sul tris, dove si può calcolare tutto, e la strada da Deep Blue ad AlphaZero.

14 minuti Matěj Žalmánek 2026-10-15

Serie Basi di IA Parte 22 di 52

1. Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
2. Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
3. Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
4. Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
5. Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
6. Funzioni e applicazioni: perché ogni modello di IA è una funzione
7. Logica e dimostrazioni: le regole con cui si ragiona nell’IA
8. Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
9. Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
10. Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
11. Discesa del gradiente: come impara un modello
12. Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
13. Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
14. Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
15. Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
16. Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
17. Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
18. Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
19. Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
20. Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
21. Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
22. Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
23. Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
24. Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
25. Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
26. Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
27. Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
28. Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
29. Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
30. Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
31. Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
32. Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
33. Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
34. Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
35. Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
36. Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
37. Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
38. Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
39. Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
40. Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
41. Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
42. Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
43. Prompt, contesto e RAG: come dare a un modello le informazioni giuste
44. Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
45. Reti generative avversarie (GAN): il falsario contro il detective
46. Modelli di diffusione: come il rumore puro diventa un’immagine
47. Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
48. Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
49. Policy gradient e PPO: imparare direttamente la politica
50. Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
51. Programmare con agenti IA: incarico, test e controllo
52. Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare

Programma completo della serie 52 di 83 argomenti pubblicati

Nel labirinto della parte precedente l’omino era solo. Il mondo stava fermo e ogni mossa portava dove doveva portare. In un gioco, invece, di fronte a te siede qualcuno che vuole l’esatto contrario — e a ogni tua mossa risponde con quella che ti fa più male. Cercare un percorso verso l’obiettivo non basta più: devi cercare una strategia che regga contro ogni risposta. Scacchi, dama e go sono stati per decenni il metro di misura dell’intelligenza artificiale, e gli algoritmi di questa parte stanno dietro sia a Deep Blue sia ad AlphaGo.

Riprende le parti Ricerca nello spazio degli stati e Grafi e alberi.

1. Un gioco come problema di ricerca

Definizione — gioco a due giocatori

Un gioco è una settupla Γ = (S, s₀, giocatore, A, T, K, U), dove

• S, s₀, A(s) e T sono gli stati, lo stato iniziale, le azioni e la funzione di transizione come in un problema di ricerca,
• giocatore : S → {MAX, MIN} dice chi deve muovere in uno stato,
• K ⊆ S è l’insieme degli stati terminali — lì il gioco finisce,
• U : K → ℝ è l’utilità di uno stato terminale dal punto di vista del giocatore MAX.

Il gioco è a somma zero: ciò che MAX guadagna, MIN lo perde, quindi l’utilità di MIN è −U. I giocatori si alternano, le mosse sono deterministiche ed entrambi vedono l’intero stato (informazione perfetta).

La differenza rispetto alla ricerca è fondamentale. La soluzione non è più un percorso — quello non lo scegli tu, perché una mossa su due la fa l’avversario. La soluzione è una strategia: una regola che dice come rispondere a ogni mossa che l’avversario può giocare.

2. L’albero di gioco

Definizione — albero di gioco

L’albero di gioco è un albero radicato la cui radice è s₀ e i cui figli di un nodo s sono i successori {T(s, a) : a ∈ A(s)}. Le foglie sono gli stati terminali. I nodi in cui muove MAX li disegniamo come triangoli con la punta in alto, i nodi MIN con la punta in basso.

Se il gioco ha fattore di ramificazione b e dura al massimo m mosse, l’albero ha fino a b^m foglie.

Il tris su una griglia 3 × 3 è un gioco piccolo, eppure il suo albero ha 549 946 nodi e 255 168 foglie — tante sono le partite diverse che si possono giocare. Le posizioni diverse, invece, sono solo 5 478: alla stessa posizione si arriva con molti ordini di mosse. Gli scacchi hanno un fattore di ramificazione intorno a 35 e una partita dura decine di mosse; nel 1950 Claude Shannon stimò il loro albero in 10¹²⁰ partite. Il go, con un fattore di ramificazione intorno a 250, è ancora molti ordini di grandezza più in là. L’intero albero lo percorriamo quindi solo nei giochi piccoli — in quelli grandi dobbiamo imparare quali rami tralasciare.

3. Minimax

Definizione — valore minimax

Il valore minimax di uno stato s è

• MM(s) = U(s), se s ∈ K,
• MM(s) = max_{a ∈ A(s)} MM(T(s, a)), se giocatore(s) = MAX,
• MM(s) = min_{a ∈ A(s)} MM(T(s, a)), se giocatore(s) = MIN.

La mossa ottima del giocatore MAX nello stato s è argmax_a MM(T(s, a)).

Il nodo MIN a sinistra tra le foglie 4, 6 e 9 sceglie 4, quello centrale tra 2, 7 e 8 sceglie 2, quello destro tra 5, 3 e 9 sceglie 3. MAX nella radice sceglie poi tra 4, 2 e 3 e gioca la mossa a sinistra con valore 4. Nota che il ramo destro nasconde un nove — solo che MAX non ci arriverà mai, perché MIN al suo posto giocherebbe il tre.

Teorema — che cosa garantisce il minimax

Se MAX gioca in modo ottimo, ottiene almeno MM(s₀) contro qualsiasi strategia di MIN. Se anche MIN gioca in modo ottimo, MAX ottiene esattamente MM(s₀).

Il minimax percorre l’albero in profondità: tempo O(b^m), memoria O(b · m).

4. Il minimax sul tris

Il tris 3 × 3 è abbastanza piccolo perché il minimax ne percorra l’intero albero. Il risultato lo conosce chiunque ci abbia giocato per più di qualche minuto: il valore minimax della griglia vuota è 0 — se entrambi giocano senza errori, è sempre pareggio. Più interessante è che cosa dice il minimax di una posizione concreta. Muove X (MAX) e in ogni casella libera c’è il valore della mossa in quella casella:

Vince una sola mossa — il centro. Con essa X crea una forchetta: minaccia di completare sia la riga centrale sia la diagonale e O non può bloccarle entrambe. La mossa in basso al centro mantiene il pareggio. Le altre tre mosse sembrano innocue, ma perdono: O risponde con una forchetta tutta sua. Una persona dovrebbe ragionarci sopra; il minimax lo calcola e basta.

def minimax(board):
    end = winner(board)                 # "X", "O", "draw" oppure None
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    values = [minimax(play(board, move)) for move in empty_squares(board)]
    return max(values) if to_move(board) == "X" else min(values)

5. Potatura alfa-beta

Il minimax percorre l’intero albero, anche se metà è inutile. Guarda di nuovo il ramo centrale: la prima foglia ha dato 2. MIN quindi in quel ramo ottiene 2 o meno — e MAX ha già in tasca il ramo sinistro con valore 4. Qualunque siano le altre due foglie, MAX nel ramo centrale non ci andrà. Non ha nemmeno bisogno di guardarle.

Definizione — alfa-beta

La ricerca in profondità porta con sé due limiti:

• α — il valore più alto che MAX si è già assicurato da qualche parte lungo il percorso dalla radice (all’inizio −∞),
• β — il valore più basso che si è assicurato MIN (all’inizio +∞).

In un nodo MAX, dopo ogni figlio si pone v ← max(v, valore del figlio) e α ← max(α, v); in un nodo MIN analogamente v ← min(…) e β ← min(β, v). Non appena α ≥ β, i figli rimanenti del nodo vengono potati — non si esplorano.

Teorema. L’alfa-beta restituisce nella radice lo stesso valore del minimax. Con il miglior ordine possibile delle mosse esplora solo O(b^m/2) nodi.

L’alfa-beta è arrivata allo stesso risultato — MAX gioca a sinistra e ottiene 4 — ma ha valutato solo 6 foglie su 9. Nel ramo centrale ha potato due foglie subito dopo il due, in quello destro una dopo il tre. Per questo nel nodo MIN potato c’è solo il limite «≤ 2» e «≤ 3»: il valore esatto non lo conosciamo, e non ci serve.

Sul tris la differenza è più drammatica. Il minimax completo dalla griglia vuota visita 549 946 posizioni, l’alfa-beta con lo stesso ordine delle mosse solo 18 297 — circa trenta volte meno — e restituisce lo stesso zero. L’esponente m/2 nel teorema significa che nello stesso tempo vedi due volte più in profondità. Per questo l’ordine delle mosse conta così tanto: i programmi di scacchi provano per prime le catture e le mosse che sono state buone la volta precedente.

def alphabeta(board, alpha=-inf, beta=inf):
    end = winner(board)
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    maximizing = to_move(board) == "X"
    v = -inf if maximizing else inf
    for move in empty_squares(board):
        h = alphabeta(play(board, move), alpha, beta)
        if maximizing:
            v = max(v, h); alpha = max(alpha, v)
        else:
            v = min(v, h); beta = min(beta, v)
        if alpha >= beta:
            break                          # potatura: il resto del ramo non cambia nulla
    return v

6. Profondità limitata e funzione di valutazione

Nemmeno l’alfa-beta percorre l’albero degli scacchi fino alla fine della partita. I programmi reali quindi cercano solo fino a una profondità fissa e la posizione in cui si fermano la stimano.

Definizione — minimax a profondità limitata

Una funzione di valutazione E : S → ℝ stima MM(s) e per gli stati terminali coincide con U. Di solito è una somma pesata di caratteristiche della posizione: E(s) = w₁f₁(s) + … + w_nf_n(s).

Minimax fino alla profondità d: MM_d(s) = E(s), se s ∈ K oppure d = 0; altrimenti il massimo, rispettivamente il minimo, dei MM_d−1 dei successori.

La profondità limitata ha la sua trappola: l’effetto orizzonte. Quando la ricerca si ferma a metà di uno scambio di pezzi — hai appena preso la donna, l’avversario te la riprende alla mossa successiva —, la funzione di valutazione vede solo la prima metà e sopravvaluta la posizione. I programmi si difendono continuando a esplorare le posizioni «instabili» finché non si stabilizzano. E poiché non sanno mai quanto tempo hanno, cercano con l’approfondimento iterativo della parte precedente: profondità 1, 2, 3, … finché il tempo non finisce. I risultati dei passaggi meno profondi servono inoltre come ordine delle mosse per quelli più profondi — e l’alfa-beta poi pota molto di più.

7. Monte Carlo tree search

La funzione di valutazione per gli scacchi è stata messa a punto per decenni. Per il go scriverne una non riusciva — una posizione che sembra tranquilla può essere persa venti mosse dopo. Monte Carlo tree search (MCTS) rinuncia del tutto alla funzione di valutazione. Invece di stimare la posizione, la gioca fino in fondo: a caso, molte volte, e guarda quanto spesso è andata bene.

Definizione — un’iterazione di MCTS

L’albero cresce dalla radice s₀. Ogni nodo i ricorda il numero di visite n_i e la somma dei risultati w_i dal punto di vista del giocatore che ha mosso verso il nodo (vittoria 1, pareggio ½, sconfitta 0). L’iterazione ha quattro passi:

1. Selezione — dalla radice scendi ripetutamente nel figlio con il valore UCT più alto, finché non incontri un nodo che non ha ancora tutti i figli.
2. Espansione — aggiungigli un figlio per una mossa non ancora provata.
3. Simulazione — dal nuovo nodo gioca la partita fino in fondo con mosse casuali, fino a uno stato terminale.
4. Retropropagazione — a tutti i nodi sul percorso di ritorno alla radice somma n ← n + 1 e aggiungi a w il risultato della partita.

Quando il tempo è esaurito, si gioca la mossa dalla radice con il n più grande.

Definizione — UCT

Nella selezione, tra i figli di un nodo con N visite si sceglie il figlio i con il valore più alto

UCT(i) = w_i / n_i + c · √(ln N / n_i),

dove c > 0 è la costante di esplorazione, di solito √2. Al crescere del numero di iterazioni la mossa consigliata si avvicina a quella del minimax.

Lanciamo MCTS sulla posizione che il minimax ha risolto sopra. I numeri nelle caselle sono le visite dopo 100, 300 e 1000 iterazioni, sotto di essi il risultato medio per X:

Dopo 100 iterazioni il centro ha 47 visite e le altre mosse messe insieme di più. Dopo mille ne ha 856 e un risultato medio di 0,94; la mossa del pareggio in basso al centro ha ricevuto 52 visite, le mosse perdenti ancora meno. MCTS, intanto, non conosce né il concetto di forchetta né alcuna funzione di valutazione — solo le regole e il caso. Eppure ha trovato la stessa mossa del minimax, che ha dovuto percorrere tutto il resto dell’albero.

8. Da Deep Blue ad AlphaZero

• Deep Blue (1997) sconfisse il campione del mondo Garry Kasparov. Al suo interno c’erano l’alfa-beta con una funzione di valutazione scritta a mano e un hardware specializzato capace di circa 200 milioni di posizioni al secondo.
• Chinook giocava a dama contro i campioni del mondo già negli anni ’90 e nel 2007 i suoi autori risolsero il gioco: esaminarono così tante posizioni da dimostrare che una partita senza errori finisce in pareggio — proprio come il tris 3 × 3.
• AlphaGo (2016) sconfisse Lee Se-dol 4 : 1. Univa MCTS a reti neurali: una rete proponeva le mosse promettenti (invece della scelta casuale), l’altra stimava il valore della posizione (invece dell’intera partita casuale).
• AlphaZero (2017) fece a meno anche delle partite umane. Imparò scacchi, shogi e go solo giocando contro sé stesso — con l’apprendimento per rinforzo — e in ciascuno dei giochi sconfisse il miglior programma esistente fino ad allora.
• I giochi con il caso e con informazione nascosta richiedono di più. Nel backgammon decidono i dadi, quindi all’albero si aggiungono nodi di caso con il valore atteso (expectiminimax). Nel poker non vedi le carte dell’avversario; il programma Libratus (2017) ha comunque battuto dei professionisti nel poker a due giocatori.

L’idea «guarda avanti prima di fare qualcosa» non è sparita dalle scacchiere. Gli agenti linguistici che pianificano provano diverse varianti di procedimento, le valutano e proseguono con la più promettente — solo che invece delle mosse dei pezzi scelgono i passi della soluzione.

9. Riepilogo

• Un gioco a due giocatori a somma zero è un problema di ricerca in cui le mosse le dividi con l’avversario; la soluzione è una strategia, non un percorso.
• Il minimax calcola il valore a ritroso: MAX prende il massimo, MIN il minimo. Il risultato è garantito contro qualsiasi avversario.
• L’alfa-beta restituisce lo stesso valore, ma pota i rami che non possono cambiare il risultato; con un buon ordine delle mosse vede due volte più in profondità.
• I giochi grandi si esplorano fino a una profondità limitata con una funzione di valutazione — e attenzione all’effetto orizzonte.
• MCTS, invece di valutare la posizione, la gioca fino in fondo a caso molte volte e sviluppa l’albero dove è promettente; unito alle reti neurali ne è nato AlphaGo.

Vuoi toccarlo con mano? Fai scrivere a un agente IA un tris con il minimax e poi calcola quante posizioni risparmia l’alfa-beta se ordini le mosse dal centro verso i bordi.

La vedi diversamente? Scrivi a support@coden-app.com.