Do you want to build a chess engine too? Read here. Now available only in Italian! Do you want to help me traslating it in english?e-mail me!!

Indice

Introduzione

Qualche tempo fa mi venne l’idea di scrivere un piccolo programma per giocare a scacchi, cominciai così a cercare sul web e nei newsgroup notizie sullo “stato dell’arte” della programmazione di IA volte al gioco degli scacchi; conobbi così l’esistenza di numerosi tornei, a livello nazionale e internazionale, in cui si poteva gareggiare con il proprio programma, Di conseguenza il mio obiettivo diventava  partecipare e , possibilmente, vincere!

Avendo accumulato decine di nozioni sull’argomento, per fare maggiore chiarezza nella mia mente decisi di cominciare a scrivere un "making of" che avrei poi allegato al programma, in maniera tale da riorganizzare le idee e allo stesso tempo rendere un piccolo servizio ai neofiti, in considerazione del fatto che la maggior parte del materiale disponibile è in inglese. La cronica mancanza di tempo mi ha impedito di portare avanti il progetto, ma ho pensato di inserire in rete i primi appunti e tenterò di aggiornarli via facendo.

In rete sono disponibili diversi sorgenti di programmi guarda nella sezione link.

Un lavoro del genere non può essere esente da errori, vi invito pertanto a segnalare mancanze, dubbi o meglio ancora nuovi argomenti.

Qualche volenteroso potrebbe mandarmi una tavola sinottica con le date piu' importanti della computer chess?Formato "*.rtf " e in italiano: la storia e' importante;-)

Indice

Cosa e' un "chess engine"

Un chess engine è niente altro che un programma eseguito da un computer che riceve come input una mossa eseguita da un essere umano o da un calcolatore e da come output una contromossa! Vi aspettavate di più?

Perchè gli scacchi sono uno dei giochi che nel campo della ricerca informatica ha avuto così successo? Il gioco degli scacchi è un tipo di gioco definito ad “informazione perfetta” cioè in ogni momento della partita entrambi i giocatori sanno che cosa fa l’altro ed essendo un gioco su scacchiera è facilmente schematizzabile d’altra parte non è un problema banale perché non è possibile calcolare, in tempi ragionevoli tutte le combinazioni possibili, ecco che allora inizia la sfida: come calcolare le contromosse più opportune?calma ci arriveremo, vediamo prima che cosa occorre per costruire un chess engine:

Indice

L'approccio

Una delle credenze più comuni in chi comincia ad avventurarsi nel mondo dell'informatica è che i computer siano macchine in grado di risolvere problemi: niente di tutto ciò, un elaboratore si limita ad eseguire in maniera "cieca" gli ordini presenti in un programma. Il tipo di comandi, e l'ordine in cui vengono eseguiti sono di esclusiva pertinenza del programmatore umano ciò implica che del determinato problema a cui il programma vuole porre soluzione, si conosca il metodo o la sequenza di azioni (algoritmo) per ottenere la soluzione. Se ad esempio volessimo scrivere un programma per calcolare l'area di un rettangolo ci basterebbe codificare con il linguaggio scelto la nota formula Area = base * altezza. 

Non tutti i problemi hanno però una soluzione algoritmica: ciò significa che non sappiamo a priori quale è la sequenza di azione da eseguire per ottenere la soluzione. Gli scacchi sono proprio un problema che non ha soluzione algoritmica: giocarlo esaustivamente richiederebbe mooolto tempo! Coma fare allora? Esiste una branca della ricerca dell'IA che studia i cosiddetti "metodi deboli" cioè metodi generali di risoluzione di un problema quando non sia disponibile un metodo più specifico. Uno di questi è proprio quello che adotteremo cioè la ricerca nello spazio del problema.

In che consiste: rimanendo nell'ambito degli scacchi, data una posizione iniziale della scacchiera (stato iniziale) generiamo tutte le possibili mosse (dalle 20 alle 40), quindi per ognuna dei nuovi stati che si verranno a creare generiamo tutte le contromosse e così via . Si formerà un vero e proprio albero alla cui radice ritroveremo la posizione iniziale e i nodi ci indicheranno tutte le possibili mosse riferite alla situazione del nodo padre. Chiamiamo ply ogni livello dell'albero che in ultima analisi rappresenta tutte le mosse possibili di un colore.

E' intuitivo come dato l'alto numero di mosse possibili per una posizione bastino pochi ply per avere a che fare con migliaia di nodi. Sarà nostra cura in seguito cercare di "potare" questo albero escludendo le mosse "inutili".

C. Shannon  nel 1949 presentò al "National IRE Convention" un intervento dal titolo "Programming a Computer for Playing Chess"; esso è considerato l'atto di nascita della computer chess e vi si trovano descritti i due fondamentali approcci con cui un calcolatore può giocare:

Il tipo di programma che ci apprestiamo a scrivere segue l'approccio definito “forza bruta”, cioè per ogni posizione genereremo tutte le possibili contromosse anche quelle che il più inesperto dei giocatori escluderebbe: sarà poi nostra cura valutare la mossa migliore ed esguirla

L'approccio "Tipo B", in cui vengono generate solo alcune mosse per ogni posizione, in verità è stato quello che per prima è stato indagato, ma non ha prodotto risultati migliori: è molto difficile cercare di implementare in un computer l'intuito scacchistico e una generazione selettiva rischia molto spesso di tralasciare mosse molto forti dal punto di vista tattico, d’altra parte l’approccio a forza bruta ha dal punto di vista algoritmico raggiunto, molto probabilmente, i suoi limiti, salti di qualità importanti si potranno ottenere, forse, nella programmazione su sistemi multiprocessori o adottando nuovi paradigmi come la programmazione genetica o le reti neurali.

Indice

La rappresentazione della scacchiera

Vediamo anzitutto come possiamo rappresentare la classica scacchiera

Alcune strutture

Una prima soluzione potrebbe essere quella di creare una matrice 8x8 dove in ogni cella indichiamo il tipo di pezzo presente (per esempio con enum{vuota, bRe, bReg, bA,….}) sarebbe una soluzione semplice e facile da maneggiare (un doppio ciclo “for” nidificato per “leggere la scacchiera e una serie di if…then…else per valutarla), ma ricordiamoci che abbiamo bisogno di capire anche cose come: la possibilità di effettuare arrocco, la presenza di caselle per un en passant… e questo tipo di rappresentazione renderebbe il codice difficile da mantenere e lento.

Un’altra soluzione potrebbe essere l’utilizzo di matrici 10x12 o, addirittura, 12x12 dove nelle caselle in più vengono memorizzate delle “sentinelle” che ci avvisano dei problemi di cui sopra; la letteratura specifica riporta esempi anche di più scacchiere “sovrapposte” (come i layer di un programma di grafica) ognuna rappresentante aspetti diversi dello stesso gioco.

Un altro tipo di rappresentazione molto utilizzato è il cosiddetto “0x88”: il nome di questo tipo di rappresentazione deriva da un semplice trucco per testare se una casella è la destinazione di una mossa valida, tramite la rappresentazione binaria del numero 136 che in esadecimale è, appunto, 0x88. Attribuiamo ad ogni casella un valore formato da un singolo byte, dove i quattro bit più alti rappresentano la riga e i 4 più bassi la colonna nella figura vediamo i valori decimali; ora se indichiamo con i la generica casella quella immediatamente a destra è i+1 e quella a sinistra è i-1, quella in alto è i+16 e quella in basso i-16. Quali sono i vantaggi? Innanzi tutto usiamo un solo indice invece di due per leggere la scacchiera, poi è molto facile stabilire se la mossa è valida (nel senso che la casella di destinazione è sulla scacchiera) infatti la mossa è valida se e solo se
i & 0x88 = 0

Esistono ancora altre rappresentazioni, e sarà mia cura inserirle via via in questa pagina, ma sono tutte varianti della stesso tipo: la rappresentazione della scacchiera tramite vettori o matrici.

Ero tentato all’inizio di utilizzare una di queste rappresentazioni, ma i vantaggi di utilizzare delle strutture dati come quelle di cui ora vi parlerò erano tanti e tali, in termini di velocità e, soprattutto, di espandibilità, che ho deciso di implementarli anche se un po’ complessi da capire, ma con un po’ di calma ed impegno ce la faremo: benvenuti nel mondo delle bitboard!!

Le Bitboard

Fino ad ora abbiamo descritto la scacchiera con array di byte, dedicando ogni singolo byte ad una casella, la tecnica delle bitboard, presentata per la prima volta da Robert Hyatt in "Cray Blitz" prevede di descrivere la singola casella con un solo e semplice bit: essendoci 64 caselle abbiamo bisogno di 64 bit che oggi possono essere facilmente rappresentati tramite una sola word di 64 bit appunto! Quindi scriviamo:

ora vi chiederete quali sono i vantaggi di usare questa rappresentazione e che valori possiamo immagazzinare avendo a disposizione un singolo bit per casella: bene diciamo anzitutto che noi non stiamo proprio rappresentando una scacchiera, ma delle condizioni logiche che avvengono su di essa, per cui utilizzeremo diverse bitboard per esprimere differenti situazioni: per esempio una si occuperà di memorizzare tutte le caselle occupate dai pezzi bianchi, un’altra dai pezzi neri, un’altra ancora le caselle attaccate dai cavalli bianchi e così via; circa il vantaggio in termini di efficienza diciamo subito che l’aggiornamento di una bitboard richiede l’uso di poche operazioni logiche le quali nei computer attuali vengono effettuate in pochissimi cicli di clock! Ricordiamoci che l’approccio utilizzato è del tipo “a forza bruta” ragion per cui ogni sistema che ci permetta di risparmiare drasticamente tempo è bene accetto! Vediamo più in dettaglio come funziona una bitboard; possiamo visualizzarne una così:

Cioè una word di 64 bit pari a: 11111111 11111111 00000000 00000000 00000000 00000000 11111111 11111111, con la convenzione, nel nostro caso(ma può variare da programma a programma) che il bit più “a sinistra” (il più significativo) corrisponde alla casella a8 e quello più “a destra” (il meno significativo) alla casella h1, state attenti è importante che venga definito all'inizio l'ordine questo è fondamentale per le operazioni di scorrimento dei bit che seguiranno!

Altri esempi? Ecco la bitboard che descrive la posizione dei pezzi bianchi:

Quella che descrive dove si trovano torri e regine:

Cioè 10010001 00000000 00000000 00000000 00000000 00000000 00000000 10010001, confusi abbastanza? Mai quanto me quando ho cominciato a studiarle!!

Ora una trattazione sequenziale prevedrebbe che vi parli delle operazioni logiche che si possono effettuare su una bitboard per ricavare il movimento dei pezzi, ma complicheremmo il discorso, per cui penso che sia meglio vedere prima il “fine” di queste strutture dati poi ritorneremo sui nostri passi e vedremo come implementarli. Siete pronti? Allacciatevi le cinture e partiamo con…

La generazione delle mosse (anticipazioni)

Abbiamo delle strutture dati che ci permettono di rappresentare la scacchiera, non importa se non avete ben compreso come, lo capiremo dopo, ora dobbiamo capire a che ci servono: il nostro obbiettivo è quello di far generare al computer, data una determinata configurazione iniziale della scacchiera, tutte le mosse che si possono effettuare, poi tra queste valuteremo quale è la migliore, ma procediamo per gradi.

Un po’ di conti

Un giocatore ha la possibilità, in ogni turno di effettuare 30-35 mosse diverse, alcune buone, altre suicide: in funzione dell’esperienza del giocatore egli saprà escludere grazie alle proprie capacità le mosse “cattive” riducendole a 1-2. Non è semplice ricreare questa situazione in programma, vi ricordate? L’approccio a “forza bruta” prevede di elaborare tutte le mosse possibili e le rispettive contromosse e così via, generando un vero e proprio albero delle configurazioni possibili, quindi applicare ad ogni situazione una funzione di valutazione per valutare la bontà della mossa, poi scegliere la migliore: allo stato attuale noi non siamo in grado ne di implementare “l’intuito scacchistico” che ci permetterebbe di non indagare le mosse suicide ne di elaborare esaustivamente tutte le mosse in tempi ragionevoli (pensate che indagare il gioco fin solo alla quarta contromossa (8 ply) possibile dell’avversario significa indagare tra 35⁸ posizioni cioè circa 2 x 10¹²!!), se consideriamo che dopo averle elaborate le dobbiamo valutare, è manifesto che le funzioni di generazione e di ricerca devono essere particolarmente veloci: ecco perché usiamo le bitboard: ci permettono di velocizzare gli algoritmi di generazione delle mosse! Vediamo come.

Richiami di logica binaria

Prima di continuare un breve appunto sulle operazioni logiche che possiamo effettuare con i bit:

AND (in C/C++: & )
Raffronta i due bit e genera 1 se entrambi sono 1, altrimenti 0

OR (in C/C++: | )
Raffronta i due bit e genera 1 se entrambi o uno dei due è 1, altrimenti 0

XOR (OR esclusivo in C/C++: ^ )
Raffronta i due bit e genera 1 se solo uno dei due è 1, se entrambi sono 1 o altrimenti, genera 0

NOT (in C/C++: ~ )
inverte ciascun bit 

Shift a destra o sinistra (in C/C++:>> oppure << )
Muove i bit a destra o a sinistra di una quantità desiderata

Il movimento dei pedoni

Abbiamo detto che una bitboard ci permette di rappresentare tramite una word di 64 bit una condizione logica sulla scacchiera, ora vedremo come operando con semplici espressione logiche bit a bit (and, or, xor e shiftaggio) possiamo ricavarne altre: immaginiamo di avere la bitboard che rappresenta la posizione dei pedoni bianchi all’inizio della partita, avremo qualcosa come:

 Cioè 00000000 00000000 00000000 00000000 00000000 00000000 11111111 00000000 , se volessimo sapere tutte le possibili mosse dei pedoni con una rappresentazione ad array dovremmo scandire tutta la scacchiera fino a trovare un pedone, quindi valutare la mossa; con le bitboard è molto più semplice e veloce basta effettuare , nel nostro caso, uno shift a sinistra di 8 posizioni per ottenere in un colpo solo tutte le mosse possibili:

otterremo così 00000000 00000000 00000000 00000000 00000000 11111111 00000000 00000000 che in termini figurativi corrisponde a

Abbiamo trovato una scacchiera in cui i pedoni sono avanzati di un posto cioè, per ogni pedone, tutte le mosse possibili, ma andiamo avanti: come possiamo sapere se tutte le mosse dei pedoni sono possibili cioè se le caselle immediatamente davanti non sono occupate? Ricordate abbiamo detto che utilizzeremo diverse bitboard (più avanti vedremo quante e quali esattamente) immaginiamo di avere oltre alla bitboard precedente una con la descrizione di tutte le caselle vuote (dove gli 1 indicano l’assenza di pezzi sulla casella) basterà effettuare un AND logico tra le due per ottenere come risultato una bitboard in cui sono indicati le mosse di avanzamento dei pedoni in caselle libere. Come ottenere una bitboard delle caselle vuote? Potremmo tenerne una sempre memorizzata e aggiornarla man mano oppure ottenerla come risultato di un operazione tra le bitboard “pezzi bianchi” e “pezzi neri”, in particolare

visto il vantaggio di utilizzare le bitboard? Non tanto per avere un codice più semplice (in effetti è un po’ più complesso ragionare in termini di bitboard) quanto per avere la possibilità di generare tutte le mosse in una volta sola invece che una alla volta.

Il movimento dei cavalli e del re

Il reale vantaggio delle bitboard si vede però nel movimento dei pezzi maggiori e minori: non dovremo calcolarli, ma basterà semplicemente "guardare" in tabelle precalcolate. Analizziamo anzitutto il movimento dei cavalli e del re.

La soluzione è  analoga e consiste nello sviluppare degli array di bitboard chiamati

BITBOARD cavallo[64];
BITBOARD re[64]

 dove in cavallo[1] sono memorizzate le caselle attaccate da un cavallo in posizione 1 (casella a1), in cavallo[2] sono memorizzate le caselle attaccate da un cavallo che si trova nella casella 2 (casella b1) e così via, vediamo come sarà cavallo [20]:

Lo stesso dicasi per il Re. Sarà poi semplice considerare ogni re e cavallo, leggere i rispettivi valori di cavallo[x] e di re[y] e rimuovere quelle caselle che coinvolgono pezzi amici o catture illegali: ora sappiamo come fare! Valutando per esempio

si può capire se il cavallo in c2 sia o meno un pezzo dei bianchi. (Attenzione io, in questo caso, considero gli array come se partissero da 1, ricordatevi che molti linguaggi considerano come primo indice lo 0)

Gli altri pezzi

Rimane da analizzare il movimento di altri tre pezzi: Torre, Regina, Alfiere; tutti accomunati dal fatto che possono scivolare di una quantità a piacere sulla scacchiera e che si possono muovere in diagonale. Il movimento di questi pezzi è funzione di due parametri:

1. la casella in cui si trovano
2. I pezzi presenti lungo la traiettoria

La soluzione consiste nello sviluppare degli array di bitboard dove si tiene conto e dell'uno e dell'altro parametro. Scindiamo i diversi movimenti e analizziamo per ora solo quello orizzontale

Movimento orizzontale (Torre, Regina)

supponiamo che la scacchiera rappresenti la posizione di tutti i pezzi di qualunque colore che si trovano sulla scacchiera; in rosso è evidenziato il pezzo (torre o regina...è lo stesso!) che vogliamo muovere orizzontalmente lungo la terza traversa:

00000000 00101000 00100000 10000101 01000000 00110010 00000000 00000000

Abbiamo ora bisogno di estrarre informazioni circa il grado di occupazione della riga, come? Considerando la riga, cioè il sottoinsieme di 8 bit che estraiamo dalla bitboard come un numero decimale!

Accederemo così a una tabella di bitboard precedentemente calcolate tramite:

Come estrarre il grado?

grado_di_occupazione = (tutti_pezzi >> (riga * 8)) AND 255;

dove riga rappresenta proprio la riga considerata  e vale 0 per la riga a1-h1, 1 per la riga a2-h2 e così via. Al'inizio del programma avremo cura di creare (una volta e per sempre) una tabella di 64 x 256 bitboard dove ognuna rappresenterà i possibili movimenti orizzontali del pezzo in funzione della casella di partenza e dei pezzi presenti lungo la traiettoria orizzontale.

A tempo di esecuzione basterà calcolare il grado di occupazione della riga e guardare nella tabella per ottenere immediatamente la bitboard con il movimento possibile! Ricordiamoci di filtrarlo con un AND con NOT(pezzi_dello_stesso_colore)

Movimento verticale (Torre, Regina)

Movimento diagonale (Alfiere, Regina)

Ormai il principio dovrebbe essere chiaro: si precalcolano le tabelle di tutti gli spostamenti possibili in funzione della casella e del grado di occupazione della traiettoria; a tempo di esecuzione si calcolano casella e il grado e si accede alla tabella di bitboard. Il problema è sempre rappresentato dal calcolo del grado.

Abbiamo capito che il calcolo del grado consiste nel rappresentare la riga, la colonna o la diagonale come un numero, per fare ciò velocemente è opportuno che la bitboard memorizzi i pezzi lungo la traiettoria desiderata in bit contigui in maniera da dover semplicemente usare una operazione di shiftaggio e un and logico. Se per il movimento verticale avevamo risolto il problema considerando una bitboard ruotata di 90° qui le cose si complicano un po'. State calmi e mantenete il sangue freddo: innanzi tutto scindiamo il movimento lungo le due diagonali e consideriamo per ora solo quello lungo la diagonale a1h8 e alle sue parallele; per calcolare il grado utilizzeremo una bitboard ruotata di 45° in senso orario, dovreste immaginarla cosi:

noi però la rappresenteremo in questo modo:

abbiamo così una bitboard dove le diagonali sono rappresentate in bit contigui, ma dobbiamo ricordarci che non tutte hanno la stessa lunghezza, quindi per effettuare il calcolo del grado di occupazione avremo bisogno di una piccola tabella che in funzione della casella ci dica di quanti bit dobbiamo "shiftare" per far si che la diagonale interessata si allinei con il bit 0 della bitboard, per esempio se il pezzo si trova nella casella b4, la nostra tabella shiftaggi[64] alla voce 25 (cioè la casella b4) ci darà il valore 43, shiftando a destra di 43 posizioni avremo:

00000000 ... e7 f8 a3 b4 c5 d6 f7 g8

il fatto che le diagonali non abbiamo la stessa dimensione ci impedisce di effettuare un and 255 per isolare la stringa, in quanto sarebbero comprese anche le caselle e7 e f8 che non ci interessano, occorre allora un'altra tabella che stavolta memorizzi in funzione della casella il valore con cui effettuare l'and.

Riepilogano, per il calcolo del movimento lungo la diagonale occorrono:

1. una bitboard "tutti i pezzi" ruotata di 45°
2. una tabella che ci dica di quanto dobbiamo shiftare
3. una tabella con il valore di and

Stesso discorso per l'altra diagonale dove la bitboard del tipo "tutti i pezzi" sarà però ruotata di 315°, cioè (45° in senso antiorario). Una ultima considerazione: è piuttosto lento generare di volta in volta le bitboard "ruotate" partendo dalla biboard tutti_pezzi, sarebbe più opportuno generarle la prima volta e aggiornarle di volta in volta.

Considerazioni

Abbiamo visto le strutture dati che ci permetteranno nel proseguo della trattazione di descrivere la scacchiera: non sono le uniche e quella data è una mia implementazione delle teorie generali. Ho deciso di rimandare alla seconda parte del nostro discorso altre strutture dati che ci permettono di ricordare posizioni o scacchiere di riferimento: sono una ottimizzazione futura che nella seconda parte implementeremo, ma che per ora andrebbero solo ad appesantire la discussione.

Un po' di codice

Vediamo come possiamo cominciare ad implementare quanto detto: cominciamo con la struttura che descriverà la nostra scacchiera:

vi ricordate avevo detto che non avremmo utilizzato solo una bitboard, ma diverse: ecco una struttura che ne raccoglie alcune, vedremo poi, via via che ne sorge la necessità, di ampliarla.

Oltre a questa struttura non dmentichiamoci delle tabelle:

e alcune Bitboard di utilità

L'array maschera_casella è pieno di bitboard in cui è posto a 1 il bit corrisposndente all'indice e servira come maschera per una sigola casella; analogamente

L’array pezzi_in_casella ci servirà in seguito per operazioni di utilità.Alcune delle bitboard non cambieranno per tutta la durata delle partita, altre dovranno essere aggiornate, tutte devono essere “riempite”, vediamo come: utilizzeremo un’array di bitboard di comodo:

L'ordine delle caselle sarà

nella bitboard saranno memorizzati così:

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

Per le funzioni di inizializzazione consiglio la visione diretta del codice di Beawulf o Galahad; state attenti che la convenzione è diversa: la scacchiera ha la seguente disposizione:

In sostanza i due autori hanno capovolto la scacchiera tradizionale considerando il nero in basso e il bianco in alto.

Indice

La generazione delle mosse

Sappiamo adesso rappresentare una scacchiera e aggiornarla, vediamo ora come questo si può essere utile nella generazione delle mosse.

Abbiamo detto più volte che le mosse da generare sono molte: se arriviamo a 4 ply abbiamo 35+35²+35³+35⁴=1550000 mosse circa, e pensate che un programma “serio” dovrebbe indagare, in gara, almeno fino a  9/10 ply! Cosa fare? Nell'ambito dei programmi "a forza bruta" si ritrovano due tendenze:

1. generare tutte le mosse in un colpo solo
2. generare le mosse a "gruppi di importanza" e indagarli 

generare tutte le mosse in un colpo solo è certamente più semplice, anche se impegnativo in termini di memoria utilizzata; l'algoritmo di ricerca che useremo in seguito, però, risente molto dell'ordine con cui vengono valutate le mosse, quindi dovremmo inserire (vedremo in seguito come) una fase di ordinamento delle mosse il cui tempo di esecuzione è funzione del numero di mosse generate, d'altra parte anche se generassimo poche mosse per avere un tempo di ordinamento migliore rischieremmo di "perdere per strada" qualche buona mossa: insomma il cane che si morde la coda!Soluzione?Il punto 2: generare le mosse a gruppi di importanza e indagarle via via. 

Ispirandoci a "Crafty" il forte e famoso programma di Hyatt, creeremo tre routine di generazione: la prima genera tutte le catture e le promozioni di pedoni , un’altra genera tutte le mosse che non portano alla cattura di un pezzo, gli arrocchi, l’ultima genera tutte le mosse che si possono fare per fuggire se il re è sotto scacco e verrà utilizzata soltanto in questa occasione.

Attenzione: non confondiamo questo modo di operare con il metodo selettivo, qui generiamo le mosse in tempi diversi e le analizziamo alla ricerca di quello che in seguito definiremo "taglio alto"(la mossa "migliore") se lo troviamo bene ci fermiamo e effettuiamo la mossa, risparmiando tempo altrimenti sotto con il prossimo gruppo di mosse! Un’altra precisazione la generazione delle prime due routine prevede che le mosse generate non siano necessariamente legali (si chiamano pseudolegali) cioè non è detto che tutte siano possibili (alcune potrebbero lasciare il re sotto scacco: vietato dal regolamento), per quanto possa sembrare strano posticipare la verifica di legalità dopo la valutazione ci consente un certo risparmio di tempo (e molto probabile che mosse illegali poiché lasciano il re sotto scacco saranno penalizzate dalla funzione di valutazione e quindi trascurate in fase di ricerca) e di verificare solo quelle mosse che ci interessano! Soltanto l’ultima routine prevede di generare mosse esclusivamente legali

Vediamo un esempio di come si possano generare le mosse di cattura dei un cavalli bianchi 

//Iniziamo un ciclo
BITBOARD partenza,obiettivi;
int da,a;
//estraiamo dalla struttura posizione la bitboard dei cavalli bianchi
partenza=pos->cavalli_bianchi;
//iniziamo un ciclo che terminerà quando non ci saranno più cavalli
while (partenza)
{
 /*estraiamo dalla bitboard la casella in cui si trova il primo bit pari a 1 */
 da=firstbit(partenza);
 /*trovato il bit lo cancelliamo in maniera da non considerare due volte lo stesso  pezzo*/
 partenza = partenza XOR maschera_casella[da];
 /*calcoliamo i possibili obiettivi del cavallo dalla casella in cui si trova*/
 obiettivi = mov_cavallo[da];
 /*consideriamo soltanto le catture*/
 obiettivi = obiettivi AND (pos->pezzi_neri)
 /*iniziamo un secondo ciclo per scandire la bitboard obiettivi e trova*/
 while (obiettivi)
 {
  a=firstbit(obiettivi);
  obiettivi = obiettivi XOR maschera_casella [a];
  .../*si inserisce la mossa nella struttura scelta per rappresentarla*/
 ^}
}

La funzione firstbit evidenziata in rossa serve, data una bitboard, a trovare qual'è il primo bit posto a uno scandendo la bitboard. Può essere implementata in diversi modi: assembly(sfruttando le istruzioni bsf bsr), appogiandosi alla libreria del compilatore oppure in questa maniera: si può precalcolare in un array firstbit[256] per ogni grado di occupazione della sottostringa di 8bit quale è il primo bit posto a 1 e utilizzarlo scandendo la bitboard data.

Se invece volessimo calcolare le mosse di non cattura basterebbe cambiare un unico passo dell'algoritmo presentato: quello evidenziato in blu che diventerebbe:

obiettivi = obiettivi AND (NOT (pezzi_bianchi OR pezzi_neri))

Indice

La ricerca

Siamo adesso in grado, data una scacchiera di partenza, di generare tutte le mosse possibili; come trovare la "migliore"? Visitando questo grafo e applicando una funzione di valutazione che ci dica quanto sia buona la posizione raggiunta! Al momento non entriamo nel dettaglio di come è fatta la funzione: immaginatela come un esperto scacchista a cui comunicate la posizione dei singoli pezzi sulla scacchiera e da cui riceverete come risposta un numero; più il numero è grande migliore è la posizione per noi, più è piccolo (minore di zero) migliore è per il nostro avversario (e quindi peggiore per noi).

Gli scacchi sono un gioco a due giocatori ragion per cui dovremo tenere conto anche delle risposte dell'avversario, l'algoritmo che utilizzeremo prende il nome di "Alpha-Beta" esso però rappresenta il raffinamento di un'altro algoritmo il "Min Max": studiamo anzitutto quest'ultimo.

Min Max

Perché è utile studiare il min max? Perché è utile capire l'idea di fondo che è la stessa di "Alpha Beta" (d'ora in poi AB) . L'idea è questa: immaginate di avere a disposizione il nostro esperto scacchista (la funzione di valutazione), data la situazione iniziale generiamo tutte le mosse possibili e le facciamo valutare all'esperto, chiaramente sceglieremo quella con la valutazione più alta: è la mossa migliore! E il nostro avversario? Beh non possiamo sapere cosa stia pensando, ma assumiamo di metterci nei suoi panni: ciò che è bene per noi è male per lui...e viceversa! State attenti, noi assumiamo non solo che l'avversario valuti la scacchiera nella stessa maniera in cui la valutiamo noi, ma anche che giochi senza mai commettere errori. Per ogni ply che ci riguarda (cioè che contiene le mosse del nostro colore) quindi noi cercheremo di scegliere la mossa che abbia il valore più alto ("Max") per i ply in cui vengono rappresentate le mosse dell'avversario sceglieremo per lui le mosse dal valore più basso ("Min") che sono, per lui, a nostro giudizio, le mosse migliori; vediamo un esempio

Ammettiamo per semplicità che in una possibile posizione della scacchiera abbiamo a disposizione solo due mosse che chiamiamo A e B; per ognuna delle due mosse il nostro avversario può rispondere sempre con due mosse (sempre per semplicità assumiamo che siano sempre le stesse). Vediamo quali sono le possibili combinazioni e delle valutazioni fittizie date dal nostro "esperto"

Abbiamo detto che assumiamo che il nostro avversario giochi sempre perfettamente (questo va a nostro vantaggio: se commette errori meglio per noi!), ragion per cui se giocassimo A il nostro avversario sicuramente risponderà D, d'altra parte se giocassimo B, sebbene non raggiungerei posizioni con valutazioni altissime (come la 20 della sequenza A-C), sarei sicuro che, male che vada, raggiungerei una posizione che mi vede sempre vincitore: il tutto senza dover sperare in un errore dell'avversario!

Rivediamo l'esempio applicato ad un grafo notate che la visita del grafo procede da sinistra verso destra: questo vale per tutti gli algoritmi di ricerca che utilizzeremo

Immaginate che questo grafo rappresenti l'evoluzione della nostra scacchiera fino a ply=2; una volta generati tutti i nodi fino a quella profondità l'algoritmo partendo dai nodi foglia (quelli terminali) comincia ad assegnare un valore per ciascun nodo. I nodi a ply 2 rappresentano le mosse del nostro avversario quindi l'algoritmo provvedera a scegliere la mossa con il valore più basso (la migliore per il nostro avversario) riportandola al nodo genitore: 

A ply=1 dobbiamo invece scegliere la mossa dal valore più alto e quindi scegliamo la mossa che ha valore 4, certi di avere scartato mosse che porterebbero a "tragiche conseguenze".

Vediamo come potremmo codificare l'algoritmo:

Maximize(posizione p)
{
 if (verifica_fine_gioco(p))
   {
     return (Valore(p))
   }
 max_valore = -infinito
 Genera_successori(p)
 for (tutti i successori)
   {
     search= Minimize(ognuno dei successori)
     max_valore = Max(max_valore,search)
   }
 return (max_valore)
}

Minimize(posizione p)
{
 if (verifica_fine_gioco(p))
   {
     return (Valore(p))
   }
 min_valore = +infinito
 Genera_successori(p)
 for (tutti i successori)
   {
     search= Maximize(ognuno dei successori)
     min_valore = Min(min_valore,search)
   }
 return (min_valore)
}

Negamax

Lo stesso algoritmo può essere scritto secondo un'altra formulazione che prende il nome di Negamax e che ritroveremo anche in seguito:

Negamax(posizione p)
{
 if (stop_search(p))
   {
     return (Valutazione(p))
   }
 gamma = -infinito
 Genera_successori(p)
 for (tutti i successori)
   {
     search= -Negamax(ognuno dei successori)
     gamma = Max(gamma,search)
   }
 return (gamma)
}

Le differenze fondamentali con la precedente formulazione sono 3:

L'algoritmo "min-max" è "matematicamente sicuro" cioè ci consiglia ogni volta la mossa migliore che si può effettuare, il problema è che la sua complessità (nel senso del tempo che impiega per svolgere la sua funzione) cresce in maniera esponenziale: per un albero che ha un fattore di ramificazione pari a W e profondità D la complessità è circa W^D  . Il che vuol dire che in un gioco come quello degli scacchi è inapplicabile, ricorriamo allora ad un algoritmo chiamato "alpha-beta" che ispirandosi al "min- max" lo approssima dandoci una soluzione ottima in minor tempo.

Alpha-beta

Domande frequenti

Il sito e questa pagina in particolare stanno riscuotendo un buon successo, al di là della mia immaginazione. Siete in tanti a scrivermi e non ho tanto tempo per rispondere, per cui ho pensato di creare questa faq con le domande più frequenti e le mie risposte.