Numero di Shannon

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Claude Shannon

Il numero di Shannon, dal nome di Claude Shannon, è una stima della complessità del gioco degli scacchi che ammonta a 10120, calcolata su una media di circa 103 possibilità per un paio di mosse consistenti in una mossa del Bianco seguita da una mossa del Nero, per partite della durata di 40 coppie di queste mosse.

Il calcolo di Shannon

[modifica | modifica wikitesto]

Nel 1950, Shannon mostrò nel suo "Programming a Computer for Playing Chess" un calcolo per la stima della complessità degli scacchi, in cui risultò la possibilità di sviluppo di 10120 partite, al fine di dimostrare come la forza bruta nell'affrontare un problema scacchistico fosse impraticabile.[1] La sua opera influenzò lo sviluppo dei computer scacchistici.

Shannon inoltre stimò l'estremo inferiore delle possibili posizioni nell'ordine generale di

o più grossolanamente 1043. Queste includono posizioni illegali (ad esempio, un pedone sulla prima riga, entrambi i Re sotto scacco) ed esclude posizioni legali a seguito di catture e promozioni. Tenendo tutto ciò in considerazione, Victor Allis calcolò come estremo superiore 5×1052 numeri di posizioni, e stimò che il vero numero fosse circa 1050.[2]. Risultati recenti[3] rifiniscono tale stima, portando l'estremo superiore a "sole" 2155 posizioni, che è inferiore a 1046,7 e che mostrano un estremo superiore di 2×1040 in assenza di promozioni.

Lo stesso Allis stimò inoltre la complessità degli scacchi essere di almeno 10123, "basata su una media del fattore di ramificazione di 35 e una durata media di gioco di 80 coppie di mosse". Per avere un'idea della vastità del problema, basti pensare che il numero di atomi nell'universo osservabile è grossolanamente stimato essere 1080.

Numero di semimosse Numero di possibili partite
1 20
2 400
3 8.902
4 197.281
5 4.865.609
6 119.060.324
7 3.195.901.860
8 84.998.978.956
9 2.439.530.234.167
10 69.352.859.712.417

Dalla tabella si evince come, dopo che entrambi i giocatori hanno mosso 5 volte, vi siano 69.352.859.712.417 possibili partite che possono essere state sviluppate.

  1. ^ (EN) Claude Shannon, Programming a Computer for Playing Chess (PDF), in Philosophical Magazine, vol. 41, n. 314, 1950. URL consultato il 15 settembre 2018 (archiviato dall'url originale il 15 marzo 2010).
  2. ^ (EN) Victor Allis, Searching for Solutions in Games and Artificial Intelligence (PDF), Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands, 1994, ISBN 90-90-07488-0.
  3. ^ (EN) John Tromp, John's Chess Playground, su tromp.github.io, 2010.