Hashing applicato: riconoscere le trasposizioni con lo Zobrist hashing

Nel post sulla crittografia e l'hashing avevo parlato delle funzioni hash dal punto di vista della sicurezza: lì il nemico è un avversario che vuole trovare collisioni. Oggi voglio mostrare l'hashing dall'altra faccia — quella in cui le collisioni le tolleri, perché ti serve solo un'impronta digitale veloce di un oggetto complesso. L'oggetto, nel mio caso, è una posizione di scacchi; e il problema che risolve è una di quelle cose che sembrano banali finché non provi a programmarle: le trasposizioni.

Il problema: la stessa posizione per strade diverse

Considera queste due partite:

1. e4  e5  2. Nf3 Nc6
1. Nf3 Nc6 2. e4  e5

Sono due sequenze di mosse diverse, eppure dopo due mosse la scacchiera è identica. Nelle aperture questo non è un caso di scuola, è la norma: l'Inglese traspone di continuo nella Difesa Indiana, il Gambetto di Donna si raggiunge da mille ordini di mossa diversi. Se stai costruendo un albero di analisi di un'apertura — come fa il mio chess trainer — il problema diventa concreto: analizzi 1.e4 e5 2.Nf3 Nc6 in un ramo e 1.Nf3 Nc6 2.e4 e5 in un altro, e ti ritrovi a studiare due volte la stessa posizione, con le note divise a metà. Spreco di tempo e di testa.

La domanda è: come riconosco che due nodi dell'albero sono la stessa posizione, senza confrontare 64 caselle ogni volta contro ogni altra? Con N nodi sarebbe O(N²) confronti, ciascuno su tutta la scacchiera. Serve qualcosa di meglio.

L'idea: ridurre la posizione a un numero

La mossa classica dell'informatico è: se confrontare gli oggetti è costoso, riducili a un numero e confronta i numeri. Una funzione hash fa esattamente questo. Ma una posizione di scacchi non è "i pezzi sulla scacchiera" e basta: è anche di chi è il tratto, quali arrocchi sono ancora possibili, se c'è una presa en passant disponibile. Due scacchiere con i pezzi negli stessi posti ma tratto diverso sono posizioni diverse. L'impronta deve tenerne conto.

Lo Zobrist hashing (Albert Zobrist, 1970) fa proprio questo, ed è di una semplicità quasi insolente.

Come funziona lo Zobrist hashing

Si parte generando, una volta sola all'avvio, una tabella di numeri casuali a 64 bit: uno per ogni combinazione (tipo di pezzo × casa). Dodici tipi di pezzo (sei bianchi, sei neri) per 64 case fanno 768 numeri. Più qualche numero in più: uno per "tocca al Nero", quattro per i diritti di arrocco, otto per la colonna dell'eventuale en passant.

import random

# una chiave casuale a 64 bit per ogni (pezzo, casa)
Z       = [[random.getrandbits(64) for _ in range(64)] for _ in range(12)]
Z_nero  = random.getrandbits(64)          # tratto al Nero
# ... + arrocchi + colonna en passant

L'hash di una posizione è semplicemente lo XOR di tutte le chiavi degli elementi presenti:

def hash_posizione(board):
    h = 0
    for casa, pezzo in board.pezzi():
        h ^= Z[pezzo][casa]
    if board.tocca_al_nero:
        h ^= Z_nero
    # ... ^= arrocchi ed en passant attivi
    return h

Tutto qui. Un numero a 64 bit che riassume l'intera posizione.

Il pezzo elegante: l'aggiornamento incrementale

Qui c'è la parte che rende Zobrist superiore a qualsiasi altro hash per questo scopo. Lo XOR ha una proprietà magnifica: applicare due volte la stessa chiave la annulla (x ^ k ^ k == x). È reversibile.

Questo significa che quando faccio una mossa non ricalcolo l'hash da zero: lo aggiorno con pochi XOR. Cavallo da g1 a f3?

h ^= Z[CAVALLO_B][g1]   # tolgo il cavallo da g1
h ^= Z[CAVALLO_B][f3]   # lo rimetto in f3
h ^= Z_nero             # cambio il tratto

Tre XOR, costo costante, indipendente dal numero di pezzi sulla scacchiera. E poiché lo XOR è commutativo e associativo, l'ordine in cui arrivo a una posizione non conta: l'hash finale è lo stesso. Che è esattamente la proprietà di cui ho bisogno per riconoscere le trasposizioni — due ordini di mossa diversi che convergono producono lo stesso numero, automaticamente.

Piccola nota da nerd: nel mio trainer non scrivo niente di tutto questo a mano. Uso chess.polyglot.zobrist_hash() di python-chess, che implementa lo standard Polyglot — gli stessi numeri casuali usati dai libri di apertura .bin. Cioè l'hash che mi serve per le trasposizioni è la stessa chiave con cui interrogo il libro di apertura. Due piccioni con una fava.

E le collisioni?

Stiamo schiacciando uno spazio enorme di posizioni in 64 bit: le collisioni sono matematicamente inevitabili. La domanda giusta non è "se", ma "quanto è probabile". Ed è qui che torna utile il paradosso del compleanno: con un hash a b bit, la probabilità di una collisione diventa significativa non a 2^b oggetti, ma intorno a 2^b/2. Per 64 bit parliamo di ~2³² ≈ 4 miliardi di posizioni prima di doverti preoccupare sul serio.

Un albero di analisi di un'apertura ha qualche centinaio, al massimo qualche migliaio di nodi. La probabilità di una collisione è dell'ordine di una su miliardi di miliardi: del tutto trascurabile. Per questo nel mio codice mi fido dell'hash e basta. Se invece stessi indicizzando un database di milioni di partite da master, aggiungerei una verifica di sicurezza (confronto del FEN) sui pochi casi che collidono — costa poco ed elimina il rischio del tutto. È la classica scelta ingegneristica: conoscere l'ordine di grandezza ti dice quando un controllo serve e quando è paranoia.

In pratica: come lo uso nel chess trainer

Il cuore sta in una funzione che costruisce, su richiesta, un indice hash → lista di nodi con quella posizione, in ordine di visita dell'albero. Il primo nodo della lista è quello "canonico" (la prima volta che la posizione è comparsa); gli altri sono le sue trasposizioni:

def _position_index(self):
    """zobrist -> [nodi con quella posizione], in ordine DFS
    (l'indice 0 è la PRIMA occorrenza, quella canonica)."""
    idx = {}
    for n in self._iter_nodes():
        z = chess.polyglot.zobrist_hash(n.board())
        idx.setdefault(z, []).append(n)
    return idx

Da qui tutto il resto viene quasi gratis:

def transpositions_of(self, node):
    """Gli altri nodi con la stessa identica posizione; [] se è unica."""
    z = chess.polyglot.zobrist_hash(node.board())
    return [n for n in self._position_index().get(z, []) if n is not node]

def is_frozen(self, node):
    """True se questo nodo è un DUPLICATO (non il canonico): le sue
    continuazioni appartengono al nodo canonico, quindi non va fatto
    crescere con nuove mosse."""
    return self.canonical_node(node) is not node

Il concetto di is_frozen ("congelato") è la parte che mi soddisfa di più. Quando l'utente arriva a una posizione già presente altrove nell'albero per un altro ordine di mosse, il trainer se ne accorge e lo avvisa, invece di lasciargli costruire un secondo ramo gemello che dovrebbe poi mantenere allineato a mano. Le continuazioni si studiano una volta sola, nel nodo canonico. Con i tasti J / Shift+J salto all'occorrenza originale o cerco una posizione per FEN dentro la partita. La duplicazione dell'analisi semplicemente non può avvenire.

Morale

Lo Zobrist hashing è uno di quegli strumenti che sembrano un trucco e invece sono profondi: un pugno di numeri casuali, lo XOR, e ottieni un'impronta di una posizione che si aggiorna in tempo costante e — gratis, per via dell'algebra dello XOR — è indipendente dall'ordine delle mosse. È la proprietà che trasforma un problema apparentemente O(N²) di confronti tra scacchiere in una banale ricerca in un dizionario. E vale la pena ricordare che lo stesso oggetto, l'hash, qui non difende da un avversario ma deduplica del lavoro: la stessa matematica, due mondi opposti.

Il codice è nel mio chess trainer su GitHub.