Dopo 2.500 anni, un informatico ha risolto il mistero del Go

Grazie a server enormi e un sacco di tempo, adesso sappiamo che il numero di posizioni valide del gioco del Go è superiore a quello degli atomi osservabili nell'universo.

|
gen 29 2016, 9:42am

Go in sostanza è un antico gioco i cui partecipanti dispongono a turno pedine bianche o nere sopra una "scacchiera" nel tentativo di occupare la zona più vasta possibile del campo da gioco. I più antichi riferimenti a Go che ci sono noti risalgono addirittura alla Cina del V secolo a.C., quindi veniva giocato lungo le rive dello Yangtze addirittura prima che il Partenone svettasse su Atene. Allo stesso tempo semplice e complesso, questo antico passatempo è noto perché il numero di posizioni che le pedine possono assumere è vastissimo, tanto che per secoli molti hanno sostenuto fosse infinito. Tuttavia le cose non stanno esattamente così perché, come ha rivelato la scorsa settimana l'informatico John Tromp, il numero di combinazioni è solo maledettamente grande.

Per essere più precisi, Tromp ha scoperto il numero di combinazioni valide che si possono presentare sui 361 punti compresi all'interno della scacchiera:

2081681993819799846
9947863334486277028
6522453884530548425
6394568209274196127
3801537852564845169
8519643907259916015
6281285460898883144
2712971531931755773
6620397247064840935

Non è certo il genere di calcolo da risolvere con carta e penna. Come ha sottolineato un utente di Reddit facendo riferimento ai precedenti lavori di Tromp, si tratta di una cifra superiore al numero totale di atomi osservabili nell'universo.

Tromp ha iniziato ad eseguire i calcoli il 6 marzo dello scorso anno, con l'aiuto del personale e dei potenti server disponibili presso l'Advanced Study's School of Natural Sciences e l'IDA's Center for Communications Research a Princeton, in New Jersey e l'aggiunta del contributo dell'Helion Cloud della Hewlett Packard.

"Il software è stato sviluppato quasi completamente nel 2005, quindi esiste da allora anche se non avevamo ancora a disposizione le risorse hardware necessarie a mandarlo in esecuzione," mi racconta Trump via mail. "Non più tardi del 2007, io e Michal Koucký, siamo stati in grado di calcolare il numero di combinazioni valide per una scacchiera da 17x17 sfruttando le capacità di calcolo disponibili presso il Dutch Centre for Mathematics and Computer Science in cui lavoravo."

Volete verificare il suo lavoro? Tromp rende disponibile il software che ha usato dal suo repository di GitHub, ma raccomanda che sono indispensabili "un server robusto con 15 TB di spazio disponibile, da 8 a 16 core e 192 GB di RAM."

In effetti, per anni la tecnologia disponibile ha imposto dei limiti a questa operazione consentendo di eseguire calcoli solo su scacchiere minori alla dimensione standard 19x19. Il divario che separa le scacchiere 17 x 17 da quelle 19 x 19 può sembrare non così ampio, ma Tromp sottolinea quanto lo svolgere calcoli per scacchiere più ampie anche di un solo ordine di grandezza, comporti il coinvolgimento di una capacità di memoria ben cinque volte maggiore, con conseguente aumento dello spazio di archiviazione richiesto e tempo di calcolo previsto.

Tromp ha contattato invano decine di aziende, finanziatori e istituzioni come Amazon e Google per farsi sponsorizzare in modo da ottenere in prestito l'hardware necessario per calcolare le combinazioni della tavola 19x19, ma l'occasione definitiva per portare a termine il suo progetto si è palesata solo nel 2014, quando il suo connazionale Piet Hut, astronomo presso l'Institute for Advanced Study, ha iniziato a collaborare con lui. Dopo che Tromp e i suoi amici hanno guadagnato una certa notorietà calcolando il numero di combinazioni valide per una scacchiera 18x18, le persone giuste sono salite a bordo del progetto per contribuire allo sforzo finale.

Così, dopo aver svelato un mistero rimasto irrisolto per 2500 anni, quale sarà la prossima sfida? Tromp dice che ha intenzione di continuare a lavorare a "Cuckoo Cycle" il suo sistema proof-of-work e a studiare Forza 4, ma di essere particolarmente interessato a perfezionare un lavoro simile a quello svolto su GO, dedicandosi questa volta al gioco degli scacchi. Tutta un'altra questione.

"La situazione è molto diversa con gli scacchi, non conosceremo mai il numero esatto di combinazioni possibili," racconta lo studioso, "in questo momento non sappiamo nemmeno l'ordine di grandezza, mi piacerebbe almeno arrivare al punto in cui potremo affermare un qualcosa del tipo: la cifra esatta si trova nell'ordine di grandezza compreso tra 10 ^ 44 e 10 ^ 45."

Questo, comunque, non risolve la questione del perché farlo.

"Essere nelle posizione di calcolare il grado di complessità del più grande gioco da tavolo di sempre, senza farlo effettivamente, non sarebbe da me", conclude Tromp. "O meglio, per citare il grande matematico Hilbert, 'Dobbiamo sapere —sapremo!"