Newsgroup: it.hobby.scacchi
Titolo: Scacchi e matematica: L'aiuto di Crafty

Come tutti i software scacchistici, Crafty dispone di un "generatore di mosse".
A differenza di altri software, pero', in Crafty e' anche possibile impartire alcuni
comandi per utilizzare questo generatore di mosse.
Il comando "perft" (abbreviazione di "Performance test") seguito da un numero
intero restituisce il numero di mosse possibili a una certa profondità (in semimosse).
Se do' a Crafty il comando:
perft 1
il programma mi restituisce il valore 20.
Questo perche' a profondita' 1 (cioe' a livello della prima mossa del Bianco)
le mosse possibili sono 20.
Ecco gli altri valori:
2 = 400
3 = 8902
4 = 197.281
5 = 4.865.609
5 = 4.865.609
6 = 119.060.324
A questo punto ci si ferma, perche' se si prova a dare il comando "perft 7" Crafty
si mette a pensare per un tempo indeterminato (dopo circa 15 minuti l'ho fermato!).
Questo perche', come avverte Bob Hyatt nel manuale di Crafty, il programma deve cercare
nell'albero TUTTE le mosse possibili... il che diventa molto lungo!
L'unico problema dei valori che ho citato sopra e' che si riferiscono a TUTTE le mosse
possibili a una certa profondita', cioe' alle mosse legali e a quelle ILLEGALI!
A questo punto mi sembra molto difficile fare il passo successivo, e cioe' calcolare il
numero delle mosse LEGALI possibili a una certa profondita'!
Intanto, per chi si vuole divertire ad approfondire il tema "Scacchi e matematica",
consiglio un ottimo libro, intitolato "Games of no Chance", disponibile quasi
completamente in formato PDF o PostScript e dedicato alla teoria dei
cosiddetti "giochi combinatori", come scacchi, dama, go, ecc.
L'URL e':
http://www.msri.org/publications/books/Book29/contents.html
Saluti
Ivo


FWD (ricevuto per E-mail da Giorgio Bertazzo):
Come al solito sono in ufficio e posso leggere ma non postare.
Il problema delle mosse illegali sta in questi termini: vengono generate 
scandendo pezzo dopo pezzo tutte le mosse possibili senza prendere in 
considerazione un unico aspetto: se il re sia sotto scacco oppure no.
In pratica hanno scoperto che e' piu' economico non testarlo in fase di 
generazione delle mosse ma al momento dell'analisi: in quel caso l'analisi 
esce subito con un errore e la mossa viene skippata.
Il che spiega bene anche perche' all'inizio da' correttamente 20, 40, 
eccetera: non ci sono mosse possibili che lasciano il re sotto scacco.
Giorgio

 wrote in message 3936cfee...@news.tin.it...



 di più!
Crafty si puo' scaricare dalla rete, certo: se usi Windows (95, 98, NT)
puoi scaricare direttamente l'eseguibile; per le altre piattaforme,
probabilmente ti tocchera' scaricare i sorgenti e compilarli.
Crafty pero' non ha una sua interfaccia grafica, per cui dovresti
scaricare anche Winboard (piattaforma Windows), o XBoard (Unix/Linux):
al sito 
http://cafelatte.freeservers.com/chess/index.html
trovi tutte le informazioni (in inglese, ahime') su come scaricare,
installare e configurare Winboard e Crafty.
Se per "qualcosa del genere" intendi altri programmi di scacchi
freeware, ce ne sono un'infinita' (fra cui anche 4 o 5 programmi
italiani!): un piccolo elenco dei programmi Winboard-compatibili
puoi trovarlo sullo stesso sito, all'URL
http://cafelatte.freeservers.com/chess/winboard_programs.html
Altri frequentatori di questo NG sapranno darti informazioni piu'
complete a questo proposito.
Veniamo alle altre domande: le mosse illegali (o meglio mosse pseudo-
legali, come si usa chiamarle in gergo nella programmazione di software
scacchistico) sono semplicemente le mosse teoricamente possibili (cioe'
che rispettano le regole di movimento dei pezzi) ma che lasciano il Re
in presa; inoltre, anche l'arrocco qualora la casa di "transito" del
Re sia attaccata dall'avversario va considerata una mossa pseudolegale.
Il fatto e' che solitamente i programmi di scacchi, per ragioni di
efficienza, generano durante la ricerca non le mosse legali bensi'
appunto quelle pseudo-legali, in quanto il controllo di legalita'
e' molto costoso in termini di risorse e viene quindi differito il
piu' possibile.
La discussione in corso verteva sul numero di mosse possibili a
partire dalla posizione iniziale, che a profondita' 1 (cioe' una
singola semimossa, quella del Bianco) sono appunto 20: sedici
spinte di pedone (a2a3, a2a4, b2b3 ecc.) e quattro mosse di Cavallo
(Ca3, Cc3, Cf3, Ch3).
Naturalmente le mosse possibili in una posizione diversa da quella
iniziale possono essere molte di piu' (anche oltre di 100): in tal
senso la tua obiezione e' corretta.
:-)
Ciao,
C.
--

 possibili a una certa profondita', cioe' alle mosse legali e a quelle ILLEGALI!
<snip>
Non sono d'accordo, IMHO il numero di mosse citate comprende solo quelle LEGALI!
Io ottengo gli stessi identici valori fino al livello 6 e nel mio programma viene fatto il controllo di legalità di tutte le mosse possibili prima di eseguirle (non
è una buona strategia, ma sono gli errori di ... gioventù).
Al livello 6 (ma basterebbe il livello 3) sono già possibili mosse di scacco e quindi il controllo di legalità ha necessariamente conseguenze sul numero delle mosse
possibili.
Calcolare il livello 7 è relativamente semplice e costerebbe meno di un'ora sul mio nuovo PC (600 Mhz), perciò con le macchine di cui dispone Bob il livello 8 è
raggiungibile in tempi ancora ragionevoli (i tempi aumentano con la profondità per un fattore 25-30). Con il computer scacchistico di Big Blue (si chiama Deep
Blue?) poi ...
Non vedo però un grande interesse nella cosa se non unicamente paragonando questi valori con quelli che un dato programma trova se impostato alla stessa profondità.
In tal modo si misurerebbe l'efficienza dell'algoritmo alfa-beta e analoghi, nella potatura dei rami inutili (pruning). Il programma ottimale, per valori pari (2,
4, 6...) di profondità, dovrebbe calcolare un numero di mosse dell'ordine della radice quadrata dei valori sopra riportati.
Naturalmente tale programma non dovrebbe utilizzare algoritmi e metodi statistici, ma unicamente  deterministici.
Vorrei inoltre precisare (per i distratti :-)) che i numeri calcolati da Crafty si riferiscono alle mosse corrispondenti a ciascuna profondità, e non comprendono
quelle fatte a profondità minore. Altrimenti si avrebbe:
1 = 20
2 = 420
3 = 9322
ecc., ecc.
Ciao
Guido
--
Posted from 
smtp1.libero.it
 [193.70.192.51] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG