Newsgroup: it.hobby.scacchi
Titolo: La stupidita' dei programmi scacchistici!!!

Se vi sembra che ormai i programmi scacchistici
siano troppo forti, fate un po' analizzare il problema
di matto in 7 che trovate sotto da tutti i programmi che
avete installato sul vostro PC...
Da una breve carrellata (solo sui motori CB!) ho visto che
soltanto Nimzo 8 "vede" la soluzione, mentre tutti gli altri
o si piantano o danno la posizione come patta!!!
Come si sa, ai programmi scacchistici non piacciono le posizioni
chiuse!!!
[Event "?"]
[Site "?"]
[Date "1954.??.??"]
[Round "?"]
[White "Speckmann"]
[Black "#7"]
[Result "1-0"]
[SetUp "1"]
[FEN "8/1K6/8/3R4/8/6p1/np1pppp1/krbrqrrn w - - 0 1"]
[PlyCount "0"]
[EventDate "2000.11.29"]
[SourceDate "2000.11.29"]
 1-0
Saluti
Ivo

 [FEN "8/1K6/8/3R4/8/6p1/np1pppp1/krbrqrrn w - - 0 1"]
Si tratta di un tipica posizione NullMove-killer, come molte di
quelle che coinvolgono in qualche modo lo stallo. In pratica in
questo tipo di posizioni la null-move heuristic, usata da tutti
i principali software scacchistici (tranne forse Rebel e pochi
altri, che comunque usano un qualche tipo di pruning), si tramuta
in un boomerang che porta il programma a sbagliare completamente
la valutazione.
Ho fatto una prova con il mio programma Leila: con le null moves
abilitate non e' in grado di risolvere il problema, e gioca 1. Ta5 e
patta fino a profondita' 23 (circa 3 minuti e mezzo sul mio PII 300); 
disabilitando le null moves, trova immediatamente la soluzione
a profondita' 12 (circa 2 secondi), con la seguente PV:
1. Td8 Cb4  2. Ta8 Ca2  3. Ra6 Cc3  4. Ra5 Ca2  5. Ra4 Cc3
6. Rb3 Ca4  7. Txa4 matto.
:-)
Ciao,
Carmelo
-- 
Posted from [209.176.20.87] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

Scusa potresti salvare la "situazione" in pgn?
Vorrei provare con Mephisto
Grazie
ciao



GRANDE! E cosi' ho capito dove sta' il problema!
Nimzo 8 da la possibilita' di configurare molti parametri
tra i quali un "Bonus Nullmove" che come impostazione predefinita
e' a "0" (quindi, penso che le nullmove siano disabilitate).
Inoltre Nimzo 8 ha come impostazione predefinita una "Selective Heuristic".
Rebel Century 3 risolve la posizione in 1 secondo!
Fantastico!
Visto che sicuramente puo' interessare anche altri frequentatori di IHS,
mi spiegheresti meglio (in sintesi, ovviamente!) che cos'e' una "nullmove"
e come viene usata dai programmi??
Saluti
Ivo

Vorrei provare con Mephisto
Nel mio primo post c'e' gia' il PGN, basta solo che lo copi,
lo incolli in un file salvandolo come solo testo con estensione *.PGN!!!
Saluti
Ivo
P.S. Comunque, rieccolo:
[Event "?"]
[Site "?"]
[Date "1954.??.??"]
[Round "?"]
[White "Speckmann"]
[Black "#7"]
[Result "1-0"]
[SetUp "1"]
[FEN "8/1K6/8/3R4/8/6p1/np1pppp1/krbrqrrn w - - 0 1"]



Sono convintissimo che i programmi di scacchi siano stupidi, ma per un problema di matto in 7 mosse con poche alternative per il Nero è sufficiente analizzare
tutte_le_mosse a profondità 13-14 per trovare la soluzione.
Sono altresì convinto che i programmi specializzati in matti (scacchistici!), trovino la soluzione immediatamente.
Infatti il mio più che modesto programma trova la soluzione Td8 in 61 s se inizia ad analizzare partendo dalle mosse del Re bianco, e in 27 s se inizia dalla Torre.
Quindi complimenti vivissimi a "Ciccio" ed al suo "Leila" che trova la soluzione in 2 secondi (vedasi il suo messaggio in questo stesso thread)!!! Sarebbe
interessante che provasse con molti matti differenti ad es. quelli presenti sul Chicco e Porreca con cui verificavo il mio programma (nella mia III Edizione sono a
pag. 133-136 ed altri a pag. 543-544).
In effetti il problema in questione richiede tempi dell'ordine dei millisecondi per la sua soluzione se il Bianco scegliesse sempre la mossa giusta come prima mossa
da analizzare in quanto le alternative del Nero che devono_essere_tutte_esplorate sono pochissime, in media poco più di 2, e quindi le mosse da esaminare sono
dell'ordine del centinaio, o al massimo migliaio.
La difficoltà nel caso dei problemi di matto, soprattutto per quelli molto artefatti come questo, è di "vedere" la mossa giusta del Bianco come più conveniente,
mentre lo sforzo dei progettisti di problemi è quello di fare in modo che la mossa giusta sia quella apparentemente più illogica e meno vantaggiosa. Per questo
motivo nel mio programma che studia i matti, sempre quelli scacchistici, non metto  un criterio di ordinamento delle mosse, se non la possibilità di eseguire, per
quanto riguarda la prima mossa, prima le mosse di un pezzo piuttosto che di un altro.
Questo spiega benissimo perché programmi anche forti possano non trovare la soluzione. Tali programmi, proprio per la ragione esposta, devono essere utilizzati con
opzioni differenti, in modo da favorire per qualche particolare motivo anche le mosse poco logiche, che poi si rivelano come le vincenti.
Ciao
Guido
Per Ivo (ed altri eventualmente interessati): hai  provato i miei programmi per giocare i finali a 3 e 4 pezzi, che ora sono disponibili sotto Windows 95/98, al
sito 
http://users.iol.it/rigel_g/
 ?
-- 
Posted from 
smtp3.libero.it
 [193.70.192.53] 



Li ho scaricati ma non ancora provati... (segue alla prossima puntata!!!).
Ciao
Ivo

 e come viene usata dai programmi??
Certo, con piacere... sperando di riuscirci, a sintetizzare! :-)
Ricordo cmq a chiunque interessi approfondire argomenti correlati
con la programmazione scacchistica, che in Italia esiste la mailing
list del G_6 (stiamo mettendo su anche un sito; 
http://www.gsei.org
).
Ok, vediamo se mi riesce di sintetizzare in maniera chiara il concetto
di null move; prima pero' credo sia utile una breve introduzione
riguardo all'algoritmo alpha-beta.
Chi frequenta il newsgroup dovrebbe avere un'idea di come funzionano
i programmi di scacchi; cmq, in sintesi tutto si basa sull'analisi
esaustiva delle varianti possibili fino ad una certa profondita', e
sulla valutazione delle posizioni che ne scaturiscono.
Data la crescita esponenziale dell'albero delle varianti, e' pero'
fondamentale "potare" il piu' possibile i rami di tale albero, una
volta stabilito che non sono "promettenti". Ad esempio, se vedo che
una data mossa lascia la Donna in presa, non e' necessario che
analizzi tutte le possibili risposte dell'avversario: basta
analizzare la presa della Donna per scartare l'intera variante.
Questa e' l'idea di base su cui si basa l'algoritmo alpha-beta, che
effettua una "potatura" (pruning) dell'albero in maniera
matematicamente "sicura", cioe' elimina soltanto rami che e'
_certamente_ inutile analizzare per stabilire qual e' migliore mossa
da giocare nella posizione di partenza.
In pratica, visitare tutto l'albero o visitare solo i rami non potati
da alpha-beta porta sicuramente allo stesso risultato; quindi usare
alpha-beta porta ad un guadagno nelle prestazioni, senza perdita di
precisione rispetto alla ricerca esaustiva (minimax).
 
Purtuttavia nonostante alpha-beta la crescita dell'albero resta
esponenziale; e' per questo che tutti i principali programmi, sia
commerciali che amatoriali, adottano anche altre tecniche di pruning
le quali, pero', non sono matematicamente "sicure": migliorano le
prestazioni _globali_, ma possono cadere in fallo (e quindi peggiorare
il gioco del programma) in qualche caso particolare.
Le null moves fanno parte di questo gruppo: se il pruning basato su
null moves e' ben tarato (cioe', ne' troppo blando ne' troppo
aggressivo), le prestazioni medie migliorano sensibilmente (a parita'
di tempo il programma e' in grado di analizzare almeno una semimossa
in piu'); pero' si perde qualcosa in termini di precisione tattica, e
in posizioni particolari il programma puo' sbagliare completamente
strada.
L'idea di base e' la seguente. In alpha-beta, come accennato in
precedenza, e' importante non tanto dare una valutazione _precisa_ ad
una determinata variante, quanto stabilire se tale variante e' da
analizzare o puo' essere scartata senza timori, perche' troppo
favorevole ad uno dei due colori (e quindi verrebbe sicuramente evitata
dall'altro). In pratica in ogni posizione ci sono due limiti (bounds),
alpha e beta (alpha<beta): se c'e' una mossa che ha una valutazione
superiore a beta, allora la linea puo' essere scartata ed e' inutile
analizzare tutte le altre mosse.
Nella null move heuristic, si da' per scontato che muovendo si puo'
solo migliorare la propria posizione. Cioe', se la valutazione della
posizione e' maggiore di beta anche quando io "passo", cioe' permetto
all'avversario di muovere due volte di seguito, allora e' ragionevole
supporre che esistera' una mossa che causa il pruning: se non muovendo
affatto sto gia' molto meglio, figuriamoci se muovo! 
Allora supponiamo di dover analizzare una determinata posizione, con
mossa al Bianco, fino a profondita' (per es.) pari a 7 e con limiti
alpha = 7, beta = 220.
Prima di considerare le varie mosse possibili, provo a vedere che
succede se non muovo affatto: faccio una mossa "nulla", e analizzo la
posizione corrispondente a profondita' 7-1-R (perche' 7-1-R lo vedremo
fra breve). Se ottengo un risultato >= 220, la null move ha avuto
successo e taglio interamente il ramo; altrimenti ho solo perso tempo
e procedo all'analisi consueta.
Qual e' il vantaggio di una cosa del genere?! Il vantaggio sta nel fatto
che la posizione dopo la null move non la analizzo fino a profondita' 6
(cioe' il 7 iniziale, meno l'1 della mossa - in questo caso nulla - che
ho giocato), bensi' a profondita' 6-R, dove R e' il fattore di riduzione
che introduco fidandomi del fatto che, non avendo giocato alcuna mossa,
ho sicuramente alternative migliori a disposizione.
Chiarisco meglio: per analizzare a prof. 7, devo giocare una per una
tutte le mosse possibili, analizzare fino a profondita' 6 le posizioni
risultanti, e scegliere il risultato migliore.
Se pero' gioco una null move, analizzo la posizione risultante a
profondita' 3 o 4, fidandomi del fatto che lo svantaggio di aver
permesso all'avversario di muovere due volte di seguito compensi
l'imprecisione di un'analisi a profondita' piu' bassa.
Ora, perche' tutto questo funziona? Sostanzialmente perche' i computer
non analizzano come gli umani. Di tutte le posizioni considerate, la
stragrande maggioranza e' pura spazzatura: linee in cui un colore lascia
in presa due o tre pezzi di seguito senza alcun motivo sono comunissime;
e riconoscere il piu' presto possibile (e nel modo piu' economico
possibile) che tali linee possono essere tagliate senza problemi e'
fondamentale.
In media, la null move ha successo (cioe' permette la potatura) in
oltre il 70% dei tentativi; e in tal caso la riduzione di profondita'
effettiva dopo la null move (pari a 2 o 3 ply rispetto alla profondita'
nominale di ricerca) permette di impiegare un decimo o anche un
centesimo del tempo che sarebbe stato necessario senza null move, per
accorgersi che il ramo puo' essere potato.
Facendo due conti, se per l'analisi di 100 date posizione impieghiamo
N secondi ciascuna senza null moves, con le null moves nel caso peggiore
avremo: in 70 posizioni la null move avra' successo, e quindi ce la
caveremo in un decimo del tempo N; nelle restanti trenta posizioni,
avremo sprecato 1/10 del tempo (al massimo! in realta' di solito ci
vuole molto, mooolto meno per accorgersi che la null move fallisce) e
quindi impiegheremo 11*N/10 secondi.
Totale:
(senza null moves)   100*N
(con le null moves)  70*N/10 + 30*11*N/10 = 40*N
Con le null moves ci vuole meno della meta' del tempo, anche
considerando il caso peggiore! In realta' in media guadagni di 5 volte
o piu' sono tutt'altro che rari; per cui l'uso delle null moves consente
effettivamente di guadagnare un ply o anche due in profondita' di
ricerca.
Vediamo ad esempio come si comporta Leila, dopo 1. e4 e5
2. d4 d5. Senza null moves, si ha:
Depth Score    Time    Nodes   PV
--------------------------------------  
  1    0.35    0.09       67   g1f3
  2    0.12    0.10      748   d4e5 d5e4 d1d8
  3    0.35    0.16     2750   e4d5 d8d5 g1f3
  4    0.12    0.32    12136   d4e5 d5e4 d1d8 e8d8
  5    0.47    1.04    55109   d4e5 d5e4 d1d8 e8d8 b1c3
  6    0.12    3.29   189170   d4e5 d5e4 d1d8 e8d8 b1c3 b8c6
  7    0.42   16.24  1004498   d4e5 d5e4 d1d8 e8d8 b1c3 b8c6 g1e2
  8    0.12   54.48  3359763   d4e5 d5e4 d1d8 e8d8 b1c3 b8c6 g1e2 g8e7
Dopo 55 secondi circa, il programma e' arrivato a prof. 8 valutando
3.359.793 posizioni. Vediamo ora che succede con le null moves
abilitate:
Depth Score    Time    Nodes   PV
--------------------------------------  
  1    0.35    0.09       67   g1f3
  2    0.12    0.10      748   d4e5 d5e4 d1d8
  3    0.35    0.14     2401   e4d5 d8d5 g1f3
  4    0.05    0.31    11800   f1b5 c7c6 e4d5
  5    0.47    0.70    33870   d4e5 d5e4 d1d8 e8d8 b1c3
  6    0.12    1.88   101004   d4e5 d5e4 d1d8 e8d8 b1c3 b8c6
  7    0.42    3.38   182842   d4e5 d5e4 d1d8 e8d8 b1c3 b8c6 g1e2
  8    0.12   10.36   591001   d4e5 d5e4 d1d8 e8d8 b1c3 b8c6 g1e2 g8e7
  9    0.50   18.14  1039760   d4e5 d5e4 d1d8 e8d8 b1c3 c8f5 c1e3
  10   0.25   58.95  3442480   d4e5 d5e4 d1d8 e8d8 b1c3 c8f5 c1f4 b8c6
                               f1c4 d8e8
Null moves tentate: 172.078; percentuale di successo 70%.
Quindi, per arrivare a profondita' 8, stavolta il programma ha impiegato
poco piu' di 10 secondi e analizzato meno di 600.000 nodi: quasi sei
volte meno! Casualmente lo score e la PV sono gli stessi del caso
precedente; ma questo non sempre succede in quanto le null moves
influenzano comunque la valutazione - anche se sarebbe meglio se non
lo facessero! ;-)
Inoltre, dopo circa un minuto il programma ha completato l'analisi fino
a profondita' 10: cioe' usando piu' o meno lo stesso tempo e visitando
all'incirca lo stesso numero di nodi, la versione con le null moves
abilitate e' riuscita ad analizzare 2 ply (semimosse) in piu'! Questo
compensa piu' che abbondantemente gli svantaggi intrinseci nell'uso di
null moves.
Ma quali sono questi svantaggi?! Innanzitutto, la riduzione della
profondita' di ricerca dopo la null move e' quasi sempre giustificata,
ma talvolta puo' portare ad errori tattici; ad esempio combinazioni con
sacrificio molto profonde possono richiedere vari ply in piu' per poter
essere viste, e quindi il programma puo' non avere tempo a sufficienza
per accorgersene.
E poi, l'ipotesi che "se non muovendo vinco, allora muovendo vinco
ancora piu' facilmente" cade evidentemente in fallo almeno in un caso
fondamentale e ben noto: quando c'e' di mezzo lo zugzwang! E' per
questo che tutti i programmi che usano le null moves le disabilitano
quando sono rimasti pochi pezzi sulla scacchiera, dato che in tal caso
la probabilita' di incappare nello zugzwang e' molto alta; ma cio' non
toglie che in posizioni particolari, come quella da te postata, il
problema possa presentarsi anche con ancora molti pezzi sulla
scacchiera.
Li' infatti il Nero ha ancora tutti i pezzi, per cui la null move non
viene disabilitata; ciononostante non ha mosse disponibili! Se potesse
realmente non muovere, non ci sarebbe alcun matto; mentre se e'
costretto a muovere il matto c'e'... ma usando le null moves non ce ne
si puo' accorgere! 
:-)
Fortunatamente pero' posizioni "null-move killers" capitano assai
raramente in partita viva, e questo riduce notevolmente l'incidenza
del problema sulle performance dei programmi.
Ciao,
Carmelo
-- 
Posted from [209.176.20.87] 


 ha scritto nel messaggio
news:3a24ed2d...@news.tin.it...


 > [FEN "8/1K6/8/3R4/8/6p1/np1pppp1/krbrqrrn w - - 0 1"]
Posizioni chiuse ??????
...uso un poco azzardato di un banale luogo comune...
In realta' credo che la cosa si possa spiegare come uno degli
effetti collaterali di un algoritmo (l'algoritmo "null-move")
ampiamente utulizzato in molti dei sw scacchistici.
Senza scendere nei dettagli, l'algoritmo null-move prevede
di esplorare l'albero di ricerca delle varianti consentendo
ad uno dei colori di eseguire due mosse consecutive (o meglio
facendo eseguire all'altro colore delle mosse "nulle").
Questo, nella stragrande maggioranza delle posizioni consente di
tagliare rapidamente molti "rami secchi" dell'albero delle varianti.
Purtroppo il difetto e' che l'algoritmo null-move "nasconde" alcune
manovre vincenti basate sullo zugzwang, in altre parole, nella posizione
critica dove il nero gioca e perde il programma "pensa" che il nero
se la possa cavare semplicemente giocando la mossa "nulla"...
Vi sono un sacco di posizioni in cui questo effetto si manifesta,
ma sono quasi tutte posizioni artificiali quanto mai lontane dal
gioco reale e quindi i programmatori non se ne occupano piu' di tanto.
Sent via Deja.com
http://www.deja.com/