Agata

Un giorno ho perso a scacchi contro un Stockfish in 11 mosse. Undici. Invece di accettarlo e andare avanti con la mia vita, ho deciso di costruirne il MIO Stockfish, e lo ho chiamato "Agata".

Ora Agata ha un ELO stimato intorno ai 2400. Non per tirarmela ma, solo 1 ogni 400mila persone che leggono questo blog riuscirebbe a batterla. Vediamo quindi come lo ho fatto.

Nota per i non tecnici: siccome non è proprio roba mainstream questa ho preferito essere un po' tecnico nella descrizione del progetto, scusate.

La rappresentazione della scacchiera

Prima di tutto: come tieni una scacchiera in memoria?

La risposta ovvia è un array di 64 elementi, dove ogni cella è un numero che indica quale pezzo c'è lì. 0 per vuoto, 1 per pedone bianco, 2 per cavallo bianco, e così via. Funziona, ma per un motore scacchistico è troppo lento, e il perché diventa chiaro appena capisci che tipo di operazioni servono davvero.

Un motore analizza milioni di posizioni al secondo. Per ognuna deve rispondere a domande tipo: "il re bianco è sotto scacco?" — il che richiede di trovare dove si trovano tutti i pezzi nemici e calcolare se uno di essi attacca la casella del re. Con un array devi scorrere tutti i 64 elementi, filtrare i pezzi avversari, calcolare i loro attacchi. Con 35 mosse possibili per posizione e ricerche a profondità 10+, ogni nanosecondo conta.

La soluzione usata da ogni motore serio è quella dei bitboard.

L'idea sfrutta il fatto che una scacchiera ha esattamente 64 caselle — e un intero a 64 bit ha esattamente 64 bit. Se assegni un bit a ogni casella, hai una rappresentazione perfetta: il bit è 1 se la casella è "attiva", 0 altrimenti.

typedef unsigned long long U64;
 
U64 bitboards[12];   // P, N, B, R, Q, K, p, n, b, r, q, k
U64 occupancies[3];  // [bianco, nero, entrambi]

Agata mantiene 12 bitboard separati, uno per ogni tipo di pezzo (6 bianchi + 6 neri). bitboards[0] è il bitboard dei pedoni bianchi: ha un 1 su ogni casella dove c'è un pedone bianco, 0 ovunque. Più tre bitboard di "occupazione" che tengono traccia di quali caselle sono occupate da pezzi bianchi, neri, o da qualsiasi pezzo.

La mappatura delle caselle è questa: il bit 0 è a8 (angolo in alto a sinistra), il bit 7 è h8, il bit 56 è a1, il bit 63 è h1. In binario, un pedone bianco in e2 è semplicemente il bit numero 52 acceso.

Il punto di forza: le operazioni sulla scacchiera diventano operazioni bitwise su interi a 64 bit, che la CPU esegue in un singolo ciclo di clock. Vuoi sapere se la quarta traversa è completamente libera? Un singolo & con una maschera. Vuoi trovare tutte le caselle attaccate dai pedoni bianchi? Un singolo shift a sinistra di 8 bit (equivalente a "avanzare di una traversa").

#define setSquare(bitboard, square)   ((bitboard) |=  (1ULL << (square)))
#define getSquare(bitboard, square)   ((bitboard) &   (1ULL << (square)))
#define popSquare(bitboard, square)   ((bitboard) &= ~(1ULL << (square)))

Due operazioni tornano continuamente: contare i bit (quanti pezzi di un certo tipo ci sono?) e estrarre il bit meno significativo (trovare la prima casella occupata per iterare sui pezzi).

Per il conteggio uso __popcnt64(), un'istruzione hardware disponibile su qualsiasi CPU x86 moderna che conta i bit a 1 in un intero a 64 bit in un singolo ciclo, letteralmente una singola istruzione assembly POPCNT. Per l'estrazione del bit meno significativo, un trucco algebrico:

int count_bits(U64 bitboard) {
    return __popcnt64(bitboard);
}
 
int get_lsb_index(U64 bitboard) {
    // bitboard & -bitboard isola il bit meno significativo
    // sottrarre 1 trasforma tutti i bit sotto di esso in 1
    // contare quei bit da l'indice
    return count_bits((bitboard & -bitboard) - 1);
}

Il pattern per iterare su tutti i pezzi di un tipo diventa quindi:

U64 bb = bitboards[P]; // pedoni bianchi
while (bb) {
    int square = get_lsb_index(bb); // trova la casella del prossimo pedone
    // ... processa la casella ...
    popSquare(bb, square);          // rimuovi quel bit e vai al prossimo
}

Codifica delle mosse

Una mossa agli scacchi ha molte informazioni: da dove parte, dove arriva, quale pezzo si muove, se cattura qualcosa, se è una promozione (e in che pezzo), se è en passant, se è arrocco. Un approccio naïve sarebbe una struct con tutti questi campi — ma le liste di mosse vengono copiate, ordinate e passate in giro continuamente, e avere oggetti grandi crea pressione sulla cache.

La soluzione è impacchettare tutto in un singolo intero a 32 bit:

bit  0- 5  →  casella di partenza   (6 bit, valori 0-63)
bit  6-11  →  casella di arrivo     (6 bit, valori 0-63)
bit 12-15  →  tipo di pezzo         (4 bit, valori 0-11)
bit 16-19  →  pezzo di promozione   (4 bit, valori 0-11)
bit 20     →  flag cattura
bit 21     →  flag doppio avanzamento pedone
bit 22     →  flag en passant
bit 23     →  flag arrocco

Per esempio, e2e4 — il classico avanzamento del pedone al centro — si codifica con: partenza = casella 52 (e2), arrivo = casella 36 (e4), pezzo = pedone bianco (0), nessuna promozione, nessuna cattura, flag doppio avanzamento = 1. Tutto in un int.

Le macro di accesso usano maschere e shift:

#define get_move_source(move)    ((move) & 0x3f)
#define get_move_target(move)    (((move) >> 6) & 0x3f)
#define get_move_piece(move)     (((move) >> 12) & 0xf)
#define get_move_promoted(move)  (((move) >> 16) & 0xf)
#define get_move_capture(move)   ((move) & 0x100000)

La lista mosse è semplicemente un array a dimensione fissa. 256 elementi sono sempre abbondanti: il massimo teorico di mosse legali in qualsiasi posizione scacchistica è 218 (una posizione particolarmente caotica con molte promozioni), e nella stragrande maggioranza dei casi sono 30-40.

typedef struct {
    int moves[256];
    int count;
} moves;

Tabelle di attacco e Magic Bitboards

Per calcolare le mosse legali, il problema centrale è determinare quali caselle attacca ogni pezzo dalla sua posizione.

Per i pezzi che non scivolano (pedoni, cavalli, re) è semplice: le caselle attaccate dipendono solo dalla casella di partenza, indipendentemente dagli altri pezzi sulla scacchiera. Si precalcolano all'avvio e si mettono in tabella:

U64 pawn_attacks[2][64];   // [colore][casella]
U64 knight_attacks[64];
U64 king_attacks[64];

Gli attacchi del pedone bianco si calcolano con shift e maschere di file. Il pedone in e4 (bit 36) attacca d5 (bit 27) e f5 (bit 29), cioè i bit 36-9 e 36-7. Le maschere di file evitano un bug sottile: senza di esse un pedone in h4 sembrerebbe attaccare a5 (perché lo shift "avvolge" attorno al bordo della scacchiera, il bit scivola dall'ultima colonna alla prima):

attacks |= (bitboard >> 7) & not_a_file;  // cattura verso destra
attacks |= (bitboard >> 9) & not_h_file;  // cattura verso sinistra

Per alfieri, torri e regine il problema è fondamentalmente diverso. Questi pezzi scivolano lungo file, traverse e diagonali, e si fermano quando incontrano un altro pezzo. Una torre in a1 con la colonna a libera attacca a2, a3, ..., a8. Ma se c'è un pedone in a4, si ferma lì (o a a4 stesso se lo cattura). Le caselle attaccate dipendono non solo dalla posizione della torre ma da dove si trovano tutti gli altri pezzi.

La soluzione bruta sarebbe: per ogni posizione della torre, itera lungo i 4 raggi (su, giù, sinistra, destra) fino al bordo o a un pezzo bloccante. Funziona, ma in un ciclo di ricerca che chiama questa funzione decine di milioni di volte, è troppo lenta.

Magic Bitboards

L'idea è precalcolare tutte le possibili configurazioni di attacco e indicizzarle con una funzione hash perfetta.

Primo passo: la maschera dei bloccanti. Per ogni casella, identifica le caselle che possono effettivamente bloccare il pezzo. Per una torre in e4, queste sono le caselle interne della colonna e e della traversa 4 — i bordi vengono esclusi perché la torre li raggiunge sempre comunque (non possono bloccare, al massimo fermano lo scivolamento sul bordo stesso).

La maschera per una torre in e4 ha circa 10-12 bit accesi. Questo significa che ci sono 2^10 = 1024 o 2^12 = 4096 possibili disposizioni dei pezzi bloccanti su quelle caselle.

Secondo passo: trovare il numero magico. Per ogni casella, si cerca una costante a 64 bit — il "magic number" — tale che questa formula:

indice = (occupazione & maschera) * magic >> (64 - n_bit_rilevanti)

mappi ogni configurazione di bloccanti in un indice unico in una tabella compatta. La moltiplicazione + shift funziona come una funzione hash: mescola i bit dell'occupazione in modo da comprimerli in un piccolo indice senza collisioni.

I magic numbers vengono trovati con ricerca random: si generano costanti casuali finché non se ne trova una che funziona (nessuna collisione per nessuna delle 4096 configurazioni). Non c'è una formula analitica — sono semplicemente numeri fortunati. I numeri trovati per Agata:

const U64 rook_magic_numbers[64] = {
    0x8a80104000800020ULL,
    0x140002000100040ULL,
    // ... 62 altri
};

Terzo passo: riempire le tabelle. All'avvio, per ogni casella e per ogni configurazione di bloccanti, si calcola il bitboard degli attacchi reali (col metodo lento, che va bene dato che lo fai una volta sola) e si salva nella tabella indicizzata dal magic:

U64 rook_attacks[64][4096];   // ~2MB
U64 bishop_attacks[64][512];  // ~256KB

A runtime, trovare le caselle attaccate da una torre diventa una singola operazione:

U64 get_rook_attacks(int square, U64 occupancy) {
    occupancy &= rook_masks[square];           // tieni solo i bloccanti rilevanti
    occupancy *= rook_magic_numbers[square];   // "mescola" i bit
    occupancy >>= 64 - rook_relevant_bits[square]; // comprimi all'indice
    return rook_attacks[square][occupancy];    // lookup O(1)
}

Tre operazioni invece di un ciclo che scorre i raggi. La regina è semplicemente l'unione degli attacchi di alfiere e torre:

U64 get_queen_attacks(int square, U64 occupancy) {
    return get_bishop_attacks(square, occupancy)
         | get_rook_attacks(square, occupancy);
}

Il costo in memoria è circa 800KB — un compromesso assolutamente conveniente dato che permette di generare le mosse dei pezzi scorrevoli alla stessa velocità dei cavalli.

Generazione delle mosse

Con le tabelle pronte, generate_moves() produce tutte le mosse possibili per il lato che deve muovere. Una precisazione importante: genera mosse pseudo-legali, cioè geometricamente valide ma che potrebbero lasciare il re sotto scacco. La verifica della legalità piena avviene dopo, in make_move().

Perché non generare solo mosse legali direttamente? Perché controllare la legalità richiede di applicare la mossa e vedere se il re è sotto scacco — un'operazione costosa. È più efficiente generare tutto e scartare le illegali durante la ricerca, dove molte mosse vengono comunque potate prima di essere esplorate.

L'arrocco è il caso speciale più delicato: richiede caselle intermedie libere, re non sotto scacco, e il re non deve passare per una casella attaccata:

if (castle & wk) {  // se il bianco ha ancora il diritto all'arrocco corto
    if (!getSquare(occupancies[both], f1) &&
        !getSquare(occupancies[both], g1) &&
        !is_square_attacked(e1, black) &&   // re non in scacco
        !is_square_attacked(f1, black))     // f1 non attaccata (il re ci passa)
        add_move(encode_move(e1, g1, K, 0, 0, 0, 0, 1));
}

La funzione is_square_attacked() usa un trucco elegante: per sapere se una casella è attaccata da un certo lato, si fa come se ci fosse un pezzo "ipotetico" su quella casella e si controlla se attaccherebbe qualcosa. Se metti ipoteticamente un alfiere su e1 e lui "vede" un alfiere avversario lungo la diagonale, allora e1 è attaccata da quell'alfiere — il ragionamento funziona in entrambe le direzioni perché gli attacchi sono simmetrici.

int is_square_attacked(int square, int side) {
    // se un pedone del lato opposto fosse qui, vedrebbe un pedone avversario?
    if (pawn_attacks[side^1][square] & bitboards[side ? P : p])  return 1;
    if (knight_attacks[square]       & bitboards[side ? N : n])  return 1;
    if (get_bishop_attacks(square, occupancies[both]) & bitboards[side ? B : b]) return 1;
    if (get_rook_attacks(square,   occupancies[both]) & bitboards[side ? R : r]) return 1;
    if (get_queen_attacks(square,  occupancies[both]) & bitboards[side ? Q : q]) return 1;
    if (king_attacks[square]        & bitboards[side ? K : k])  return 1;
    return 0;
}

Fare e disfare le mosse

Durante la ricerca, il motore applica e poi annulla milioni di mosse. La domanda è: come "tornare indietro" dopo aver applicato una mossa?

Ci sono due approcci. Il primo — unmake move — inverte ogni singola modifica fatta alla scacchiera: rimette il pezzo dove era, ripristina il pezzo catturato, ripristina i diritti di arrocco precedenti, e così via. È più veloce ma molto più complesso da implementare correttamente (ci sono decine di casi speciali).

Il secondo — copy-restore — salva l'intero stato della scacchiera prima di applicare una mossa, e lo ripristina con un memcpy se serve annullare. Più semplice, leggermente più lento, ma abbondantemente sufficiente per un motore single-threaded.

#define copy_board() \
    U64 bitboards_copy[12], occupancies_copy[3]; \
    int side_copy, castle_copy, enpassant_copy; \
    U64 hash_key_copy; \
    memcpy(bitboards_copy, bitboards, sizeof(bitboards)); \
    memcpy(occupancies_copy, occupancies, sizeof(occupancies)); \
    side_copy = side; castle_copy = castle; \
    enpassant_copy = enpassant; hash_key_copy = hash_key;
 
#define take_back() \
    memcpy(bitboards, bitboards_copy, sizeof(bitboards)); \
    memcpy(occupancies, occupancies_copy, sizeof(occupancies)); \
    side = side_copy; castle = castle_copy; \
    enpassant = enpassant_copy; hash_key = hash_key_copy;

I diritti di arrocco sono codificati in 4 bit (uno per ogni tipo: arrocco corto bianco, lungo bianco, corto nero, lungo nero). Invece di scrivere una serie di if per ogni mossa che potrebbe invalidarli, uso una tabella di lookup: ogni casella della scacchiera ha un valore che, in AND con i diritti correnti, azzera automaticamente i bit giusti. Qualsiasi mossa da o verso e1 toglie entrambi i diritti al bianco, qualsiasi mossa da h1 toglie il corto bianco, e così via:

const int castling_rights[64] = {
 7, 15, 15, 15,  3, 15, 15, 11,  // traversa 8: toccare a8 azzera arrocco lungo nero, h8 azzera corto nero
 // ...
13, 15, 15, 15, 12, 15, 15, 14   // traversa 1: toccare a1 azzera arrocco lungo bianco, ecc.
};
 
castle &= castling_rights[source];
castle &= castling_rights[target];

Zobrist Hashing

Ogni posizione scacchistica ha una chiave hash a 64 bit associata. Serve a due cose: riconoscere quando la stessa posizione si ripete (triplice ripetizione = patta) e, in futuro, indicizzare una transposition table per non ricercare la stessa posizione due volte.

L'approccio di Zobrist (1970) funziona così: all'avvio, genera un numero random a 64 bit per ogni combinazione possibile di (tipo di pezzo, casella) — 12 × 64 = 768 numeri. Più un numero per ogni combinazione di diritti di arrocco (16 combinazioni), uno per ogni casella di en passant (64), e uno per indicare "tocca al nero".

La chiave di una posizione è lo XOR di tutti i numeri corrispondenti ai pezzi presenti e allo stato corrente:

U64 piece_keys[12][64];
U64 enpassant_keys[64];
U64 castle_keys[16];
U64 side_key;

La proprietà fondamentale dello XOR è che è invertibile: se fai A ^ B, puoi tornare ad A rifacendo ^ B. Questo rende gli aggiornamenti della chiave incrementali — invece di ricalcolare tutto da zero dopo ogni mossa, si fa XOR con i soli cambiamenti:

hash_key ^= piece_keys[piece][source];  // "rimuovi" il pezzo dalla casella di partenza
hash_key ^= piece_keys[piece][target];  // "aggiungi" il pezzo alla casella di arrivo
hash_key ^= side_key;                   // cambia il turno
// aggiorna en passant e diritti arrocco con lo stesso meccanismo...

Con 64 bit, la probabilità che due posizioni diverse abbiano la stessa chiave (una "collisione") è circa 1 su 18 miliardi di miliardi — praticamente nulla.

La ricerca: Negamax Alpha-Beta

Qui sta la vera intelligenza del motore.

Per trovare la mossa migliore, il motore deve esplorare l'albero di gioco: dalla posizione corrente, genera tutte le mosse possibili, poi per ognuna genera tutte le risposte avversarie, poi tutte le risposte a quelle risposte, e così via fino a una certa profondità. Alla fine di ogni sequenza, valuta la posizione. La mossa migliore è quella che porta alla posizione con il punteggio più alto.

Il problema è la dimensione di quest'albero. Con circa 35 mosse possibili per posizione e una ricerca a profondità 10, si ottengono 35^10 ≈ 2.7 × 10^15 posizioni. Anche con un miliardo di posizioni al secondo, ci vorrebbero anni.

Minimax e Negamax

L'algoritmo base è minimax: il bianco vuole massimizzare il punteggio, il nero vuole minimizzarlo. Si alternano: quando è il turno del bianco si sceglie la mossa col punteggio più alto, quando è il turno del nero si sceglie quella col punteggio più basso (per il bianco).

Negamax è una variante più elegante che sfrutta il fatto che gli scacchi sono un gioco a somma zero: quello che è buono per uno è ugualmente cattivo per l'altro. Invece di avere due casi separati (massimizza/minimizza), si nega semplicemente il punteggio ad ogni livello e si massimizza sempre:

negamax(posizione, profondità):
    se profondità == 0: restituisci valuta(posizione)
    punteggio_migliore = -infinito
    per ogni mossa:
        fai_mossa()
        punteggio = -negamax(posizione, profondità - 1)  // il "-" ribalta la prospettiva
        disfai_mossa()
        punteggio_migliore = max(punteggio_migliore, punteggio)
    return punteggio_migliore

Alpha-Beta Pruning

Alpha-beta è l'ottimizzazione che rende la ricerca praticabile. L'intuizione: se mentre stai analizzando una mossa scopri che l'avversario ha già una risposta che ti porta in una posizione peggiore di quella che puoi già garantirti con un'altra mossa, puoi smettere di analizzare quella mossa — non cambierà mai la tua scelta.

Si tengono due variabili:

• Alpha: il punteggio migliore che il giocatore corrente può già garantirsi con le mosse analizzate finora. "So già che posso fare almeno questo bene."
• Beta: il punteggio migliore che l'avversario può garantirsi. "L'avversario non mi lascerà fare meglio di questo."

Se in qualsiasi momento il punteggio di una mossa supera beta — cioè è così buono che l'avversario non lo permetterà mai (perché avrebbe già potuto evitare di arrivare qui) — si taglia l'intero sottoalbero. È un beta cutoff.

int negamax(int alpha, int beta, int depth) {
    pv_length[ply] = ply;
 
    if (depth == 0)
        return quiescence(alpha, beta);
 
    if (ply && is_repetition())
        return 0;  // patta per ripetizione
 
    nodes++;
 
    int in_check = is_square_attacked(
        get_lsb_index(bitboards[side == white ? K : k]),
        side ^ 1
    );
 
    if (in_check) depth++;  // estendi la ricerca quando si è sotto scacco
 
    int legal_moves = 0;
    moves move_list;
    generate_moves(&move_list);
    sort_moves(&move_list);
 
    for (int i = 0; i < move_list.count; i++) {
        copy_board();
        ply++;
 
        if (!make_move(move_list.moves[i], all_moves)) {
            ply--;
            continue;  // mossa illegale (lascia il re in scacco)
        }
        legal_moves++;
 
        int score = -negamax(-beta, -alpha, depth - 1);
 
        ply--;
        take_back();
 
        if (score >= beta)
            return beta;  // beta cutoff: l'avversario eviterà questa posizione
 
        if (score > alpha) {
            alpha = score;
            // aggiorna la variante principale (la sequenza di mosse migliori trovata)
            pv_table[ply][ply] = move_list.moves[i];
            for (int j = ply + 1; j < pv_length[ply + 1]; j++)
                pv_table[ply][j] = pv_table[ply + 1][j];
            pv_length[ply] = pv_length[ply + 1];
        }
    }
 
    if (legal_moves == 0)
        return in_check ? -49000 + ply : 0;  // matto o stallo
 
    return alpha;
}

Il punteggio del matto è ply-dipendente: -49000 + ply. Se il motore trova un matto in 3 mosse e uno in 5, il primo ha un punteggio più alto (meno ply sottratti), quindi lo preferisce. Senza questo dettaglio, il motore troverebbe il matto ma potrebbe scegliere la sequenza più lunga senza motivo.

La variante principale (PV, principal variation) è la sequenza di mosse migliori che il motore ha trovato. È mantenuta in una tabella triangolare pv_table[ply][ply] e viene visualizzata nella riga info del protocollo UCI — è quello che vedi scorrere quando guardi una GUI mentre l'engine analizza.

Nel caso ottimale, alpha-beta riduce il fattore di ramificazione effettivo da 35 a circa √35 ≈ 6. Questo significa che con lo stesso numero di nodi si raggiunge il doppio della profondità — la differenza tra trovare un matto in 5 e uno in 10.

Quiescence Search

Immagina questa situazione: la ricerca principale si ferma a profondità 8. L'ultima mossa esaminata è Dxe5 — la regina cattura un pedone in e5. Il motore valuta la posizione e vede: "sono avanti di un pedone, ottimo". Gioca quella mossa.

Il problema: il motore non ha visto che il prossimo turno l'avversario fa Axe5, ricatturando il pedone con l'alfiere. La regina è in attacco, deve spostarsi, e alla fine è semplicemente in parità. Il motore ha scambiato una mossa basandosi su una valutazione sbagliata perché si era fermato a metà di uno scambio.

Questo è l'effetto orizzonte: il motore vede solo fino alla sua profondità, e la valutazione alla foglia è spesso inaccurata perché la posizione è tatticamente instabile.

La quiescence search risolve il problema: invece di chiamare evaluate() direttamente a profondità 0, si chiama quiescence(), che continua la ricerca ma considera solo le catture finché la posizione non si stabilizza:

int quiescence(int alpha, int beta) {
    nodes++;
 
    // "Standing pat": il valore della posizione senza fare altre catture.
    // Il motore può sempre scegliere di non catturare — quindi questo è il minimo garantito.
    int stand_pat = evaluate();
 
    if (stand_pat >= beta) return beta;  // già troppo buono, l'avversario lo evita
    if (stand_pat > alpha) alpha = stand_pat;
 
    moves capture_list;
    generate_moves(&capture_list);  // genera solo catture
    sort_moves(&capture_list);
 
    for (int i = 0; i < capture_list.count; i++) {
        copy_board();
        ply++;
 
        if (!make_move(capture_list.moves[i], only_captures)) {
            ply--;
            continue;
        }
 
        int score = -quiescence(-beta, -alpha);
 
        ply--;
        take_back();
 
        if (score >= beta) return beta;
        if (score > alpha) alpha = score;
    }
 
    return alpha;
}

Lo "standing pat" è cruciale: il motore può sempre scegliere di non catturare nulla, il che stabilisce un limite inferiore. In una posizione con 10 catture possibili, il motore esplorerà solo quelle che migliorano realmente la posizione.

In pratica la quiescence aggiunge un numero relativamente piccolo di nodi ma risolve completamente il problema degli scambi a metà. Senza di essa, qualsiasi motore commetterebbe errori tattici elementari.

Ordinamento delle mosse

Alpha-beta è efficiente solo se le mosse buone vengono analizzate per prime. Per capire quanto conta, considera questo: se la mossa migliore è sempre la prima analizzata, ogni nodo porta quasi certamente a un cutoff immediato e l'albero si riduce al minimo. Se invece le mosse arrivano in ordine casuale, molti sottoalberi vengono esplorati inutilmente prima di trovare il cutoff.

La differenza non è trascurabile: un buon ordinamento può ridurre il numero di nodi di un fattore 10x o più rispetto a nessun ordinamento.

Agata usa un sistema di punteggi a priorità decrescente:

1. PV move (punteggio: 20000) — la mossa migliore trovata nell'iterazione di ricerca precedente (l'iterative deepening viene spiegato dopo). È quasi certamente ancora la mossa migliore e porta quasi certamente a un cutoff immediato.

2. MVV/LVA — Most Valuable Victim, Least Valuable Attacker (10000+) — per le catture, si prioritizzano quelle "buone": catturare una regina con un pedone è un affare (vale +900 in materiale), catturare un pedone con una regina è rischioso. La tabella MVV/LVA codifica questo: righe = attaccante, colonne = vittima.

const int mvv_lva[12][12] = {
//   Ped  Cav  Alf  Tor  Reg  Re  (vittime, dal meno al più prezioso)
    {105, 205, 305, 405, 505, 605, ...},  // Pedone attaccante
    {104, 204, 304, 404, 504, 604, ...},  // Cavallo attaccante
    // ...
};

Pedone cattura Regina (605) batte sempre Cavallo cattura Pedone (104), indipendentemente dal resto.

3. Killer moves (9000 e 8000) — una mossa "killer" è una mossa non-cattura che ha causato un beta cutoff in un altro ramo dell'albero allo stesso livello di profondità (lo stesso "ply"). L'intuizione: se questa mossa era così buona da tagliare la ricerca in un altro contesto, potrebbe farlo anche qui.

Il "ply" è la distanza dalla radice: ply 0 è la posizione iniziale, ply 1 è dopo una mossa, ply 2 dopo due mosse, ecc. Si tengono due killer per ply in LIFO:

int killer_moves[2][64];  // [slot 0/1][ply]
 
// dopo un beta cutoff su mossa silenziosa:
killer_moves[1][ply] = killer_moves[0][ply];  // sposta il vecchio killer nel secondo slot
killer_moves[0][ply] = move;                  // salva il nuovo killer nel primo slot

4. History heuristic — per le mosse silenziose rimanenti, si usa uno storico: ogni volta che una mossa non-cattura causa un beta cutoff, il suo "punteggio storia" aumenta proporzionalmente alla profondità della ricerca (cutoff a profondità alta sono più significativi). Le mosse con storia alta vengono provate prima.

int history_moves[12][64];  // [pezzo][casella di arrivo]
 
history_moves[get_move_piece(move)][get_move_target(move)] += depth;

Tecniche di pruning

L'ordinamento migliora alpha-beta riducendo il numero di nodi esplorati. Il pruning va oltre: taglia interi sottoalberi che con alta probabilità non cambieranno la valutazione finale.

Null Move Pruning

L'idea si basa su un'osservazione empirica: nella maggior parte delle posizioni, fare una mossa è meglio che passare il turno. Se anche "passando" (dando il turno all'avversario senza muovere nulla) la posizione è così buona da superare beta, allora il nostro vantaggio è talmente evidente che non ha senso continuare ad analizzare questa linea in profondità.

Si implementa letteralmente saltando il turno — si cambia il lato che muove senza applicare alcuna mossa, si fa una ricerca ridotta (depth - 1 - R, dove R=2 è il fattore di riduzione), e se il risultato supera beta si taglia:

if (depth >= 3 && !in_check && ply > 0) {
    copy_board();
    ply++;
 
    side ^= 1;  // passa il turno
    if (enpassant != no_sq) hash_key ^= enpassant_keys[enpassant];
    enpassant = no_sq;
    hash_key ^= side_key;
 
    int score = -negamax(-beta, -beta + 1, depth - 1 - 2);  // ricerca con R=2
 
    ply--;
    take_back();
 
    if (score >= beta)
        return beta;  // anche passando siamo in vantaggio: tagliamo
}

Questo pruning va disabilitato in posizioni di zugzwang — situazioni in cui qualsiasi mossa peggiora la posizione (il passaggio sarebbe la mossa migliore, ma non è legale agli scacchi). Lo zugzwang si verifica quasi esclusivamente nei finali di re e pedoni, dove ogni mossa del re cede terreno. Il controllo !in_check è già un filtro parziale, ma in implementazioni più avanzate si disabilita il null move negli endgame.

Late Move Reduction (LMR)

Dopo un buon ordinamento mosse, le prime 3-4 mosse sono quelle più probabili di essere buone. Le mosse successive — specialmente le non-catture — sono statisticamente molto meno promettenti. LMR riduce la profondità di ricerca per queste mosse tardive, scommettendo che non cambieranno la valutazione finale.

if (moves_searched >= 4 &&   // dopo le prime 4 mosse
    depth >= 3 &&             // solo a profondità significativa
    !in_check &&              // non sotto scacco (troppo forzante)
    !get_move_capture(move) && // non catture
    !get_move_promoted(move))  // non promozioni
{
    // ricerca ridotta a depth-2 con finestra zero (alpha-1, alpha)
    // una "finestra zero" verifica solo se il punteggio supera alpha, non di quanto
    score = -negamax(-alpha - 1, -alpha, depth - 2);
} else {
    score = alpha + 1;  // forza la ricerca completa nel blocco sotto
}
 
// Se LMR trova qualcosa di promettente, ri-cerca a profondità piena per confermare
if (score > alpha) {
    score = -negamax(-alpha - 1, -alpha, depth - 1);
    // se anche questa ricerca a finestra zero è promettente, fai la ricerca completa
    if (score > alpha && score < beta)
        score = -negamax(-beta, -alpha, depth - 1);
}

La "finestra zero" (-alpha-1, -alpha) è una tecnica in sé: una finestra di ampiezza 1 che risponde solo alla domanda "questo nodo supera alpha sì o no?" senza valutarlo con precisione. È più veloce perché taglia quasi tutto.

Il rischio di LMR è ridurre una mossa che in realtà è buona. Per questo il meccanismo di ri-ricerca è fondamentale: se la ricerca ridotta restituisce un punteggio promettente, si ri-cerca a profondità piena per avere la certezza. In pratica, la stragrande maggioranza delle mosse tardive è effettivamente scarsa e la ri-ricerca non viene quasi mai attivata.

Check Extension

Quando si è sotto scacco, la posizione è forzante: ci sono pochissime risposte legali, spesso una o due. Saltare la ricerca di queste risposte perché si è raggiunta la profondità massima sarebbe un errore grave — si rischierebbe di subire un matto non previsto.

if (in_check) depth++;

Un'unica riga che garantisce che la ricerca non si fermi mai nel mezzo di una sequenza di scacchi. L'esplosione dell'albero che potrebbe derivarne è contenuta dal fatto che il numero di mosse legali sotto scacco è tipicamente molto basso (1-5), quindi l'estensione aggiunge pochi nodi in pratica.

La funzione di valutazione

Quando la ricerca si ferma — o la quiescence search non trova più catture — evaluate() assegna un punteggio alla posizione. Questa funzione è chiamata decine o centinaia di milioni di volte per partita: deve essere veloce e accurata.

I punteggi sono espressi in centipedoni: 100 = valore di un pedone. Un vantaggio di +250 significa che il motore stima di essere avanti di 2.5 pedoni in materiale+posizione. Un punteggio negativo significa svantaggio. Il punteggio del matto è ±49000 — abbondantemente sopra qualsiasi vantaggio materiale, così che il motore preferisce sempre trovare il matto piuttosto che accumulare materiale.

Materiale

const int material_score[12] = {
    100, 300, 350, 500, 1000, 10000,   // bianco: ped, cav, alf, tor, reg, re
   -100,-300,-350,-500,-1000,-10000    // nero (negativo perché il bianco vuole massimizzare)
};

L'alfiere vale 350 contro i 300 del cavallo. Questo riflette il vantaggio empirico della "coppia di alfieri" nelle posizioni aperte, dove le lunghe diagonali libere amplificano il loro raggio d'azione. In posizioni chiuse con catene di pedoni, i cavalli sono spesso più utili. Usare 350 invece di 300 fa sì che il motore sia restio a cedere un alfiere per un cavallo senza compensazione.

Tabelle pezzo-casella

Il materiale da solo non basta. Un cavallo in a1 vale tecnicamente lo stesso di un cavallo in e4, ma in pratica il secondo attacca 8 caselle, il primo solo 2. Le tabelle pezzo-casella (piece-square tables) aggiungono un bonus o malus posizionale che dipende dalla casella:

const int pawn_score[64] = {
     0,   0,   0,   0,   0,   0,   0,   0,
    90,  90,  90,  90,  90,  90,  90,  90,  // traversa 7: a una mossa dalla promozione
    30,  30,  50,  70,  70,  50,  30,  30,  // traversa 6: avanzamento centrale premiato
    10,  10,  20,  50,  50,  20,  10,  10,  // traversa 5: centro vale di più
     5,   5,  10,  40,  40,  10,   5,   5,  // traversa 4
     0,   0,   0,  20,  20,   0,   0,   0,  // traversa 3
     5,  -5, -10,   0,   0, -10,  -5,   5,  // traversa 2: leggera penalità se non sviluppati
     0,   0,   0,   0,   0,   0,   0,   0   // traversa 1 (irraggiungibile in pratica)
};
 
const int knight_score[64] = {
    -50,-40,-30,-30,-30,-30,-40,-50,  // bordo: il cavallo qui è inutile
    -40,-20,  0,  0,  0,  0,-20,-40,
    -30,  0, 10, 15, 15, 10,  0,-30,
    -30,  5, 15, 20, 20, 15,  5,-30,  // centro: il cavallo qui attacca 8 caselle
    -30,  0, 15, 20, 20, 15,  0,-30,
    -30,  5, 10, 15, 15, 10,  5,-30,
    -40,-20,  0,  5,  5,  0,-20,-40,
    -50,-40,-30,-30,-30,-30,-40,-50   // angoli: -50, il cavallo ci "muore"
};

Questi numeri codificano principi scacchistici fondamentali: i pedoni valgono di più avanzati verso la promozione, i cavalli al centro controllano molte più caselle che ai bordi ("cavallo al bordo, soldato perduto"), i re devono stare al riparo nell'apertura e nel mediogioco ma centralizzarsi nel finale.

Per i pezzi neri si usa una mirror table che riflette la scacchiera verticalmente, così le stesse tabelle funzionano per entrambi i colori senza duplicarle. Un pedone nero in e5 usa lo stesso bonus positionale di un pedone bianco in e4 (la casella speculare).

Accumulazione del punteggio

int evaluate() {
    int score = 0;
 
    for (int piece = P; piece <= k; piece++) {
        U64 bb = bitboards[piece];
        while (bb) {
            int square = get_lsb_index(bb);
            score += material_score[piece];  // materiale (positivo per bianco, negativo per nero)
 
            switch (piece) {
                case P: score += pawn_score[square];                      break;
                case p: score -= pawn_score[mirror_score[square]];        break;
                case N: score += knight_score[square];                    break;
                case n: score -= knight_score[mirror_score[square]];      break;
                // ... tutti i 12 tipi
            }
            popSquare(bb, square);
        }
    }
 
    // il punteggio è sempre dal punto di vista del lato che muove
    return (side == white) ? score : -score;
}

Il ritorno finale con la negazione per il nero è importante: la ricerca negamax si aspetta che evaluate() restituisca sempre un punteggio "positivo = buono per me", indipendentemente dal colore. Quindi se è il turno del nero e lui è in vantaggio, il punteggio materiale grezzo sarebbe negativo (il bianco ha meno), ma va restituito come positivo.

Questa valutazione è intenzionalmente semplice. I motori più forti aggiungono analisi della struttura pedonale (pedoni passati, isolati, doppiati), punteggi di mobilità (quante caselle attacca ogni pezzo), sicurezza del re (scudo di pedoni, colonne aperte vicino al re) e logica specifica per l'endgame. Queste sono sul roadmap per v3.

Iterative Deepening e Aspiration Windows

Una domanda ragionevole: perché non fare subito la ricerca alla profondità massima disponibile?

La risposta ha a che fare con il time management. In una partita reale, il motore ha un budget di tempo limitato per ogni mossa. Non sa in anticipo quanta profondità riuscirà a raggiungere nel tempo disponibile. Se inizia una ricerca a profondità 12 e il tempo scade quando ha analizzato metà dell'albero, non ha nessuna mossa da giocare.

L'iterative deepening risolve questo: si cerca a profondità 1, poi 2, poi 3, e così via. Ogni iterazione completa prima di iniziare quella successiva. Quando scade il tempo, si gioca la mossa migliore trovata nell'ultima iterazione completata.

C'è un secondo vantaggio: l'ordinamento mosse. La mossa migliore trovata alla profondità d è quasi sempre ancora la migliore alla profondità d+1. Usarla come prima mossa da esaminare garantisce cutoff immediati e rende la ricerca più profonda molto più efficiente.

L'overhead di ripetere il lavoro è trascurabile perché l'albero cresce esponenzialmente: la profondità 10 richiede circa 35 volte più nodi della profondità 9, quindi tutta la ricerca fino alla profondità 9 è meno del 3% del lavoro totale della profondità 10.

Aspiration Windows

Nell'iterative deepening, il punteggio dell'iterazione precedente è una buona stima del punteggio della prossima. Le aspiration windows sfruttano questo: invece di partire con la finestra completa [-50000, +50000], si usa una finestra stretta centrata sul punteggio precedente, per esempio [score-50, score+50].

Una finestra più stretta significa alpha e beta più vicini, il che produce molti più cutoff e rende la ricerca significativamente più veloce. Se il punteggio cade fuori dalla finestra (perché la posizione è cambiata drammaticamente), si allarga a tutto e si ri-cerca — ma nella stragrande maggioranza dei casi la finestra stretta funziona:

int alpha = -50000, beta = 50000;  // prima iterazione: finestra completa
 
for (int current_depth = 1; current_depth <= search_depth; current_depth++) {
    int score = negamax(alpha, beta, current_depth);
 
    if (score <= alpha || score >= beta) {
        // fallito fuori dalla finestra: ri-cerca con finestra completa
        alpha = -50000;
        beta  =  50000;
        score = negamax(alpha, beta, current_depth);
    }
 
    // imposta finestra stretta per la prossima iterazione (±50 centipedoni)
    alpha = score - 50;
    beta  = score + 50;
 
    printf("info score cp %d depth %d nodes %lld pv ", score, current_depth, nodes);
    for (int i = 0; i < pv_length[0]; i++) print_move(pv_table[0][i]);
    printf("\n");
}

Protocollo UCI

Agata comunica con le GUI scacchistiche tramite il protocollo UCI (Universal Chess Interface) — lo standard del settore. Il motore legge comandi da stdin e scrive risposte su stdout, secondo un protocollo testuale specifico:

• La GUI manda uci → il motore risponde con il nome e uciok
• La GUI manda position startpos moves e2e4 e7e5 ... → il motore aggiorna la scacchiera
• La GUI manda go wtime 60000 btime 60000 movestogo 40 → il motore inizia la ricerca
• Il motore risponde con righe info depth X score cp Y pv ... durante la ricerca
• Il motore risponde con bestmove e2e4 quando ha finito

void uci_loop() {
    printf("id name Agata\n");
    printf("id author Filippo Maretti\n");
    printf("uciok\n");
 
    while (1) {
        fgets(input, sizeof(input), stdin);
 
        if (!strncmp(input, "isready", 7))       printf("readyok\n");
        else if (!strncmp(input, "position", 8)) parse_position(input);
        else if (!strncmp(input, "go", 2))       parse_go(input);
        else if (!strncmp(input, "quit", 4))     break;
    }
}

La gestione del tempo: il comando go include wtime e btime (tempo residuo in ms per bianco e nero), winc/binc (incremento per mossa), e movestogo (mosse alla prossima time control). Da questi si calcola quanto tempo spendere per questa mossa:

stoptime = get_time_ms() + time / movestogo + inc / 2 - 50;

La ricerca controlla il tempo ogni 2047 nodi — usando una maschera bit (nodes & 2047) == 0 invece di un modulo, che è leggermente più veloce. Il -50 è un margine di sicurezza per evitare di sforare il tempo per via della latenza.

Il motore include anche una modalità server TCP che accetta comandi UCI su porta 8080 — utile per integrarlo in applicazioni web senza doverlo lanciare come subprocess.

Perft: verificare la correttezza

Come fai a sapere che il generatore di mosse è corretto? Non puoi semplicemente giocare e sperare che i bug saltino fuori — molti bug nei casi speciali (en passant, arrocco sotto scacco, promozioni con cattura) emergono solo in posizioni rare.

La soluzione è il perft (performance test): contare il numero esatto di nodi alla foglia a una data profondità da una data posizione. Questi valori sono noti con certezza matematica — calcolati e verificati da decine di motori nel corso degli anni.

void perft_driver(int depth) {
    if (depth == 0) { nodes++; return; }
 
    moves move_list;
    generate_moves(&move_list);
 
    for (int i = 0; i < move_list.count; i++) {
        copy_board();
        if (!make_move(move_list.moves[i], all_moves)) { take_back(); continue; }
        perft_driver(depth - 1);
        take_back();
    }
}

Dalla posizione iniziale i valori corretti sono:

A profondità 1 ci sono esattamente 20 mosse legali dalla posizione iniziale (16 mosse di pedone + 4 mosse di cavallo). Qualsiasi scostamento — anche di una singola unità — indica un bug.

La tecnica di debug è dividere per mosse: si stampa il conteggio per ogni mossa alla radice e si confronta con i valori tabulati. La mossa con il conteggio sbagliato è quella che contiene il bug. Si scende ricorsivamente fino a trovare la posizione esatta che genera troppi o troppo pochi nodi.

Ho passato un quantità ridicola di tempo su questi numeri. I bug più comuni: la casella en passant non viene azzerata dopo ogni mossa (il che fa credere al motore che l'en passant sia disponibile per molti turni), gli aggiornamenti dei diritti di arrocco sono sbagliati per certi pezzi, le promozioni con cattura non rimuovono correttamente il pezzo catturato.

Cosa manca ancora

Agata v2 gira intorno ai 2400 Elo, ma ci sono parti che voglio ancora aggiungere:

Transposition table. La chiave Zobrist viene calcolata incrementalmente ma non è ancora usata per salvare risultati. Una TT permette di riconoscere posizioni già analizzate (raggiungibili tramite ordini di mosse diversi — le "trasposizioni") e riutilizzare il risultato invece di ri-analizzare. In un motore maturo può ridurre i nodi di un fattore 2-4x.

Struttura pedonale. Attualmente i pedoni vengono valutati solo per posizione e materiale, ma le loro relazioni reciproche contano molto. Un pedone passato (nessun pedone avversario può bloccarlo sulla sua colonna) vale molto di più del suo valore nominale. Un pedone isolato (nessun pedone amico nelle colonne adiacenti) è strutturalmente debole. Un pedone doppiato (due pedoni sulla stessa colonna) è quasi sempre un problema.

Mobilità. Contare le caselle legalmente raggiungibili da ogni pezzo è uno dei predittori di qualità della posizione più affidabili. Un alfiere con 12 caselle libere è molto più attivo di uno con 3 — anche se entrambi valgono 350 centipedoni in materiale puro.

Sicurezza del re. La valutazione attuale del re è piuttosto grezza. Motori forti tengono conto dello scudo di pedoni davanti al re arrocato, delle colonne aperte vicino al re (canali di attacco), e del numero di pezzi avversari che si avvicinano.

Costruire un motore scacchistico è uno dei progetti più formativi che abbia mai fatto — manipolazione di bit, ottimizzazione algoritmica, teoria dei giochi, tutto insieme. Il codice completo è su GitHub.