M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1. INTRODUZIONE

P er valutare l’efficacia di un dispositivohardware ne analizziamo le caratteristi-

che tecniche: possiamo per esempio misu-rare la velocità di calcolo di un processore,la dimensione di una memoria centrale operiferica, la risoluzione di un monitor, labanda di comunicazione disponibile su unaconnessione. Ma come si valuta l’efficaciadi un software? Per esempio, come possia-mo confrontare due sistemi operativi? Ilconfronto tra Windows e Linux di solito av-viene su basi ideologiche, dunque forte-mente soggettive. E comunque, come si di-mostra che la versione 2.0 di un certo pro-gramma è migliore della 1.0 ? Non stiamoparlando di contare gli errori; supponiamoche entrambe le versioni siano prive di erro-ri: come si confronta la loro “efficacia”?Nel caso dei programmi che giocano a scac-chi, la risposta è semplice: tra due program-mi, è migliore quello che batte l’altro. In figu-ra 1, tratta da [11], vediamo un grafico chemostra l’evoluzione di questi programmi. Inascissa ci sono tre scale correlate che descri-

vono rispettivamente la profondità media dianalisi dell’albero di gioco (in ply, ossia semi-mosse), il numero medio di posizioni analiz-zate per secondo, i MIPS offerti dall’hardwa-re. In ordinata abbiamo la scala Elo, che de-scrive la forza di un giocatore di Scacchi. Lascala prende il nome da A. Elo, uno studiosodi statistica, che tra il 1960 ed il 1970 mise apunto un sistema di valutazione della forza digioco che è tutt’oggi usato in tutto il mondo.Per esempio, il campione del mondo “vale”di solito circa 2800 punti, un principiante va-le 800 punti, mentre la curva di Gauss chedescrive la “popolazione scacchistica” mon-diale ha una mediana intorno ai 1400. Le va-riazioni di punteggio avvengono in seguito alconteggio delle vittorie e delle sconfitte intornei ufficiali. La figura mostra le date di na-scita e la forza relativa dei principali pro-grammi di gioco, e culmina con Deep Blue,una macchina creata da IBM nei laboratori diYorktown appositamente per battere il cam-pione del mondo.In effetti, Domenica 11 maggio 1997 è unadata che gli storici dell’informatica segnano

La storia delle macchine che giocano a scacchi è ancor più antica di quel-

la del computer. Infatti la prima macchina scacchistica venne esibita nel

1770 a Vienna: era il Turco, un famoso automa che giocava con l’inganno,

perché celava abilmente una persona tra i suoi ingranaggi. In questo arti-

colo viene delineata la storia più recente delle macchine che giocano a

scacchi e i principali aspetti di ricerca ad esse correlati.

Paolo Ciancarini

IL COMPUTERGIOCA A SCACCHI

3

3.6

0

con un sassolino bianco. Quel giorno DeepBlue ha sconfitto il campione del mondo discacchi, il russo Garry Kasparov, dopo unmatch di sei partite (due vinte, una persa etre patte). L’evento è stato seguito e com-mentato in diretta da decine di migliaia dipersone connesse a Internet [10]. Tale im-presa va considerata come uno dei grandisuccessi scientifici di questo secolo, cuihanno contribuito in varia misura sin dallafine degli anni ’40 parecchi studiosi, comeAlan Turing, Claude Shannon, Herbert Si-mon, John McCarthy e Ken Thompson, soloper citarne alcuni.Per quali ragioni si costruiscono macchinecapaci di giocare? La giustificazione scientifi-ca di tali sforzi è stata espressa quasi 50 annifa in un articolo di Newell, Shaw e Simon:

“Gli Scacchi sono il gioco intellettuale per eccel-lenza. Senza far uso di strumenti casuali (come idadi o la roulette), che inquinerebbero la conte-sa, due intelletti vengono contrapposti in una si-tuazione così complessa che nessuno dei duepuò sperare di comprenderla completamente,ma sufficientemente analizzabile di modo checiascuno dei due può sperare di sconfiggere l’al-tro. Il gioco è tanto profondo e sottile che ha per-

messo la nascita di giocatori professionisti, edha sopportato senza esaurirsi 200 anni di partitee di studi analitici intensivi. Tali caratteristicherendono gli Scacchi un’arena naturale per i ten-tativi di meccanizzazione. Se si potesse svilup-pare un giocatore artificiale vincente, si potreb-be affermare di aver penetrato il nucleo dell’atti-vità intellettuale umana.”

Gli Scacchi permettono di studiare le proce-dure astratte che usano gli esseri umaniquando prendono decisioni. Se riusciamo afar giocare bene un computer, possiamo spe-rare di insegnargli a ragionare “come noi”, eforse meglio, grazie alla grande velocità concui la macchina elabora immense quantità didati. Alcuni problemi pratici che avrebberotratto giovamento dallo studio del progettodi giocatori artificiali vennero elencati daShannon in [15]:❙ macchine capaci di progettare componentielettronici;❙ macchine capaci di sostituire le centrali te-lefoniche elettromeccaniche;❙ macchine capaci di tradurre frasi da una lin-gua in un’altra;❙ macchine capaci di decisioni strategiche incampo militare o economico;

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

0

0

1

4

2800270026002500240023002200210020001900180017001600150014001300120011001000900800

Ches

s Ra

ting

KasparovGrand Master

Senior Master

Master

Expert

Class A

Class B

Class C

Class D

Bernstein, IBM 704, 1957

19971996 DEEP Blue1994

Cray Blitz, Cray C90/16, 1993 1991 DEEP Thought IIDEEP Thought, 1989

Chiptest, 1987Hitech, 1985Belle, 1983

Cray Blitz, Cray 1, 1981Chess 4.9, Cyber 176, 1979

Chess 4.6, Cyber 176, 1977Belle, 1978

Chess 4.4, Cyber 176, 1975

Chess 4.0, CDC 6400, 1973Chess 3.5, CDC 6400, 1971

MacHack, PDP-10, 1970

MacHack, PDP-6, 1966

3 4 5 6 7 8 9 10 11 12 13 14

1 10 100 1K 10K 100K 1M 10M 100M

0.1 1 10 100 1K 10K 100K 1M 10M

Profondità di analisi (ply)

Posizioni/secondo

MIPS equivalenti

FIGURA 1Il progresso

dei programmidi gioco

❙ macchine capaci di orchestrare una melodia;❙ macchine capaci di deduzione logica.È davvero mirabile osservare come quasi tut-ti gli obiettivi proposti da Shannon siano sta-ti raggiunti, e questo grazie anche al contri-buto delle ricerche sui giocatori artificiali.

2. PICCOLA STORIA

Già all’inizio degli anni ’50 Shannon [15] eTuring [17] avevano descritto algoritmi pergiocare a scacchi, ma non avevamo macchi-ne adatte a realizzarli. Verso il 1955 A.Newell e H. Simon della Carnegie MellonUniversity iniziarono la progettazione delprogramma CP-1 (Chess Player 1). Il loro sco-po era quello di costruire una macchina “in-telligente”, capace di dimostrare teoremimatematici o di progettare sistemi comples-si. Newell e Simon decisero che gli scacchifornivano un buon terreno di prova per pro-gettare una “macchina intelligente”. Nellasua autobiografia Simon racconta di comeuna mattina del gennaio del 1956 entrò inclasse annunciando ai suoi studenti: “Du-rante le vacanze di Natale io e Newell abbia-mo progettato una macchina che pensa”[16]. Negli stessi giorni scrive:

“… Allen Newell e io abbiamo fatto progressi so-stanziali sulla macchina che gioca a scacchi, soloche per il momento non sa giocare a scacchi masolo cercare e scoprire dimostrazioni di teoremi dilogica simbolica …”.

Il programma che avevano progettato sichiamava Logic Theorist ed era scritto in IPL-2, un linguaggio di programmazione apposi-tamente sviluppato. Il programma di scacchivenne effettivamente scritto solo qualcheanno dopo, in collaborazione con C. Shaw,per cui venne chiamato NSS. Il programmadi gioco era abbastanza sofisticato, ma l’usodi un linguaggio sperimentale di program-mazione penalizzò talmente le prestazionidella macchina che occorreva un’ora per fareuna mossa. A causa della sua lentezza, ilprogramma venne usato per giocare una so-la partita, ma comunque entusiasmò i suoiautori che ottimisticamente profetizzaronoche entro 10 anni il Campione del Mondo sa-rebbe stato un giocatore artificiale.

Un altro programma famoso fu scritto al MITdi Boston da A. Bernstein e altri alla fine de-gli anni ’50. Il programma di Bernstein usa-va una strategia che Shannon definì di tipoB: sceglieva in una posizione le sette mossemigliori usando alcuni principi generali,analizzava per ciascuna mossa le sette mi-gliori risposte, e ripeteva il procedimentoper ciascuna delle 49 posizioni così ottenu-te. Il programma veniva eseguito da un ela-boratore IBM 704 ed impiegava circa ottominuti per analizzare 74 = 2401 varianti pri-ma di effettuare una mossa. L’esame di unasingola posizione comportava l’effettuazio-ne di 7.000 operazioni di macchina, che rea-lizzavano alcune semplici valutazioni strate-giche: bilancio del materiale, misura dellamobilità dei pezzi, analisi del controllo dellospazio e valutazione del grado di sicurezzadel Re. Il programma giocava come un prin-cipiante, ma venne enormemente pubbliciz-zato negli Stati Uniti, contribuendo a far co-noscere al grosso pubblico scopi e prospet-tive dell’Intelligenza Artificiale.Il MIT per diversi anni fu il più importante cen-tro di ricerca sul gioco artificiale. Il principalericercatore impegnato nel tentativo di co-struire macchine intelligenti era J. McCarthy.Egli aveva ottenuto la disponibilità di uno deiprimi mainframe IBM, un modello 704, che isuoi studenti programmavano usando unnuovo linguaggio, il LISP, inventato da Mc-Carthy stesso. L’interesse di McCarthy neiprogrammi di scacchi era puramente teorico,ma alcuni suoi studenti si entusiasmaronodel progetto e lo portarono avanti. Nel 1962A. Kotok, uno di tali studenti, terminò di scri-vere un programma di scacchi e lo presentòcome tesi di laurea. Per ragioni di efficienza ilprogramma era scritto in FORTRAN e assem-bler. Il programma di Kotok venne ulterior-mente sviluppato da McCarthy che si era tra-sferito a Stanford, in California, e nel 1967 di-venne il rappresentante americano in una fa-mosa sfida contro una macchina sovietica. Isovietici avevano iniziato le loro ricerche daalcuni anni, e si avvalevano dell’aiuto di alcu-ni esponenti della loro grande scuola scacchi-stica. Era la prima volta che le ricerche sovie-tiche venivano allo scoperto, e il risultato fe-ce sensazione: l’URSS vinse per 3-1 quella sfi-da, con due vittorie e due patte. L’incontro fu

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

5

0

0

0

1

0

particolarmente interessante dal punto di vi-sta scientifico, perché i due programmi usa-vano strategie di ricerca opposte. Il program-ma sovietico usava una strategia di Shannondi tipo A (o “forza bruta”): esplorava tutte levarianti possibili fino alla profondità di 5 se-mimosse. Il programma americano usava unaricerca di tipo B: non tutte le varianti possibilivenivano esplorate, ma solo quelle definite“plausibili” da una funzione euristica.Negli anni della corsa alla Luna, una sconfittatecnologica di questo genere venne vista ne-gli USA come una vera e propria onta naziona-le. Il risultato dell’incontro stimolò nuove ri-cerche, e R. Greenblatt costruì poco dopo unanuova macchina. Il programma si chiamavaMacHack, usava un Digital PDP-6 del MIT edebbe l’onore di essere il primo giocatore artifi-ciale a debuttare in un torneo a Boston nel1967. La prestazione di MacHack al torneo fu

pessima. Tuttavia, col suo debutto agonisticola lunga corsa verso il Campionato del Mondoera davvero cominciata: infatti al programmafu permesso di iscriversi alla federazionescacchistica americana (USCF), stabilendo co-sì un precedente. A parte il risvolto commer-ciale, è importante che partecipando a torneiufficiali un programma ottiene un punteggioElo. MacHack raggiunse una valutazione Elopari a 1500 punti: il livello di un dilettante dimedia forza. MacHack non riuscì mai a gioca-re bene, ma quando fu mostrato ad una confe-renza che si tenne ad Edimburgo nel 1968 eb-be il merito di attirare l’attenzione di un gioca-tore scozzese, D. Levy, che era anche uno stu-dioso di Intelligenza Artificiale. MacHack ave-va scatenato l’euforia dei congressisti presen-ti, alimentando rosee speranze per il futuro.Fu allora che Levy, colpito dall’entusiasmo in-giustificato che avevano acceso le mediocri

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

0

0

1

6

Nei programmi di scacchi sono state messe alla prova parecchie tecnologie tipiche dell’Intelligenza Artificiale.

Rappresentazione della conoscenza. La conoscenza scacchistica è di vario tipo. Una forma di conoscenza dichiarativa riguarda larappresentazione dei pezzi e della scacchiera, e poi la formazione di concetti in base a dei principi (mettere al sicuro il Re) e la con-seguente definizione di piani e tattiche di gioco (arrocca, per mettere al sicuro il Re). Una forma di conoscenza procedurale riguar-da invece il modo in cui si calcolano le conseguenze di una serie di scambi di pezzi (conviene sempre iniziare gli scambi dal pezzo divalore minore). Per rappresentare questi tipi di conoscenze sono state usate varie tecniche, in particolare per la conoscenza dichia-rativa la logica e i linguaggi logici come Prolog, mentre la conoscenza procedurale è stata rappresentate mediante euristiche, di so-lito all’interno della funzione di valutazione.

Esplorazione dello spazio degli stati. Esistono diversi algoritmi di esplorazione dello spazio degli stati di una partita a scacchi.Sono stati infatti inventati raffinamenti algoritmici che si comportano mediamente meglio di Alfabeta, ed altri se ne continuanoad inventare.

Machine Learning. L’apprendimento automatico viene usato per aumentare le conoscenze dei programmi specie nella fase di aper-tura. I cosiddetti libri di aperture vengono da tempo creati in modo automatico, a partire da partite giocate da Grandi Maestri. È in-teressante notare che ci sono stati molti tentativi di costruire programmi che apprendono giocando contro se stessi, ma sono tuttifalliti (nessuno ha ottenuto un giocatore efficace usando questa tecnica).

Pattern recognition. Una tecnica importante in alcuni programmi è il riconoscimento di schemi di gioco, di solito allo scopo di ap-plicare una strategia che in altre partite ha dato buona prova. Il riconoscimento avviene definendo prima degli schemi (in inglese:pattern, o chunks) associati a una o più euristiche da applicare quando viene rilevato lo schema nella posizione in analisi.

Algoritmi genetici. Questa tecnica permette di far evolvere i programmi di gioco, raffinandone le funzioni di valutazione. Vengonocreate alcune varianti della funzione di valutazione, e poi le si fanno “competere” usando un insieme di posizioni di test. Le funzio-ni migliori (quelle che risolvono meglio le posizioni di test) vengono poi leggermente alterate in modo casuale, ripetendo il ciclo. Al-la lunga (dopo migliaia di cicli) si ottiene una sorta di “selezione naturale” evolutiva delle funzioni di valutazione. Gli algoritmi ge-netici hanno dato buona prova nel miglioramento delle funzioni di valutazione.

Reti neurali. Esistono programmi le cui funzioni di valutazione sono reti neurali. Tali programmi, giocando o osservando le partite dialtri, sono in grado di sviluppare una “teoria subsimbolica” (cioè non basata su conoscenza dichiarativa) degli scacchi e di metterlaalla prova. Questa tecnologia non ha dato buoni risultati nel caso degli scacchi.

TTTT eeee cccc nnnn iiii cccc hhhh eeee dddd iiii IIII nnnn tttt eeee llll llll iiii gggg eeee nnnn zzzz aaaa AAAA rrrr tttt iiii ffff iiii cccc iiii aaaa llll eeeeaaaa pppp pppp llll iiii cccc aaaa tttt aaaa aaaa gggg llll iiii ssss cccc aaaa cccc cccc hhhh iiii

prestazioni delle macchine che aveva esami-nato, scommise che nessun programma sa-rebbe riuscito a batterlo nei 10 anni seguenti.Sfidare Levy divenne un punto d’onore pertutti i principali ricercatori. La scommessavenne accettata da due ricercatori presenti al-la conferenza, J. McCarthy e D. Michie. Nel cor-so degli anni la scommessa venne ribadita edaltri ricercatori scommisero contro Levy; nel1976 valeva in totale 1.250 sterline, che Levyvinse facilmente battendo nel 1978 il migliorprogramma dell’epoca.La sfida di Levy ebbe il merito di spronare imembri della comunità scientifica, che deci-sero di incontrarsi annualmente per misurarei progressi conseguiti. Nel 1970 a New Yorkiniziò infatti una competizione riservata aigiocatori artificiali che continua ogni annoancora oggi, raccogliendo sempre una parte-cipazione molto qualificata: il torneo dell’As-sociation for Computing Machinery (ACM), inseguito denominato torneo NACC (NorthAmerican Computer Championship). Nel1974, a Stoccolma, venne introdotta su sug-gerimento di Levy una nuova manifestazioneufficiale: il Campionato del Mondo per gioca-tori artificiali. La novità del torneo di Stoccol-ma fu la partecipazione di un programma so-vietico, Kaissa, diretto discendente del pro-gramma che aveva vinto la sfida USA-URSSdel 1967. Kaissa era stato scritto da M. Don-sky e V. Arlazarov, dell’Istituto per le ScienzeSistemiche di Mosca. Ebbe l’onore di diven-tare il primo giocatore artificiale a fregiarsiufficialmente del titolo di Campione del Mon-do, vincendo tutte le partite. Questa primaaffermazione però non venne seguita da altrisuccessi. Infatti tre anni dopo, a Toronto,Kaissa non riuscì a ripetersi e giunse solo se-condo dopo il programma americano Chess4.6. Andò anche peggio nel 1980, nel torneodi Campionato del Mondo svoltosi a Linz:Kaissa giunse solo sesto, perché l’hardwareimpiegato era diventato obsoleto rispetto al-le macchine più moderne a disposizione deisuoi competitori. La sconfitta fu dovuta so-prattutto al fatto che il tempo di macchina inURSS era costosissimo, a causa della scar-sità di calcolatori, quindi gli autori del pro-gramma non avevano potuto migliorarloquanto i suoi concorrenti. Kaissa sparì deltutto dalle competizioni, e da allora nessun

programma sovietico ha più partecipato adalcuna competizione ad alto livello.

3. LA NUOVA GENERAZIONE:MACCHINE BASATE SU HWSPECIALE

In quegli stessi anni venivano gettate le basiteoriche e tecnologiche per la costruzionedella nuova generazione di programmi di gio-co, che cominciò a dominare i tornei all’iniziodegli anni ’80. Le novità tecnologiche più im-portanti della fine degli anni ’70 furono due:l’introduzione del microprocessore, ed igrandi miglioramenti delle tecniche di pro-gettazione di hardware specializzato (VLSI).L’invenzione del microprocessore mise allaportata di tutte le borse un calcolatore perso-nale; nel 1974 esistevano già i primi micro-processori per hobbysti. Nel 1977 vennecommercializzata la prima scacchiera elettro-nica (Figura 2): si chiamava Chess Challen-ger, era stata progettata da R. Nelson e ven-ne prodotta dalla Fidelity International. Co-stava poche centinaia di dollari e venne ven-duta in decine di migliaia di esemplari.Per comprendere il significato economico diquesta invenzione, basterà riportare alcunecifre. I sedici computer partecipanti al cam-pionato mondiale di Toronto nel 1977 eranotutti grossi calcolatori; venne calcolato che illoro costo totale era di 40 milioni di dollari, eun’ora di gioco costava 10.000 dollari. Al

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

7

0

0

0

1

FIGURA 2 Fidelity Chess Challenger, la prima scacchiera elettronica

0

campionato del 2004 hanno partecipato in-vece normali personal computer che costanoal più qualche migliaio di dollari.L’altra grande novità che rivoluzionò profon-damente la ricerca sui giocatori artificiali ful’introduzione di hardware specializzato perla generazione di mosse. Mentre i primi gio-catori artificiali utilizzavano calcolatori “nor-mali”, ovvero di uso generale, ad un certopunto si cominciò a costruire hardware pro-gettato specificatamente per giocare. Nel1977 uno studente di Berkeley, O. Babaoglu(oggi docente dell’Università di Bologna)progettò un circuito capace di funzionare co-me generatore di mosse. Poco dopo venneprogettata nei Laboratori Bell da J. Condon eK. Thompson una nuova macchina, chiamataBelle. Nel 1972 i due ricercatori avevanoscritto per uno dei primi sistemi Unix un pro-gramma che si era comportato senza infamiae senza lode ai vari tornei cui aveva parteci-pato. Dopo la pubblicazione della tesi di Ba-baoglu i due ricercatori decisero che valevala pena di sviluppare una macchina concepi-ta appositamente per gli scacchi, in cui lo svi-luppo delle varianti veniva calcolato diretta-mente da alcuni circuiti in hardware.Belle conseguì rapidamente in tornei ufficialidella USCF il grado di Maestro di scacchi (2200punti Elo). Una prima pietra miliare nella storiadel gioco artificiale era stata raggiunta.I successi di Belle, e la simultanea nascita diun ricco mercato per le macchine commercia-li, diedero finalmente una certa credibilitàsportiva alle ricerche sul gioco artificiale. Trail 1982 ed il 1985 vennero organizzate a Mila-no da M. Somalvico e B. Pernici tre conferen-ze sui giocatori artificiali intitolate L’Intelli-genza Artificiale ed il Gioco degli scacchi. ALondra venne creata la International Compu-ter Chess Association (ICCA), un’associazio-ne di scienziati che si interessano di informa-tica scacchistica. Oggi ICCA ha cambiato no-me in ICGA (International Computer GamesAssociation) e si occupa di organizzare mani-festazioni agonistiche per giocatori artificiali.È a cura dell’ICGA l’organizzazione delle con-ferenze Computer Games e Advances in Com-puter Games.All’inizio degli anni ’80 i progettisti di gioca-tori artificiali cominciarono ad esplorare lepossibilità di una nuova tecnologia, quella

del calcolo parallelo. L’idea del calcolo paral-lelo è ingannevolmente semplice: due pro-cessori sono meglio di uno perché possonoeffettuare una doppia quantità di calcoli. Inrealtà esistono grandi problemi di coordina-mento delle operazioni: in molti casi non siottiene nessun guadagno usando più calco-latori invece di uno solo, perché essi perdonomolto tempo a cercare di mettersi d’accordo!Nel 1983 a New York il Campionato del Mon-do fu vinto da Cray Blitz, un programma chesi avvantaggiò della potenza del calcolatoreparallelo Cray-1, che era allora il sistema dielaborazione più potente del mondo. CrayBlitz fu il secondo giocatore artificiale capacedi guadagnarsi il titolo di Maestro, e dominòla scena per la prima metà degli anni ’80.Sia Belle che Blitz usavano programmi basatisul concetto di espansione cieca dell’albero digioco (strategia A): gli anni ‘70 erano stati do-minati da programmi basati su espansione eu-ristica, ma ormai l’hardware era diventato cosìveloce da permettere lunghe analisi per forzabruta. Nel 1985 però si affacciò sulla scena Hi-tech, un programma di H. Berliner, che si basa-va ancora su euristiche. Sin dal suo apparireHitech guadagnò una valutazione record di2220 punti Elo Usa, e subito sconfisse CrayBlitz. L’anno successivo, nel 1986, Hitech vale-va già 2360 punti Elo. Per qualche tempo sem-brò che l’approccio “intelligente” scelto daBerliner fosse quello giusto, lento ma sicuroverso il Campionato del Mondo assoluto. E in-vece nel 1987 apparve una nuova macchinabasata sul principio dell’analisi per forza bru-ta, Chiptest. Era stata progettata da uno stu-dente cinese, FH. Hsu, in collaborazione conuno studente di Berliner, M. Campbell. L’annosuccessivo Hsu e Campbell battezzarono ilnuovo prototipo di ChipTest con un nuovo no-me: Deep Thought, dal nome di un personag-gio di un libro di fantascienza. Analizzando700.000 posizioni al secondo grazie al suo ge-neratore hardware, Deep Thought era in gradodi analizzare tutte le varianti possibili ad unaprofondità media di 10 semimosse in apertura(con un libro di aperture estremamente ridot-to) e 9 semimosse nel mediogioco.Nel 1990 sia Hsu che Campbell vennero as-sunti dai laboratori di ricerca di IBM a York-town, e lì svilupparono la macchina che oggiconosciamo col nome di Deep Blue.

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

0

0

1

8

4. ANALISI DEL PROBLEMA

Analizziamo brevemente i dati del problema,e vediamo come è stato “risolto” dai proget-tisti di Deep Blue. Nel gioco degli scacchi:❙ ci sono due avversari che alternano le mos-se e conoscono in ogni istante le stesse infor-mazioni, cioè hanno informazione completasullo “stato del gioco”;❙ ad ogni turno di gioco le mosse ammessedalle regole sono in numero limitato e bendefinite;❙ ogni partita termina con la vittoria di unodei due giocatori, oppure in parità.Nella posizione iniziale del gioco degli scac-chi si hanno 20 mosse possibili per il Bianco.Per ogni mossa del Bianco il Nero può rispon-dere in 20 modi diversi, per un totale di 400posizioni possibili dopo sole due semimos-se. Per quanto gli scacchi siano un gioco fini-to, e quindi in teoria completamente analiz-zabile, siccome il numero medio di mosse inogni posizione è circa 33 e una partita duramediamente 40 mosse, ovvero 80 semimos-se, un programma che volesse “risolvere” ilgioco dovrebbe esplorare 3380 partite, un nu-mero di 120 cifre! Immaginando un computertalmente veloce da poter analizzare un mi-liardo di mosse al secondo (un compito leg-germente al di sopra della tecnologia attua-le), servirebbero circa 10105 anni per analizza-re tutte la partite possibili. E se ci si limita adanalizzare le posizioni, queste sono di meno,circa 1043, ma certo è impensabile analizzarletutte per poi memorizzarne l’esito.La soluzione universalmente adottata neiprogrammi di gioco è di fermare la generazio-ne delle mosse ad un certo livello di profon-dità dell’albero, proporzionalmente alla po-tenza di calcolo disponibile, di applicareun’euristica sulle foglie dell’albero e poi divalutare i nodi interni mediante l’algoritmominimax (o meglio mediante la sua ottimiz-zazione chiamata algoritmo alfabeta) [3].Un esempio del funzionamento di Minimax èdescritto nelle figure 3 e 4. L’algoritmo iniziavalutando con la funzione di valutazione tut-te le posizioni del livello più profondo dell’al-bero. A questo punto l’algoritmo “trasmette”verso l’alto i valori delle posizioni successiveusando la regola minimax.Per esempio, nella figura 3 la posizione d, in

cui deve muovere MAX, ottiene il valore 4,che è il massimo tra le valutazioni delle posi-zioni sottostanti. La posizione e ottiene il va-lore 5 per lo stesso motivo. La posizione b, incui deve muovere MIN, ottiene invece il valo-re 4, che è il minimo tra i valori delle sue posi-

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

9

0

0

0

1

Algoritmo minimax

Tutte le possibili evoluzioni di una partita, a partire da una certa mossa,vengono rappresentate con un albero i cui nodi sono caratterizzati da uncerto peso. L’elaboratore viene programmato per ricercare la miglior mos-sa possibile all'interno di una determinata strategia. Una possibile strate-gia è quella realizzata con gli algoritmi minimax: ogni mossa viene sceltain modo da ridurre al minimo il massimo dei vantaggi che l’avversario po-trà conseguire. L’algoritmo alfabeta consente di velocizzare quello mini-max, “potando” l’albero dei rami che risultebbe inutile esaminare.

a

1 4 5 3 3 82 1

b c

d e f g

Muove MAX

Muove MINI

Muove MAX

a

1 4

4 5 2 8

4

4

5 3 3 82

2

1

b c

d e f g

Muove MAX

Muove MINI

Muove MAX

FIGURA 3Situazione iniziale dell’algoritmo Minimax

FIGURA 4Risultatodi Minimax; le lineein evidenzaindicano la varianteprincipale (a-b-d)

0

zioni sottostanti. La situazione finale, in cuila radice ha ottenuto un valore, è schematiz-zata nella figura 4.La variante principale è quindi composta dal-le mosse che producono in successione leposizioni a-b-d, e la mossa da giocare è quel-la che porta da a in b.L’ipotesi grazie alla quale questo metodo fun-ziona è che più profondo è l’albero da valuta-re, più è precisa la valutazione della mossa dagiocare. Dal punto di vista teorico questa ipo-tesi non è mai stata dimostrata, ed anzi alcunistudi tenderebbero addirittura a dimostrarel’ipotesi contraria, che cioè più profondo èl’albero, meno precisa risulta la valutazione.In effetti in un albero molto grosso le posizionidel livello finale saranno molto diverse tra lo-ro, e quindi sarà difficile paragonarle. D’altraparte i risultati empirici confermano che unprogramma X che usa uno hardware più velo-ce Y batte sistematicamente lo stesso pro-

gramma che usa uno hardware meno veloceZ, perché esplora più approfonditamente edestesamente l’albero di gioco.A questo proposito K.Thompson effettuò unfamoso esperimento con la sua macchinaBelle. Fece giocare un torneo tra sei diverseversioni; l’unica differenza tra i programmiera la profondità di analisi dell’albero di gio-co, che variava tra 4 e 9 semimosse. Ogni in-contro comprendeva 20 partite. La tabella 1riassume i risultati del torneo.Come si vede, un incremento di profonditànell’analisi pari a una semimossa comportain media un incremento nella forza di gioco diquasi 200 punti Elo. Si confronti questa ta-bella con quella ottenuta da un diverso espe-rimento di J. Schaeffer [13], che non variava laprofondità di analisi del programma, ma solola sua “conoscenza”, cioè l’importanza dellafunzione di valutazione. Schaeffer effettuòuna serie di esperimenti per valutare il bilan-ciamento relativo dei vari fattori componentiuna funzione di valutazione. Egli usò il suoprogramma Phoenix per giocare un torneocui partecipavano varie versioni del program-ma stesso, che differivano per la funzione divalutazione utilizzata. La versione di riferi-mento (che chiameremo versione 1), tentavasemplicemente di massimizzare il materiale.Le altre erano via via arricchite come segue:

versione 2: mobilità e spazio: mosse pseudo-legali + controllo delle case nellametà avversaria della scacchiera.

versione 3: controllo del (grande) centro;versione 4: struttura pedonale: penalizzazio-

ni per pedoni isolati o doppiati;versione 5: valutazione incrementale di mos-

se: catture di pedone verso il cen-tro, torre in settima, sviluppo diun pezzo, arrocco;

versione 6: sicurezza del Re;versione 7: case deboli e pedoni passati;versione 8: pianificatore strategico.

Le otto versioni del programma giocaronolungamente tra di loro, ed i risultati sonoriassunti nella tabella 2.Confrontando i due esperimenti si deduce chesi guadagna molto di più migliorando la velocitàdi analisi di un programma che non la sua co-noscenza specifica della strategia scacchistica.

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

0

0

1

10

P4 P5 P6 P7 P8 P9 Elo

P4 - 5 0.5 0 0 0 1235

P5 15 - 3.5 3 0.5 0 1570

P6 19.5 16.5 - 4 1.5 1.5 1826

P7 20 17 16 - 5 4 2031

P8 20 19.5 18.5 15 - 5.5 2208

P9 20 20 18.5 16 14.5 - 2328

TABELLA 1Incremento di forza in funzione della profondità di analisi

versione 1: solo materiale 1110

versione 2: vers. 1 + mobilità e spazio 1420

versione 3: vers. 2 + controllo del centro 1530

versione 4: vers. 3 + struttura pedonale 1600

versione 5: vers. 4 + valutazione mosse 1630

versione 6: vers. 5 + sicurezza del Re 1750

versione 7: vers. 6 + case deboli e P passati 1760

versione 8: vers. 7 + pianificazione 1780

TABELLA 2Confronto Elo tra diverse funzioni di valutazione

Infatti i grandi successi dei giocatori artificia-li si sono verificati a partire dagli anni ‘80,quando i progressi delle tecnologie VLSI han-no permesso il progetto di hardware specia-lizzato per la generazione di mosse [5].Deep Blue aveva un’architettura parallela: unmodello SP/2 con 24 processori, che control-lano 512 processori specializzati per la gene-razione delle mosse. Ciascun processorespecializzato analizza circa 1 milione di po-siz/s, e complessivamente i 512 processoriarrivano a circa 200 milioni di posiz/s utili.Questo permetteva a Deep Blue di esplorarealberi profondi 12/14 semimosse in circa 3min, il tempo medio per mossa di torneo.

5. LO STATO DELL’ARTE

Un’importante misura dell’efficienza di un al-goritmo parallelo è lo speed-up (accelerazio-ne). Questo parametro è definito come il rap-porto tra il tempo di esecuzione di una imple-mentazione sequenziale efficiente di un al-goritmo e quello di una sua versione paralle-la. L’obiettivo ideale è di ottenere valori perlo speedup che aumentino linearmente con ilnumero di processori usati. Purtroppo que-sto risultato è difficile da ottenere per gli al-goritmi paralleli di ricerca su alberi di gioco.Esistono infatti diversi motivi di degrado del-le prestazioni di questa classe di algoritmiche vengono indicati con il termine overhead(degradazione) [14].L’overhead in tempo (OT) esprime una misu-ra quantitativa della degradazione totale del-l’algoritmo: è la perdita percentuale di spee-dup confrontata con lo speed-up ideale. Èespressa come:

nOT = (tempo con n CPU) · –––––––––––––––

tempo con 1 CPU

L’ overhead totale è in realtà composto dapiù componenti:❑ overhead di ricerca (OR): in ambiente se-quenziale tutte le informazioni ricavate finoad un dato punto della ricerca sono disponi-bili per effettuare decisioni quali il taglio diun sottoalbero.In ambiente distribuito le stesse informazionipossono essere disperse su macchine diver-se e quindi non efficacemente utilizzabili: ciò

può portare ad una esplorazione non neces-saria di una porzione dell’albero di gioco. Lacrescita delle dimensioni dell’albero è chia-mata overhead di ricerca. Tale forma di de-grado può essere approssimata osservandoche la dimensione dell’albero esplorato èproporzionale al tempo di ricerca. OR è preci-samente definito dalla relazione:

nodi visitati da n CPUOR = ––––––––––––––––––––– – 1

nodi visitati da 1 CPU

❑ overhead di comunicazione (OC): è il caricoaddizionale che un programma parallelo de-ve sopportare quando è impiegato un temponon trascurabile per la comunicazione deimessaggi fra i processi. Questo costo può es-sere limitato in fase di programmazione sce-gliendo opportunamente le dimensioni e lafrequenza dei messaggi. Una stima di OC èdata dal prodotto fra il numero di messaggiinviati e il costo medio di un messaggio.❑ overhead di sincronizzazione (OS): è il co-sto che occorre quando alcuni dei processorisono inattivi. In teoria tutti i processori do-vrebbero essere occupati nello svolgere lavo-ro utile per tutto il tempo di esecuzione. Nel-la realtà questo comportamento ideale vienemeno quando un processo deve sincroniz-zarsi con un altro determinando attesa atti-va. Potrebbe accadere per esempio che unprocesso P voglia agire su un valore condivi-so in mutua esclusione, mentre un altro pro-cesso Q sta già operando su tale valore. Ilprocesso P rimarrà bloccato (e quindi inatti-vo) fintanto che Q non abbia completato lasua operazione. Tale overhead può presen-tarsi anche quando un processo è in attesache certi risultati, senza i quali non può conti-nuare, gli siano forniti da un altro.L’overhead complessivo OT è funzione delletre forme di overhead elencate:

OT = f (OR, OC, OS)

Per massimizzare le prestazioni di un algorit-mo parallelo è necessario minimizzare i varitipi di degradazione. Purtroppo essi non so-no mutuamente indipendenti e lo sforzo nel-la minimizzazione di uno di essi può risultarenell’aggravio di un altro. Per esempio la ridu-zione dell’overhead di ricerca richiede nor-

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

11

0

0

0

1

0

malmente un aumento del numero delle co-municazioni.Esistono comunque diverse fonti di paralleli-smo nella ricerca di alberi di gioco le qualihanno originato approcci completamentedifferenti al processo di parallelizzazione del-la ricerca sequenziale:❙ parallelismo nella valutazione statica deinodi terminali; ❙ generazione parallela delle mosse;❙ decomposizione dell’albero di gioco.

5.1. Parallelismo nella funzionedi valutazione staticaUna considerevole porzione del tempo di ri-cerca è spesa nella valutazione statica deinodi terminali. La qualità delle scelte strate-giche operate durante il gioco è fortementelegata alla affidabilità e quindi alla comples-sità della funzione di valutazione. Spesso sisceglie di praticare una valutazione staticasemplice e grossolana preferendo impiegareil tempo di ricerca nel condurre esplorazionipiù in profondità nell’albero di gioco. Il tem-po dedicato alla valutazione dei nodi termi-nali può tuttavia essere ridotto distribuendotale operazione su più processori, ciascunodedicato a valutare differenti termini dellafunzione di valutazione. I risultati del lavorocosì partizionato saranno riuniti per originareun unico valore per la posizione esaminata.

Chiaramente lo speedup massimo ottenibileè limitato dalla scomponibilità e modularitàdella funzione di valutazione implementata.Deep Blue fa uso di un hardware specificoper l’esecuzione della valutazione statica.In particolare esso consiste di due compo-nenti denominati rispettivamente valutato-re veloce e lento:❑ l’hardware per la valutazione veloce ag-giorna i termini della funzione di valutazioneche possono essere calcolati in modo incre-mentale, cioè a mano a mano che vengonoeseguite o retratte le mosse. Tale aggiorna-mento avviene in parallelo alle altre fasi diesplorazione interna dell’albero; quandosarà raggiunto un nodo terminale parte deisuoi termini saranno quindi già valutati.❑ i restanti termini della funzione di valutazio-ne sono calcolati dal valutatore lento quandola ricerca arriva ad un nodo terminale. Il lorocalcolo è completato molto rapidamente poi-ché la risorsa di elaborazione ad esso dedica-ta utilizza un insieme di tabelle indirizzate viahardware. Ogni tabella contiene informazioniriguardanti proprietà salienti di una posizioneaggiornate durante la ricerca.

5.2. Generazione in parallelo delle mosseLa generazione delle mosse è un’altra opera-zione molto frequente nella ricerca su un al-bero di gioco ed in generale incide pesante-mente sul tempo globale di esecuzione. Ne-gli scacchi la velocità di generazione dellemosse è il fattore che limita le dimensionidella ricerca poiché le regole che governanoil movimento dei pezzi sono piuttosto com-plicate. Un accorgimento desiderabile è dun-que la generazione in parallelo di tutte lemosse relative ad un nodo.Ogni colonna della scacchiera potrebbe esse-re assegnata ad un diverso processore, chegenererà tutte le mosse per tutti i pezzi di-sposti sulla propria colonna. Poiché ogni co-lonna può contenere più pezzi di un’altra ènecessaria una forma di bilanciamento delcarico, cioè un riassegnamento dei lavori permantenere tutti i processori attivi. In questatecnica un motivo di degrado delle prestazio-ni è dovuto al fatto che per molti nodi non ènecessario generare tutte le mosse (a causadi tagli) e così parte del lavoro andrà perduto.Il metodo descritto si presta per una sua im-

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

0

0

1

12

Sistema Posizioni/sec HW

Ananse 6.000 Intel 486/66

MChess 10.000 Pentium 90

Amy 10.000 Sun Sparc10

Arthur 20.000 Sun Sparc20

Cray Blitz 750.000 Cray C90

*Socrates 1.000.000 CM5 / 512

DeepThought 2 4.000.000 IBM/6000

Deep Blue (1997) 200.000.000 IBM SP/2 (24processori) + 512chip speciali

Fritz, Junior, Shredder 3-5 milioni Quadriprocessoresu PC di ultimagenerazione

(2004)

TABELLA 3Numero di posizioni

per secondoanalizzate da alcuni

sistemi

plementazione in hardware, cioè che utilizzicomponenti architetturali progettati ad hoc.HITECH [5] utilizzava hardware specifico perla generazione in parallelo delle mosse. Inparticolare veniva impiegata una matrice 8 ×8 di processori, uno per ogni casa della scac-chiera: ciascun processore calcolava in pa-rallelo agli altri le mosse legali per il pezzoche occupa la casa cui è associato (ammes-so che essa non sia vuota). Il generatore im-plementava inoltre l’ordinamento delle mos-se: quella suggerita è la mossa con maggio-re priorità; la priorità di una mossa è una sti-ma del suo valore ed è attribuita autonoma-mente dal processore che l’ha generata.Ogni processore deposita la priorità dellasua migliore mossa su un bus accedibile datutti gli altri: quando il processore con lamossa a più alta priorità riconosce che nes-sun altro dispone di mossa migliore, essopresenta la sua mossa al modulo dedicato alcontrollo della ricerca.

5.3. Decomposizione dell’albero di giocoIl metodo di decomposizione divide l’alberoin sottoalberi e stabilisce che sottoalberi di-versi siano esplorati da processori in genera-

le distinti. Tale approccio al parallelismo nonprevede, in linea di principio, limitazioni perlo speed-up. In [4] sono confrontate le pre-stazioni di diversi algoritmi distribuiti di de-composizione dell’albero di gioco. La pro-spettiva di prestazioni elevate su architetturespecializzate ha fatto sì che i maggiori sforzinella ricerca siano stati concentrati nella di-rezione tracciata da questa classe di algorit-mi paralleli. In effetti, questo è l’approccioscelto da Deep Blue [1].

5.4. I programmi commercialiQuelle che abbiamo delineato sono le li-nee di ricerca più note, in quanto pubblica-te su riviste scientifiche dagli autori deiprogrammi. Esistono però centinaia di pro-grammi di vari autori e di diversa forza, al-cuni dei quali hanno valore commerciale edi cui nulla si sa circa il funzionamento in-terno. I pincipali tra questi programmi sisfidano annualmente in un Campionato delMondo organizzato da ICGA. Nel 2004 ilCampionato si è svolto presso l’UniversitàBar-Ilan di TelAviv, con i risultati mostratinella tabella 4.Questa tabella è interessante perché sembra

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

13

0

0

0

1

Nome Nazione Hardware Punti (su 11 incontri)

Junior Israele 4proc 2.2GHz, Proliant HP 9

Shredder Germania 4proc AMD 2.0 GHz, Transtec 8.5

Diep Olanda 4proc AMD 2.0 GHz 7.5

Fritz Olanda 4proc AMD 2.0 GHz, Transtec 7

Crafty USA 4proc AMD 2.0 GHz 7

Jonny Germania AMD64 3200+ 6.5

ParSOS Germania AMD64 3200+ 6

Falcon Israele AMD64 3200+ 6

ISIChess Germania AMD64 3400+ 6

Deep Sjeng Belgio AMD64 3400+ 5.5

Woodpusher UK Pentium 4 2.8 GHz 3

Movei Israele Pentium 4 2.8 GHz 3

The Crazy Bishop Francia Pentium 4 2.8 GHz 2

FIBChess Spagna Pentium 4 2.8 GHz 0

TABELLA 4La classifica finaledel Campionatodel Mondo 2004

0

mostrare che l’elemento dominante anchecon software diversi sia l’hardware.I programmi commerciali sono così “ottimiz-zati” che ormai battono regolarmente i mi-gliori giocatori umani. Per esempio nelloscorso settembre 2004 all’IRST di Trento ilmigliore giocatore italiano, Michele Godena,ha sfidato il programma campione del mon-do 2004, Deep Junior, creato in Israele da Bu-shinsky e Ban (Figura 5). La partita, vinta dalprogramma, è la seguente:

[Event “Uomo vs Computer”][Site “Povo - Trento ITA”][Date “2004.09.27”][Round “1”][White “Deep Junior”][Black “Godena, Michele”][Result “1-0”][PlyCount “89”]

1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Ba4 Nf6 5. 0-0 b56. Bb3 Bc5 7. a4 Bb7 8. d3 b4 9. c3 d6 10. a5 h611.d4 Ba7 12. Be3 0-0 13. Nbd2 bxc3 14. bxc3exd4 15. cxd4 Nb4 16. Qb1 Rb8 17. Re1 d5 18. e5Nd7 19. e6 fxe6 20. Bxh6 Qf6 21. Bg5 Qf7 22. Bh4Rfe8 23. Bg3 Nf8 24. Ba4 Bc6 25. Ne5 Qf6 26.Ndf3 Bxa4 27. Rxa4 Nc6 28. Qd3 Nxe5 29. Bxe5Qf5 30. Qxa6 Rb1 31. Ra1 Rxa1 32. Rxa1 Rb8 33.Rf1 Rb1 34. Qxa7 Rxf1+ 35. Kxf1 Qb1+ 36. Ke2Qb5+ 37. Ke3 Qb3+ 38. Kf4 Qc2 39. h4 Qxf2 40.Qb8 Qxg2 41. a6 Qe2+ 42. Qxc7 Ng6+ 43. Kg3Nxe5 44. Qd8+ Kh7 45. dxe5 1-0

6. CONCLUSIONI

La ricerca sul gioco artificiale è ritenuta tut-tora da alcuni studiosi di importanza capita-le per lo sviluppo della teoria e delle tecno-logie della Intelligenza Artificiale. SecondoDonald Michie:

“la costruzione di giocatori artificiali di scacchi, unaricerca di tipo tecnologico ma che ha una portatache va ben al di là della pura tecnologia, è oggi la ri-cerca scientifica più importante del mondo. Possia-mo confrontarla con le ricerche fatte da T.Morgan aNew York durante la Prima Guerra Mondiale sullaDrosophila. Quelle ricerche ebbero un impatto fon-damentale sulle basi teoriche della genetica mo-derna. Ci accorgiamo oggi delle conseguenze indu-striali dell’ingegneria genetica, che è figlia delle ri-cerche di Morgan. Stiamo oggi usando l’analisiscientifica del gioco degli scacchi come studio preli-minare per l’ingegneria della conoscenza”.

Tuttavia, anche se l’Intelligenza Artificialepuò guadagnare ancora molto dall’approfon-dimento di ricerche sui giochi, non c’è dubbioche il risultato di Deep Blue va considerato inprimo luogo un successo della ricerca sul cal-colo parallelo.Il successo di Deep Blue è irripetibile, perchéla macchina è stata smantellata. Negli ultimianni ci sono stati altri incontri tra i più fortigiocatori del mondo e i migliori programmicommerciali che giravano su normali perso-nal computer. La maggior parte di questi in-contri si è conclusa in parità. Dunque dicia-mo che al momento la superiortà delle mac-chine sugli umani nel gioco degli scacchi nonè affatto netta. Certo però ormai sono pochedecine gli umani che riescono a resistere allaforza di gioco delle macchine. Per esempio imigliori giocatori dell’Internet Chess Club so-no da anni i computer: al momento domina ilprogramma Shredder.Occorre domandarsi come si orienterà la ri-cerca in futuro. Esistono molti giochi piùcomplessi degli scacchi, ad esempio il Go ogli scacchi cinesi. Noi crediamo che siano igiochi ad informazione incompleta ad n gio-catori quelli che debbono essere studiati infuturo: un esempio è il Risiko. Questi giochicreano situazioni molto complesse che so-no poco studiate.

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

0

0

1

14

FIGURA 5Da sinistra: Shay Bushinky e Amir Ban, autori di Deep Junior

Bibliografia

[1] Anantharaman T., Campbell M, Hsu F.: Singu-lar Extensions: Adding Selectivity to Brute For-ce Searching. Artificial Intelligence, Vol. 43,1990, p. 99-110.

[2] Berliner HJ., Goetsch G., Campbell M., EbelingC.: Measuring the Performance Potential of

Chess Programs. Artificial Intelligence, Vol. 43,1990, p. 7-20.

[3] Ciancarini P.: I giocatori artificiali di scacchi.Mursia, 1992.

[4] Ciancarini P.: Distributed Searches: a Basis for Com-parison. Journal of the International ComputerChess Association, Vol. 17:4, 1994, p. 194-206.

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

15

0

0

0

1

MINIGLOSSARIO SCACCHISTICO

ALBERO DI GIOCO

In un gioco ad informazione completa, è la rappresentazione astratta dello sviluppo di tutte le varianti possibili, ciascuna calcolata fi-no ad una posizione terminale. Negli scacchi l’albero del gioco è completamente sviluppabile in teoria ma non in pratica, a causa del-l’esplosione combinatoria delle varianti.

EFFETTO ORIZZONTE

Difetto intrinseco di un algoritmo di valutazione basato su una visita parziale dell’albero di gioco. Si rimedia in parte continuando adespandere l’albero fino ad ottenere solamente posizioni quiescenti.

ELO, PUNTEGGIO

Sistema di misura e classificazione della forza dei giocatori di scacchi. Introdotto dal prof. A. Elo negli Stati Uniti durante gli anni ’60,venne ufficialmente adottato dalla FIDE nel 1970. Al punteggio Elo, che varia col variare dei risultati conseguiti in tornei ufficiali, è le-gato il conseguimento dei titoli nazionali e internazionali, secondo la seguente tabella indicativa: Maestro = 2200; Maestro Fide =2300; Maestro Internazionale = 2400; Grande Maestro = 2500. Il sistema Elo locale di una nazione può differire da quello internazio-nale. In particolare, il sistema Elo della federazione americana USCF è leggermente inflazionato rispetto a quello internazionale. Perquesto motivo i punteggi Elo dichiarati dai costruttori di scacchiere elettroniche sono solitamente riferiti all’Elo USCF.

OBIETTIVO

Situazione di gioco da raggiungere mediante un piano strategico.

PIANO

Definizione dell’obiettivo e dei mezzi per raggiungerlo.

PLY

Vedi Semimossa.

POSIZIONE QUIESCENTE

Posizione in cui non sono possibili scacchi o prese. Una posizione quiescente viene valutata dalla funzione di valutazione senza ulte-riore sviluppo dell’albero di gioco.

POSIZIONE TERMINALE

Nel gioco degli Scacchi una posizione è terminale se uno dei due giocatori ha dato scacco matto all’avversario, oppure se non è piùpossibile il matto, e quindi la partita è patta (esempio: Re solo contro Re solo).

POSIZIONE TURBOLENTA

Posizione non quiescente. Tipicamente, una posizione in cui sono possibili scacchi o prese.

SEMIMOSSA

Movimento di un pezzo di uno dei due giocatori. Due semimosse consecutive, una per ciascun giocatore, costituiscono una mossa nelsenso tradizionale.

STRATEGIA

Definizione ed esecuzione di un piano di gioco a lungo termine allo scopo di conseguire un certo obiettivo. Nei commenti ad una par-tita la descrizione di una strategia è spesso generica e non dettagliata.

TATTICA

Definizione ed esecuzione di piani di gioco a breve termine, solitamente subordinati alla strategia. Un piano tattico va elaborato det-tagliatamente.

VARIANTE PRINCIPALE

Risultato ottenuto dalla valutazione minimax di una posizione. Contiene la mossa da giocare ed il seguito più probabile previsto dal-la macchina.

ZUGZWANG

Una posizione di zugzwang è una posizione in cui la parte che deve muovere non può che peggiorare le proprie possibilità, mentre in-vece se potesse “passare” la mossa non comprometterebbe nulla.

0

[5] Ebeling C.: All the Right Moves: A VLSI Architec-ture for Chess. MIT Press, 1987.

[6] Finkel RA., Fishburn J.: Parallelism in Alpha-Beta Search. Artificial Intelligence,Vol. 19,1982, p. 89-106.

[7] Hsu FH.: Behind Deep Blue. Princeton Univer-sity Press, 2002.

[8] Marsland TA., Campbell M.: Parallel Search ofStrongly Ordered Game Trees. ACM ComputingSurveys, Vol. 14:4, 1982, p. 533-551.

[9] Marsland TA., Popowich F.: Parallel Game TreeSearch. IEEE Trans. on Pattern Analysis and Ma-chine Intelligence, Vol. 4:7, 1985, p. 442-452.

[10] McGrew T.: Collaborative Intelligence. IEEE In-ternet Computing, Vol. 1:3, 1997, p. 38-42.

[11] Moravec H.: When will computer hardware mat-ch the human brain?. Journal of Evolution andTechnology, Vol. 1, 1998 (anche in Moravec H:,ROBOT: Mere Machine to Transcendent Mind,Oxford Univ. Press, 1998).

[12] Newborn M.: Deep Blue: An Artificial Intelligen-ce Milestone. Springer, 2003.

[13] Schaeffer J.: Experiments in Search and Know-ledge. PhD Thesis, University of Alberta, 1986.

[14] Schaeffer J.: Distributed Game-Tree Searching.Journal of Parallel and Distributed Computing,Vol. 6, 1989, p. 90-114.

[15] Shannon CE.: Programming a Computer for PlayingChess. Philosophical Magazine, Vol. 41:7, 1950,p. 256-275.

[16] Simon H.A.: Models of My Life. Basic Books, 1991.

[17] Turing AM.: Digital Computers Applied to Ga-mes. In Faster Than Thought (Ed. Bowden BV.),Pitman 1953, p. 286-295.

[18] Siti web: www.research.ibm.com/deepblue - si-to di IBM su Deep Blue.www.icga.org - sito dell’associazione interna-zionale di giochi e computer.www.chessclub.com - internt Chess Club, dovemolti giocatori sono computer

M O N D O D I G I T A L E • n . 3 - s e t t e m b r e 2 0 0 5

1

0

0

1

16

PAOLO CIANCARINI è Ordinario di Ingegneria del Software all’Università di Bologna. È Candidato Maestro di Scac-chi, anche se non gioca più in torneo da parecchi anni. È uno degli organizzatori del Campionato del Mondo diScacchi per computer che si terrà nel 2006 a Torino nell’ambito delle Olimpiadi degli Scacchi. È socio e consi-gliere di AICA, nonché membro del Comitato Scientifico di Mondo Digitale.ciancarini@cs.unibo.it