Newsgroup: it.hobby.scacchi
Titolo: Per i programmatori: Rappresentazione binaria di posizioni negli scacchi

Premetto di avere dei dubbi nell'inviare questa e-mail perché non so a
quanti interessano argomenti così specifici, tuttavia ci provo
considerando che si può sempre non leggere :-).
Per coloro che si dilettano di programmazione oltre che di scacchi,
vorrei perciò illustrare brevemente alcune mie considerazioni su 2 tipi
di codifica binaria di una particolare posizione negli scacchi,
tralasciando la codifica ASCII, dove il metodo più comunemente adottato
è noto come FEN.
A) Metodo di Huffman
Recentemente mi era capitato di leggere un articolo di Paul Verhelst su
come rappresentare in binario una posizione degli scacchi con il minimo
numero di bit, compressione a parte.
Parlava del metodo di Huffman in cui si indicavano le caselle di una
scacchiera con le seguenti codifiche di bit a seconda del pezzo
presente:
     Casella vuota: 0
     Pedone: 10C
     Alfiere: 1100C
     Cavallo: 1101C
     Torre: 1110C
     Regina: 11110C
     Re: 11111C
Il C indica il bit che individua il colore (0 = Bianco, 1 = Nero).
Si dovrebbero poi aggiungere alcuni bit per indicare chi ha la mossa, le
Torri con diritto di arrocco e l'eventuale Pedone catturabile en
passant. Per questi bit, non chiariti nell'articolo, io aggiungerei in
coda alla rappresentazione delle 64 caselle la seguente codifica:
   * 1 bit per stabilire chi ha la mossa (Bianco = 0, Nero = 1).
   * Da 0 a 4 bit  per indicare nell'ordine le torri con diritto di
     arrocco (Non arrocco = 0, Arrocco = 1). Il numero di bit è fissato
     in base alla disposizione dei pezzi sulla scacchiera (letta in
     precedenza) che mi dice quali sono le Torri per cui esiste il
     dubbio se hanno ancora o meno il diritto di arrocco (solo quelle
     che insieme al proprio Re si trovano nella posizione iniziale).
   * Da 0 a 3 bit per indicare il Pedone catturabile en passant. Anche
     qui io conosco chi ha la mossa e quindi posso sapere quanti Pedoni
     avversari sono nella possibilità di essere catturati en passant. Il
     Pedone catturabile è indicato mediante  la sua posizione (da 0 a 4)
     nella sequenza dei Pedoni catturabili (al max 5?) ed il numero di
     bit usato è il minimo per una rappresentazione di tale posizione in
     binario assoluto.
 Chiusa la parentesi, se sono presenti tutti i pezzi, come ad inizio
partita, si ha un totale di soli 164 bit:
          32*1 + 16*3 + 4*5 +4*5 + 4*5 +2*6 + 2*6 = 164
mentre con meno pezzi la lunghezza si riduce fino a 74 bit (2 soli Re =
62*1 +2*6).
In casi del tutto artificiali con molti Pedoni promossi a Regine si
supererebbero i 164 bit in quanto la Regina occupa 6 bit contro i 3 del
Pedone.
Se provate a codificare con queste regole una sequenza di caselle in una
stringa di bit e
successivamente partendo dall'inizio della stringa ne fate la
decodifica, vi accorgerete di ritrovare esattamente nell'ordine i pezzi
codificati senza possibilità di equivoco !!!
Questa rappresentazione è interessante anche per il seguente motivo:
supposto per semplicità che 165 bit (164 + il bit che indica chi ha la
mossa) siano sufficienti a codificare una qualsiasi posizione, essa
fornisce un limite superiore al numero totale di queste posizioni, cioè
2^165  pari a circa  4.7 x 10^49.
Nella realtà le posizioni degli scacchi dovrebbero essere molto meno ma
è difficile stabilire un valore plausibile giustificabile con criteri
matematici.
Se poi zippando questi record si potesse dimostrare di poter ridurre
comunque il valore 165, si
otterrebbe un valore limite inferiore a quello calcolato.
Il difetto di questa rappresentazione sta nel fatto che la lunghezza non
è fissa e questo richiederebbe una lettura sequenziale oppure un file
indice di appoggio contenente un puntatore all'inizio di ogni record.
B) Formato binario a lunghezza fissa
L'altra alternativa era quella di rappresentare in ordine le 64 caselle
mediante un semibyte (4 bit) per ciascuna casella.
Mi ricollego qui alle idee esposte tempo fa da Julian (mi pare), che
aveva indicato un'ipotesi di rappresentazione che vorrei qui riprendere
e precisare ulteriormente.
Premetto che quanto dico è ... farina del mio sacco, anche se penso che
qualche soluzione simile possa essere stata data da altri. Avendo 4 bit
noi disponiamo di 16 codifiche:
0001 = Pedone bianco
0010 = Alfiere bianco
0011 = Cavallo bianco
0100 = Torre bianca
0101 = Regina bianca
0110 = Re bianco
1001 = Pedone nero
1010 = Alfiere nero
1011 = Cavallo nero
1100 = Torre bianca
1101 = Regina nera
1110 = Re nero
Restano libere quattro codifiche per le quali propongo:
0000 = casella vuota
1000 = casella vuota
0111 = Pedone catturabile en passant
1111 = Torre con diritto di arrocco
L'attribuzione di 2 rappresentazioni alla cella vuota non è un errore:
essa permette di disporre di almeno 32 "bit" (anche se sono 4 bit
contengono un'informazione binaria), quante sono certamente al minimo le
caselle vuote.
Con questi 32 bit (da 0 a 31 visto che siamo tra programmatori)
indicherò:
   * bit 0  =  mossa al Bianco (0000) o al Nero (1000). Questa
     informazione è obbligatoria.
   * bit 1-2 = 2 bit, cioè 4 combinazioni indicanti il risultato della
     posizione (vittoria, patta, sconfitta, ignoto)
   * bit 3-14 = 12 bit: rappresenta la mossa suggerita data come casella
     di partenza (da 0 a 63) + casella di arrivo (da 0 a 63). Per
     l'arrocco viene dato lo spostamento di 2 posizioni del Re.
   * bit 15-16 = 2 bit, cioè 4 combinazioni: indica il pezzo ottenuto se
     la mossa era di promozione.
I bit 17-31 = 15 bit potrebbero essere impiegati per fornire il numero
di mosse, se noto, in caso di vittoria o sconfitta o, nel caso di
risultato ignoto, una valutazione della bontà o meno della posizione
codificando i  '!'  e  i  '?'  che si usano normalmente, o altre
informazioni utili che non saprei al momento precisare.
Conclusioni
Il secondo metodo sembra più semplice e quindi preferibile, tenendo
anche conto della lunghezza costante dei record che facilita la ricerca
su grossi file.
Tuttavia dal punto di vista dello spazio occupato il primo metodo è in
ogni caso migliore perchè ogni posizione avrebbe un'occupazione pari a
164+1+4+3 = 172 bit ai quali possiamo aggiungere 32 bit occupati per
ogni posizione dal puntatore sul file indice (fino a 4 Giga posizioni
indirizzabili) e, per un confronto alla pari, altri 31 bit di
informazione aggiuntiva.
In totale la rappresentazione di Huffman occuperebbe solo 235 bit contro
i 256 della seconda.
Graditissimi commenti, critiche e miglioramenti.
Ciao
Guido
--
Posted from 
smtp2.libero.it
 [193.70.192.52]
via Mailgate.ORG Server - 
http://www.mailgate.org

 
Ho letto con interesse il tuo post. E mi e' risultato piuttosto familiare,
visto che ho gia' affrontato spesso questo tema, sia per il mio programma,
che per l'analisi di alcuni formati di rappresentazione.
Il sistema B) ad esempio e' praticamente identico a quello usato dal
formato chessbase vecchio (CBF) apparte il discorso sulla possibilita' di
en passant, che in chessbase e' incredibilmente incasinato. 
Probabilmente c'e' stata, da parte degli autori, proprio la volonta' di
rendere difficile (ma non impossibile come si e' visto) la decodifica.
Se mi posso permettere un giudizio personale. Ritengo che non esistano
paragoni tra la due scelte. La codifica a lunghezza fissa e' l'unica che
permette accessi rapidi alla posizione senza la necessita' di decodificarla
(espanderla). Tutto sommato il vantaggio che si ottiene in termini di
spazio con quella variabile, non mi sembra compensino la perdita di
efficienzia (velocita') della prima scelta.
Ciao
Paolo B.

 efficienzia (velocita') della prima scelta.
Ti confermo che non sapevo di ... aver copiato il vecchio formato CBF. Bisognerà che li vada a
vedere tutti per evitare di reinventare l'acqua calda. Nel software scacchistico ho sempre
fatto così, forse con poca utilità ma grossa soddisfazione personale.
Riguardo al formato Huffman a lunghezza variabile vorrei precisare quanto segue:
1) Nella mia lettera ho detto la seguente c...ata (leggasi cavolata):
" Tuttavia dal punto di vista dello spazio occupato il primo metodo è in ogni caso migliore
perchè ogni posizione avrebbe un'occupazione pari a 164+1+4+3 = 172 bit ai quali possiamo
aggiungere 32 bit occupati per ogni posizione dal puntatore sul file indice (fino a 4 Giga
posizioni indirizzabili) e, per un confronto alla pari, altri 31 bit di informazione
aggiuntiva."
Normalmente il discorso sui 4 Giga viene fatto per gli indirizzi di RAM perché legato alla
struttura delle istruzioni macchina  che prevedono 32 bit per l'indirizzo, mentre qui mi
dovevo riferire a 4 Giga bit (non posizioni). In effetti si potrebbero utilizzare più di 32
bit per indirizzare il bit di inizio di ogni posizione.
2)  E' pur vero che se i record non hanno lunghezza fissa io devo crearmi un file indice
supplementare (quei 32 bit o più) se voglio accedere all'n-esima posizione, ma che interesso
ho a fare questo?
Se io devo cercare una data posizione, non la cerco in genere in base al numero d'ordine, ma
con una chiave di interesse scacchistico, e quindi ho comunque bisogno di un file indice sia
che le posizioni abbiano  lunghezza costante o che abbiano lunghezza variabile (naturalmente a
meno che il database non nasca fisicamente ordinato secondo la chiave, ma questo preclude
"append" successivi, o richiede sort sempre più pesanti) . L'unica differenza sta nel fatto
che nel primo caso ho bisogno di leggere nel file indice il numero della posizione da
ricercare, nel secondo il numero del bit da cui inizia la posizione cercata. Quindi quei 32
bit di cui parlavo in realtà non andrebbero tutti conteggiati, ma ne aggiungerei solo 8 dato
che una posizione è compresa tra 128 e 256 bit  e quindi 8 sarebbe la differenza di lunghezza
tra i due "indirizzi". Il vantaggio di spazio sarebbe perciò maggiore di quanto detto nel mio
primo post. Spero di non aver detto schiocchezze ...
3)  Pur non avendo mai sviluppato programmi per gestire le posizioni, concordo pienamente con
te che è molto più rapido processare record a lunghezza costante, che record a lunghezza
variabile che richiedono in aggiunta una decodifica più complessa.


 B) Formato binario a lunghezza fissa
Avevo affrontato questo problema quando mi era venuto in mente di codificare in
qualche modo un DB di apertura. A scapito di una maggiore occupazione di
memoria (ma oggi ci sono i DVD no? :-) ) per operazioni abbastanza
time-critical, come l'apertura, la velocita` che il metodo a lunghezza fissa
permette di ottenere rende questa scelta obbligata. Poi e` anche piu` semplice,
che per un ``programmatore'' (le virgolette sono d'obbligo) pigro come me e`
molto :-)


Ovviamente sei in buona compagnia. Io che cominciai a lavorare al mio
programma di scacchi gia' a meta' degli anni 80, mi ritrovai a "inventare"
un mucchio di cose: tecnica di potatura dell'albero (alcune nodi non era
piu' necessario esplorarli conoscendo la tecnica mini-max di selezione di
voto maggiore), metodi per generare le mosse legali, il piu' possibile
veloci, sistemi di rappresentazione delle posizioni ecc.
Fino a quel momento non avevo nessun tipo di sostegno tecnico. Nel senso
che non avevo trovato alcun libro o rivista che entrasse in dettagli su
questi argomenti. Quando poi, molti anni piu' tardi, entrando in internet,
trovai un'enorme quantita' di materiale sull'argomento scoprii che tutto
quello che io credevo di aver inventato ... era gia' stato inventato da
altri!
Fu comunque una soddisfazione, perche' ce l'avevo fatta con le mie sole
forze.
Per te e' la stessa cosa. Puoi rallegrarti di essere riuscito ad arrivare
la, dove solo gli uomini della ChessBase sono giunti prima!
Ciao fatti sentire
Paolo B.

 wrote in message 3818199B...@iol.it...
[SNIP]
| B) Formato binario a lunghezza fissa
|
| L'altra alternativa era quella di rappresentare in ordine le 64 caselle
| mediante un semibyte (4 bit) per ciascuna casella.
|
Una possibile alternativa è quella di memorizzare le coordinate dei pezzi.
Verrebbe così omessa la memorizzazione delle caselle vuote (invece di
memorizzare lo stato delle 64 caselle si memorizzano solo le coordinate dei
32 pezzi!). Supponendo di avere un ordine *implicito* dei pezzi (ad es.
prima viene il Re Bianco, poi il Re Nero, poi la Donna Bianca ecc.) basta
memorizzare una sequenza di coordinate (3 bit [0..7] per la colonna e 3 bit
per la traversa) per un totale di 6 bit per pezzo, e quindi per un massimo
di 6*32=192 bit (24 byte).
Questo codifica è a lunghezza fissa ma presenta alcuni inconvenienti
(codifica dei pezzi assenti, codifica dei pezzi ottenuti da una promozione
ecc.).
Altra idea (più efficiente) è la seguente:
-1- Si utilizza una mappatura della scacchiera (con codifica binaria fissa
pari a 64 bit = 8 byte) per stabilire le caselle vuote(0) da quelle
occupate(1) .
-2- Si utilizza una codifica dei pezzi a 4 bit il cui ordine è stabilito
dalla mappatura precedente. Cioè il primo pezzo memorizzato sarà situato
nella prima casella che risulta occupata dalla mappatura, il secondo pezzo
corrisponderà alla seconda casella occupata... e così via.
L'occupazione di spazio (nel peggiore dei casi si avranno tutti i pezzi
sulla scacchiera) sarà di 32*4=128 bits a cui vanno sommati i 64 bits della
mappatura per un totale di... 192 bits = 24 bytes!
Le posizioni che presentano un numero di pezzi inferiore al numero massimo
(32) avranno una codifica di lunghezza inferiore.
Infatti la mappatura (passo -1-) ha dimensione costante ma la sequenza
successiva dei pezzi è variabile perché dipende dalla mappatura.
In ogni caso si può ottenere la codifica della posizione a lunghezza fissa
con una rappresentazione dei pezzi simile a questa (ma può essere variata
senza controindicazioni):
0001 = Re bianco
0010 = Re nero
0011 = Donna bianca
0100 = Donna nera
0101 = Torre bianca
0110 = Torre nera
0111 = Torre con diritto di arrocco (senza memorizzare il colore, che viene
dedotto dalla posizione!).
1000 = Alfiere bianco
1001 = Alfiere nero
1010 = Cavallo bianco
1011 = Cavallo nero
1100 = Pedone bianco
1101 = Pedone nero
1110 = Pedone catturabile "en passant" (senza memorizzare il colore. [vedi
sopra]).
restano libere due codifiche (0000 e 1111) di cui una (o entrambe) possono
essere utilizzate per memorizzare pezzi fittizzi non presenti nella
posizione al fine di rendere costante la lunghezza finale della codifica
della posizione.
(non è elegante ma funziona)  :-)
[SNIP]
Ovviamente queste codifiche di natura "casareccia" possono presentare
inefficienze per ciò che riguarda ad esempio i tempi di ricerca. Quindi
bisogna vedere se il gioco vale la candela.
So di essere stato poco chiaro...
Spero almeno di essere stato un po' utile...
:-)
Ciao
Alex.

 ecc.).
L'ordine implicito dei pezzi è quello che uso (e credo che usi anche Nalimov) per il calcolo
dei finali proprio perché i pezzi non possono cambiare; infatti se cambiassero per cattura o
per promozione, verrei a trovarmi in un altro finale, che devo aver già calcolato in
precedenza.
A mio avviso proprio gli inconvenienti da te citati sconsigliano tale codifica in questo
caso.

Mi pare che tu sia stato chiarissimo e utilissimo e aggiungo che una delle due codifiche non
usate, nel caso che si vogliano avere record a lunghezza costante di 192 bit, deve essere
utilizzata per i pezzi mancanti al totale di 32 (ad es. 0000) e l'altra per indicare ... chi
ha la mossa (te ne eri dimenticato?) :-)
La soluzione che mi viene in mente è quella di indicare il Re del colore che ha la mossa con
l'ultimo codice libero (1111). Il suo colore si deduce dal fatto che l'altro Re ha la
codifica normale da te indicata comprensiva del colore. Quindi in questo caso tutti e 16 i
codici sarebbero necessari, almeno per risparmiare un bit!
Concordo quindi con te che in 192 bit è possibile codificare una qualsiasi posizione, senza
però aggiungere altre informazioni utili, quali il risultato, la mossa migliore, ecc., che
però potrebbero essere aggiunte a seguire con lunghezza fissa restando molto al di sotto di
256 bit.
Visto che siamo sull'argomento,  il 29/10 avevo inviato una lettera al CCC (Computer Chess
Club) sulla possibilità di ridurre il codice Huffman, lettera che ha innescato una
discussione molto tecnica tra 2 esperti di scacchi e di compressione file sulla possibilità
di codificare una qualsiasi posizione, anche la più assurda purché legale, entro il limite
massimo di 160 bit (con codifica a lunghezza variabile), la qual cosa, come è emerso dalla
discussione, sembra che resti un obiettivo molto difficile da raggiungere nel caso peggiore
in cui vi siano tutti e 32 i pezzi con 12 pedoni promossi.


 wrote in message 381ED134...@iol.it...
[SNIP]
| L'ordine implicito dei pezzi è quello che uso (e credo che usi anche
Nalimov) per il calcolo
| dei finali proprio perché i pezzi non possono cambiare; infatti se
cambiassero per cattura o
| per promozione, verrei a trovarmi in un altro finale, che devo aver già
calcolato in
| precedenza.
Esatto. L'ordine implicito è un metodo molto importante per memorizzare
informazioni a costo zero. Per minimizzare le dimensioni il più possibile
bisognerebbe memorizzare quanta più "roba" possibile in forma implicita.
(Scusa l'ignoranza... chi è Nalimov?).
[SNIP]
| La soluzione che mi viene in mente è quella di indicare il Re del colore
che ha la mossa con
| l'ultimo codice libero (1111). Il suo colore si deduce dal fatto che
l'altro Re ha la
| codifica normale da te indicata comprensiva del colore. Quindi in questo
caso tutti e 16 i
| codici sarebbero necessari, almeno per risparmiare un bit!
Perfetto!
Vedo che hai capito l'idea! (Che è la cosa più importante... come a scacchi
del resto). :-)
[SNIP]
| Visto che siamo sull'argomento,  il 29/10 avevo inviato una lettera al CCC
(Computer Chess
| Club) sulla possibilità di ridurre il codice Huffman, lettera che ha
innescato una
| discussione molto tecnica tra 2 esperti di scacchi e di compressione file
sulla possibilità
| di codificare una qualsiasi posizione, anche la più assurda purché legale,
entro il limite
| massimo di 160 bit (con codifica a lunghezza variabile), la qual cosa,
come è emerso dalla
| discussione, sembra che resti un obiettivo molto difficile da raggiungere
nel caso peggiore
| in cui vi siano tutti e 32 i pezzi con 12 pedoni promossi.
Queste sono le sfide che mi appassionano! Se hai ancora quella lettera mi
piacerebbe leggerla (me la puoi spedire?).
Ciao
Alex.