Un robot che gioca a Un robot che gioca a Dama è spesso Dama è spesso

avanti di un passo, se avanti di un passo, se utilizza Windows 7utilizza Windows 7

Roberto MANCA ITIS M.GIUA CAGLIARI

A mio padre Luigi MancaA mio padre Luigi Manca

per avermi trasmesso la per avermi trasmesso la passione per lo studio del passione per lo studio del gioco della Dama Italiana 8x8.gioco della Dama Italiana 8x8.

Algoritmo di generazione dell’”Albero delle mosse” secondo le

regole della Federazione Italiana Dama

IntroduzioneIntroduzioneIl gioco non è solo un modo piacevole per trascorrere il tempo libero, ma rappresenta spesso un’attività esplorativa. Ai giochi classici come la Dama e gli Scacchi si sono interessati un po’ tutti i pionieri dell’informatica. Arthur Samuel era un programmatore alla ricerca di fondi. Nella vicina cittadina di KanKakee si stava svolgendo un campionato mondiale di dama. Arthur ebbe l’idea di provare a creare un programma che alla fine del torneo sfidasse il campione mondiale vincendolo, ed attirando così fondi ed attenzione. Dopo alcuni giorni si rese conto che era stato molto ingenuo. Fu dopo alcuni anni, quando fu assunto come ricercatore nei Laboratori dell’IBM, che riuscì a realizzare un programma funzionante di un certo livello.Il motivo è che da una scacchiera iniziale delle mosse detta “root” si crea una struttura dinamica ad albero rovesciato che cresce verso il basso.“Anche se ogni scacchiera avesse due successori, un albero che si biforcasse a questo modo 64 volte avrebbe più rami di tutti gli alberi della terra. L’Esplosione esponenziale del numero dei rami fa sì che un normale calcolatore possa esplorare solo una piccola parte dell’albero delle mosse”

A.K. Dewdney SCIENTIFIC AMERICAN

Il Sistema Operativo (S.O.)Il Sistema Operativo (S.O.)Il S.O. è quel modulo software che si interpone tra l’hardware Il S.O. è quel modulo software che si interpone tra l’hardware (CPU, Ram, Hardisk, ecc.) e qualsiasi altro programma (CPU, Ram, Hardisk, ecc.) e qualsiasi altro programma applicativo, controlla che l’uso delle risorse avvenga in modo applicativo, controlla che l’uso delle risorse avvenga in modo corretto ed efficiente.corretto ed efficiente.

Come Sistema Operativo è stato scelto Windows 7, il nuovo Come Sistema Operativo è stato scelto Windows 7, il nuovo S.O. della Microsoft. E’ stato "testato“ utilizzando le principali S.O. della Microsoft. E’ stato "testato“ utilizzando le principali versioni Beta, in particolare la Build 6956, la 6801, la 7000 ed versioni Beta, in particolare la Build 6956, la 6801, la 7000 ed infine la Release Candidate. infine la Release Candidate.

Come programmi applicativi sono stati utilizzati: il compilatore Come programmi applicativi sono stati utilizzati: il compilatore NXT, NXC, NBC per programmare i robot della serie NXT, NXC, NBC per programmare i robot della serie MindStormsMindStorms Lego, il software RIOS per programmare il Lego, il software RIOS per programmare il braccio robotico Lynxmotion AL5B. Inoltre è stata utilizzata braccio robotico Lynxmotion AL5B. Inoltre è stata utilizzata una versione di prova di Dama 4x4 ( programma simulatore di una versione di prova di Dama 4x4 ( programma simulatore di sviluppo) riprendendo dei programmi scritti quando ero sviluppo) riprendendo dei programmi scritti quando ero studente universitario al Politecnico di Torino. Il sistema studente universitario al Politecnico di Torino. Il sistema operativo in fase beta non ha mai dato problemi. In alcuni operativo in fase beta non ha mai dato problemi. In alcuni forum dei programmatori hanno affermato di utilizzare la forum dei programmatori hanno affermato di utilizzare la versione Release Candidate come sistema operativo versione Release Candidate come sistema operativo principale essendo quest’ultima molto stabile.principale essendo quest’ultima molto stabile.

Windows 7 Beta UltimateWindows 7 Beta Ultimate

Una volta installata la versione definitiva di Windows 7, assieme Una volta installata la versione definitiva di Windows 7, assieme agli studenti di 5^A informatica ci siamo messi l’obiettivo di agli studenti di 5^A informatica ci siamo messi l’obiettivo di collegare il software del gioco della dama 8x8 ed il braccio collegare il software del gioco della dama 8x8 ed il braccio robotico. Muovendo una pedina sul monitor il programma di robotico. Muovendo una pedina sul monitor il programma di dama calcola la mossa ed il braccio robotico la esegue spostando dama calcola la mossa ed il braccio robotico la esegue spostando le pedine. Questo è un lavoro complesso, il prototipo è in fase di le pedine. Questo è un lavoro complesso, il prototipo è in fase di sviluppo. sviluppo. All'Università di Alberta (Canada), nel 2007 il docente universitario All'Università di Alberta (Canada), nel 2007 il docente universitario Jonathan Schaeffer responsabile del Dipartimento di Intelligenza Jonathan Schaeffer responsabile del Dipartimento di Intelligenza Artificiale dopo 18 anni di lavoro (assieme ad altri ricercatori) ha Artificiale dopo 18 anni di lavoro (assieme ad altri ricercatori) ha realizzato un programma che calcola 500 miliardi di miliardi di realizzato un programma che calcola 500 miliardi di miliardi di mosse! Centinaia di computer hanno contribuito allo sviluppo di mosse! Centinaia di computer hanno contribuito allo sviluppo di una parte iniziale del database delle mosse.una parte iniziale del database delle mosse.Jonathan Schaeffer ha annunciato di aver risolto “debolmente” il Jonathan Schaeffer ha annunciato di aver risolto “debolmente” il gioco della dama (inglese). Un gioco si dice risolto debolmente se gioco della dama (inglese). Un gioco si dice risolto debolmente se è possibile fornire un algoritmo che assicuri una vittoria per un è possibile fornire un algoritmo che assicuri una vittoria per un giocatore ,o una patta per l’altro contro ogni possibile mossa giocatore ,o una patta per l’altro contro ogni possibile mossa dell’avversario, a partire dalla prima mossa.dell’avversario, a partire dalla prima mossa.

[2] Centro Studi Scacchistici Turing DuchampCentro Studi Scacchistici Turing Duchamp

Programmi ed Algoritmi di gioco della Dama 8x8Programmi ed Algoritmi di gioco della Dama 8x8

Un gioco invece si dice risolto in maniera “forte” se è Un gioco invece si dice risolto in maniera “forte” se è possibile costruire un algoritmo in grado di produrre un possibile costruire un algoritmo in grado di produrre un gioco perfetto a partire da ogni tipo di posizione, anche se gioco perfetto a partire da ogni tipo di posizione, anche se sono già stati commessi degli errori. sono già stati commessi degli errori.

A differenza di quello che si può leggere su qualche sito, A differenza di quello che si può leggere su qualche sito, anche autorevole, non esiste un file contenente tutte le anche autorevole, non esiste un file contenente tutte le informazioni su ogni posizione “legale” che può verificarsi informazioni su ogni posizione “legale” che può verificarsi durante il gioco, e quale mossa porterà alla patta, se durante il gioco, e quale mossa porterà alla patta, se possibile, o alla vittoria (si tratterebbe in quel caso di un possibile, o alla vittoria (si tratterebbe in quel caso di un gioco risolto in maniera forte).gioco risolto in maniera forte).

[2] Centro Studi Scacchistici Turing DuchampCentro Studi Scacchistici Turing Duchamp

Schema grafico Algoritmo Generazione Albero Mosse Dama 8x8Schema grafico Algoritmo Generazione Albero Mosse Dama 8x8

Albero mosse gioco Dama 4x4Albero mosse gioco Dama 4x4

Beta- testingBeta- testing[1*] Per “testare” il nuovo Sistema Operativo Windows 7 della[1*] Per “testare” il nuovo Sistema Operativo Windows 7 della

Microsoft è stato utilizzato l’algoritmo Genera Albero Dama 4x4 e 8x8 Microsoft è stato utilizzato l’algoritmo Genera Albero Dama 4x4 e 8x8 utilizzando i compilatori utilizzando i compilatori Borland C++ e Dev C++ Bloodshed Software.Borland C++ e Dev C++ Bloodshed Software.

[3]

[3]Oltre al Generatore di Albero,è stato utilizzato a scopo didattico anche il programma Commerciale Dama.exe distribuito dalla Finson S.p.A.

Programma simulazione gioco Dama 4x4Programma simulazione gioco Dama 4x4

Tipologia di Bracci RoboticiTipologia di Bracci Robotici

CartesianoCartesiano CilindricoCilindrico SfericoSferico ScaraScara AntropomorfoAntropomorfo

Corso di aggiornamento per docenti svolto all’ ITIS M.GIUA tenuto dall’Università di Pisa

Taratura braccio roboticoTaratura braccio robotico

Utilizzo del programma di calcolo e visualizzazione Utilizzo del programma di calcolo e visualizzazione dell’Insieme di Mandelbrot per testare Windows 7dell’Insieme di Mandelbrot per testare Windows 7

L’insieme di Mandelbrot è stato definito il “più complesso fra gli L’insieme di Mandelbrot è stato definito il “più complesso fra gli oggetti della Matematica” A.K. Dewdney Scientific American. Per oggetti della Matematica” A.K. Dewdney Scientific American. Per calcolarlo occorrono miliardi di calcoli. Per questo motivo viene calcolarlo occorrono miliardi di calcoli. Per questo motivo viene spesso utilizzato nella fase di testing delle CPU e Sistemi Operativi.spesso utilizzato nella fase di testing delle CPU e Sistemi Operativi.

E’ stato scoperto da Benoit B. Mandelbrot, un ricercatore dell’IBM.E’ stato scoperto da Benoit B. Mandelbrot, un ricercatore dell’IBM.

Mandelbrot by Aros Magic Research www.arosmagic.com

L’Insieme di MandelbrotL’Insieme di MandelbrotViene realizzato ultilizzando un algoritmo che prevede l’utilizzo della Viene realizzato ultilizzando un algoritmo che prevede l’utilizzo della formula z<-z^2+c dove z appartiene all’insieme dei numeri complessi,formula z<-z^2+c dove z appartiene all’insieme dei numeri complessi,

Z=x+jy con x,y reali e j immaginario, j è la radice quadrata di meno uno. Z=x+jy con x,y reali e j immaginario, j è la radice quadrata di meno uno. Viene controllato il modulo di Z, utilizzando il Teorema di Pitagora,Viene controllato il modulo di Z, utilizzando il Teorema di Pitagora,

Per fare in modo da rendere più veloce l’algoritmo di calcolo che Per fare in modo da rendere più veloce l’algoritmo di calcolo che prevede un ciclo for <100, si eleva al quadrato il modulo e |z|prevede un ciclo for <100, si eleva al quadrato il modulo e |z|^2=(x^2+y^2)<4 in questo modo si evita di utilizzare l’uso della radice ^2=(x^2+y^2)<4 in questo modo si evita di utilizzare l’uso della radice quadrata che rallenterebbe l’algoritmo. Se dopo 100 interazioni il quadrata che rallenterebbe l’algoritmo. Se dopo 100 interazioni il modulo di Z non cresce viene assegnato il colore nero. Vengono creati modulo di Z non cresce viene assegnato il colore nero. Vengono creati per esempio 8 intervalli di colore, se cresce subito si assegna il colore per esempio 8 intervalli di colore, se cresce subito si assegna il colore bianco. Appaiono così delle figure infinitamente varie e bianco. Appaiono così delle figure infinitamente varie e spaventosamente belle.spaventosamente belle.

Nonostante i miliardi di calcoli il Sistema Operativo Windows 7 ha Nonostante i miliardi di calcoli il Sistema Operativo Windows 7 ha gestito alla perfezione la risorsa CPU e la memoria RAM, consentendo gestito alla perfezione la risorsa CPU e la memoria RAM, consentendo in pochi secondi di visualizzare l’Insieme di Mandelbrot nella sua in pochi secondi di visualizzare l’Insieme di Mandelbrot nella sua impressionante ed infinita bellezza.impressionante ed infinita bellezza.

Nell’home-computer Sinclair QL che possedevo da studente Nell’home-computer Sinclair QL che possedevo da studente universitario al Politecnico di Torino, occorrevano anche 24 ore per universitario al Politecnico di Torino, occorrevano anche 24 ore per realizzare un’immagine.realizzare un’immagine.

Beta Tester CPU (Microprocessore µP)Beta Tester CPU (Microprocessore µP)Prima di iniziare la fase di testing è stato preso come riferimento teorico il µPPrima di iniziare la fase di testing è stato preso come riferimento teorico il µPZ80 progettato dall’italiano ing. Federico Faggin che è il padre del µP.Z80 progettato dall’italiano ing. Federico Faggin che è il padre del µP.

Cosa è il microprocessore Z80? Cosa è il microprocessore Z80? E' dal 1976, anno della sua presentazione sul mercato che lo Z80 consegueE' dal 1976, anno della sua presentazione sul mercato che lo Z80 consegueun vasto successo nell'affollato campo del microprocessori. un vasto successo nell'affollato campo del microprocessori.

La sua longevità appare ancor più sorprendente se si considera la sua La sua longevità appare ancor più sorprendente se si considera la sua evoluzione negli ultimi decenni, con architetture di progettazione che sono evoluzione negli ultimi decenni, con architetture di progettazione che sono passate da 8 a 64 bit e frequenze di lavoro da 5 MHz a 2 GHz. passate da 8 a 64 bit e frequenze di lavoro da 5 MHz a 2 GHz.

Ciò nonostante lo Z80 mantiene un grosso spazio applicativo, non come CPU Ciò nonostante lo Z80 mantiene un grosso spazio applicativo, non come CPU di personal computer (l'unico è stato lo Specrtum), ma come controllore di una di personal computer (l'unico è stato lo Specrtum), ma come controllore di una vasta gamma di apparecchiature automatiche: vasta gamma di apparecchiature automatiche: • Gestore del computer di bordo della Gestore del computer di bordo della JaguarJaguar

• Utilizzato in vari campi applicativi dello Utilizzato in vari campi applicativi dello Shuttle alla NASAShuttle alla NASA

* Sistemi di supervisione degli ambienti (antifurti, centraline elettroniche)* Sistemi di supervisione degli ambienti (antifurti, centraline elettroniche)

Beta Tester CPU (Microprocessore µP)Beta Tester CPU (Microprocessore µP)

Dotato di un'architettura sufficientemente completa ed efficiente con Dotato di un'architettura sufficientemente completa ed efficiente con linee di interrupt, wait, bus request per il DMA, lo Z80 mantiene per linee di interrupt, wait, bus request per il DMA, lo Z80 mantiene per contro una certa semplicità hardware che consente assemblaggi contro una certa semplicità hardware che consente assemblaggi molto facili. Per questo è ancora enormemente richiesto nonostante molto facili. Per questo è ancora enormemente richiesto nonostante prodotti ben più sofisticati. Lavora a frequenze molto basse, prodotti ben più sofisticati. Lavora a frequenze molto basse, consentendo di esaminare e visualizzare le singole fasi operative di consentendo di esaminare e visualizzare le singole fasi operative di funzionamento. funzionamento.

Lo Z80 è realizzato in tecnologia NMOS (sovrapposizione di strati di Lo Z80 è realizzato in tecnologia NMOS (sovrapposizione di strati di metallo a semiconduttori). Appartiene alla categoria dei metallo a semiconduttori). Appartiene alla categoria dei microprocessori con bus dati a 8 bit; con le sue linee è in grado di microprocessori con bus dati a 8 bit; con le sue linee è in grado di gestire fino a 64 kbyte di memoria. Venne introdotto dalla Zilog e gestire fino a 64 kbyte di memoria. Venne introdotto dalla Zilog e successivamente prodotto dalla SGS. Sharp, Toshiba e Motorola che successivamente prodotto dalla SGS. Sharp, Toshiba e Motorola che sono riuscite a realizzare la versione CMOS, permettendo così una sono riuscite a realizzare la versione CMOS, permettendo così una perfetta integrazione con la tecnologia digitale di oggi. perfetta integrazione con la tecnologia digitale di oggi. E' correlato da un linguaggio a basso livello Assembler E' correlato da un linguaggio a basso livello Assembler comprendente 158 istruzioni. comprendente 158 istruzioni.

Ultimata la parte teorica sul uP sono stati testati processori della Ultimata la parte teorica sul uP sono stati testati processori della famiglia (x86) dell’Intel e Amd 64 Athlon. Tutti i test sono stati famiglia (x86) dell’Intel e Amd 64 Athlon. Tutti i test sono stati superati.superati.

Linguaggi NXC ed NQC ed NBCLinguaggi NXC ed NQC ed NBC

Durante la svolgimento dei corsi pomeridiani sono stati installati, Durante la svolgimento dei corsi pomeridiani sono stati installati, utilizzando il nuovo sistema operativo Windows 7, dei compilatori che utilizzando il nuovo sistema operativo Windows 7, dei compilatori che utilizzano i linguaggi NXC, NQC ed NBC, progettati per applicazioni utilizzano i linguaggi NXC, NQC ed NBC, progettati per applicazioni robotiche (Robot serie robotiche (Robot serie MindStormsMindStorms Lego) . Tale linguaggi sono stati Lego) . Tale linguaggi sono stati sviluppati dai ricercatori del dipartimento di Informatica ed Intelligenza sviluppati dai ricercatori del dipartimento di Informatica ed Intelligenza Artificiale di un’Università Olandese (Departement of Computer Science, Artificiale di un’Università Olandese (Departement of Computer Science, Utrecht University – the Netherlands).Utrecht University – the Netherlands).

Tutti i programmi eseguiti durante i corsi pomeridiani hanno funzionato Tutti i programmi eseguiti durante i corsi pomeridiani hanno funzionato perfettamente. perfettamente.

Foto di gruppo con gli studenti partecipanti al corso.Foto di gruppo con gli studenti partecipanti al corso.

BibliografiaNN Tipo di pubblicazioneTipo di pubblicazione Nome Cognome – Titolo operaNome Cognome – Titolo opera

11 Rivista ScientificaRivista Scientifica Virginio SALA- Divertirsi con il Virginio SALA- Divertirsi con il Calcolatore –Le Scienze SpACalcolatore –Le Scienze SpA

22 Sito webSito web Centro Studi Scacchistici Turing Centro Studi Scacchistici Turing DuchampDuchamp

33 Programma dama.exeProgramma dama.exe Evviva la Dama – Fision S.p.A.Evviva la Dama – Fision S.p.A.

44 Programma CompilatoreProgramma Compilatore Borland C++Borland C++

55 Programma CompilatoreProgramma Compilatore Dev C++ Bloodshed SoftwareDev C++ Bloodshed Software

66 Programma ArosFractal.exeProgramma ArosFractal.exe Mandelbrot by Aros Magic Research Mandelbrot by Aros Magic Research www.arosmagic.comwww.arosmagic.com

Studenti Beta TesterStudenti Beta Tester11 Andrea MutoloAndrea Mutolo

22 Federico PauFederico Pau

33 Matteo Sanna Matteo Sanna

44 Giampaolo MameliGiampaolo Mameli

55 Michele AllegramenteMichele Allegramente

© 2010 Microsoft Corporation. All rights reserved.© 2010 Microsoft Corporation. All rights reserved.

Università degli studi di Cagliari

Departement of Computer ScienceUtrecht University – the Netherlands

Bibliografia