le operazioni permesse (le mosse degliscacchi) sia nell'obiettivo finale (lo scac-co matto); inoltre, non è tanto semplice

• da essere banale né tanto complesso darendere impossibile una soluzione sod-disfacente. E organizzando una partitafra una macchina del genere e un gioca-tore si può avere una chiara indicazionedella capacità del calcolatore in questotipo di ragionamento.»

Forse la conseguenza pratica più im-portante di questi studi è stata la dimo-strazione dell'efficacia dell'analisi al cal-colatore; il perfezionamento delle rela-tive tecniche porterà senza dubbio a pro-gressi nei settori della progettazione direti, della messa a punto di modelli direazioni chimiche e anche dell'analisilinguistica.

Dicembre 1990Numero 268Anno XXIIIVolume XLV

LE SCIENZESCIENTIFICAMERICAN

Jastoria delle macchine che giocano ascacchi iniziò negli anni successivi al

1760, allorquando il barone Wolfgangvon Kempelen presentò in Europa il suoautoma, che venne soprannominato «ilturco» perché si presentava come unamarionetta con tanto di mustacchi e tur-bante, apparentemente azionata da uncomplicato meccanismo che si trovava in

un compartimento sottostante. In gene-re il congegno giocava bene e una voltamandò su tutte le furie Napoleone Bo-naparte sconfiggendolo in 19 mosse.Edgar Allan Poe, fra gli altri, scoprì inseguito il segreto dell'automa: nel com-partimento era nascosto un abile scac-chista di piccolissima statura. Tuttaviala ragione che fece intuire a Poe l'imbro-glio era erronea: lo scrittore affermò in-fatti che se si fosse trattato di unamacchina autentica, non avrebbe maidovuto perdere!

Alan M. Turing, matematico, studio-so di calcolatori e crittografo, fu trai primi a confrontarsi con il problemadi un calcolatore che fosse in grado digiocare a scacchi, ma si accorse che erapiù semplice attuare il suo programmadi generazione delle mosse e di valuta-zione della posizione a mano anzichécon la macchina. Il tedesco Konrad Zusee altri studiosi fecero tentativi analo-ghi, ma l'opera fondamentale fu quelladi Shannon. Egli prese le mosse dallescoperte di John von Neumann e OskarMorgenstern che, nella loro teoria ge-nerale dei giochi, avevano escogitatoun algoritmo «minimax» mediante il

quale era possibile determinare la mos-sa migliore.

Essenzialmente, l'algoritmo determi-na tutte le possibili posizioni risultantidopo un certo numero di mosse dei duegiocatori, assegna loro un valore nume-rico e, in funzione di questi valori, sta-bilisce quale sia la mossa migliore. All'i-nizio il generatore di mosse calcola tut-te le mosse possibili per il calcolatorea partire dalla posizione in corso, poitutte le possibili risposte dell'avversarioe così di seguito. L'algoritmo esaminapertanto un albero di gioco, nel qualeciascuna posizione è connessa alle posi-zioni successive consentite dalle regoledel gioco.

A ciascun livello dell'albero vi è unnumero di posizioni circa 38 volte supe-riore a quello del livello precedente (38è il numero medio di mosse possibili inuna tipica posizione di gioco), oppurecirca sei volte superiore se si utilizzala «potatura alfa-beta» (si veda la 4i-nestra>, a pagina 16). La maggior partedelle posizioni si trova dunque alle estre-mità dei rami dell'albero, dove esso con-tinua a crescere fino a quando l'analisinon sia completata o il tempo a disposi-

Il calcolatoreGrande Maestro di scacchi

Nei 40 anni trascorsi dai primi tentativi di programmare calcolatori capacidi giocare a scacchi, le macchine hanno battuto in torneo giocatori di tuttii livelli di abilità: il campione del mondo sarà il prossimo a cadere?

di Feng-hsiung Hsu, Thomas Anantharaman, Murray Campbell e Andreas Nowatzyk

N

el gennaio 1988, durante unaconferenza stampa tenuta a Pa-rigi dal campione del mondo di

scacchi Gary K. Kasparov, un giornali-sta chiese se un calcolatore sarebbestato in grado di sconfiggere un grandemaestro prima della fine del secolo. Sen-za indugio Kasparov rispose: «Certa-mente no, e se qualche Grande Maestroavesse davvero difficoltà a giocare con-tro un calcolatore sarei felice di dargliqualche consiglio».

Dieci mesi dopo questa affermazionedi Kasparov, in un importante torneo te-nutosi a Long Beach, in California, ilGrande Maestro Bent Larsen, che erastato in lizza per il titolo mondiale, fusconfitto da un calcolatore da noi ideatoalla Carnegie-Mellon University. Oltre aquesto incontro, Deep Thought, unacombinazione di software e di hardwarededicato, vinse altre cinque partite, nepareggiò una e una ne perse, conquistan-do in tal modo il primo posto ex aequocon il Grande Maestro Anthony Miles.Dato che per regolamento un calcolato-re non può vincere denaro in un torneo,Miles intascò tutti i 10 000 dollari del pri-mo premio. (Tuttavia Deep Thought losconfisse un anno dopo in una partita diesibizione.)

Entro l'estate 1990 - durante la qualetre fondatori del gruppo Deep Thoughtsono entrati a far parte della IBM - ilcalcolatore aveva vinto cinque delle 10partite disputate in torneo contro Gran-

12 LE SCIENZE n. 268, dicembre 1990

di Maestri e 12 delle 14 partite giocatecontro Maestri Internazionali. Alcuni diquesti incontri e decine di altri che hannoopposto il calcolatore ad avversari di li-vello inferiore sono stati giocati sotto gliauspici della US Chess Federation, cheha attribuito a Deep Thought una valu-tazione Elo di 2552. [P, da notare tutta-via che la scala statunitense sopravvalutai punteggi di circa 100 punti rispetto aquella della FIDE (Fédération Interna-tionale des Echecs).] Questa valutazionepone Deep Thought fra i Grandi Maestridi livello più basso, ma è comunque mol-to superiore a quella di un giocatore me-dio di torneo, che in genere ha un pun-teggio intorno a 1500 (si veda l'illustra-zione alle pagine 14 e 15). Nelle partitedisputate dopo l'agosto 1988, quando ilcalcolatore è stato portato alla sua attua-le velocità di analisi di 750 000 posizionial secondo, la sua valutazione Elo è statasuperiore a 2600.

Il modello perfezionato del nostro cal-colatore, che si prevede disputerà le sueprime partite nel 1992, sarà dotato di unhardware molto più potente che aumen-terà di oltre 1000 volte la velocità di ana-lisi, fino a circa un miliardo di posi-zioni al secondo. Questa sola modificapotrebbe rendere il discendente di DeepThought addirittura più forte di Kaspa-rov o di qualunque altro giocatore del-la storia.

Ma perché si insegna a una macchinacome minacciare un re di legno su una

scacchiera? In primo luogo gli scacchivengono tradizionalmente considerati inOccidente come il principale gioco di in-telligenza; per dirla con Goethe, sono«la pietra di paragone dell'intelletto».Secondo alcuni, la costruzione di un cal-colatore in grado di giocare bene a scac-chi dimostrerebbe che è possibile mette-re a punto modelli dei processi di pen-siero o, viceversa, che in questo gioconon è necessario pensare. Sia l'una sial'altra conclusione imporrebbero di rive-dere ciò che si intende comunemente perintelligenza.

Oltre a ciò, un calcolatore che giochia scacchi costituisce un problema tecnicoappassionante, come scrisse 40 anni fa su«Scientific American» Claude E. Shan-non, il padre della teoria dell'informa-zione: «Si studia il problema del giocodegli scacchi al fine di sviluppare tecni-che che possano essere sfruttate per ap-plicazioni più pratiche. Il calcolatore chegioca a scacchi rappresenta un punto dipartenza ideale per diverse ragioni. Ilproblema è definito nettamente, sia nel-

Il campione del mondo Gary Kasparov po-sa con un IBM PS/2, usato per comunicarecon Deep Thought, prima di una partitadisputata alla fine del 1989. Kasparov vinsefacilmente sebbene la macchina venga con-siderata al livello di un Grande Maestro.

600 700 800 900 1000 1100 1200 1 1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000

PUNTEGGI ASSEGNATI DALLA US CHESS FEDERATION

3100 3200 3300 3400

3

o

15

14

Iii

O2

LU

9 zEO

8 i-<"(DjoO

6o

U,"

4 0

3 OO

O2a.

7

13

12

10

ATORE MEDIO DI TORNEO IFICAZIONITENSI

NAZIONALETITOLI INTERNAZIONALI -

DEEP THOUGHTA 10 LIVELLI

HITECHA 9 LIVELLI

BELLEA 8 LIVELLI SPAROV

NE DEL MONDOBELLEA 7 LIVELLI

ANATOLIJ KARPOV- SFIDANTE

BELLEA 6 LIVELLI

BOBBY FISCHER,VERSO IL 1972

ENENDO CONTOLL'INFLAZIONE

DEI PUNTEGGI)

BELLEA 5 UVELLI

MAESTRO STRO SENIORzione del calcolatore non sia scaduto.Una funzione di valutazione assegnaquindi un punteggio a ciascuna posizio-ne finale, attribuendo per esempio un 1a uno scacco matto ai danni dell'avver-sario, un — 1 a uno scacco matto aidanni della macchina e uno O a una pat-ta. E anche possibile considerare e con-frontare situazioni meno nette: per e-sempio il calcolatore può tener contodella qualità (ossia il valore dei pedoni edelle figure) e calcolare il valore delleposizioni in base a parametri che defini-scono la disposizione delle figure, loschieramento dei pedoni, l'occupazionedi una colonna aperta, il controllo delcentro e così via.

Si può migliorare il gioco di un calco-latore aumentandone la profondità d'a-nalisi (ossia il numero di semimosse cheesso considera prima di valutare le posi-zioni) o perfezionandone la funzione divalutazione. La macchina giocherebbein maniera perfetta se fosse in grado diesaminare in modo esaustivo tutte lepossibili successioni di mosse fino al mat-to di una delle due parti o alla patta. Unamacchina siffatta potrebbe allora sor-prendere l'avversario annunciando giàalla prima mossa: «Il bianco muove evince in 137 mosse» oppure giudicandola posizione insostenibile e abbandonan-do. Ma, se l'analisi esaustiva è facile ingiochi come il filetto, è impossibile negliscacchi, dove si possono avere 10 120 par-tite diverse. Un gioco egualmente per-fetto potrebbe nascere dall'esame di unsolo livello dell'albero, ammesso che lavalutazione delle posizioni fosse di livel-lo pari a quella rivendicata da Capablan-ca, il quale affermava di prevedere unasola mossa: la migliore.

primi studiosi a occuparsi di questosettore erano ben lungi dall'avanza-

re pretese del genere, dato che fino al1958 non si era neppure in grado di pro-grammare macchine che rispettassero leregole degli scacchi. Dovevano infattipassare altri otto anni prima che il pro-gramma MacHack-6, ideato da RichardD. Greenblatt del Massachusetts In-stitute of Technology, riuscisse a rag-giungere il livello del giocatore mediodi torneo.

Gli autori di programmi per gli scac-chi, via via più numerosi, comincia-rono a dividersi in due fazioni dalle fi-losofie distinte, che potremmo chiama-re degli «strateghi» e dei «tecnici». Iprimi affermavano che un calcolatoredovrebbe giocare a scacchi allo stessomodo di una persona, decidendo le mos-se per mezzo di ragionamenti espliciti,mentre i tecnici adottavano un atteggia-mento meno rigido, sostenendo che untipo di ragionamento valido per gli esseriumani potrebbe non essere applicabile auna macchina. Agli inizi, quando la pro-gettazione di calcolatori capaci di gioca-re a scacchi era più una questione teoricache pratica, gli strateghi sembraronoavere il sopravvento.

La competitività sempre crescente dei cal-colatori è chiara in questo confronto fra ipunteggi dei 35 000 membri della US ChessFederation e quelli di macchine con diverseprofondità di analisi (in verde). I calcola-tori guadagnano circa 200 punti per ciascu-na semimossa, o livello dell'albero di gioco,in più che esaminano. Attualmente DeepThought analizza 10 livelli e ha una valu-tazione di circa 2600; il suo successore po-trà esaminare 14 o 15 livelli e ottenere cosìuna valutazione di gran lunga superiore.

La fazione dei tecnici divenne prota-gonista negli anni settanta, quando siscoprì che le prestazioni dei programmierano quasi proporzionali alla profondi-tà di analisi: a ogni livello aggiuntivo del-l'albero di gioco che viene esaminatol'Elo aumenta di 200 punti (si veda l'il-lustrazione in queste due pagine). I pro-grammatori si affannarono allora peravere accesso a calcolatori sempre piùveloci e applicarono tutti i trucchi delmestiere per ottenere una maggiore pro-fondità d'analisi dalla potenza di cal-colo disponibile.

Tuttavia, mettere a punto la ricercadelle posizioni non basta. I primi pro-grammi per gli scacchi generavano le po-sizioni senza alcun discernimento: con-sideravano, per esempio, distinte suc-cessioni che, per inversione di due mos-se, portavano alla medesima posizione.Queste operazioni ridondanti vengonoattualmente evitate conservando le po-sizioni in matrici di memoria. Questostratagemma facilita anche il processodi potatura dell'albero di gioco, in quan-to consente di scartare immediatamentenumerose successioni di mosse prive diinteresse.

Il problema più arduo è quello di sta-bilire fino a quale profondità occorraesaminare una diramazione dell'alberodi gioco. Non è certo possibile continua-re l'analisi indefinitamente, ma sarebbecomunque auspicabile non interromper-la in una posizione «instabile», comequella che si ha nel bel mezzo di unoscambio di pezzi. Si supponga, per esem-pio, che il calcolatore esamini otto se-mimosse per ciascuna diramazione e ar-rivi a una posizione, dopo l'ottava se-mimossa , in cui esso apparentementeguadagna un cavallo in cambio di un pe-done. Anche se con la mossa immedia-tamente successiva l'avversario potesserecuperare il cavallo e ottenere il guada-gno netto di un pedone il calcolatoreperseguirebbe ostinatamente il vantag-gio illusorio.

Questo «effetto orizzonte», come vie-ne chiamato, spinge spesso i calcola-tori a commettere una sorta di suici-dio scacchistico che non si osserva nep-pure in partite tra giocatori alle primearmi: all'improvviso e senza alcuna ra-gione apparente, la macchina cominciaa sacrificare pedoni e figure, riducen-

dosi in breve in una posizione insosteni-bile. Per diminuire la probabilità di er-rori di questo tipo, virtualmente tutti iprogrammi attuali comprendono una fa-se aggiuntiva di ricerca delle posizionistabili, il cui scopo è esaminare una se-quenza di cattura di pezzi fino al raggiun-gimento di una posizione stabile checonsenta di applicare in un contesto nonfuorviante la funzione di valutazione.

Negli anni settanta e agli inizi deglianni ottanta si assistette al predomi-nio delle macchine che si basavano sul-la «forza bruta», nel senso che il lorosuccesso era dovuto a un'abile attuazio-ne delle strategie di ricerca e analisidelle posizioni descritte in precedenza.Questo periodo fu dominato quasi inin-terrottamente dal programma Chess 4.0della Northwestern University e dai pro-grammi 4.X da esso derivati. Via viaadattati alle nuove generazioni di cal-colatori, questi programmi sono andatimigliorando costantemente il loro pun-teggio nella scala di valutazione fino asuperare nel 1979 il livello di Esperto(2000 punti).

Sempre negli anni settanta si sonoavuti diversi tentativi di costruire calco-latori dedicati per il gioco degli scacchi.Il più famoso, Belle, realizzato presso gliAT&T Bell Laboratories, raggiunse illivello di Maestro (2200 punti) nel 1983.L'apogeo dell'era delle macchine che sibasavano sulla forza bruta si ebbe nel

1986 con l'emergere di Cray Blitz, unprogramma ideato per i supercalcolatoriCray, e di Flitech, una macchina dedica-ta che calcolava le successioni di mos-se per mezzo di 64 microelaboratori (unoper ciascuna casella della scacchiera).Hitech vinse nel 1985 il Campionato discacchi nordamericano per calcolatori,mentre l'anno successivo Cray Blitz di-venne campione del mondo fra i calco-latori, battendo proprio Hitech nella«bella» per il titolo. Cray Blitz e Hi-tech erano in grado di esaminare rispet-tivamente 100 000 e 120 000 posizionial secondo.

La storia di Deep Thought è piuttostosingolare. In primo luogo, questa mac-china è stata sviluppata da un gruppo distudenti specializzandi senza alcun ap-poggio ufficiale o supervisione diretta dimembri della Carnegie-Mellon Univer-sity. (Il gruppo di ricerca che lavora suicalcolatori che giocano a scacchi pressoquesta università non ha alcuna connes-sione con gli ideatori di Deep Thought.)In secondo luogo, i membri del grupponon hanno tutti la stessa formazione eprobabilmente proprio questa circostan-za ha consentito loro di affrontare il pro-blema in maniera originale.

Nei giugno 1985 uno di noi (Hsu) sco-prì che sarebbe stato possibile co-

struire un generatore di mosse su un sin-golo chip sfruttando le tecnologie di in-

tegrazione su grandissima scala (vLsi)fornite alla comunità scientifica dallaDefense Advanced Research ProgramsAgency (DARPA). Hsu trasse ispirazio-ne per il suo chip dal generatore dimosse di Belle, ma vi introdusse diver-si perfezionamenti per rendere il pro-getto compatibile con le tecnologie VLSI.Il chip venne concepito in modo che icomponenti elettronici (fra cui 35 925transistori) potessero essere sistematisulla superficie più piccola possibile,nonostante la mediocre qualità del siliciofornito dalla MOSIS, la società che of-friva i servizi di fabbricazione per iprogetti sovvenzionati dalla DARPA (ladimensione minima di un componenteera di tre micrometri). Hsu impiegò seimesi per il lavoro di progettazione, veri-fica e messa a punto, ma poi dovetteaspettare altri quattro mesi prima di ri-cevere i primi esemplari funzionanti. Ilcollaudo del chip fu eseguito collegando-lo a una stazione di lavoro scientifica;riuscimmo così ad appurare che esso erain grado di elaborare più di due milionidi mosse al secondo, a una velocità oltre10 volte maggiore della schiera di 64 mi-croelaboratori dell'Hitech.

A questo punto Hsu iniziò a collabo-rare con Thomas Anantharaman, che al-l'epoca si stava specializzando in scien-za dei calcolatori presso il gruppo diricerca sul riconoscimento del linguag-gio della Carnegie-Mellon University.

Anantharaman aveva scritto un proprioprogramma per gli scacchi che generavale mosse attraverso un pacchetto di soft-ware. Sostituendo quest'ultimo con ilcongegno messo a punto da Hsu, Anan-tharaman riuscì a migliorare del 500 percento la velocità di analisi del program-ma, giungendo fino a 50 000 posizionial secondo.

Hsu e Anantharaman, ringalluzzitidal successo, decisero di preparare lamacchina per farla partecipare all'edi-zione 1986 del Campionato nordameri-cano di scacchi per calcolatori, che do-veva avere inizio di lì a sette settimane.Murray Campbell e Andreas Nowatzyk,che si stavano specializzando in scienzadei calcolatori, vennero chiamati a farparte del gruppo. Era importante poterdisporre di una funzione di valutazionepiù raffinata e Campbell, che avevaesperienza di gioco agonistico, accettò difarsene carico. Il secondo e più impegna-tivo compito, data la limitatezza del tem-po disponibile, era quello di potenziareil congegno in modo che potesse fungereda semplice strumento di ricerca, al finedi sfruttare più a fondo di quanto nonfosse possibile con la stazione di lavorola velocità potenziale del chip generato-re di mosse.

Hsu dovette adottare misure draco-niane per poter ultimare il progetto intempo utile, tanto da decidere che lamacchina avrebbe ignorato due regole

14 LE SCIENZE n. 268, dicembre 1990 LE SCIENZE n. 268, dicembre 1990 15

Un programma scacchistico genera un albero digioco che contiene tutte le mosse possibili a partireda una posizione data, valuta le posizioni risultantie risale a determinare la migliore prima mossa. Allevarie posizioni vengono assegnati punteggi utili dalpunto di vista del programma: un punteggio elevatocorrisponde a una posizione vantaggiosa.

Una tecnica molto semplice, detta algoritmo mini-max, seleziona solo le linee di gioco migliori cercan-do i punteggi massimi per le mosse del calcolatoree quelli minimi per le risposte dell'avversario. Nel-l'albero in alto, per esempio, i nodi B ed E sonominimizzati a 3 e —1 rispettivamente, mentre il nodoA è massimizzato a 3.

Con questa semplice procedura è possibile ana-G lizzare un ulteriore livello dell'albero solo aumentan-do la potenza di calcolo di un fattore 38 (pari alnumero medio di mosse possibili in una tipica posi-zione sulla scacchiera). La potatura «alfa-beta» per-feziona l'algoritmo consentendo al programma diignorare linee di gioco irrilevanti, cosicché è suffi-ciente un potenziamento di un fattore sei per analiz-zare un livello in più. Se per esempio il calcolo deipunteggi comincia nel nodo C e procede verso de-stra, il programma assegna a B il valore 3 e trovache E ha un valore inferiore o uguale a 2; pertantoconclude che è inutile considerare F.

Un altro metodo, detto dell'estensione particola-re » sfrutta meglio le capacità del calcolatore con-centrandosi sulle posizioni critiche. Nell'albero in

D basso, il valore di B dipende fortemente da quello diC, mentre il valore di D non è legato a nessuno deivalori delle posizioni derivate. Per migliorare l'affi-dabilità del punteggio di A l'algoritmo analizza quindiun'ulteriore semimossa successiva a C. Questo me-

o o todo permette a Deep Thought di spingere l'analisia profondità straordinaria in molte posizioni tattica-mente complesse.

1 -10 -10 -10 0 0

D F

4 3 2

1'990dijimajnterna aie Michae

fondamentali degli scacchi: l'arrocco ela patta per ripetizione della posizione.(Si ha questo esito quando in una partitauna stessa posizione si ripresenta per trevolte e la mossa tocca sempre al mede-simo giocatore.) Per compensare alme-no in parte queste omissioni adottammouna strategia di ricerca ibrida: i primilivelli dell'albero di gioco venivano esa-minati da un calcolatore ausiliario, chetenesse conto dell'arrocco e della pattaper ripetizione della posizione, mentre ilivelli successivi (che ovviamente com-prendevano la maggior parte delle posi-zioni) venivano analizzati dalla nostramacchina.

Data la scarsità di fondi, realizzammola nostra prima macchina, ChipTest, uti-lizzando componenti e sistemi che face-vano parte di altri progetti; il valorecomplessivo degli elementi non supera-va i 500 dollari (1000 tenendo conto delcosto dei chip costruiti con i fondi dellaDARPA). Ma né il nostro congegno néil calcolatore ausiliario erano perfetta-mente a punto all'inizio del campionato,sicché ChipTest riuscì soltanto a pareg-giare vittorie e sconfitte. Non si trattavain ogni caso di un risultato scadente, persole sette settimane di lavoro.

Questa esperienza ci permise di impa-rare molte cose. Hsu osservò, per esem-pio, che altri due programmi partecipan-ti al campionato si erano impegnati inlinee di gioco in cui tutte le mosse appa-rivano forzate e nessuna delle due partipoteva prevedere l'esito finale. In altritermini, il programma che otteneva unvantaggio lo doveva unicamente al caso.Hsu propose di correggere questo difet-to introducendo quello che egli chiamaalgoritmo di estensione particolare: nelcaso in cui il calcolatore trovi una solarisposta adeguata l'analisi viene spinta amaggiore profondità, allo scopo di stu-diare con particolare attenzione le posi-zioni critiche (si veda la «finestra» inquesta pagina).

Quando uno dei giocatori sta per cat-turare un alfiere intrappolato, per esem-pio, il difensore ha a disposizione un nu-mero sempre minore di mosse correttevia via che la profondità di analisi au-menta; alla fine vi è una sola rispostapossibile, dopo di che l'alfiere è perso.L'algoritmo di estensione particolare siapplica a casi di questo tipo; in unapartita ha permesso al calcolatore di stu-pire un maestro annunciando un mattoin 19 mosse.

Anantharaman, l'unico fra noi capacedi comprendere il programma da luiscritto per il calcolatore ausiliario diChipTest, programmò da solo l'algo-ritmo di estensione particolare, mentreHsu completava il microcodice, ossial'insieme di istruzioni che controllanol'hardware al livello più elementare.Con una capacità di analisi di 400 000--500 000 posizioni al secondo, ChipTestvinse nettamente l'edizione 1987 delCampionato nordamericano di scacchiper calcolatori, riuscendo a sconfiggerefra gli altri anche la macchina campionedel mondo, Cray Blitz. In questo modosi concluse l'era della forza bruta; oggiquasi tutti i programmi migliori com-prendono almeno alcuni elementi di ri-cerca selettiva.

Il nostro lavoro aveva indicato che viera un notevole margine di miglioramen-to per quanto riguardava la velocità e lacapacità di analisi di ChipTest. La som-ma di circa 5000 dollari necessaria per losviluppo del nuovo progetto - chiamatoDeep Thought - ci venne generosamentemessa a disposizione dal relatore di Hsu,H. T. Kung.

La versione base di Deep Thoughtcomprende 250 chip, fra cui due microe-laboratori, montati tutti su un singolopannello grande quanto metà di una pa-gina di questa rivista (si veda l'illustra-zione a pagina 18). Il congegno è gestitoda un programma - il cosiddetto soft-ware ospite - che «gira» su una stazionedi lavoro. I microelaboratori non sonoin sé più veloci di quelli montati suChipTest, ma i perfezionamenti dell'al-goritmo di ricerca permettono loro dioperare con un 30 per cento di effi-cienza in più.

Il sistema di valutazione ha quattrocomponenti. Un circuito di valutazionedella disposizione delle figure (il soloereditato da ChipTest) considera la po-sizione di queste ultime rispetto al centrodella scacchiera, la loro mobilità e altrifattori. Un secondo circuito valuta loschieramento dei pedoni in base a para-metri quali il sostegno vicendevole, ilcontrollo del centro e la protezione delre. Un terzo circuito riconosce i pedoni«passati», ossia quelli che possono esse-re fatti avanzare fino all'ottava traversae promossi a regina senza incontrarel'opposizione di pedoni avversari. Infi-ne un circuito di valutazione delle colon-ne assegna valori a configurazioni piùcomplesse di pedoni e torri su una da-ta colonna.

Da allora abbiamo anche cominciatoa considerare in che modo sia possibileaffinare i circa 120 parametri della fun-zione di valutazione specificati dal soft-ware. Tradizionalmente i programmato-ri stabiliscono a priori, in base a consi-derazioni di carattere teorico, i «pesi» daassegnare ai pezzi e alle posizioni sullascacchiera; riteniamo che Deep Thoughtsia il solo programma importante capa-ce di regolare automaticamente questiparametri.

Abiamo selezionato 900 partite di-sputate da Maestri, decidendo di

definire ottimali quei pesi grazie ai qualisi otteneva la migliore corrispondenzafra le mosse prescelte dalla macchina equelle effettivamente giocate dai Mae-

BIANCO

NEROKARPOV

DEEP THOUGHT1 e2-e4

c7-c62 d2-d4

d7-d53 Cb1-d2

g7-g64 c2-c3

Af8-g75 e4-e5

Con questa mossa Deep Thought esce dal suorepertorio di aperture.

f746!

Una mossa eccellente per una macchina. Il neroattacca immediatamente il più avanzato dei pedonibianchi e indebolisce il controllo delle caselle bian-che da parte del suo avversario.

6 f2-f4

Cg8-h67 Cg1-f3

0-08 Af1-e2

f6xe51

Deep Thought effettua una contromossa attiva.

9 f4xe5 c6-c5!

In questo modo la presa d4xc5 consentirebbe alnero di ottenere un vantaggio con Ch6-g4!

10 Cd2-b3

c5xd411 c3xd4

Cb8-c6120-O

0d8-b613 Rg1-hl a7-a5

I due pedoni centrali danno ancora al bianco unpiccolo vantaggio, ma il pedone d4 è debole e lefigure non cooperano adeguatamente né occupanocaselle vantaggiose.

14 a2-a4

Ac8-f515 Ac1-g5

Af5-e416 Cb3-c5'

Questa mossa, che minaccia un attacco simultaneoalla torre e alla regina nere alla prossima mossa,tiene probabilmente conto di come i calcolatorisono programmati. Deep Thought non resiste allatentazione di catturare il pedone.

Db6xb2?

È uno sbaglio; sarebbe stato meglio 16 ... Ch645!.in preparazione al sacrificio di una torre con 17Cc5-d7, Db6xb2: 18 Cd7xf8, Cf5xd4l; a questopunto l'attacco del nero sarebbe stato molto perico-loso.

17 Cc5xe4 d5xe4

Deep Thought ritiene ora di essere in svantaggiodell'equivalente di un terzo di pedone. In seguitoKarpov ha dichiarato di essere rimasto impressio-nato dalla capacità di valutazione del calcolatore,che corrispondeva alla sua.

18 Tal -b1 Db2-a3

Mossa forzata, dato che a 18 Db2-c3 seguirebbe19 Tb1-b3, mentre 18 Db2-a2 dovrebbe fronteg-giare 19 Cf3-d2 seguita da 20 Ae2-c4.

19 Ag5-cl Da3-c3

stri. Il programma di valutazione è sta-to quindi completamente riscritto daCampbell e Nowatzyk in base a questicriteri: per autoregolarsi, la funzione divalutazione invece di assegnare sempli-cemente un valore numerico finale a cia-

20 Ac1-d2

Dc3-a321 Ad2-cl

Da3-c322 Tb1-b3

Dc3-a1

Karpov ripete le mosse per guadagnare tempo perriflettere.

23 Ae2-c4 (+) Rg8-h824 Ac1xh6! Da1 xd125 Ah6xg7 (+) Rh8xg726 Tf1xd1 e4xf327 g2xf3

Sarebbe stato meglio 27 Tb3xb7; ma come potevaKarpov indovinare la mossa successiva di DeepThought?

Ta8-a7!!

DEEP THOUGHT

E= t I e I

t I

I fi

fi A, fi

g fi.

2

g tA BC D E F G H

KARPOV

Il pubblico deride questa mossa, che ritiene disa-strosa, ma secondo Karpov è l'unica scelta possibileper Deep Thought.

28 Ac4-d5

Tf8-d829 Tb3-b5

Ta7-a6!

Il calcolatore si difende motto bene. Ora minaccia30 ... Cc6-a7: 31 Ad5xb7, Ca7xb5: 32 Ab7xa6.Td8xd4, che porterebbe la situazione in parità.

30 Ad5-c4

Ta6-a731 Ac4-d5

Ta7-a632 Tb5-c5

Td8-d733 Rh1-g2

Ta6-b6'34 Ad5xc6

b7xc635 Rg2-f2!

Una mossa arrischiata, data la posizione legger-mente superiore del nero, ma Karpov vuole ancoravincere.

Td7-d536 Tc5xd5

c6xd537 Td1-cl

Tb6-b4

scuna posizione sulla scacchiera deter-mina un'equazione contenente un certonumero di termini di primo grado (valea dire, un vettore).

Sono stati utilizzati due meccanismi diautoregolazione. Il primo, che chiamia-

38 Rf2-e3

Tb4xa4

Un altro modo, forse più semplice, per ottenere lapatta sarebbe 38.. Tb4-b3 (+l; 39 Re3-e2, Tb3-b4con ripetizione della posizione, dato che il bianconon può certo permettersi di perdere il pedone nellacolonna d.

39 Tc1-c5

e7-e640 Tc5-c7 (+1

Rg7-g841 Tc7-e7

Ta4-a3 (+142 Re3-f4

Ta3-d343 Te7xe6

Td3xd4 (+)44 Rf4-g5

Rg847!

Una buona manovra difensiva.

45 Te6-a6 a5-a4

Deep Thought ritiene di essere in vantaggio e quindinon vuole forzare la patta con 45 ... h7-h6 (+l; 46Rg5xh6, Td4-h4 (+); 47 Rh6-g5, Th4-h5 ( +1:48 Rg5-f4, Th5-f5 (+); seguita da 49 ... Tf5xe5.

46 f3-f4

h7-h6 (+)47 Rg5-g4

Td4-c4?

Con 47 96-g5i vi sarebbe stata patta, ma lamacchina, ritenendosi ancora in vantaggio, nonvuole perdere un pedone in cambio della sicurezza.

48 h2-h4

Tc4-d449 Ta6-f6 (+1

Rf7-g750 Tf6-a6

Rg7-f751 h4-h5

g6xh5?

Questa mossa sancisce la sconfitta. 51 ... g6-g5,secondo Karpov, avrebbe concesso al bianco unmargine di manovra troppo esiguo per vincere.

52 Rg4-f5

Rf7-g753 Ta6-a7 (+1

Rg7-f854 e5-e6

Td4-e455 Ta7-d7

Te4-c456 Td7xd5

h5-h457 Td5-d3

Rf8-e758 Td3-d7 (+)

Re7-f859 Td7-h7

h6-h560 Rf5-e5

h4-h361 f4-f5

Rf8-g862 Th7xh5

a4-a363 Th5xh3

a3-a2

Un giocatore preferirebbe 63 ... Tc4-a4 per prolun-gare la lotta, ma in questo caso 64 Re5-f6 avrebberapidamente la meglio.

64 Th3-a3

Tc4-c5 (+)65 Re5-f6

Abbandona

Deep Thought si considera in svantaggio dell'equi-valente di almeno sei pedoni, cosicché i suoi pro-grammatori decidono di abbandonare. A questopunto la macchina ha ancora circa 20 minuti ditempo a disposizione, mentre a Karpov rimanemeno di un minuto; tuttavia è più che sufficiente, perun giocatore del suo calibro, per conseguire la vittoria.

7

6

5

4

3

2

16 LE SCIENZE n. 268, dicembre 1990

LE SCIENZE n. 268, dicembre 1990 17

I principali circuiti di Deep Thought stanno in un pannello grande quanto metà di una pa-gina di questa rivista. Ognuno dei suoi due microelaboratori analizza fino a 500 000 posi-zioni al secondo. Il successore di Deep Thought, ora allo studio, sarà un sistema ad altogrado di parallelismo con 1000 chip progettati specificamente per il gioco degli scacchi.

I GRANDI SCIENZIATIAi personaggi che hanno fatto fare passi da gigante

al pensiero umano e ai retroscena delle loro scoperte

LE SCIENZEedizione italiana di SCIENTIFIC AMERICAN

ha dedicato numerosi articoli tra cui:

COPERNICO E TYCHO BRAHEdi O. Gingerich

(n. 67, marzo 1974)

La scoperta della copia del libro di Coper-nico annotata da Tycho Brahe.

ALFRED WEGENER E L'IPOTESIDELLA DERIVA DEI CONTINENTI

di A. Hallam(n. 82, giugno 1975)

Nel 1912 questo scienziato avanzava l'i-potesi che i continenti si muovono e pro-poneva una teoria della loro migrazione.

GAUSSdi I. Stewart

(n. 111, novembre 1977)

Si trovava a suo agio sia con le astrazionidella teoria dei numeri sia con i lunghicalcoli dell'astronomia e le applicazionipratiche della fisica.

LA MELA DI NEWTONE IL DIALOGO DI GALILEO

di S. Drake(n. 146, ottobre 1980)

Fu probabilmente un diagramma visto neiMassimi Sistemi di Galileo a far sì cheNewton collegasse la caduta della famosamela al moto orbitale della Luna.

SADI CARNOTdi S.S. Wilson

(n. 158, ottobre 1981)

È noto per l'analisi di una macchina termi-ca ideale, ma i suoi interessi erano rivoltialle applicazioni pratiche dell'energia delvapore.

LA BREVE VITADI ÉVARISTE GALOIS

di T. Rothman(n. 166, giugno 1982)

Secondo la leggenda il giovane matema-tico formulò di getto la teoria dei gruppinella notte precedente il duello che loportò alla morte.

GEORG CANTOR E LA TEORIADEGLI INSIEMI TRANSFINITI

di J.W. Dauben(n. 180, agosto 1983)

Cantor ha dimostrato che esiste una ge-rarchia di infiniti, ciascuno più “grande»del precedente; oggi la sua teoria degliinsiemi è uno dei cardini della matematica.

MONDINO DE' LIUZZIdi P.L. Lollini e L. Pelegatti

(n. 182, ottobre 1983)

Ebbe il merito di rinnovare la scienzamedica medievale introducendo nell'aulauniversitaria la dissezione a scopo didat-tico e di ricerca.

DARWIN GEOLOGOdi S. Herbert

(n. 215, luglio 1986)

Nei cinque anni passati sulla Beagle lasua principale attività di ricerca riguardòla geologia.

WILLIAM HERSCHEL E LA NASCITADELL'ASTRONOMIA MODERNA

di M. Hoskin(n. 216, agosto 1986)

Mediante i telescopi da lui stesso costruitiHerschel scoprì migliaia di stelle enebulose.

I CONTRIBUTI DI LEONARDOALLA MECCANICA TEORICA

di V. Foley e W. Soedel(n. 219, novembre 1986)

Un esame approfondito dei Codici di Ma-drid fa emergere l'importanza delle intui-zioni di Leonardo su quattro aspetti fonda-mentali della meccanica.

ANDRÉ-MARIE AMPÈREdi L. Pearce Williams(n. 247, marzo 1989)

Fu il primo ricercatore a valutare quantita-tivamente gli effetti magnetici della cor-rente elettrica, ma si interessò anche difilosofia della scienza.

mo meccanismo «di arrampicata», fissaarbitrariamente il valore di uno dei pa-rametri di valutazione e, per le diverseposizioni della sua base di dati di 900partite, effettua l'analisi di cinque o seilivelli dell'albero di gioco al fine di tro-vare le mosse che la macchina giochereb-be in quelle situazioni. Modifica poi leg-germente il parametro e ripete il calcolo.Se il numero di corrispondenze fra lemosse prescelte dal calcolatore e quelleeffettivamente giocate aumenta, il para-metro viene ulteriormente modificatonello stesso senso e il processo continuafino a che tutti i parametri siano statiottimizzati. Tuttavia per applicare que-sto metodo a tutti i parametri individuatioccorrerebbero anni di lavoro e quindilo abbiamo riservato solamente ai casidifficili.

Il secondo meccanismo di autoregola-zione, proposto e messo in atto da No-watzyk , è molto più rapido. Esso si basasemplicemente sulla ricerca della miglio-re corrispondenza fra il valore della fun-zione di valutazione calcolato dalla mac-china e il valore presunto vero. A questoscopo si determina lo scarto minimo frail quadrato della funzione calcolata equello del valore vero, che per i nostriscopi è ottenuto con una ricerca spintaparticolarmente in profondità (se si vuo-le affinare un punto particolare) o da unconfronto fra le decisioni prese dallamacchina e quelle assunte da giocatori dialto livello.

Le 900 partite della base di dati for-niscono ottime informazioni sul valorerelativo di posizioni diverse: in defi-nitiva, una posizione raggiunta in segui-to a una mossa di un Grande Maestro èpresumibilmente migliore di tutte le po-sizioni prodotte da mosse alternative.Anziché calcolare il valore di una posi-zione a partire dai parametri, Nowatzykha calcolato i parametri stessi in base alladifferenza postulata fra la posizione pre-scelta da un Grande Maestro e quelle dalui respinte. L'algoritmo richiede untempo di calcolo di pochi giorni e, con-trariamente a quello «di arrampicata»,non ottimizza i parametri uno per voltama li considera simultaneamente tutti.

La nostra funzione di valutazione adautoregolazione automatica non è némigliore né peggiore delle funzioni uti-lizzate dai più noti fra i programmi pergli scacchi sviluppati in ambito universi-tario, come Hitech e Cray Blitz. Sembraesserci ancora una notevole differenza,tuttavia, fra le capacità di analisi di DeepThought e quelle delle migliori macchinecommerciali per gli scacchi, che di soli-to sono il frutto di anni di lavoro da par-te di esperti. Perfezionando le proceduredi autoregolazione, speriamo di ridurreben presto il divario.

Può apparire strano che la nostra mac-china, pur basandosi su conoscenze scac-chistiche relativamente modeste, riescaa battere giocatori eccellenti. Tuttaviaoccorre ricordare che il calcolatore non

simula i processi di pensiero umani, maraggiunge gli stessi scopi per vie diverse.Deep Thought vede in profondità ma os-serva poco, ricorda ogni cosa ma nonimpara nulla, non fa mai errori mador-nali ma non migliora le proprie presta-zioni. Tuttavia può a volte scoprire com-binazioni che neppure un Grande Mae-stro riesce a vedere.

Queste particolari capacità spieganoforse perché il Grande Maestro KevinSpraggett abbia deciso di allenarsi conDeep Thought in vista dell'incontro conil Grande Maestro Artur Yusupov per ilquarto di finale del campionato dl mon-do. Anche se la partecipazione dellamacchina non ha avuto effetti rilevantisull'esito dell'incontro, costituisce co-munque un precedente interessante.

Nell'ottobre 1989 a New York unaversione sperimentale di Deep Thoughtcon sei microelaboratori giocò un incon-tro di esibizione in due partite controKasparov. Questo nuovo modello era ingrado di analizzare più di due milioni diposizioni al secondo, ma Kasparov losconfisse senza difficoltà. Benché il risul-tato non fosse inatteso, il gioco di DeepThought risultò piuttosto deludente.

Nel febbraio 1990 Deep Thought siesibì nuovamente incontrando AnatolijKarpov, ex campione del mondo e at-tualmente sfidante di Kasparov nella fi-nale del campionato del mondo di scac-chi. I difetti manifestatisi nel programmasperimentale delle versioni a sei e a quat-tro microelaboratori ci indussero a ripre-sentare il modello a due microelabora-tori. Deep Thought, potendo beneficia-re di vari perfezionamenti della funzionedi valutazione, giocò una delle sue mi-gliori partite per le prime 50 mosse, poigettò al vento una patta quasi sicura.Una versione più stabile a sei microela-boratori avrebbe avuto una velocità suf-ficiente per evitare questo errore grosso-lano (si veda la «finestra» a pagina 16).

JJa velocità d'analisi è l'aspetto delle

nostre ricerche, condotte presso ilThomas J. Watson Research Center del-l'IBM, a cui attualmente dedichiamomaggiore attenzione; il nostro obiettivoè di migliorare almeno di un fattore 1000la versione attuale di Deep Thought. Ilcalcolatore al quale stiamo lavorandoesaminerà quindi più di un miliardo diposizioni al secondo e potrà spingere laricerca a una profondità di 14-15 livellidell'albero di gioco nella maggior partedei casi e addirittura a 30-60 livelli nellesuccessioni di mosse forzate. Se conti-nuerà a valere la relazione osservata fravelocità di analisi e livello di gioco, lamacchina della nuova generazione do-vrebbe conseguire una valutazione dicirca 3400 punti, ossia 800 punti al disopra del suo livello attuale e ben 500punti al di sopra del livello di Kasparov.

A questo fine Hsu sta progettando unchip specifico per il gioco degli scacchiche dovrebbe calcolare almeno tre mi-lioni di mosse al secondo, con una velo-

cità più di tre volte superiore a quel-la attuale di Deep Thought; è inoltre im-pegnato nell'ideazione di un sistema adalto grado di parallelismo che sarà com-posto da 1000 di questi chip, con un ul-teriore guadagno di circa 300 volte.Anantharaman e Campbell stanno per-fezionando diversi aspetti della versio-ne attuale di Deep Thought, in vista diuna loro introduzione nel futuro calco-latore, e Nowatzyk persegue altri inte-ressi di ricerca.

Noi riteniamo che questo nuovo siste-ma sarà sufficientemente forte, grazie al-la sua sola velocità, da costituire un va-lido avversario per il campione del mon-do; e siamo convinti che l'adozione diuna lunga lista di miglioramenti già pre-visti consentirà alla macchina di avere lameglio, forse già nel 1992.

Kasparov è di avviso contrario e noirispettiamo la sua opinione. In privatoegli ha ammesso che una macchina ingrado di analizzare un miliardo di posi-zioni al secondo potrebbe sconfiggere unGrande Maestro di medio livello, «manon Karpov e me!». Il campione delmondo afferma che un giocatore di altis-simo livello dovrebbe riuscire a prepa-rarsi adeguatamente per trarre vantag-gio dalle particolari carenze che sono ca-ratteristiche dei calcolatori; a parere diKasparov la creatività e l'immaginazioneumana, e in particolare la sua creativitàe immaginazione, non potranno che ave-re la meglio su un semplice congegno abase di silicio.

Di fatto, quando le due parti si trove-ranno di fronte sulla scacchiera, l'inge-gno di un giocatore di grandissimo talen-to sarà opposto non a una macchina, maal lavoro di generazioni di matematici,informatici e tecnici. Riteniamo che l'e-sito dello scontro ci rivelerà non se lemacchine siano in grado di pensare, mapiuttosto se uno sforzo umano collettivopossa avere la meglio anche sugli indivi-dui più dotati.

BIBLIOGRAFIA

ZOBRIST ALBERT L. e CARLSON EREDE-RIC R., Jr., Il calcolatore a lezione di scac-chi , in «Le Scienze» n. 62, ottobre 1973.

CONDON H. J. e THOMPSON KEN, Bellein Chess Skill in Man and Machine (se-conda edizione), a cura di P. W. Frey,Springer-Verlag, 1984.

SLATE DAVID J. e ATKIN LAWRENCE R.,Chess 4.5 - The Northwestern UniversityChess Program in Chess Skill in Man andMachine (seconda edizione), a cura di P.W. Frey, Springer-Verlag, 1984.

HSU FENG-HSIUNG, Large Scale Paral-lelization of Alpha-Beta Search: An Al-gorithmic and Architectural Study withComputer Chess, Carnegie-Mellon Uni-versity Computer Science Department,CMU-CS-90-108, febbraio 1990.

18 LE SCIENZE n. 268, dicembre 1990LE SCIENZE n. 268, dicembre 1990 19