Scacchi al computer, storia del software

Se all’inizio erano considerati della pura teoria, in seguito, con lo sviluppo dell’informatica e dei concetti alla base dell’intelligenza artificiale, i programmi di scacchi si sono evoluti al punto tale da poter battere un Grande Maestro umano. Ripercorriamo le tappe di questa evoluzione.

Il 9 Marzo 1949, Claude Shannon (1916-2001), all’epoca ricercatore nei Laboratori Bell nel New Jersey, presentò un documento intitolato “Programming a Digital Computer for Playing Chess”
che descriveva come un programma per computer avrebbe potuto giocare a scacchi basandosi sulla posizione dei pezzi e la selezione delle mosse. Shannon propose un ragionamento basilare mirato a restringere il numero delle possibili mosse da considerare durante una partita di scacchi.
Nel 1950 Shannon perfezionò l’algoritmo che aveva ideato e il suo lavoro fu pubblicato su Philosophical Magazine (N. 314, Marzo 1950). Questo fu il primo articolo a trattare il tema del gioco degli scacchi al computer.

Nel 1950 Alan Turing (1912-1954) scrisse il primo programma di scacchi. Nello stesso anno egli propose il “Turing Test” in cui sosteneva che in futuro prossimo, dei computer adeguatamente programmati (anche per giocare a scacchi) sarebbero stati in grado di acquisire abilità da rivaleggiare con l’intelligenza umana, tanto che un umano che non avesse di fronte a se l’avversario durante un gioco che richiede particolare abilità come quello degli scacchi, non sarebbe stato in grado di distinguere se stesse sfidando un altro essere umano o un computer.

Nel 1951 Turing provò ad implementare il suo programma “Turbochamp” sul computer Ferranti Mark I presso l’Università di Manchester ma non riuscì a completare il lavoro.
Comunque, un suo collega Dr. Dietrich Prinz scrisse una versione semplificata di Turbochamp che era in grado di risolvere situazioni di “scacco in due mosse”. Il programma girò per la prima volta sul Ferranti Mark I nel Novembre 1951: erano elaborate tutte le possibili mosse finchè veniva trovata la giusta soluzione per lo scacco matto in due mosse, impiegava circa 15 minuti.

Nel 1956, nei Laboratori di Los Alamos, Paul Stein and Mark Wells scrissero un programma MANIAC I per il computer Univac  (accreditato di 11.000 operazioni al secondo) che era in grado di giocare una variante del gioco degli scacchi priva degli alfieri su una scacchiera 6x6.
Il programma impiegava 12 minuti per calcolare una profondità di 4 mosse, aggiungere i due alfieri avrebbe portato il tempo di elaborazione a circa 3 ore.

Al Massachusetts Institute of Technology, nel 1957, Alex Bernstein, dipendente IBM, creò il primo vero programma di scacchi completamente funzionante su un IBM 704, uno degli ultimi computer ad usare le valvole, capace di 42.000 istruzioni al secondo.
Il software impiegava circa 8 minuti per calcolare una mossa. Bernstein si avvalse della collaborazione di Arthur Bisguier, un maestro di scacchi assunto dall’IBM.
Edward Lasker, giocatore di livello internazionale, disputò una partita contro il programma e lo sconfisse facilmente ma commentò dicendo che il computer aveva giocato a scacchi a livello di un modesto principiante.

Il programma di scacchi di Bernstein è stato il primo ad usare una tecnica di ricerca selettiva in avanti chiamata Shannon tipo B. Prevedeva quattro livelli di ricerca e considerava le sette mosse più plausibili da ogni posizione, valutando i pezzi, la mobilità, il controllo dell’area e la difesa del re.

Nel 1958, presso la Carnegie Mellon University di Pittsburgh, Allen Newell, Herbert Simon and Cliff Shaw, tre ricercatori della Rand Corporation, svilupparono un programma di scacchi per il computer Johnniac. Il loro NSS (Newell, Simon, Shaw) Chess Program fu il primo programma di scacchi scritto con un linguaggio di alto livello, conosciuto come IPL (Information Processing Language). L’innovazione più importante di NSS fu l’implementazione dell’algoritmo di ricerca alpha-beta, molto più efficiente degli algoritmi di enumerazione che provavano tutte le possibili mosse. In pratica, il computer valuta una mossa ed inizia a calcolare la mossa successiva. Appena si accorgeva di trovarsi in posizione svantaggiosa rispetto alla mossa precedente terminava la ricerca in quel nodo così da risparmiare gran parte dei calcoli senza pregiudicare il risultato finale.

Nel 1959, la matricola del MIT Alan Kotok, insieme ad altri allievi del Professor John McCarthy, riprese il programma di Bernstein implementando l’algoritmo alpha-beta e un generatore di mosse plausibili. Il programma fu scritto in Fortran su un mainframe IBM 7090, calcolava circa 1100 posizioni al secondo ed impiegava tra i cinque e i venti minuti per elaborare una singola mossa.
Assistito e spronato da McCarthy, fondatore del dipartimento di Intelligenza Artificiale, Kotok continuò a perfezionare il suo programma e vi scrisse anche la tesi di laurea nel 1962.
The Chess Playing Program for the IBM 7090 Computer, il programma di scacchi del MIT realizzato da Kotok e McCarthy, era il primo che giocasse in modo credibile una partita vera e propria ed era in grado di sconfiggere avversari umani di basso livello.

Kotok fu assunto dalla DEC e diventò una figura determinante nell’evoluzione dell’industria dei computer, contribuendo allo sviluppo del PDP-6 e guidando la progettazione del PDP-10.
Fece anche parte del team di hacker del MIT che crearono il primo videogioco, Spacewar, per il quale ideò anche il joystick.

Nel 1965 il Professor McCarthy si recò in URSS dove fece visita al gruppo di ricercatori guidato da Alexander Kronrod presso l’Istituto di Fisica Teorica e Sperimentale di Mosca.
I Russi gli mostrarono un programma di scacchi che avevano sviluppato, in seguito ribattezzato KAISSA, e McCarthy accettò la sfida.
Il software sovietico girava su un computer M-20, mentre il programma Kotok-McCarthy si avvaleva di un IBM 7090. Il match si protrasse per nove mesi fra il 1966 e il 1967. Il programma Kotok-McCarthy perse la sfida 3-1. È paradossale che dopo questa prestigiosa affermazione, Konrod perse la direzione dell’Istituto e la sua cattedra di Fisica perchè fu accusato di sperperare risorse nel gioco degli scacchi.

Nel 1965, Dr. Hubert Dreyfus, un professore di filosofia al MIT, in seguito docente a Berkeley, fu incaricato dalla RAND Corporation di esplorare il settore dell’intelligenza artificiale. Scrisse un documento di 90 pagine intitolato “Alchemy and Artificial Intelligence” (che successivamente ampliò nel libro What Computers Can’t Do) in cui metteva in discussione il fatto che i computer avessero mai potuto imitare le capacità del cervello umano. E asserì che qualsiasi programma per computer, poteva battere a scacchi al massimo un bambino di 10 anni.

Proprio in quel periodo, verso la metà degli anni ‘60, Richard Greenblatt, un giovane hacker del MIT, stava mettendo a punto il Greenblatt Chess Program, meglio conosciuto come MacHack.
MacHack VI passerà alla storia come il primo programma di scacchi in grado di sconfiggere un accreditato avversario umano durante una regolare partita di torneo.
Il nome deriva dal Project MAC (Multilevel Access Computer or Machine-Aided Cognition), che era un progetto di ricerca portato avanti dal MIT. Il numero romano “VI” si riferisce alla macchina DEC PDP-6 per la quale era scritto. DEC progettò il PDP-6 e destinò il prototipo al progetto MAC. Il PDP-6 aveva una frequenza di 200KHz ed era accreditato di 225.000 istruzioni al secondo.

Greenblatt era molto interessato all’intelligenza artificiale e all’informatica. Pensava che i computer adeguatamente programmati potessero essere una grande risorsa in questo campo.
Aveva visto all’opera il programma di scacchi di Kotok e l’aveva giudicato pessimo. Greenblatt era fin da piccolo un grande appassionato di scacchi e gli venne naturale concentrare i suoi sforzi per scrivere una versione migliore del programma di Kotok che ne colmasse gli evidenti limiti.
Greenblatt fu ulteriormente stimolato dagli scritti di Hubert Dreyfus che circolavano al MIT in cui si affermava che i computer non avrebbero mai potuto competere con l’intelligenza umana.

Decise allora che avrebbe scritto un programma di scacchi in grado di battere un essere umano. Marvin Minksy, che era all’epoca il suo professore, provò a scoraggiarlo dicendo che in quel software non erano possibili altri progressi. Greenblatt decise comunque di concretizzare il suo intento, iniziò il lavoro nel Novembre del 1966 e si mise a macinare codice senza sosta sul PDP-6 che la DEC aveva donato al MIT.
Per sfruttare al massimo l’hardware, Greenblatt scelse di scrivere il suo programma in MIDAS, il linguaggio assembler del PDP-6, piuttosto che avvalersi di un linguaggio di alto livello come il Fortran, che gli consentì di condensare il codice in soli 16K di memoria. Iniziò con l’aggiungere 50 euristiche, degli schemi convenzionali per eseguire delle mosse in determinate situazioni.

MacHack fu il primo programma ad implementare un database di aperture e una tabella di trasposizione. Questa innovazione portò notevoli benefici perchè si basa sul fatto che circa il 25% di tutte le possibili sequenze di mosse termina nella medesima posizione.
Greenblatt scrisse il motore del suo programma in una sola settimana e passò i mesi successivi nel debuggarlo e nell’inserire nuove funzioni. Per raggiungere una profondità di ricerca di 5 mosse, il programma restringeva il numero di mosse plausibili da esaminare ad ogni nodo dell’albero: 15 per i primi due nodi e 9 per i successivi due passaggi, per un totale di 127.575 mosse per tutto l’albero di ricerca.
A Greenblatt fu offerta una laurea dal MIT se avesse scritto una tesi che documentasse il suo eccezionale lavoro. Ma quella tesi non fu mai scritta.

Nella primavera del 1967 studenti e professori del MIT organizzarono un evento in cui sfidavano Dreyfus a giocare una partita di scacchi contro MacHack VI. Dreyfus accettò.
Il computer giocò con il nero e la combattuta partita durò 37 mosse; il programma sembrava in netto vantaggio ma Dreyfus riuscì a conquistare la regina avversaria. A quel punto MacHack poteva portare a casa la partita solo tenendo costantemente sotto scacco il re, e fu proprio quello che fece, concluse dando scacco matto con un pedone.
Non ci furono plateali scene di esultanza da parte degli hacker, loro sapevano già che sarebbe finita così. Anche se il professor Dreyfus non si dimostrò un gran giocatore, quella fu un’affermazione storica.

Nello stesso anno, MacHack fu anche il primo programma di scacchi a partecipare ad un regolare torneo, il Boston Amateur championship, con classiche partite da 40 mosse in due ore e mezza.
Il programma riuscì ad imporsi in due partite e ne pareggiò altrettante.
Alla fine del 1967 MacHack venne fatto membro onorario della Federazione di scacchi americana e gli fu attribuito un rating di 1493 punti che salirono a 1529 nel corso del 1968, superando il livello medio dei giocatori iscritti alla federazione.
MacHack è stato anche il primo programma di scacchi che ottenne una vasta diffusione, essendo distribuito gratuitamente su molte macchine DEC. In seguito ne fu sviluppata anche una versione per PDP-10.

A quel punto la strada era tracciata e si assistette ad una rapida proliferazione di nuovi programmi di scacchi. Nei tre anni successivi al debutto di MacHack VI, ne furono rilasciati una decina, tanto che nel 1970 fu istituito il North American Computer Chess Championship, e nel 1974 Stoccolma ospitò il primo campionato del mondo dedicato a programmi di scacchi per computer.

Nel 1996 IBM Deep Blue vince contro il campione del mondo in carica Garry Kasparov, imponendosi nella sfida uomo vs computer più famosa della storia.