Scrivere un programma di scacchi – 2



Continuiamo la serie di articoli che ci porterà a scrivere un piccolo motore di scacchi. Nella prima parte ci siamo fatti un’idea generale di cosa è e come funziona un chess engine, abbiamo visto come scegliere il linguaggio e abbiamo fatto un piccolo programma di lavori. In questo secondo articolo vedremo invece come si rappresenta una scacchiera, non ci inoltreremo nelle specifiche implementazioni, ma faremo una dettagliata panoramica sulle principali strutture dati utilizzate sui rispettivi pro e conto e soprattutto sui problemi che cercano di risolvere. Ovviamente si da per scontato la conoscenza delle regole del gioco degli Scacchi. Se non sapete da dove cominciare ecco un po’ di riferimenti utili:

I modi in cui una scacchiera può essere rappresentata in memoria sono molteplici. L’idea generale è avere una matrice di dati: ogni elemento della matrice rappresenta una casella della scacchiera, il valore in esso contenuto rappresenta il pezzo che è collocato su quella specifica casella. Muovere un pezzo sulla scacchiera significa quindi copiare un valore da una casella all’altra. Rappresentando la matrice con un array, abbiamo bisogno di calcolare solo i due indici “from” e “to”; in pseudocodice:

board[index_square]

una mossa è quindi rappresentata dalla coppia di istruzioni:

board[to] = board[from]
board[from] = EMPTY

In prima approssimazione si potrebbe credere che abbiamo bisogno di un array di 64 elementi: la scacchiera è formata da 8*8 caselle, quindi occorre un array di 8*8=64 caselle, ma non è così. Per velocizzare la generazione delle mosse abbiamo bisogno di capire velocemente se un pezzo si muove al di fuori della scacchiera; con soli 64 elementi non è possibile: immaginiamo di sovrapporre alla scacchiera gli indici…

 0  1  2  3  4  5  6  7
 8  9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

Se un pezzo, una torre, si trovasse nella casella con l’indice numero 40 e volessimo sapere se può spostarsi di una casella verso destra, basterebbe aggiungere 1 all’indice e controllare che la casella di destinazione 40+1=41 sia vuota, ma se volessimo sapere se lo stesso pezzo può muoversi di una casella a sinistra non possiamo effettuare lo stesso calcolo che ci darebbe come risultato una casella la 40-1 = 39 in cui è impossibile che il pezzo possa andare anche se fosse vuota. Esistono delle strutture dati create appositamente per ovviare a questo problema; senza avere la pretesa di essere esaustivi, diciamo che i sistemi di rappresentazione più conosciuti e usati al momento sono quattro:

  1. Gli array di 144 (12×12) elementi o gli array di 120 (12×10) elementi
  2. Lo “0x88” che sta per 88 esadecimale (un array di 16×8 = 128 elementi)
  3. Gli array di 16×16 0 16×12 elementi
  4. Le Bitboard (di cui ci occuperemo nel prossimo articolo)

Quale tra preferire tra queste? Non esiste la rappresentazione “perfetta”. Periodicamente si può assistere sui forum specializzati a vere e proprie “guerre ideologiche” sulla superiorità di una rappresentazione rispetto ad un’altra principalmente in ambito di velocità computazionale. La velocità di generazione delle mosse che è condizionata dal tipo di rappresentazione scelta, è certamente un problema importante, ma sicuramente non il principale. Non è la velocità del generatore in sé a fare di un programma un buon programma. Tutt’altro. Personalmente consiglio di iniziare con lo “0x88” o con un array 12×12, dato che sono tra i più semplici da implementare, in seguito si può passare, se ce ne fosse bisogno, alle bitboard. Vediamole adesso in dettaglio.

Posizione di partenza

Posizione di partenza

Array 12×12 o 12×10

L’idea è quella di estendere il nostro array da 64 elementi con due due anelli concentrici di “caselle sentinella” contenenti un valore spia che marca la casella come illegale. Qualora l’indice calcolato contenesse questo valore spia capiremmo di trovarci fuori dalla scacchiera. Potete immaginarlo così, assumendo -1 come valore spia

-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,A8,B8,C8,D8,E8,F8,G8,H8,-1,-1,
-1,-1,A7,B7,C7,D7,E7,F7,G7,H7,-1,-1,
-1,-1,A6,B6,C6,D6,E6,F6,G6,H6,-1,-1,
-1,-1,A5,B5,C5,D5,E5,F5,G5,H5,-1,-1,
-1,-1,A4,B4,C4,D4,E4,F4,G4,H4,-1,-1,
-1,-1,A3,B3,C3,D3,E3,F3,G3,H3,-1,-1,
-1,-1,A2,B2,C2,D2,E2,F2,G2,H2,-1,-1,
-1,-1,A1,B1,C1,D1,E1,F1,G1,H1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,

Questo stratagemma aumenta di molto la velocità di generazione delle mosse, per esempio un alfiere potrebbe generare mosse strisciando di una casella alla volta e fermarsi quando raggiunge una casella illegale. Non occorrono calcoli complicati ne tabelle precompilate di riferimento. Una mossa è fuori dalla scacchiera se e solo se:

if ( board[to] =! -1 )

Il secondo anello di caselle è richiesto per il controllo delle mosse dei cavalli posti ai margini della scacchiera e per i quali un singolo anello non sarebbe sufficiente. Vediamo ora due semplici routine in pseudocodice per la generazione delle mosse del cavallo e della torre

//Cavallo
delta[]={-25,-23,-14,-10,10,14,23,25};
for (i=0 to 7) {
 to=from+delta[i];
 if (board[to] != -1) {
  if (board[to] == EMPTY) Generate_move();
  else if (board[to] == ENEMY) Generate_capture();
 }
}
//Torre
delta[]={-12,-1,1,12};
for (i=0 to 3) {
 to=from + delta[i];
 while(board[to] != -1) {
  if (board[to] == EMPTY) Generate_move();
  else if (board[to] == ENEMY) Generate_capture();
  to = to + delta[i];
 }
}

Vedremo in seguito come ottimizzare queste routine, eseguendo, per esempio, un singolo controllo per determinare se una casella è vuota, fuori dalla scacchiera regolamentare od occupata. L’array 12×10 fa un miglior uso della memoria sovrapponendo la colonna più a sinistra e quella più a destra; al giorno d’oggi questa necessità di risparmiare memoria è meno sentita, ma ancora attuale se pensiamo alla programmazione per cellulari e dispositivi portatili. Dato l’indice di una casella possiamo avere la necessità di calcolare la colonna (Column è la sequenza di caselle in verticale, generalmente nominate con le lettere da A ad H, da sinistra a destra) e la riga (Rank è la sequenza di caselle orizzontali, generalmente nominate con i numeri da 1 a 8 dal basso verso l’alto), per convenzione la casella a1 è in basso a sinistra e la h8 in alto a destra, il bianco gioca dal basso verso l’alto e il nero dall’alto verso il basso.

Column = index MOD 12;//array 12 x 12, mod che ritorna il resto di una divisione intera è un’operazione piuttosto lenta
Column = index MOD 10;//array 10 x 12
Rank = index / 12;//è una divisione intera, piuttosto lenta
Rank = index / 10;//(10 x 12)è una divisione intera
Ovviamente i valori di riga e colonna vanno da 2 a 9.

0x88

La struttura “0x88” usa un array di 16 x 8 = 128 elementi, numerati da 0 a 127. Può essere pensata come due scacchiere appaiate. La scacchiera reale è sulla sinistra, quella sulla destra serve a tener traccia delle mosse illegali.

A8,B8,C8,D8,E8,F8,G8,H8,-1,-1,-1,-1,-1,-1,-1,-1,
A7,B7,C7,D7,E7,F7,G7,H7,-1,-1,-1,-1,-1,-1,-1,-1,
A6,B6,C6,D6,E6,F6,G6,H6,-1,-1,-1,-1,-1,-1,-1,-1,
A5,B5,C5,D5,E5,F5,G5,H5,-1,-1,-1,-1,-1,-1,-1,-1,
A4,B4,C4,D4,E4,F4,G4,H4,-1,-1,-1,-1,-1,-1,-1,-1,
A3,B3,C3,D3,E3,F3,G3,H3,-1,-1,-1,-1,-1,-1,-1,-1,
A2,B2,C2,D2,E2,F2,G2,H2,-1,-1,-1,-1,-1,-1,-1,-1,
A1,B1,C1,D1,E1,F1,G1,H1,-1,-1,-1,-1,-1,-1,-1,-1,

Durante la generazione delle mosse, per stabilire se una casella è all’interno della scacchiera, basta effettuare un bitwise AND l’indice della casella e il numero 0x88 ( 136 decimale). Se il risultato è diverso da zero la casella è al di fuori della scacchiera legale.

if ((index & 0x88)!=0)...la casella è sulla scacchiera illegale//& è BITWISE AND

Perchè? È presto detto, guardiamo nel dettaglio gli indici delle due righe estreme, sono:

112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127
A8, B8, C8, D8, E8, F8, G8, H8, -1, -1, -1, -1, -1, -1, -1, -1,
...
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,
A1,B1,C1,D1,E1,F1,G1,H1,-1,-1,-1,-1,-1,-1,-1,-1,

Quello a cui siamo interessati è sapere se la casella di destinazione della mossa è nella scacchiera reale e se l’indice è tra 0 e 127. Ipotizziamo di avere una torre in h1 (indice 7) e vogliamo sapere se può muoversi di una casella a destra, semplicemente addizioniamo 1 all’indice: 7+1 = 8 ed effettuiamo un and bit a bit con il numero 0x88. In binario abbiamo:

8 0000000: 00001000
0x88(136): 10001000
8 & 0x88 : 00001000 -> mossa illegale

Ogni indice che rappresenta una casella reale (la scacchiera a sinistra nella nostra rappresentazione) ha il bit evidenziato settato a 0, invece tutti gli indici delle caselle che si trovano sulla scacchiera a destra ( quindi irraggiungibili) hanno il bit evidenziato pari a 1.

Vogliamo anche sapere, avendo una torre in H8 (indice 119) se è possibile spostarla di una casella verso l’alto: semplicemente addizioniamo 16 all’indice: 119 + 16 = 135. In binario avremmo:

135 00000: 10000111
0x88(136): 10001000
135 &0x88: 10000000 -> mossa illegale

Anche in questo caso sfruttiamo una proprietà matematica degli indici: nella loro rappresentazione binaria gli indici maggiori di 128 o minori di 0 hanno il bit evidenziato settato a 1.

Un’altra interessante proprietà matematica di tutte le rappresentazioni con array del tipo 16 x N (16 x 8, 16 x 12, 16x 16) è che sottraendo tra loro due qualunque indici possiamo ricavare dal risultato delle informazioni sulla loro disposizione geometrica sulla scacchiera. Per esempio se la differenza tra due indici è 16 (o un multiplo intero dello stesso: 32, 48…) sappiamo subito che le due caselle si trovano sulla stessa colonna, se la differenza è 1 (o un multiplo intero dello stesso: 2,3…) sono sulla stessa riga, se 15 o 17 (o un multiplo intero degli stessi) sulla stessa diagonale. Questa proprietà matematico-geometrica risulterà utilissima per scrivere una funzione di attacco (cioè una funzione che ci dica se una determinata casella è attaccata da un’altra casella) notevolmente rapida. Anche qui dato l’indice vorremmo poter calcolare a che riga o colonna appartengono, anche qui la rappresentazione in base 16 da i suoi vantaggi in termini di velocità:

Column = index MOD 16;//che diventa: index & 15...molto veloce
Rank = index / 16;//che diventa: index >> 4...molto veloce

In questo caso i valori di riga e colonna vanno da 0 a 7.

Array 16×12 o 16×16

La prima volta che lessi di questo tipo di rappresentazione fu in un vecchio post di Christophe Theron (il programmatore di Chess Tiger) sul CCC forum. Egli stesso utilizzava questo schema nel proprio programma commerciale. Potete immaginare il 16×12 in questa maniera

-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,A8,B8,C8,D8,E8,F8,G8,H8,-1,-1,-1,-1,
-1,-1,-1,-1,A7,B7,C7,D7,E7,F7,G7,H7,-1,-1,-1,-1,
-1,-1,-1,-1,A6,B6,C6,D6,E6,F6,G6,H6,-1,-1,-1,-1,
-1,-1,-1,-1,A5,B5,C5,D5,E5,F5,G5,H5,-1,-1,-1,-1,
-1,-1,-1,-1,A4,B4,C4,D4,E4,F4,G4,H4,-1,-1,-1,-1,
-1,-1,-1,-1,A3,B3,C3,D3,E3,F3,G3,H3,-1,-1,-1,-1,
-1,-1,-1,-1,A2,B2,C2,D2,E2,F2,G2,H2,-1,-1,-1,-1,
-1,-1,-1,-1,A1,B1,C1,D1,E1,F1,G1,H1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,

In sostanza si cerca di coniugare i vantaggi matematico-geometrici della 0x88 con la velocità di generazione degli array 12×12. La rappresentazione 16×16 è praticamente identica, ma permette di usare un array di 256 elementi che in fase di compilazione permette discrete ottimizzazioni.

Le bitboard, l’ultimo tipo di rappresentazione che rimane, essendo più complesse e costituendo anche un approccio tecnologico filosoficamente diverso, meritano un articolo a parte. Nel frattempo potete trovare informazioni e risorse qui:

Nel prossimo articolo: le bitboard.

Annunci sponsorizzati:
Condividi su Facebook Condividi su Twitter!
Pinterest