La storia dei programmi scacchistici

Vimes non aveva mai apprezzato nessun gioco più complesso delle freccette. In particolare, gli scacchi l’avevano sempre infastidito. Era lo stupido modo in cui i pedoni partivano e si massacravano con i pedoni opposti, mentre i re se ne stavano a passeggiare senza fare niente, che gli aveva sempre dato sui nervi; se solo i pedoni si fossero alleati, e magari si fossero coalizzati con le torri, l’intera scacchiera sarebbe potuta diventare una repubblica in una dozzina di mosse.

Riparte il nostro viaggio nel tempo alla scoperta della nascita dei programmi scacchistici, percorso fondamentale per capirne il significato e poi il funzionamento. Risaliamo dunque sulla DeLorean e viaggiamo a circa 100 anni da dove ci siamo lasciati l'ultima volta.

Verso la metà del ‘900 tre nerd ricercatori statunitensi dell’IBM, Herbert Simon, Allen Newell e Cliff Shaw si misero a studiare come la mente umana riesce a risolvere i problemi in modo intelligente per cercare di simulare questo procedimento in modo meccanico. I tre pensavano che se fossero riusciti a “far giocare” bene un computer, sarebbero riusciti anche a insegnargli a ragionare “come l’uomo” e magari anche meglio, visti gli enormi progressi in termini di velocità di calcolo delle macchine. In un articolo del 1958 scrivevano proprio la citazione di apertura dello scorso articolo, lanciando così la sfida per la costruzione di automi scacchistici.

Già nel 1950 il matematico Claude Shannon descriveva i possibili modi per programmare un giocatore di scacchi. Egli riteneva che, grazie alla teoria del Minimax (che approfondiremo in seguito) inventata da von Neumann sei anni prima, un computer potesse giocare in modo perfetto qualsiasi gioco ad informazione completa, compresi quindi gli scacchi.

Shannon si accorse però che questo compito era al di là della portata di qualsiasi computer, a causa dell’enormità delle mosse da considerare. Pensò quindi che per ottenere qualche risultato bisognasse considerare il massimo numero possibile di mosse e cercare di valutare la loro “bontà” e scegliere quella apparentemente migliore. Chiamò questo tipo di ricerca Strategia B o ricerca con valutazione euristica, mentre quella che considera tutte le mosse possibili Strategia A o ricerca per forza bruta.

Sebbene non sia possibile costruire una funzione di valutazione semplice ed accurata per valutare le posizioni degli Scacchi, ogni buon giocatore è in grado di fare una valutazione approssimata. Tali valutazioni si basano sulla struttura generale della posizione, sul numero e tipo di pezzi, sulla formazione dei pedoni, la mobilità, ecc. Tali valutazioni non sono perfette, ma quanto più è forte il giocatore, tanto migliore risulta la sua capacità di giudizio.

La linea di pensiero di Shannon venne seguita contemporaneamente dal logico britannico Alan Turing che, dopo aver proposto l’idea del test di Turing nel 1950, studiò gli scacchi come terreno ideale per lo sviluppo dell’Intelligenza Artificiale. Turing studiò il gioco sin da quando era al servizio del Department of Communications inglese per decifrare i codici usati nelle comunicazioni naziste durante la Seconda Guerra Mondiale, criptate tramite il cosiddetto sistema Enigma.

Dopo la guerra Turing si chiese se esistessero compiti impossibili per una macchina ma possibili per gli esseri umani; se fosse riuscito a far giocare una macchina a scacchi avrebbe dimostrato che un problema in cui è richiesta intelligenza è affrontabile in modo computazionale. Pur non avendo nessun calcolatore a disposizione Turing progettò un programma ideale, composto da una serie di regole che permettessero anche ad un essere umano totalmente inesperto di scacchi di giocare in modo automatico, seguendo alla lettera le istruzioni del programma. In effetti, a patto di eseguire alla perfezione le regole dell’algoritmo, è indifferente se ad eseguirle sia una macchina o una persona, il risultato è il medesimo.

Turing fu talmente entusiasta del suo programma che pur di farlo giocare calcolò egli stesso, facendo i conti con carta e matita, le istruzioni del programma, giocando contro un tale A. Glennie, un giocatore non molto forte. Questa può essere considerata la prima partita in assoluto che una macchina disputò contro un essere umano.

Mostra Approfondimento ∨

L’era dei calcolatori


La vera storia dei programmi scacchistici nacque quando si cominciarono a costruire i primi veri elaboratori elettronici. I principali laboratori di ricerca, all’inizio degli anni ’50, si cimentarono nell’affrontare la sfida più grande: costruire una macchina in grado di dominare i giochi di intelligenza.

Nel 1951, Turing cercò di implementare il programma Turbochamp sul computer Ferranti Mark I alla Manchester University, ma non raggiunse il suo obiettivo. Il suo collega, Dr. Dietrich Prinz, scrisse un programma per il Ferranti che risolveva puzzle scacchistici di matto in due mosse. Il programma girò per la prima volta nel novembre del 1951: esso esaminava ogni possibile mossa fino a trovare la soluzione, impiegando circa 15 minuti di tempo.

Attorno al 1955 alla Carnegie Mellon University di Pittsburgh, Allen Newell e Herbert Simon iniziarono invece la progettazione del programma CP-1 (Chess Player 1). Nel gennaio 1956 Simon scrisse:

[…] Newell e io abbiamo fatto progressi sostanziali sulla macchina che gioca a Scacchi, solo che per il momento non sa giocare a Scacchi ma solo cercare e scoprire dimostrazioni di teoremi di logica simbolica.

Il programma, chiamato Logic Theorist, dimostrò 38 dei primi 52 teoremi contenuti nei Principia Mathematica di Russell e Whitehead, e per alcuni trovò addirittura dimostrazioni più eleganti di quelle già sviluppate. Newell e Simon completarono il programma di scacchi solo nel 1958, in collaborazione con Cliff Shaw, ma vennero battuti sul tempo dall’IBM, che nel frattempo fece girare sull'Univac MANIAC I a Los Alamos in California, un programma in grado di giocare ad una versione semplificata degli scacchi, con una scacchiera 6X6 senza gli alfieri. Il programma giocò solo tre partite, una contro se stesso, una contro un giocatore esperto che vinse pur lasciando il vantaggio di una donna, e una contro un’anonima studentessa, che perse la partita perché aveva imparato a giocare a Scacchi la settimana prima (viene spontaneo chiedersi come mai i ricercatori scelsero proprio una donna per essere il primo umano a perdere una partita contro un computer…).

MANIAC I, utilizzato per lo sviluppo della prima bomba atomica, era capace di 11000 operazioni al secondo, grazie alla sua memoria di 80KB, 11KHz di velocità, e 2400 tubi catodici.

Nel 1957 un ricercatore IBM, Alex Bernstein, con i suoi colleghi Michael Roberts, Thomas Arbucky e Martin Belsky, creò al MIT il primo vero e proprio programma di scacchi. Venne eseguito sull’IBM 704 (42000 istruzioni al secondo), uno degli ultimi computer a tubo catodico. Ci metteva circa 8 minuti ad eseguire una mossa.

Il programma di Newell, Simon e Shaw, chiamato poi NSS, fu nel 1958 il primo programma scritto in un linguaggio ad alto livello ed impiegava circa un’ora per eseguire una mossa. Il programma utilizzò per la prima volta degli algoritmi di ricerca basati su strategie euristiche con la tecnica della potatura alfa-beta (sì, vedremo anche questa più avanti ;) ).

La corsa alla Luna


Per diversi anni il MIT fu il più importante centro di ricerca sul gioco artificiale. I principali nuovi programmi furono scritti in LISP da John McCarty (RIP “zio” :o ) e in FORTRAN e assembler da Alan Kotok, che scrisse il programma per la sua tesi di laurea. I primi successi dei giocatori artificiali americani indussero anche alcuni ricercatori europei e russi a sviluppare programmi per giocare a scacchi. Nel 1967, nel periodo della guerra fredda e della corsa allo spazio, Kotok e McCarty, da Stanford in California, sfidarono per corrispondenza una macchina sovietica, realizzata con la collaborazione dell’ex Campione del Mondo Mikhail Botvinnik. Il risultato fun un clamoroso 3-1 a favore dell’URSS, che si aggiudicò l’incontro con due vittorie e due patte.

Una sconfitta del genere negli anni della corsa alla Luna venne vista come una vera e propria onta nazionale, che stimolò nuove ricerche in tutti gli Stati Uniti. Greenblatt, una altro ricercatore del MIT, scrisse il programma MacHack, che, usando un calcolatore Digital PDP-6, fu il primo giocatore artificiale a debuttare in un torneo ufficiale a Boston, ottenendo anche un punteggio Elo. Migliorato freneticamente per un incontro con un Campione del Mondo R. Fisher, ottenne un punteggio Elo di 1500, pari ad un dilettante di medio livello.

MacHack non giocò mai bene, ma ad un convegno del 1968 attirò l’attenzione del Maestro di Scacchi David Levy. Egli scommise cospicue somme di denaro affermando che nessun giocatore artificiale sarebbe riuscito a batterlo nei seguenti 10 anni. In questo modo, più di ogni altro egli incoraggiò le ricerche sui giocatori artificiali di scacchi. I ricercatori decisero di incontrarsi annualmente per misurare i progressi conseguiti nei giocatori artificiali: nel 1970 iniziò una competizione a New York, la North American Computer Chess Championship, che venne ripetuta ogni anno fino al 1994. Nel 1974 venne introdotta, sempre sotto suggerimento di Levy, il primo Campionato del Mondo per giocatori artificiali. Da allora questo torneo si tenne ogni tre anni fino al 2002 e ogni anno dal 2003 ad oggi, passando per Lega Nè Torino nel 2006 e Pechino nel 2008.

Nel 1974 ancora una volta vinse un programma russo, Kaissa, che però fu l’ultimo a vincere in competizioni internazionali. Nel 1978, a dieci anni esatti dal lancio della scommessa di Levy, Chess 4.7, che l’anno prima aveva vinto il Campionato del Mondo, batté in una partita lo stesso Levy, raggiungendo una valutazione Elo di circa 1900 punti.

La nuova generazione


La fine della scommessa di Levy chiuse l’epoca pionieristica dei giocatori artificiali. Con la fine degli anni ’70 vennero introdotte due grandi novità: l’arrivo dei microprocessori ed il miglioramento delle tecniche di progettazione di hardware specializzato. Nel 1977, ad esempio, uno studente di Berkley, Özalp Babaoglu, progettò un circuito capace di funzionare come generatore di mosse. Questo diede il via a numerose ricerche volte a creare macchine studiate appositamente per il gioco. Nei Laboratori Bell venne messo a punto il primo computer con hardware dedicato capace di giocare a scacchi, chiamato Belle. Esso perse per mezzo punto il Campionato del Mondo nel 1979 piazzandosi secondo, mentre vinse il titolo nel 1980.

All’inizio degli anni ’80 venne inoltre presa in considerazione la possibilità di utilizzare il calcolo parallelo; nel Campionato del 1983 Cray Blitz battè Belle, aggiudicandosi il titolo; il programma utilizzava la potenza del calcolatore parallelo Cray-1, che era il sistema di elaborazione più potente del mondo. Cray Blitz, dopo Belle, fu il secondo programma a guadagnare il titolo di Maestro, dominando la scena per la prima metà degli anni ’80. Nel 1985 arrivò Hitech, che con una valutazione Elo di 2220 punti sconfisse Cray Blitz e arrivò l’anno successivo a 2360 punti. Nel frattempo vari programmi commerciali cominciarono a farsi strada, tra i quali Mephisto, che rimase vincitore fino ai primi anni ’90, quando viene battuto da Gideon, un programma che girava su un normale computer IBM corredato di una scheda speciale detta Chess Machine.

La vera svolta si ebbe nel 1988, quando Deep Thought (epic cit, non c’è bisogno di spiegarvela :res: ) battè in un torneo il danese Bent Larsen, un Grande Maestro classificato tra i migliori 100 giocatori del mondo, con una valutazione Elo di 2551 punti. L’anno seguente il suo inventore, Feng-hsiung Hsu della IBM, ebbe l’onore, impensabile fino a qualche anno prima, di far giocare il programma contro il Campione del Mondo in carica, Garry Kasparov, il primo uomo ad aver raggiunto una valutazione di 2800 punti Elo. La differenza di 300 punti a quei livelli è abissale e Kasparov battè Deep Thought con un secco 2-0. Qualche mese dopo anche Anatolij Evgen’evič Karpov, ex Campione del Mondo, volle sfidare il programma e rischiò seriamente di essere battuto. L’interesse suscitato da questo programma richiamò l’attenzione di Levy, che decise di sfidare anch’egli Deep Thought, perdendo con un sonoro 4-0.

L’intelligenza dei programmi scacchistici era davvero in rapido aumento.

Nel 1990 il Campione del Mondo Karpov perse contro Mephisto in una esibizione demmerda a Monaco. L’onore degli scacchisti venne difeso a spada tratta da Kasparov, che nel 1992 batté Fritz 2 in una partita lampo Mostra Approfondimento ∨

con il risultato di 6 vittorie, 1 pareggio e 4 sconfitte.

Nel 1994 WChess fu il primo programma a conquistare il titolo di Grande Maestro e sempre nello stesso periodo Kasparov perse contro Fritz 3 in un torneo blitz. L’anno seguente si prese però una rivincita battendo Fritz 4 e Genius 3.0, entrambi forti programmi commerciali.

Il Blu Profondo


Nel 1996 i tempi erano ormai maturi per organizzare un incontro uomo-macchina a cadenza di tempo da torneo: la sfida venne raccolta dal Campione del Mondo Kasparov e da Feng-hsiung Hsu e i ricercatori dell’IBM, che progettarono e realizzarono una macchina su misura per giocare a scacchi: Deep Blue, diretto erede di Deep Thought. La sfida iniziò il 10 febbraio 1996 e si svolse in 6 partite. Deep Blue vinse la prima partita, ma Kasparov rovesciò il risultato nelle seguenti cinque (tre vinte e due patte) vincendo così il match. Era la prima volta che un Campione del Mondo veniva battuto in una partita in torneo da una macchina.

Mostra Approfondimento ∨

Deep Blue fu poi pesantemente aggiornato per un rematch e giocò nuovamente con Kasparov nel maggio 1997, vincendo la rivincita da sei partite per 3,5 – 2,5.

La forza di Deep Blue derivava principalmente dalla sua straordinaria potenza computazionale. Il computer aveva un massiccio parallelismo, costituito da 30 nodi basati su RS/6000, ognuno dei quali conteneva un microprocessore P2SC da 120 Mhz, supportati da altri 480 processori specifici VLSI progettati per il gioco. L’algoritmo per il gioco fu scritto in C, girava sotto un sistema operativo AIX ed era capace di calcolare più di 200 milioni di posizioni al secondo. Nel giugno 1997 Deep Blue venne classificato al 259 posto tra i più potenti supercomputer mai costruiti, con prestazioni nei test da 11.38 Gigaflops.

Le sue funzioni di valutazione erano inizialmente scritte in forma generale, con molti parametri da definire (per esempio quanto è importante una posizione sicura per il re in confronto a un vantaggio spaziale nel centro della scacchiera). I valori ottimali per questi parametri furono poi determinati dal sistema stesso, analizzando migliaia di partite di campioni. Prima del secondo incontro, la conoscenza sugli scacchi del programma era stata finemente migliorata dal Gran Maestro Joel Benjamin. La lista delle aperture fu fornita dai campioni Miguel Illescas, John Fedorovich e Nick De Firmian.

Dopo il match perso, Kasparov disse che alcune volte gli era parso di notare un’intelligenza e una creatività così profonde nelle mosse della macchina, che non riusciva a comprenderle. Egli avanzò anche il sospetto che la macchina avesse avuto un “aiuto” umano durante la partita, sospetto che ritornò più volte sia quando si seppe che la macchina non era posta nella stanza nella quale si disputava la partita ma ad alcuni chilometri di distanza e che quindi i dati venivano inviati da terzi sia per il fatto che al campione russo non furono mai forniti i tabulati sull’attività del computer, che egli aveva richiesto secondo gli accordi della sfida. Chiese la rivincita, ma l’IBM rifiutò e ritirò Deep Blue.

Oltre il limite del Super Sayan


Oggi le macchine hanno superato di gran lunga la capacità e la bravura degli esseri umani. Nelle ultime valutazioni il programma Houdini 1.5a (64-bit 4CPU) ha ottenuto una valutazione Elo di 3277 punti girando su un semplice personal computer Athlon 64 X2 4600+ ad una velocità 2.4 GHz. Il punteggio è di gran lunga superiore ai 2851 totalizzati da Kasparov come più alto punteggio umano mai raggiunto. È interessante notare che i sedici computer partecipanti al campionato mondiale di Toronto nel 1977 erano tutti grossi calcolatori: venne calcolato che il loro costo totale era di 40 milioni di dollari, e un’ora di gioco costava 10.000 dollari. Negli ultimi campionati invece partecipano normali personal computer che, al più, costano qualche migliaia di euro.

Occorre domandarsi ora come si orienterà la ricerca in futuro. Esistono molti giochi più complessi degli scacchi, quali ad esempio il Go o gli Scacchi cinesi. Nonostante questo i ricercatori sostengono che siano i giochi ad informazione incompleta ad [latex]n[/latex] giocatori quelli che devono essere studiati in futuro: un esempio è il Risiko. Questi giochi creano interazioni molto complesse che sono poco studiate.

E adesso?


Ora che abbiamo concluso la sorvolata sul panorama informatico scacchistico dai suoi albori, è tempo di dedicarsi alle cose veramente nerd, ovvero l’intelligenza artificiale che muove i motori scacchistici odierni.

Nel prossimo articolo inforcheremo gli occhiali da nerd programmatori e cercheremo di capire quali sono le fondamenta su cui poggia la struttura di un motore scacchistico: la rappresentazione in memoria della schacchiera e dei pezzi e la conseguente generazione delle mosse.

Stay tuned.

[How machines play chess] è una rubrica tenuta da @ryanvespucci sul funzionamento dei giocatori artificiali di scacchi.

Ryan Vespucci a.k.a. Ryan Vespucci

Il senso comune immagina che, quando uno vede un tavolo, vede un tavolo. Grossolana illusione. (Bertand Russel, L'abc della relatività)
Aree Tematiche
Boardgames Select Storia
Tag
martedì 25 ottobre 2011 - 15:47
Edit

Lega Nerd Podcast

Lega Nerd Live

LN Panic Mode - Premi "P" per tornare a Lega Nerd