Scrivere un programma di scacchi – 3



Nel secondo articolo di questa serie abbiamo visto come descrivere in memoria una scacchiera tramite diversi tipi di matrici implementati tramite array. In questo articolo vedremo come descrivere la scacchiera tramite le bitboard.

Per Bitboard (scacchiera di bit) si intende un intero senza segno di 64 bit a ciascuno dei quali è associata una casella.

typedef unsigned __int64 bitboard

In generale data una casella ciò che il programma vorrebbe sapere è:

  1. Se è vuota;
  2. Se contiene un pezzo amico o nemico (2 valori possibili: bianco e nero)
  3. Il tipo di pezzo (5 valori possibili: pedone, cavallo, alfiere, torre, regina, re)

Nove condizioni dunque, che in un array possono essere espresse tramite valori diversi o combinazioni degli stessi, ma in una bitboard possiamo solo usare, per ogni casella, due valori come fare? Pensando la bitboard come descrittrice di una condizione di “vero o falso”, di “si o no” o di “occupato o libero” sulla scacchiera e utilizzandone diverse; avremo dunque una bitboard per i pedoni bianchi e che risponde alla domanda “in quale casella ho un pedone bianco?”, una per i pedoni neri, una per cavalli bianchi e così via, ne potremo avere ( o calcolare, vedremo dopo come) una che descrive per esempio l’insieme dei pezzi bianchi presenti sulla scacchiera o l’insieme delle caselle libere. Raggiunta una posizione come la seguente:

Scacchiera posizione 1

possiamo immaginare la bitboard che descrive i pedoni bianchi come:

00000000
01000000
00000000
00000000
00000000
00000000
00000000
00000000

Cioè

white_pawns = 0000000001000000000000000000000000000000000000000000000000000000; = 18014398509481984 (in decimale)

Una piccola avvertenza: esistono diverse notazioni per le bitboard, quando abbiamo parlato degli altri tipi di rappresentazione, come 12×12 o 0x88 cominciavamo a contare da A1, invece qui (per semplicità) cominciamo da A8 e continuiamo nel senso A8, B8, C8,… , H8, A7, B7, C7,… , G1,H1. Per ciascuna casella inseriamo un ‘1’ se la condizione che ci interessa è verificata (ad esempio un pedone bianco), oppure uno ‘0’. Il bit più a sinistra è A8, il bit più a destra è H1.
Lavorare con le bitboard significa conoscere e capire le operazioni con i bit, quindi, se già non le conoscete: fermatevi e studiate! ;) Per gli altri ricordo velocemente le operazioni fondamentali (tra parentesi la simbologia C/C++):

  • NOT (~): NOT 1000 = 0111
  • OR (|): 0101 OR 0011 = 0111
  • XOR(^): 0101 XOR 0011 = 0110
  • AND (&): 0101 AND 0011 = 0001

Cosa possiamo fare con le bitboard? Diverse cose: innanzitutto la generazione delle mosse di fatto diventa una semplice operazione di controllo di tabelle (look-up) grazie alle bitboard, infatti possiamo precalcolare moltissimi dati e usarli alla bisogna. Possiamo in sostanza generare un database di bitboard con tutte le caselle attaccate da ogni singolo pezzo su ogni singola casella e tramite poche operazioni logiche conoscere i risultati. Vediamo le differenza con gli altri sistemi di rappresentazione, nella posizione

Scacchiera 2

se volessimo sapere se il re bianco è sotto scacco da parte della regina nera, usando un metodo di rappresentazione bastao su array dovremmo:

  1. Trovare la posizione della regina nera, il che richieda una ricerca lineare sull’array;
  2. Per ognuna delle otto possibili direzioni controllare ogni casella fino al ritrovamento di un pezzo o del re

Il processo è piuttosto dispendioso in termini di tempo, soprattutto in casi come questo dove alla fine il re non è sotto scacco! Ragionando in termini di bitboard, invece, opereremmo così:

  1. Si hanno in memoria la bitboard che rappresenta la posizione della regina (o delle regine nere) che chiamiamo “black_queen_position” e la bitboard che rappresenta la posizione del re bianco “white_king_position”
  2. Si identifica dalla bitboard su che casella è la regina e si usa il numero della casella come indice per leggere nel database la bitboard contente tutte le caselle attaccate dalla regina da quella particolare posizione: la “queen_attacked_squares”
  3. Si effettua un AND logico tra le bitboard: “queen_attacked_squares” e la “white_king_position”

Se il risultato è diverso da zero (quindi le due bitboard hanno un elemento in comune) vuol dire che il re si trova su una delle caselle in cui è possibile per la regina nera attaccare. Altrimenti no! Nel nostro caso possiamo visualizzare le bitboard in questo modo:

BITBOARD black_queen_position =

00000000
00000000
10000000
00000000
00000000
00000000
00000000
00000000

BITBOARD white_king_position =

00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000010

BITBOARD queen_attacked_squares [16][grado_di_occupazione];//It'll be:

 

00100000
01000000
10000000
01000000
00100000
00010000
00001000
00000000

Ragion per cui il re è sotto scacco solo se:

if ((white_king_position & queen_attacked_squares [16][grado_di_occupazione]) != 0) KING_IS_IN_CHECK

Il valore grado di occupazione rappresenta un valore che identifica in maniera univoca la scacchiera tenendo conto della posizione degli altri pezzi. Vedremo in seguito come calcolarlo. Le bitboard, a mio modo di vedere rappresentano una vero e proprio linguaggio tramite il quale si possono porre domande sulla configurazione della scacchiera, il che li rende molto utili ad esempio nella scrittura di sofisticate funzioni di valutazione, del resto l’avere precalcolato molti dati permette di disporre da subito di numerose informazioni sul gioco, per esempio la mobilità (il numero di mosse disponibili per un colore), o di avere delle funzioni di attacco praticamente a costo zero. Non ho posto l’accento sulla velocità dei programmi basati sulle bitboard perché è un dato piuttosto controverso: solo da poco i processori a 64bit sono disponibili sul mercato consumer; su processori a 32 bit programmi, ben scritti, basati su array 16*16 o simili danno più o meno gli stessi risultati, d’altra parte come ho già detto e come non mi stancherò mai di ripetere non è la velocità di generazione delle mosse il parametro principale da cui deriva la forze di un chess engine.

Nel prossimo articolo cominceremo a gettare le basi per un piccolo generatore di mosse e a mettere, finalmente mano, ad un compilatore.

Annunci sponsorizzati:
Condividi su Facebook Condividi su Twitter!
  • Raffaele

    Complimenti! Una lezione davvero magistrale.

Pinterest