Newsgroup: it.hobby.scacchi
Titolo: Un programma per gli scacchi: parte II

Ok gente, siamo un bel gruppo. Per organizzare i lavori, propongo di fare
cosi': chi e' interessato risponda a questo messaggio.
Per distribuire i compiti in modo equilibrato, compiliamo una specie di
"scheda" in cui indichiamo TUTTI i linguaggi di programmazione conosciuti,
il grado di conoscenza degli algoritmi utilizzati per la generazione delle
mosse e la valutazione delle posizioni ed infine il tempo disponibile da
dedicare all'operazione.
Potremmo dividerci in due gruppi: un gruppo di programmatori ed un gruppo
che si occupi principalmente di (ri)cercare e perfezionare (non a livello
di linguaggio di programmazione) le routines del programma: poiche' da
quello che ho letto tutti -bene o male- conosciamo  il buon vecchio C
"liscio", il gruppo algoritmi potrebbe presentare le routines scritte in C
ai programmatori, che le tradurrebbero, una volta approvate, nel linguaggio
scelto per il programma. Ciascuno dei due gruppi potrebbe avere un
"coordinatore": sarebbero poi i due coordinatori a fare da ponte fra i
gruppi.
Sarebbe anche meglio, secondo me, che questi gruppi fossero "statici",
cioe' ad es. chi e' programmatore lo rimane indefinitamente. Questo
perche', per la mia esperienza, una certa definizione dei ruoli e' quella
che permette di coordinare meglio un progetto come questo.
Ovviamente, ben vengano i consigli e le opinioni dal NG.
Comincio io con il compilare la "scheda":
LINGUAGGI CONOSCIUTI:
C (non ++), Assembly, QuickBasic (solo per DOS)
VisualBasic (ambiente windows)
CONOSCENZA ALGORITMI:
solo teoria: in effetti ho iniziato da poco e per ora ho solo "studiato"!
Possiedo un certo numero di articoli su alfa-beta pruning, negascout,
algoritmi sperimentali piu' veloci di negascout (sembra!), generazione
mosse, tabelle hash ... molta roba (in teoria!).
Infine, un paio di idee inedite (credo) che vorrei mettere alla prova.
TEMPO:
Poco, a causa di tesi. In effetti, se non trovavo qualcuno disposto a fare
qualcosa, avrei iniziato "seriamente" dall'inizio del prossimo anno. Per
ora posso solo mettere a disposizione tutte le mie informazioni e scrivere
qualche routine in pseudocodice per illustrarle.
Ciao a tutti,
-- 
Stefano Costa
^^^^^^^^^^^^^
sco...@enjoy.it
cos...@odino.unipv.it

Mi piacerebe moltissimo partecipare al progetto ma... purtroppo non ho
tempo.
Se piu' avanti saro' piu' libero mi faro' avanti. :-)
In ogni caso avete tutto il mio appoggio "spirituale" ;-)
ciao
Gianluigi Masciulli

 
cos...@odino.unipv.it
Ok, Stefano...
Team: stabiliamo quali logiche dobbiamo implementare. Non c'ho pensato ancora,
pero' uno schema e' importante.
DA SVILUPPARE.
(modulo I) "Gestore della scacchiera"
(modulo I) Caratteristiche. Offre diverse funzioni inerenti la scacchiera, i
pezzi sulla scacchiera, i pezzi catturati, lo spostamento dei pezzi. Si puo'
settare o interrogare. E' in pratica il punto d'uscita degli algoritmi di
calcolo/valutazione/etc. Qui vediamo "graficamente" il risultato. Deve  essere
un modulo completamente indipendente dal resto. Controlla la validita' delle
richieste che gli arrivano, ritornando un segnale d'errore se la funzione
richiesta non e' fattibile.
(modulo I) Funzionalita'.
(1)Si possono posizionare i pezzi sulla scacchiera, singolarmente. (2)si puo'
interrogarlo per sapere le posizioni di ogni pezzo(1). Permette di variare la
posizione di un pezzo(3). Permette di variare la posizione di un pezzo, con
cattura del pezzo avversario(4). Permette di variare la posizione di un pezzo,
con promozione. (5) Permette l'interrogazione dei pezzi catturati. (6) Si puo'
"pulire" la scacchiera, partendo con scacchiera vuota.
(modulo I) Note.
(1) Riconosce una serie di comandi semplici. (2) Il modulo non esegue
valutazioni sulle posizioni per calcolare le mosse succesive. (3) Esegue solo i
comandi (funzionalita') se sono leciti. (3) Non permette mosse illegali o
errate, o mosse in ogni caso non permesse dal regolamento. (4) Riconosce gli
spostamenti dei pezzi, con cattura, ed in en passant, con promozione. (5)
Comunica con l'esterno tramite messaggi sulla riuscita o meno di un comando.
---QUESTA E' UNA BOZZA--- mi sembra buono indicare le funzioni che stiamo
implementando (a livello generale) senza specificare magari la routine
"cerco_ultimo_elemento()" !! ok?
Numerando in questo modo possiamo riferirci in modo preciso alle specifiche.
Non pensiamo in modo troppo puntiglioso, perche' la sostanza conta piu' della
forma. Nel Modulo I (G.d.S) il modo in cui gli arrivano i comandi non e'
fondamentale. Si puo' darglieli da riga di comando, usando una locazione di ram
in comune (tipo 0:416 o giu' di li'), o mediante un file temp su disco, o (la
migliore) mediante eventi asincroni (---che a parte la parola ostica, in pratica
sono un metodo come un altro). ok?
Per il Modulo I "Gestore della scacchiera", qui ci posso pensare io... e' molto
semplice e lo posso fare in completa trasparenza, ovvero ho risorse anche per le
altre cose.
Fatemi sapere e definite quello che c'e' da implementare. Possiamo anche
scrivere piu' di un algoritmo per lo stesso problema, lanciarli in parallelo e
fare un merge sui risultati or else.
bye,
Julian//



   Stefano Costa wrote:


Ok gente, siamo un bel gruppo. Per organizzare i lavori, propongo di
fare

cosi': chi e' interessato risponda a questo messaggio.

.......

Ti spiego brevemente quello che ho già fatto.

Come detto in altra e-mail sono partito qualche anno fa a sviluppare
programmi per scacchi (dama, bridge e un simpatico solitario di carte), 
partendo unicamente dalla mia esperienza di programmazione, dalla conoscenza
delle regole degli scacchi (anche se sono un pessimo giocatore), e senza
conoscenze precedenti sulla teoria dei giochi.


In questi giorni ho scaricato e letto la tesi di Gianluca Giunta (
http://etna.dipmat.unict.it/~gianluca/
)
ed ho finalmente capito di aver utilizzato nella ricerca minimax l'algoritmo
Alpha-Beta con ricerca Depth-First, anche se non sicuro su come inquadrare
esattamente il mio test di confronto utilizzato per ridurre le mosse esaminate.


Per il gioco ho realizzato due programmi non interattivi, ma puramente
sequenziali:


Il primo risolve problemi di matto con livello fisso assegnato. Come
esempio dei tempi, con il mio Pentium 133 I° tipo, percorrendo 
tutte
le vie
 a partire dalla posizione di inizio partita ho verificato che
non è possibile dare scacco matto (ovvio!), ottenendo questi risultati:


Mosse del Bianco         
Call           
Tempi         Tempo per call

                                                         
sec            
microsec

          1                             
1               
-                     
-

          2                           
41               
-                     
-

          3                         
970              
0.09            
92.784

          4                      
19689             
1.62             
82.279

          5                    
444924           
35.71             
80.261

          6                
10547767           832.96             
78.970

          7               
249692499       20204.62             
80.918


Call = chiamata routine che trova 
tutte le mosse
 di un giocatore
in una data situazione

Supponendo che in media ogni posizione dia luogo a 25 mosse, il mio
programma su un normale P133 calcolerebbe circa 300000 mosse al secondo
(senza funzione di valutazione però!).


Ogni mossa in più del B e del N moltiplica il tempo per un fattore
23-25, che è più o meno la radice quadrata del fattore che
moltiplica i casi totali per l'aumento di una mossa dei due giocatori.


Il secondo programma permette di giocare a scacchi sempre con livello
fisso assegnato, e rispetto al precedente possiede due elementi in più:
una funzione di valutazione estremamente rozza, su cui non ho insistito
cosciente delle mie capacità scacchistiche, ed un algoritmo di mia
invenzione per tenere in memoria il minimo numero di sequenze di mosse
tra le quali vi è la sequenza ottimale, la cui occupazione è 
O(n^2)  se n è il livello di ricerca.


Una domanda che mi sono sempre posto è la seguente: perché
nei tornei con computer, laddove fosse permesso, non si affianca al computer
giocante che ricerca la mossa, un secondo computer (o processore) che ricerca
il matto dalla stessa posizione? La ricerca del matto è parecchie
volte più veloce della ricerca della mossa migliore, sia perché
non deve valutare alcuna funzione, sia perché, se la penultima mossa
non dà scacco, non vi può essere matto alla successiva (questo
spiega perché basta una Call per concludere che non vi è
matto in una mossa, e, se ci pensate, potrete capire anche perché
bastano 41 Call per 2 mosse). Inoltre il criterio di eliminazione di rami
inutili è molto più efficace.


Sul secondo programma ho anche costruito una gestione delle aperture,
con formato da me inventato e certamente non ottimale; ho inoltre provato
a costruire una specie di transposition table, ma ho constatato che al
mio programma non dava alcun vantaggio in termini di tempo, pur riducendo
i casi esaminati.


Per quanto riguarda i finali ho realizzato alcuni programmi che mi permettono
di risolvere completamente in tutti i dettagli i finali studiati (max alcuni
casi di 4 pezzi Re compresi). Sono in grado cioè per una qualsiasi
disposizione dei pezzi, di indicare tutte le mosse possibili con il loro
risultato (vittoria e sconfitta con numero di mosse o patta),  nell'ipotesi
di mosse ottimali di entrambi i giocatori. Con computer più potenti
del mio e ottimizzando i formati si potrebbe estendere il numero dei finali
trattati.


Come esempio propongo a te ed ai lettori il seguente caso del finale
R+T contro R+C:

Bianco:    Rd3  Tc7

Nero:       Rh4  Ce1


Il Bianco muove (è sotto scacco) e matta in 40 mosse.

Le prime 16 mosse del Bianco e del Nero sono obbligate per rispettare
l'assunto, nel senso che qualsiasi altra mossa del  B patta o ritarda
la vittoria, qualsiasi altra mossa del N accelera la sconfitta. La 17a
mossa del B ha 3 varianti equivalenti, che danno origine a molteplici ramificazioni.
Questa disposizione rappresenta l'unica situazione, in cui il Bianco vince
in 40 mosse; i casi totali, tenuto conto delle simmetrie, sono 1347906
con vittoria (in <= 40 mosse) in 651492 disposizioni e patta in 
696413 a cui si aggiunge 1 disposizione in cui il B perde trovandosi sotto
scacco matto.


Mi farebbe piacere se qualcuno verificasse con un programma "serio"
l'esattezza di quanto detto.

Non ho messo la soluzione perché forse a qualcuno interessa
provare senza vederla, ma è ovviamente a disposizione di chi la
vuole.

 

Non ho invece sviluppato:


- Ambiente interattivo di gioco (presentazione, disegno scacchiera,
modifica parametri di gioco) e quindi possibilità di "pensare" durante
il tempo dell'avversario

- Gestione del tempo disponibile

- Funzioni serie di valutazione della posizione

- Variazione del livello di analisi per sequenze di cattura o per mosse
interessanti

- Ottimizzazione dei formati dei database delle aperture e dei finali.

- Altre euristiche per aumentare l'efficienza del programma


Linguaggi conosciuti: Fortran, Basic, C e altri ...


Sul linguaggio da usare penso che per un insieme di ragioni si debba
usare il C++; esso è un linguaggio ormai universale, e quindi "portabile",
particolarmente efficiente, e gira su Unix.

Utilizzando il sistema operativo Linux, che è un clone di Unix
freeware e di provata stabilità ed efficienza, tutti potrebbero
disporre gratuitamente dello stesso sistema. La scelta del C++  permette
inoltre di trasferire quasi pari pari le funzioni scritte in C.


In questo contesto la definizione di ruoli, "pensatori" e "programmatori", 
perde senso se è vero che chi pensa gli algoritmi, li dovrebbe trasferire
in C ai programmatori, che si limiterebbero ad inserirli nel programma
con piccole variazioni.


Io penso che per realizzare il nostro progetto la cosa più importante
sia trovare un luogo fisico dove alcune persone e il responsabili del progetto
risiedono e vi lavorano, mentre gli altri contribuiscono con idee e/o routine
tramite e-mail. Se questo luogo fosse un'università o un politecnico?
Ho il timore che i problemi sorgano quando si dovrà decidere l'impostazione
e gli algoritmi da utilizzare senza scontentare i partecipanti, soprattutto
quelli che hanno già lavorato per proprio conto. Per un'idea in
proposito collegatevi a 
www.cs.ualberta.ca
 e cercate il progetto chinook
relativo al gioco della dama.


Sia pur moderatamente, ho disponibile un po' di tempo per questo progetto.


Guido