Negli scacchi, una tablebase è un database di tutte le posizioni possibili in un finale. Grazie ad esse è possibile conoscere il risultato finale di una data posizione (vittoria del Bianco, del Nero o patta) e anche il numero delle mosse necessarie per la vittoria nel caso che i due giocatori giochino nel miglior modo possibile. Le tablebase indicano inoltre le migliori mosse possibili in ogni posizione.
Attualmente sono state risolte tutte le posizioni in cui sono presenti sulla scacchiera sette o meno pezzi (inclusi i due re). La soluzione di queste posizioni ha migliorato la comprensione dei finali: alcune posizioni che venivano considerate patte sono state invece risolte come vittorie, in alcuni casi con sequenze di più di cento mosse, molto al di là della possibilità di calcolo di un umano o di un motore scacchistico.
Le tablebase hanno inoltre facilitato la composizione degli studi.
Le tablebase sono generate attraverso analisi retrograda, calcolando all'indietro da ogni posizione possibile e legale di scacco matto o di stallo.
Storia e contesto In linea di principio, è possibile risolvere ogni gioco che non prevede scelte casuali e in cui lo "stato del gioco" è noto ad ogni scelta, cioè stabilire quale dei giocatori ha la possibilità, muovendo nel modo migliore possibile, di vincere (oppure se il gioco finirà in un pareggio). Alcuni semplici giochi, come forza quattro, il tris o la dama inglese, sono stati risolti (il primo è vinto per il giocatore che inizia, gli altri due sono pareggi), mentre altri giochi, come il go e gli scacchi, sono troppo complessi per poter attualmente valutare tutte le possibilità e tutte le posizioni. Per ovviare a questo problema, si è cominciato con lo studiare posizioni in cui è ridotta la grandezza della scacchiera (come per il go), oppure in cui sono presenti pochi pezzi sulla scacchiera (ad esempio negli scacchi).
Uno dei primi campi di applicazione dell'intelligenza artificiale furono gli scacchi: dopo esser cominciata negli anni Trenta, nel 1949 Claude Shannon propose dei criteri per valutare delle mosse, mentre due anni più tardi Alan Turing creò un primitivo motore scacchistico che assegnava dei valori al materiale e alla mobilità dei pezzi.D. Levy e M. Newborn, How Computers Play Chess, p. 25-38 Nel tempo, nonostante il loro miglioramento, i software che giocavano a scacchi esibivano sempre una debolezza nel finale; i programmatori aggiunsero così degli elementi euristici per rafforzarli, ad esempio che il re si dovesse muovere verso il centro della scacchiera.D. Levy e M. Newborn, op. cit., p.129-130
Nel 1965, Richard Bellman propose la creazione di un database per risolvere i finali di scacchi e di dama inglese usando l'analisi retrograda.B. L. Stille, Exploiting symmetry on parallel architectures, p.84 Anziché calcolare le mosse a partire da una data posizione, si sarebbe dovuta analizzare la posizione all'indietro, partendo dalle posizioni finali, cioè da quelle di scacco matto o di stallo. In questo modo un motore non avrebbe più avuto la necessità di analizzare le posizioni di un finale, perché avrebbe avuto in memoria la miglior mossa possibile.
Nel 1970 Thomas Ströhlein pubblicò una tesi di dottorato in cui analizzava alcuni finali (re e donna contro re, re e torre contro re, re e pedone contro re, donna contro torre, torre contro pezzo minore).Vedi anche Ken Thompson e altri estesero in seguito le tablebase fino a coprire tutti i finali con quattro e cinque pezzi.D. Levy e M. Newborn, op. cit., p.144Vedi anche e Nel 1995 Lewis Stille pubblicò una tesi con l'analisi di alcune posizioni con sei pezzi.L.B. Stiller, op. cit., p.68-113 Contributi più recenti sono venuti, tra gli altri, da Eugene Nalimov (che dà nome alle popolari tablebase di Nalimov), Eiko Bleicher (che ha adattato il concetto delle tablebase ad un programma chiamato "Freezer"), Guy Haworth, Marc Bourzutschky e Yakov Konoval (questi ultimi due hanno collaborato all'analisi di alcuni finali con sette pezzi).
L'analisi di tutti i finali con sei o meno pezzi è stata completata nel 2006, sebbene non siano state prodotte quelle relative alle posizioni con cinque pezzi contro il solo re, in quanto il risultato è ovvio, mentre le tablebase a sette pezzi sono state completate nel 2013. Le tablebase fino a sei pezzi sono disponibili su internet sia per il download gratuito che per la consultazione on-line.
Metriche: DTC e DTM
Prima di creare una tablebase, il programmatore deve decidere un modo di scegliere la "migliore" possibilità tra le varie mosse possibili; detto in un altro modo, deve decidere quali posizioni considerare vinte, per poter poi contare quante mosse sono necessarie per arrivarvi. Generalmente sono usate due di queste metriche: DTM (depth to mate, distanza dal matto): l'unica posizione vinta è considerata lo scacco matto; DTC (depth to conversion, distanza dalla conversione): il colore più forte vince anche catturando del materiale, arrivando così in un finale più semplice. Ad esempio, in un finale di donna contro torre, il Bianco converte catturando la torre.
Quando si mette in conto anche la regola delle cinquanta mosse, vengono considerate anche due altre metriche, la DTZ (depth to zeroing-move) e la DTR (depth by the rule): tuttavia queste ultime non sono in genere state calcolate, mentre le tablebase DTZ sono state pubblicate dopo molti anni e sono disponibili per l'analisi e lo studio. Nel caso particolare della composizione di studi scacchistici, inoltre, per convenzione stabilita dalla WFCC la regola delle cinquanta mosse non è applicata se non diversamente specificato, per cui anche una posizione che nel gioco vivo potrebbe essere reclamata patta per eccesso di mosse senza catture né spinte di pedoni, viene considerata valida (queste posizioni sono definite in gergo blessed loss e cursed win).
In molti finali, la metrica DTC è più piccola della DTM, ma quest'ultima porta allo scacco matto più rapido. In alcuni casi DTC=DTM: questo avviene ad esempio quando il lato debole ha solamente il re (e non è possibile quindi convertire in un altro finale), oppure nel finale di due cavalli contro un pedone, nel quale l'unico modo di arrivare al matto è di non catturare il pedone.
Generare le tablebase Passo 1: generare tutte le possibili posizioni
Una volta scelta la metrica, il primo passo nel calcolare le tablebase è generare tutte le posizioni con una data combinazione di materiale. Ad esempio, nel finale di re e donna contro re, il computer deve descrivere tutte le circa 40.000 posizioni in una matrice.
Il numero di 40.000 deriva da un ragionamento di simmetria. Il re nero può essere posto in una qualsiasi tra le case a1, b1, c1, d1, b2, c2, d2, c3, d3 e d4 (contrassegnate da una X nel diagramma): se fosse in un'altra casa, infatti, la posizione potrebbe essere trasportata tramite riflessione o rotazione in una già considerata con questo metodo. Ad esempio, non c'è differenza se il re è in uno degli angoli a1, a8, h1 o h8. Moltiplicando quindi 10 per le 63 case in cui può trovarsi re bianco e per le 62 possibilità offerte alla donna, si ottiene . Alcune di queste sono tuttavia illegali (perché i due re sono a contatto), e quindi il numero effettivo è più piccolo.D. Levy e M. Newborn, op. cit., p.140-143L. B. Stille, op. cit, p.93-98
Ogni posizione è valutata sia nel caso sia il Bianco a muovere, sia che il tratto sia al Nero. Assumendo che il Bianco abbia la donna, quasi tutte le posizioni sono vinte per il Bianco, con il matto forzato in non più di dieci mosse, ad eccezione di casi di stallo e di inevitabile perdita della donna.
Nei finali senza pedoni, ogni pezzo moltiplica il numero di possibili posizioni circa di un fattore 60; nel caso dei pedoni, la situazione è più complessa, in quanto la simmetria è ridotta. Potendo infatti questi muoversi solo in avanti ma non di lato, le posizioni che risultano attraverso riflessione verticale o rotazione non possono essere considerate equivalenti. La miglior simmetria possibile è limitare un pedone nel rettangolo a2-a7-d7-d2, composto da 24 case, e poi sistemare gli altri pezzi nel resto della scacchiera. Di conseguenza, la complessità dei finali con pedoni è circa 24/10=2,4 volte quella di un finale con lo stesso numero di pezzi, ma senza pedoni.
Passo 2: valutare le posizioni con l'analisi retrograda L'idea delle tablebase è di costruire, a partire dalle posizioni di matto, tutte le posizioni da cui si può raggiungere la vittoria; per questo si creano, in sequenza, dei sotto-database in cui: il Bianco dà matto; il Nero è forzato ad entrare in una posizione in cui subisce matto; il Bianco forza il Nero ad essere mattato alla mossa successiva, eccetera.
In generale, uno di questi elenchi è formato dalle posizioni in cui il Bianco entra in una posizione presente nel sotto-database precedente, oppure il Nero è forzato ad entrarvi (a seconda del tratto).
I diagrammi illustrano l'idea dell'analisi retrograda: la prima posizione è generata per prima, in quanto il Bianco può dare matto (con Dd7#); nella seconda, il Nero non può evitare il matto (1...Rb8 2.Db7#, 1...Rd8 2.Dd7#), mentre nella terza il Bianco può raggiungere la seconda con 1.Rc6. La posizione del terzo diagramma è quindi un "matto in tre semimosse" (o ply), mentre le altre due sono un "matto in due semimosse" e un "matto in una semimossa": ogni posizione viene valutata come vittoria o sconfitta dopo un certo numero di mosse. Le posizioni che non appaiono né nel database delle vittorie né in quello delle sconfitte sono patte.
Passo 3: verifica Dopo che le tablebase sono state generate e ogni posizione è stata valutata, il risultato deve essere verificato in maniera indipendente, per controllare la coerenza dei risultati.
Per esempio, a partire dall'ultimo diagramma, il programma di verifica legge che, attraverso Rc6, vi è matto in tre semimosse; poi passa alla posizione dopo questa mossa, e verifica che essa è classificata come "matto in due semimosse". In questo caso le due valutazioni sono coerenti l'una con l'altra; in caso contrario, sarebbe stato necessario correggere le tablebase.
Problemi e strategie Catture, promozioni e mosse speciali Una tablebase con quattro pezzi sulla scacchiera deve basarsi sulle tablebase di tre pezzi che possono risultare quando un pezzo viene catturato. Allo stesso modo, se si considerano posizioni con almeno un pedone, è necessario possedere già una tablebase in cui sono presenti i pezzi che risulterebbero da un'eventuale promozione. Il programma deve tenere conto, durante l'analisi, della possibilità di una cattura o di una promozione.Stiller, op. cit., p.99-100.
Le tablebase, inoltre, assumono che l'arrocco non sia possibile: questa è un'ipotesi ragionevole nella gran parte dei finali (sebbene l'arrocco sia ammesso in alcuni studi), e inoltre non in tutte le posizioni in cui re e torre sono nelle case di partenza è possibile effettuare questa mossa. A causa di questa ambiguità, sarebbe necessario effettuare valutazioni separate nel caso in cui l'arrocco sia o meno possibile.
Lo stesso problema esiste nel caso delle catture en passant, in quanto la possibilità di questa mossa dipende dalla mossa precedente dell'avversario. Questo problema è più delicato del precedente, in quanto la cattura en passant appare frequentemente nei finali di pedoni; per questo motivo le tablebase devono essere calcolate nel caso in cui entrambi i giocatori abbiano almeno un pedone.
Usare informazioni a priori
Usando il metodo generale, le tablebase devono considerare la possibilità che ogni pezzo occupi una qualsiasi delle 64 case della scacchiera. In alcune posizioni è possibile restringere la ricerca senza cambiare il risultato finale, diminuendo la richiesta di risorse computazionali e permettendo analisi altrimenti impossibili.