Newsgroup: it.hobby.scacchi
Titolo: Le posizioni in cui possono disporsi 2 Re e altro


Mi spiace dover smentire quanto ha postato Ivo nel messaggio "Scacchi e
matematica" ma le posizioni distinte occupabili da 2 Re sulla scacchiera
sono solamente 462 per la fortuna di chi si occupa di tabelle dei finali.

Tutte le altre sono illegali oppure sono equivalenti per simmetria.


Il calcolo va fatto in questo modo:


     Posizioni        
No. Posiz.


     Re bianco         
Re nero


       a1       
1  *     33     =   
33       angolo


     b1,c1,d1    3  *    
58     =   174      
bordi


     c2,d2,d3    3  *    
55     =   165      
posizioni interne


     b2,c3,d4    3  *    
30     =    90      
diagonale


                                   
----


                        
Totale      462


 

Nota
: Il valore 462 vale solo quando il finale non contiene
pedoni. In quest'ultimo caso, poiché esiste la sola simmetria rispetto
ad un asse centrale verticale, le posizioni dei 2 Re sono:


     Posizioni        
No. Posiz.


     Re bianco         
Re nero


       a1,a8    
2  *     60     =  
120       angoli


     b1,c1,...  12  *    
58     =   696      
bordi


     b2,c2,...  18  *    
55     =   990      
posizioni interne


                                   
----


                        
Totale     1806


 

Riguardo al problema del numero di disposizioni legali nel gioco degli
scacchi esiste un solo modo per calcolarle esattamente:


CONTARLE!!!!!!


(vedasi anche mio  "Re: Numero di mosse possibili in una partita
a scacchi",  Fri, 10 Dec 1999)


Per i programmatori interessati il procedimento è il seguente:


Disponendo di un generatore di mosse con controllo della loro legalità,
impostatelo con profondità di analisi infinita (1000000 è
più che sufficiente!) partendo dalla posizione iniziale, che avrete
in precedenza salvato insieme alle informazioni aggiuntive (mossa al Bianco,
diritti d'arrocco), come primo elemento di una mastodontica tabella, che
vi siete allocati in memoria


Ad ogni mossa eseguita aggiungete nella tabella la nuova disposizioni
dei pezzi con le informazioni aggiuntive (vi è anche il pedone catturabile
en-passant) dopo aver verificato che tale posizione non sia già
presente nella tabella. Questo implica che se volete usare l'algoritmo
di ricerca binomiale dovrete mantenere la tabella delle disposizioni ordinata
in qualche modo durante la sua costruzione.


Se la posizione è già presente in tabella, fate il "pruning",
cioè non salvate la posizione duplicata e tagliate il ramo sottostante
perché tutte le mosse successive sono state già salvate.


Nota
: se voleste considerare solo le disposizioni che si hanno
con la composizione iniziale dei pezzi, nella ricerca mosse "prunate" tutte
le mosse di cattura e promozione.


Anche se la profondità di analisi è infinita, il procedimento
è finito. Prevedo tuttavia che la vostra tabella mastodontica si
riempirà in brevissimo tempo e sarete solo a qualche miliardesimo
di miliardesimo di miliardesimo ... del vostro lavoro!  Per divertirsi
si può impostare una bassa profondità di analisi e iniziare
a costruire un diagramma con il numero di disposizioni in funzione della
profondità di analisi. Non sperate comunque di poter estrapolare!


Questo procedimento io l'ho comunque già realizzato per la dama
contando le possibili disposizioni delle 24 pedine iniziali: sono solo
9.697.698, non una di più non una di meno, alla faccia del calcolo
combinatorio per il quale peraltro ho molta stima e qualche rudimento.
Al posto della profondità infinita, in questo caso è sufficiente
usare il valore 65.


Purtroppo per gli scacchi le disposizioni possibili dei soli pezzi iniziali
sono un numero molto superiore sia per il maggior numero di pezzi e di
caselle disponibili che per la mancanza dell'obbligo di cattura.


Tutti gli altri metodi di conteggio sono approssimati, anche se la valutazione
più accreditata delle disposizioni legali degli scacchi dovrebbe
essere dell'ordine di 10^43.


Ciao

Guido

 



--------------------------------------------
Cancella "BIT" dopo @ per inviarmi un'e-mail
Delete "BIT" after @ to send me an e-mail
--------------------------------------------

 dei pezzi sulla scacchiera orientata, per puro diletto matematico, non per costruire tablebases.
Mi sembra un discorso "opinabile" nel senso che possiamo aver entrambi torto o ragione a seconda dei punti di vista.
In altre parole, anche prescindendo dal problema delle tabelle dei finali, per le quali ridurre a metà  o a circa un ottavo le posizioni è fondamentale per motivi
di spazio di memoria e tempi di CPU,  il problema può porsi in termini generali:
Due disposizioni dei pezzi perfettamente simmetriche ed equivalenti ai fini del gioco vanno conteggiate per una o come due disposizioni differenti?
Astrattamente sono due, ma credo che la maggior parte dei programmatori propendano per la mia tesi. Resta il fatto che questa riduzione per simmetria pesa molto nel
calcolo delle tabelle dei finali, mentre per le hash table ad esempio il gioco IMHO non vale la candela.
Proprio riguardo alle posizioni occupate dai 2 Re sulla scacchiera, tempo fa avevo inviato le stesse considerazioni a CCC, e nessuno aveva mosso obiezioni ... :-).
Comunque come ti dicevo entrambe lo opinioni sono rispettabili, si tratta solo di essere d'accordo sui termini del problema proposto da Ivo.
Ciao
Guido
--
Posted from 
smtp3.libero.it
 [193.70.192.53] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

Chiaro, se parliamo di programmazione, certi finali (senza pedoni,promozioni&GrandiSconti...:))
possono considerarsi simmetrici. Tale semplificazione del resto è implicita nel ragionamento dello
scacchista che si trova ad applicare i principi dei finali di soli pezzi.
Aaaaah sti informatici avversi alle prolissità :) 
In Fede,
Emilio


--------------------------------------------
