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...