Newsgroup: it.hobby.scacchi
Titolo: Ancora sui finali con 3-6 pezzi

Ho sentito Guido Antonelli, autore delle GAFS, utility + tabelle di finali
(per maggiori informazioni, 
www.gsei.org
, poi sezione progetti) e ha
chiarito molti aspetti della discussione avvenuta sul newsgroup negli ultimi
giorni... per problemi tecnici con il newsgroup ha chiesto a me di mandare
le sue considerazioni sul newsgroup.
Ciao a tutti
----->
Non so bene da che parte cominciare dopo tutto ciò che è stato scritto nei
giorni scorsi sull'argomento.
Devo confessare di aver letto un grande numero di informazioni che almeno
IMHO non sono del tutto corrette.
Innanzitutto riguardo a questo punto scritto da Ivo:
" <cut>
Nel corso delle analisi, Nunn ha riscontrato anche curiosità interessanti,
ad esempio: la posizione della vittoria più lunga nel finale R+D+A contro
R+D+C, che è la seguente (ASCII):
wKd6,Qc7,Bh5/bKf7,Qa1,Nb1
in realtà è illegale (il Re nero è sotto scacco di due pezzi!).
Questo perché le analisi delle tablebase vengono ricostruite a ritroso
dalle posizioni terminali e quindi non sono in grado di determinare se una
posizione
sia illegale per motivi retroanalitici!
"
La posizione è chiaramente illegale, ma la spiegazione IMHO non c'entra.
Prima del calcolo vero e proprio io, e forse anche Nalimov e Thompson,
faccio una passata di tutte le posizioni per stabilire quelle illegali e
quindi controllo tutti gli scacchi doppi, tripli, ecc..
Nel mio programma ho inoltre aggiunto a questi controlli la possibilità
opzionale di verificare la legalità di una posizione eseguendo UNA mossa
retrograda, per cui elimino ulteriori posizioni che apparentemente
sembrerebbero lecite (Es. B:Ra1, Pa2; N:Rb3 e mossa al Nero). Questo costa
qualcosa inizialmente, ma riduce le posizioni da calcolare e quindi il
successivo tempo di calcolo vero e proprio. Nalimov, col quale ebbi uno
scambio di e-mail, fa un controllo molto più blando per non complicare
troppo il programma e mantiene anche posizioni duplicate per simmetria.
Comunque anche il controllo con mossa retrograda non è matematicamente
sicuro e vi sono alcune posizioni illegali, soprattutto con pedoni, non
rilevabili neppure in questo modo, in quanto per avere la certezza
matematica bisognerebbe poter tornare indietro attraverso una sequenza
retrograda di mosse legali fino a una posizione sicuramente legale, al
limite alla posizione iniziale!
Le posizioni illegali non causano tuttavia problemi perché non saranno mai
interrogate in una partita regolare e non possono mai trovarsi in un
percorso che inizi da una posizione legale, mentre possono ricollegarsi con
una mossa ordinaria, cioè in avanti, a posizioni legali.
Spero di non essere stato troppo confuso....
SIMMETRIE: se il finale è costituito da soli pezzi allora esistono in
generale 8 posizioni equivalenti per simmetria e quindi sette operatori che
trasformano una posizione in un'altra equivalente oltre ad un operatore
identità, che come è noto non fa nulla.
Le 7 trasformazioni si hanno per: simmetria orizzontale, verticale,
simmetria rispetto alla diagonale principale (a1-h8) e a quella secondaria
(h1-a8), rotazione di 90, rotazione di 180 e rotazione di 270 (ovvero  -90).
Se vi sono pedoni si hanno invece due sole posizioni equivalenti ottenibili
l'una dall'altra per simmetria rispetto ad un asse verticale. (Nota per i
cultori della dama: vi sono 4 posizioni equivalenti con sole dame e nessuna
simmetria in presenza di pedine).
Questo spiega perché i finali con pedoni occupano in genere più spazio.
Infatti nel caso di soli pezzi i due Re si dispongono in 462 posizioni,
mentre nei finali con pedoni in ben 1806 posizioni diverse. E' peraltro vero
che aggiungendo un pedone si moltiplica per (48-N.pedoni già presenti),
mentre aggiungendo un pezzo per (64-2 (i Re)-N.di altri pezzi e pedoni già
presenti).
Vorrei però sottolineare che nella generazione di finali  con pedoni si ha
la massima occupazione di RAM in quanto bisogna tenere in memoria anche
tutte le tabelle ottenibili per promozione, che sono di dimensioni notevoli
perché contengono lo stesso numero di pezzi, mentre questo non succede
quando non vi sono pedoni perché le tabelle aggiuntive necessarie sono
quelle ottenibili per cattura che sono molto più piccole perché contengono
un pezzo in meno.
I NUMERI di finali differenti  e le loro OCCUPAZIONI in funzione dei pezzi,
IMHO ovviamente e per i miei finali, sono:
N. pezzi       N. finali       Occupazione in Mb
   2              1                      ---
   3              5                     0.275  (rar e rcr non esistono)
   4             30                   152.333
   5            110                31 865.260
   6            365             5 150 003.501
   7           1001           611 686 390.198
   8           2520            non calcolato
   9           5720                   "
  10          12190                   "
  11          24310                   "
  12          46252                   "
Quindi il numero corretto di finali a 6 pezzi per me è 365, che si avvicina
ma non coincide con il valore di 360 riportato da Claudio.
Naturalmente il numero dei pezzi comprende i 2 Re ed i valori più alti della
seconda colonna non tengono conto delle regole degli scacchi che
impedirebbero di avere ad es. 10 pedoni di un colore.
Il calcolo del numero dei finali l'ho ottenuto con una tabella su Excel ed
il valore è stato  confermato dal programmino con cui ho calcolato
l'occupazione di memoria.
Le tabelle inoltre devono essere raddoppiate di numero per tenere conto del
giocatore che muove, anche se questo raddoppio potrebbe essere evitato per
tabelle simmetriche (es rprp, rdarda, ecc.) in quanto in questi casi una
sola tabella sarebbe sufficiente.
Piccola osservazione: il raddoppio delle tabelle non sarebbe strettamente
necessario per l'utilizzo delle tabelle (in questo caso però aumentano
enormemente il tempo e le complicazioni), ma è fondamentale per la loro
generazione.
Detto questo passiamo al problema delle dimensioni complessive di queste
tabelle.
Le occupazioni sopra riportate tengono conto del raddoppio delle tabelle,
comprese quelle simmetriche, e sono dati per tabelle non compresse. Vi
sarebbe da aumentare qualcosa per tener conto della cattura en passant per
quei finali che hanno pedoni da entrambe le parti.
IMHO la prima fondamentale precisazione è quella di stabilire se i valori di
occupazione di cui si è parlato nel thread si riferiscano a tabelle
compresse o non compresse.
Dai dati da me riportati credo che non vi siano dubbi che il valore di 1 Tb
per le tabelle a 6 pezzi si riferisca a tabelle compresse.
A questo punto mi sembra difficile prevedere a priori i fattori di
compressione di ogni tabella e quindi un valore medio attendibile, tenendo
conto che tali fattori possono essere diversissimi da tabella a tabella in
funzione della casualità con cui si succedono i dati. Se tutti i risultati
fossero patte e quindi i byte fossero tutti uguali il file compresso si
ridurrebbe a pochi byte, se invece i risultati si succedessero con perfetta
casualità la compressione non servirebbe a niente. Questo spiega la
fortissima differenza di dimensioni dei finali già calcolati sul sito di
Hyatt.
Quindi, se ci riferiamo ai finali compressi, è possibile solo sapere a
posteriori quale è la loro occupazione, mentre se ci riferiamo ai finali non
compressi, il calcolo della loro dimensione è quello sopra riportato..
OT: Nel fare il programmino di cui sopra ho scoperto che i caratteri '*' e
'?'  non possono essere messi da soli nella linea di comando almeno sotto
Linux.
Esempio: per calcolare le tabelle a 6 pezzi volevo scrivere:     calcmem
??????
in modo da dare ad ogni  '?'  il valore di qualsiasi pezzo. Ebbene non
funziona (:-( ) e ho dovuto utilizzare 'x' al posto di '?'.
Il calcolo da me fatto non coinciderebbe comunque con il calcolo che si
potrebbe fare con le tabelle di Nalimov, perché queste ultime sono in genere
più piccole di una certa percentuale in quanto usano un algoritmo di
indicizzazione diverso dal mio.
Un ulteriore considerazione è che per molti finali a 6 pezzi saranno
necessari più di 8 bit per posizione e mi pare che Nalimov abbia scelto di
passare per questi finali da 8 bit a 16 bit.  Quindi le dimensioni non
compresse raddoppiano, ma nel caso di compressione ciò potrebbe non accadere
poiché vi sono molti zeri in posizione fissa (non sono comunque un esperto
di compressioni).
Da quello che ho capito la compressione usata da Nalimov è realizzata in
blocchi indipendenti in modo tale da poter decomprimere un blocco, una volta
trasferito in RAM, senza dover decomprimere l'intero finale. Ho però qualche
perplessità su questa strategia, che ha il solo vantaggio per l'utente di
mantenere le tabelle in uno spazio ridotto su disco, mentre potrebbe essere
penalizzante per il tempo di cpu richiesto alla decompressione, perché se i
blocchi sono piccoli (ho letto 8 kb ?) è facile che ogni volta si debba
leggere da disco e decomprimere un nuovo blocco prima di ottenere la
risposta cercata.
Se qualcuno ha fatto delle prove con le tabelle di Nalimov  compresse,
sarebbe interessante conoscerne i risultati.
Vorrei infine far presente che con l'ultima versione del mio programma sarei
anch'io in grado di generare tutti finali a 6 pezzi ed anche finali
interessanti a 7 pezzi con le RAM attuali. Per questi ultimi avevo pensato a
rdttrdd e rtaartt (finali in genere molto combattuti!) che non compressi
occupano solo, si fa per dire, 89 GB per tabella.
Dovrei però trovare un Bob Hyatt o una Bell che mi metta a disposizione
computers a 64 bit. Sfruttando un'elaborazione a blocchi, quello che serve
per il calcolo è soprattutto un disco molto capiente; per i finali citati ci
vorrebbero almeno 400 Gb (4* 89 + spiccioli) e sia la cpu che l'I/O devono
essere estremamente veloci (col mio 600Mhz per una delle citate tabelle a 7
pezzi ci vorrebbero parecchi decenni di tempo). Se c'è qualche Bob o qualche
Bell disponibile,  si faccia avanti ...
Ricordo ancora a chi non ne fosse a conoscenza che nel mio sito
http://users.iol.it/rigel_g/
 vi è il programma per generare le tabelle dei
finali, interrogarle e fare su di esse altre operazioni come un'estrazione
per risultato semplice e per risultato combinato con mossa al B e al N
(trebuchet secondo Ivo). Ho aggiunto anche una libreria in formato obj per
poterle usare in modo semplice in un proprio programma (vi è anche un
esempio d'uso). Le tabelle generabili sono limitate ai finali a 5 pezzi
(rpprp escluso), e utilizzano interamente la RAM e non il disco come
l'ultima versione di cui ho prima parlato, per cui  512 Mb NON sono
sufficienti a generare le tabelle più complesse a 5 pezzi con pedoni.
Sperando che la soluzione che ho in mente sia esatta, termino con un
problemino per Ivo ed altri volonterosi:
Nel calcolo del finale RDCR con mossa al Nero questa posizione di doppio
scacco deve essere considerata, oppure scartata perché illegale?
Bianco: Rc2, Dh3,Ch2
Nero: Rf1
Ciao
Guido


Innanzitutto GRAZIE per le spiegazioni, veramente esaurienti!
Vorrei che vivessi negli Stati Uniti, cosi' forse troveresti qualche
istituzione che potrebbe offrirti l'hardware necessario per portare
avanti il tuo progetto sui finali...
La posizione riportata sopra mi sembra illegale, visto che il Re
è sotto doppio scacco... ma forse tu hai qualcosa in mente, vero?
Pero' mi sfugge :-(
Saluti
Ivo

   12          46252                   "
Noto che con questi numeri il fattore di moltiplicazione dello spazio in Mb
all'aumentare dei pezzi tende a calare (cosa che mi lascia molto
perplesso...)
Da 4 a 5 fattore 209
Da 5 a 6 fattore 161
Da 6 a 7 fattore 118
Come ho già scritto in un post precedente secondo me queste stime di
occupazione di memoria sono molto difficili da fare se non dopo aver risolto
tutti i finali con un certo numero di pezzi...
Luigi Caselli

 Nero: Rf1
La posizione deve essere considerata, perché ruotata di 90° in senso
antiorario deriva dalla posizione legale dove il Cavallo bianco è appena
nato da un pedone promosso, con scacco doppio di Cavallo e di Donna di
scoperta.
Alex



Posto qui di seguito la replica di Guido (inviatami tramite E-mail),
visto che lui in questi giorni non puo' accedere a IHS!
La "soluzione" al quesito era già stata anticipata da Alex
in una altro post di questo thread!
**********
Beh, chiaramente vi è sotto qualcosa ...
Se ruoti la posizione di 90 gradi in senso antiorario ottieni:
Bianco: Rg3, Df8,Cg8
Nero: Rh6
Questa posizione è legale perché la mossa precedente era stata Pg7-g8C
con scacco doppio di scoperta.
Per lo stesso motivo sarebbe parimenti legale la posizione ottenibile da
quella iniziale per simmetria rispetto alla diagonale a1-h8.
Di conseguenza nel calcolo di questo finale la posizione indicata nel
problema, che è l'unica presente nel file perché contiene il Re bianco
nel triangolo a1-d1-d4, anche se di per sé illegale, deve venire
ugualmente calcolata altrimenti utilizzando le tabelle mancherebbe la
risposta per le due situazioni legali ad essa riconducibili per
simmetria.
Ciao
Guido

 ma non coincide con il valore di 360 riportato da Claudio.
Vorrei dissipare ogni possibile dubbio su questo valore calcolandolo con
precisione scientifica :)
Situazione 4-0.
Abbiamo 5 possibilità:
- 4 pezzi uguali. Ci sono 5 combinazioni, naturalmente.
- 3 pezzi uguali e un pezzo diverso. Ci sono sempre 5 combinazioni per i 3
pezzi uguali; per ciascuna di esse il pezzo diverso può essere scelto fra i
rimanenti 4. Totale 5x4=20.
- 2 pezzi uguali e 2 diversi. Ancora 5 possibili tipi di pezzi uguali; i 2
pezzi diversi sono le combinazioni dei restanti 4 pezzi presi a due per
volta e senza ripetizioni, quindi 4x3/2=6 (ab,ac,ad,bc,bd,cd). Totale
5x6=30.
- 2 pezzi uguali e 2 pezzi uguali, ma diversi dai primi due. Ancora 5 per la
prima coppia, moltiplicata per i 4 possibili rimanenti tipi, cioè 20.
- 4 pezzi differenti. Qui ci sono 5 combinazioni (quella senza la Donna,
quella senza la Torre, eccetera).
Il totale è 5+20+30+20+5=80.
Situazione 3-1.
Per i tre pezzi, le possibilità sono 3:
- 3 pezzi uguali. 5 possibilità.
- 2 pezzi uguali e uno differente. Ci sono sempre 5 combinazioni per i 2
pezzi uguali; per ciascuna di esse il pezzo diverso può essere scelto fra i
rimanenti 4. Totale 5x4=20.
- 3 pezzi differenti. Sono le combinazioni di 5 pezzi presi a tre per volta
e senza ripetizioni, quindi 5x4x3/3/2=10
(DTA,DTC,DTP,DAC,DAP,DCP,TAC,TAP,TCP,ACP).
Il totale, 5+20+10=35, va moltiplicato per le 5 possibilità che può avere il
pezzo dell'avversario, quindi 35x5=175.
Situazione 2-2.
Qui consideriamo la situazione dei due giocatori, e abbiamo 3 casi:
- Ciascuno ha una coppia di pezzi uguali. Servono le combinazioni di 5 pezzi
a presi a due a due (5x4/2=10) più le combinazioni ripetute (5), totale 15
(DT,DA,DC,DP,TA,TC,TP,AC,AP,CP,DD,TT,AA,CC,PP - DT è inteso 2 donne contro 2
torri, e così via).
- Un partito ha 2 pezzi uguali, l'altro 2 pezzi diversi. Le combinazioni dei
pezzi uguali sono 5, da moltiplicare per quelle di due pezzi diversi, che
sono 5x4/2=10, totale 5*10=50.
- Entrambi hanno 2 pezzi differenti. Le possibilità sono 10 per ciascuna
parte, quindi senza ripetizioni abbiamo 10x9/2=45 combinazioni.
In complesso, 15+50+45=110.
Il numero totale dei finali è perciò pari a 80+175+110=365, come
correttamente indicato da Guido.
Alex

 correttamente indicato da Guido.
Esatto, ma i contributi sono 70,175,120. :)
ciao,
Claudio

 Esatto, ma i contributi sono 70,175,120. :)
Giusto, mi sono sfuggiti questi due particolari; il caso ha voluto che i due
errori si compensassero :)
Alex