Il numero di Shannon: come si misura la complessità degli scacchi

Negli scacchi due numeri compaiono spesso insieme e finiscono per essere usati come se fossero intercambiabili: circa 10¹²⁰ e circa 10⁴⁴. Sono due grandezze che rispondono a domande diverse, e questa pagina prova a separarle.

Il primo numero è probabilmente quello che hai già incrociato da qualche parte: viene chiamato numero di Shannon, dal nome dell'ingegnere che lo propose nel 1950. Qui ricostruiamo il calcolo che porta a 10¹²⁰ — è più semplice di quanto suggerisca la sua taglia — e proviamo a chiarire una cosa: quel numero non sta contando posizioni sulla scacchiera, sta contando partite. È una distinzione che, una volta vista, cambia il modo in cui leggi tutti gli articoli successivi sull'argomento.

Dove nasce 10¹²⁰

Nel 1950 Claude Shannon — l'ingegnere che aveva da poco fondato la teoria dell'informazione — pubblica sul Philosophical Magazine un articolo intitolato Programming a Computer for Playing Chess. Dentro ci sono le idee che diventeranno alpha-beta pruning, valutazione di posizione, ordinamento delle mosse: in sostanza il primo schema funzionante di un motore di scacchi. In una pagina di calcolo, Shannon stima quante variazioni servirà esplorare a partire dalla posizione iniziale. Scrive testualmente: "there will be 10¹²⁰ variations to be calculated from the initial position".

Da dove viene quel numero? Shannon parte da due osservazioni di buon senso, dichiarate nel paper:

• in una posizione tipica un giocatore ha circa 30 mosse legali tra cui scegliere
• una partita media dura circa 40 mosse per ciascun giocatore

Da qui il calcolo. Una coppia bianco–nero genera circa 30 × 30 ≈ 10³ alternative. Su 40 coppie successive: (10³)⁴⁰ = 10¹²⁰.

Tre cose da sottolineare prima di proseguire. Primo: il calcolo è semplicissimo. Due numeri ragionevoli moltiplicati. La grandezza non viene da raffinatezze, viene dall'esponente. È anche un piccolo esercizio di metodo: si stima un ordine di grandezza con due numeri di buon senso, non con il colosso che sembra.

Secondo: 30 e 40 sono medie, non massimi. Shannon stesso le presenta come stime conservative. Numeri leggermente diversi (35 mosse legali, 80 mosse totali) producono 10¹²³, dello stesso ordine di grandezza.

Terzo, e meno banale: questo numero conta sequenze di mosse, non posizioni distinte sulla scacchiera. È una distinzione che Shannon non aveva motivo di sviluppare nel 1950, ma che diventa cruciale quarant'anni dopo.

L'altro numero: ~10⁴⁴

Se 10¹²⁰ conta sequenze, c'è un altro numero che conta posizioni. La domanda sotto è diversa: non "quante partite si possono giocare", ma "quante diverse configurazioni dei pezzi sono legali su una scacchiera 8×8".

La distinzione viene formalizzata nel 1994 da Victor Allis, in una tesi di dottorato all'Università di Limburg dedicata proprio alla complessità dei giochi. Allis propone due indicatori distinti per qualunque gioco: la state-space complexity (numero di posizioni distinte raggiungibili dalla posizione iniziale) e la game-tree complexity (numero di nodi nell'albero delle partite, cioè la grandezza stimata da Shannon). Per gli scacchi Allis dà una stima di state-space dell'ordine di 10⁴³.

Negli anni successivi il valore viene raffinato. Il lavoro più recente che si possa citare con fonti pubbliche è quello di John Tromp (2021): usando un metodo di campionamento casuale su circa due milioni di posizioni, con verifica formale di legalità, Tromp arriva a una stima di (4,82 ± 0,03) × 10⁴⁴.

Le due stime — Allis 1994, Tromp 2021 — possono sembrare in disaccordo, ma raccontano cose leggermente diverse: Allis lavora sull'ordine di grandezza con argomenti combinatori; Tromp produce un valore numerico stretto con metodo statistico. Sono entrambe oneste, ed entrambe ci dicono una cosa che nei post divulgativi passa raramente: anche un numero apparentemente "fisso" come quello delle posizioni legali sulla scacchiera è un oggetto di ricerca aperto, non un dato chiuso.

Cosa 10¹²⁰ non sta contando

Il rapporto fra i due numeri è il pezzo interessante. Le sequenze di mosse (10¹²⁰) sono enormemente più numerose delle posizioni distinte (10⁴⁴): un fattore di 10⁷⁶, che è uno scarto vertiginoso. Perché tanta differenza? Perché molte sequenze di mosse arrivano alla stessa posizione finale percorrendo strade diverse.

In gergo scacchistico si chiamano trasposizioni: due partite che fanno mosse diverse nei primi venti turni e si ritrovano alla stessa identica configurazione al ventunesimo. Per chi gioca, e per chi programma motori, le trasposizioni sono pane quotidiano: i motori usano apposite transposition tables per riconoscere posizioni già analizzate e non ricalcolarle.

Significa che il numero di "partite distinte come storie" è molto inferiore a 10¹²⁰, anche se non c'è una stima esatta pubblicata. 10¹²⁰ include tutti i percorsi, anche quelli che si annullano. Per chi insegna scacchi, è il momento giusto per dire ai bambini: non importa quale strada prendi, importa dove arrivi.

Un paragone, scelto con cura

A questo punto si capisce perché molti articoli divulgativi citano il numero di Shannon accanto al numero di atomi nell'universo osservabile (~10⁸⁰). Il paragone è vero ed è quello giusto, ma per il numero piccolo, non per quello grande.

Le posizioni legali sulla scacchiera (~4,8 × 10⁴⁴) sono di parecchi ordini di grandezza inferiori al numero di atomi nell'universo. Significa che lo spazio degli stati degli scacchi entra fisicamente nell'universo: si potrebbero in linea di principio assegnare posizioni a porzioni di materia, con un avanzo di 10³⁶ atomi per ogni posizione. Non è una verità mistica: è una conseguenza diretta del fatto che 8×8 caselle, con un alfabeto limitato di pezzi, generano uno spazio combinatorio comunque grande ma fisicamente compatibile.

Il numero di Shannon, 10¹²⁰, è invece di 40 ordini di grandezza superiore al numero di atomi. Non è una sorpresa: è la conseguenza meccanica del fatto che le sequenze sono enormemente più numerose delle configurazioni. Citarlo come "più combinazioni che atomi nell'universo" non è scorretto, ma è un confronto sproporzionato: paragoniamo un albero di possibili storie con un censimento di particelle. Sono cose diverse misurate in unità diverse.

Il paragone più interessante, casomai, è interno: 10¹²⁰ contro 10⁴⁴, cioè albero di gioco contro spazio degli stati. Quel rapporto, 10⁷⁶, è il vero indicatore di quanto la storia di una partita sia molteplice.

Un computer non gioca esplorando 10¹²⁰

Una conseguenza importante: nessun motore di scacchi ha mai esplorato neanche una frazione visibile di 10¹²⁰, eppure i migliori motori battono qualunque essere umano da prima dell'anno 2000.

Stockfish, Komodo e gli altri motori "classici" usano alpha-beta pruning: una tecnica che taglia interi rami dell'albero quando si dimostra che non possono produrre risultati migliori dei rami già esplorati. Combinata con tabelle di trasposizione e con valutazioni euristiche di posizione, riduce drasticamente lo spazio di ricerca effettivo.

AlphaZero (DeepMind, 2017) ha fatto un salto ulteriore: usa Monte Carlo Tree Search guidato da una rete neurale che impara a valutare posizioni e a suggerire mosse promettenti. Il risultato è che AlphaZero esplora molte meno posizioni al secondo di Stockfish, ma quelle che esplora sono scelte molto meglio.

Per dare un'idea concreta — senza pretese di precisione, perché i valori esatti dipendono da hardware, versione e tempo di pensiero — Stockfish moderno valuta dell'ordine di decine di milioni di posizioni al secondo su CPU comune; AlphaZero originale ne valutava qualche decina di migliaia al secondo su TPU dedicate. In entrambi i casi siamo a una frazione infinitesima dell'albero teorico.

La lezione è onesta e va contro la divulgazione romantica: la completezza non è il modo in cui si risolvono i giochi complessi. Né per le macchine né per gli umani. Quando un campione del mondo gioca, non sta visualizzando 10¹²⁰ partite — sta riconoscendo schemi, eliminando candidati, calcolando profondamente solo poche linee. È esattamente quello che fa AlphaZero, in scala diversa.

Quanto sono lontani gli scacchi dall'essere "risolti"

Un gioco si dice risolto in tre modi diversi: ultra-debolmente (sappiamo qual è il risultato di una partita perfetta), debolmente (sappiamo anche la strategia per ottenere quel risultato dalla posizione iniziale), fortemente (sappiamo la strategia ottimale da qualunque posizione).

La dama 8×8 nella variante inglese (checkers) è risolta debolmente: nel 2007 il team di Jonathan Schaeffer all'Università dell'Alberta ha dimostrato che con gioco perfetto da entrambe le parti finisce in patta. Ci sono voluti quasi vent'anni di calcolo distribuito.

Gli scacchi non sono risolti in nessuna delle tre forme. Il numero di Shannon e il numero di Tromp sono i motivi: nessun calcolo esaustivo è plausibile, neanche con orizzonti tecnologici ragionevoli.

Quello che sì è stato risolto sono i finali con pochi pezzi, attraverso le endgame tablebase: database costruiti con calcolo retrogrado che, data una posizione finale, dicono il risultato perfetto e la mossa migliore. Lo standard attuale arriva a 7 pezzi sulla scacchiera (tablebase Lomonosov, 2012; standardizzata da ICCF nel 2019). Le prime esplorazioni a 8 pezzi sono in corso, ma il volume dei dati si misura in petabyte.

Conseguenza pratica: nei finali con poche pedine i motori giocano in modo provatamente perfetto. Nelle aperture e nel medio-gioco no — calcolano molto in profondità ma senza certezza assoluta.

I numeri stessi sono in evoluzione

Una pagina che racconta come si conoscono i numeri deve dichiarare anche dove i numeri sono ancora aperti.

10¹²⁰ viene da assunzioni dichiarate da Shannon nel 1950: 30 mosse legali per giocatore, 40 mosse per parte. Sono medie, e non gli unici valori plausibili. Statistiche su database di partite di alto livello suggeriscono branching factor medi tra 30 e 40 e lunghezze medie tra 70 e 90 ply. Significa che stime alternative producono valori tra 10¹¹⁵ e 10¹²⁵. L'ordine di grandezza tiene; il valore preciso oscilla.

10⁴⁴ (Tromp 2021) è una stima statistica con barre di errore esplicite: (4,82 ± 0,03) × 10⁴⁴. Il limite superiore precedente (1998, ~10^45,9) era meno verificabile e oggi va considerato superato. Conteggi esatti via enumerazione completa sono fuori portata: anche solo verificare la legalità di una posizione richiede prove non banali, e le posizioni totali sono troppe per enumerarle tutte.

Nessun numero in questa pagina è "il valore definitivo". Sono i migliori che la letteratura citabile produce oggi, con i loro intervalli di fiducia. Tra venti anni ci saranno stime più strette. Ma 10¹²⁰ e 10⁴⁴ non si rovesceranno: cambieranno solo le cifre dopo la prima.

Cosa portarsi in classe (o in famiglia)

Tre cose, se domani devi parlarne a un bambino o ai tuoi alunni.

Primo: la stima di Shannon è esattamente l'esercizio matematico che si fa a scuola con altri nomi. Quante combinazioni ho con due numeri? Si moltiplicano. E con quaranta numeri di seguito? Si elevano a potenza. Tre minuti di lavagna mostrano come da 30 e 40 si arriva a un numero con 120 zeri. Funziona dalla quarta elementare in su, e regala uno dei pochi momenti in cui la matematica fa effettivamente impressione.

Secondo: la distinzione tra "quante posizioni" e "quante partite" è un esercizio di pensiero scientifico applicabile a qualunque cosa. Quante combinazioni di sapori posso fare con cinque ingredienti? Dipende: quante mi servono per essere considerate "la stessa pasta"? Stati contro percorsi è una distinzione concettuale che torna in chimica, in genetica, in informatica.

Terzo: il numero di Shannon non rende gli scacchi imbattibili. Rende solo gli scacchi abbastanza grandi da garantire che ogni partita sia diversa, e che il dominio non si esaurisca con la pratica. È un argomento per giocarci, non per esserne intimoriti. Vale per gli scacchi come per qualunque altro gioco aperto: la matematica della complessità non sostituisce l'esperienza del gioco, la giustifica.

P.S. — view source.