Tablebase, storia dalle origini.

<Articolo Chessbase liberamente tradotto.>

Una delle chiavi di volta per migliorare la nostra comprensione dei finali sono le tablebase dei finali, una sorta di oracolo che è nato per la prima volta più di 40 anni fa. Questa tecnologia rivoluzionaria, che per prima ha visto la luce nel mondo degli scacchi grazie allo scienziato informatico e pioniere Ken Thompson, si è evoluta molto da allora. Ecco uno sguardo ai suoi inizi e ciò che ogni generazione successiva ha portato.

Cosa sono le tablebase dei finali?
In poche parole: sono scacchi perfetti. Sappiamo tutti che il numero di posizioni possibili negli scacchi supera di gran lunga il numero di atomi nell'universo, o almeno questo è quello che ci viene detto (chiedendo la domanda a chi ha contato gli atomi), ma è sufficiente dire che nessun computer potrà mai calcolarle tutte. Tuttavia, questo è vero con tutti i 32 pezzi sulla scacchiera. Per un numero ridotto di pezzi (come nei finali) sono stati creati dei database in cui ogni possibile posizione risultante da essa è stata calcolata e memorizzata in modo che tu o un computer puoi immediatamente conoscere le mosse migliori. Non è necessario "calcolare" nulla a questo punto, basta consultare il database delle posizioni di fine gioco note come tablebases.

Una breve storia
I primi passi verso la creazione delle tablebase sono venuti dal noto matematico Richard Bellman, che ha proposto di costruire un database per risolvere i finali di scacchi e dama usando analisi retrograde. Sebbene non fosse propriamente l'analisi, l'idea era di analizzare all'indietro dalle posizioni più semplici (cioè tre pezzi, che includono i due Re) e aggiungere gradualmente di più.
Questo è diventato realtà pratica con il database KQKR (Re e Donna vs Re e Torre) di Ken Thompson usato nel 1977 in una partita contro il campione americano in carica, GM Walter Browne. Ken Thompson ha quindi esteso le tablebase per coprire tutti i finali a quattro e cinque elementi.

Da zero a sei in ...

Poi, nel 1991, il passo successivo fu fatto quando Lewis Stiller costruì il primo database di sei pezzi usando un computer con 65.536 processori che lavoravano in parallelo. Il finale era di Torre e Alfiere contro due Cavalli. Il computer ha generato 100 miliardi di posizioni legali, e Stiller ha utilizzato il metodo sperimentato da Ken Thompson, descritto in dettaglio nell'articolo ‘Come Dio gioca a scacchi’. Il suo risultato è stato sorprendente: la Torre e l’Alfiere in genere possono vincere, anche se in alcuni casi richiedono (e questo non è uno scherzo) ben oltre duecento mosse per farlo!

In questo periodo, gli esperti che hanno ripetuto gli esempi forniti da Stiller non potevano discernere alcuna strategia che gli esseri umani potessero comprendere. Il database dei finali sembrava giocare in modo completamente inutile fino a quando - quasi 200 mosse dopo - il Re nero era stato in qualche modo spinto fino al bordo della scacchiera e i due Cavalli stavano lottando per difendersi a vicenda. Poi uno di loro cade.

Frederic Friedel mi ha detto che in questo momento ha mostrato due posizioni di questo finale a una delle squadre di analisi più potenti che si possano immaginare: il team di addestramento del campionato del mondo di Garry Kasparov. Frederic non ha chiesto loro di risolvere le posizioni, semplicemente ha detto loro che in una delle due posizioni il Bianco ha dovuto trovare 28 mosse uniche per forzare l'altra posizione in modo da non rinunciare alla vittoria. Quello che il team di Kasparov doveva fare era semplicemente dirgli quale era la posizione precedente e quella che doveva essere forzata per non pattare. C'era una buona dose di gioia nel vedere come le più grandi menti di scacchi del mondo non riuscivano a decidere quale fosse. "Sembrano completamente equivalenti, è impossibile dire quale sia migliore", ha detto Garry. Capì che gli umani alla fine non avrebbero mai potuto giocare perfettamente e sarebbero sempre stati inferiori al computer. Aveva solo bisogno di assicurarsi che, mentre giocava in modo imperfetto, lo gestisse leggermente meglio del suo avversario (umano), che non sarebbe mai stato in grado di comprendere le complessità del finale. Questo è il motivo per cui lui e altri grandi maestri si eserciterebbero contro il computer e lo userebbero per affinare la loro strategia.

La successiva evoluzione: Edwards e Nalimov
Nonostante questo, i progressi nel completare l'intero file di sei pezzi sono stati lenti. Le tablebase di Thompson sono state la prima incursione ma hanno avuto problemi che le hanno reso inutilizzabile nella ricerca di un programma. Questo è stato risolto da Steven Edwards, che ha costruito un set nei primi anni '90 per il suo programma 'Spector' che utilizzava un nuovo design, e la codifica, che riguardava le carenze. Dopo aver terminato la procedura di costruzione nel 1994, Steven Edwards ha reso disponibili su Internet tutti i dati, la documentazione e un programma di test scritti in ANSI-C. Va aggiunto che questa non era la portata del suo contributo agli scacchi, dato che Edwards, uno scienziato informatico, avrebbe anche ideato gli standard PGN, EPD e FEN che sono usati fino ad oggi. I file PGN che scarichi per vedere i giochi ci sono grazie ai suoi sforzi.

Fino all'avvento delle tabelle di Nalimov compresse, le tablebase di Edwards erano piuttosto popolari e utilizzate in diversi programmi di scacchi, come Crafty, Gromit e MChess Pro commerciale, solo per citarne alcuni. L'unico problema era che il set completo di cinque pezzi da solo era ben oltre 50 GB! Inoltre, se si considera che ogni pezzo aggiuntivo a una tablebase occupa circa 160 volte più spazio, ci si può aspettare che un set completo di sei pezzi abbia bisogno di circa dieci terabyte di spazio ovvero di 10.000 GB. Se oggi 10 TB sembra ancora tanto, immagina 25 anni fa.

Arrivo delle Nalimov.
Eugene Nalimov è uno scienziato informatico russo, che viveva negli Stati Uniti, lavorando per Microsoft come membro del team che sviluppa il compilatore Visual C ++. Nel 1998, ha pubblicato il suo lavoro per ridurre enormemente lo spazio necessario per riporre le TB complete da cinque pezzi, nonché per ottimizzarlo per i motori in modo che potessero usarli nella loro ricerca. Il set completo di cinque pezzi ora ha un semplice 7,1 GB di ‘peso’. Ciò ha avuto anche grandi ripercussioni sul set di sei pezzi, che avrebbe avuto bisogno di molto meno spazio, e nel 2005 sono stati rilasciati i file dei finali di sei pezzi. Le Nalimov TB da sei pezzi occupavano 1,2 terabyte. Sebbene i file siano stati scaricati gratuitamente dai server universitari in cui sono stati archiviati, l'idea era molto più che scoraggiante. C'erano anche altri problemi pratici. La velocità di consultare al volo un intero disco rigido di TB per milioni di posizioni con un motore non era pratica e ha portato a rallentamenti in generale, che non era chiaro se un motore giocasse meglio con le TB che senza. Un altro era che non erano progettate per ricerche multi-thread, in altre parole processori multi-core.

Arrivo delle Syzygy
Ci sarebbero voluti alcuni anni, ma il successivo grande passo è arrivato nel 2013, quando Ronald de Man ha annunciato in un forum specializzato di scacchi per computer (come aveva fatto Nalimov) la creazione di un nuovo generatore di TB con nuove idee. Ronald è un matematico e scienziato informatico olandese che ha ottenuto una medaglia d'argento nelle Olimpiadi matematiche internazionali del 1990 (per esempio). È co-sviluppatore dell'ambiente desktop Linux GNOME e un appassionato di scacchi e scacchi per computer. Le sue nuove tablebases dei finali, pubblicate gratuitamente per il pubblico, hanno introdotto diverse importanti innovazioni. Il primo riguarda il problema di oltre 200 mosse di soluzione. Le TB includevano cinque valutazioni per una posizione nel contesto della regola FIDE delle 50-mosse negli scacchi:

- Aggiunta patta per la regola delle 50 mosse:
+2 = vittoria incondizionata per il lato che muove
+1 = vittoria che può essere frustrata da una rivendicazione di patta per la regola delle 50 mosse.
+0 = patta incondizionato
-1 = sconfitta salvata da una rivendicazione di patta per la regola delle 50 mosse.
-2 = sconfitta incondizionata

Contrariamente alle precedenti versioni delle TB che assumevano i nomi dei loro creatori, R. de Man scelse di chiamarle Syzygy (pronuncia Sih-Zih-Gee), che significa un paio di cose connesse o corrispondenti. Queste nuove TB non sono solo le migliori per le ricerche multithread, ma anche il set completo occupa solo 150 GB (contro 1,2 terabyte delle Nalimov). Come tali, ora sono la scelta de facto per l'uso con un motore.


Articolo originale in Inglese: - TBstory -