Sì, le tabelle di trasposizione introducono instabilità di ricerca.
Fortunatamente, si verifica raramente sufficiente che i vantaggi di tabelle di recepimento superano che complicazione di gran lunga.
1. Qual è la funzione di una tabella di trasposizione?
Dopo aver aggiunto le tabelle di recepimento (TT) al vostro programma, si dovrebbe notare due differenze principali:
- Migliorare mossa ordinazione: Il passaggio da TT è in genere la mossa migliore possibile
- I primi tagli: quando si raggiunge nuovamente una posizione, che è già stata cercata con una maggiore distanza, è possibile interrompere e utilizzare il valore memorizzato nella voce TT
Negli scacchi, l'ordine di spostamento migliorato è il fattore più importante. Solo nei finali, la probabilità di trasposizione è aumentata e vedrai più tagli iniziali.
Quindi, che cosa significa instabilità della ricerca? Significa che quando si cerca una posizione con una data distanza e successivamente si ripete la stessa ricerca (stessa posizione, stessa distanza), si otterrà lo stesso risultato.
2. Semplice Minimax/alpha beta ricerca algorthm
Vediamo prima ignoriamo estensione di ricerca e iniziare con un semplice minimax o di ricerca alfa-beta.
Si noti che è la ricerca avrà la proprietà che le ricerche sono ripetibili, e vedrete nessun instabilità di ricerca. Anche se migliori la tua mossa ordinando con una mossa da una tabella di trasposizione, otterrai comunque lo stesso risultato per ogni ricerca. Tuttavia, dopo aver aggiunto TT, i tagli extra da una ricerca più approfondita interromperanno in generale quella proprietà e introdurranno instabilità.
Ad esempio, si consideri una posizione contenente una tattica profonda:
- Una ricerca con una distanza basso non può vedere, ma una ricerca con una maggiore volontà distanza.
- Dopo che il risultato è stato memorizzato nel TT, una ricerca con la distanza bassa vedrà anche la tattica. Ora si comporta in modo diverso rispetto alla ricerca originale.
- Ancora peggio, quando la voce TT viene sovrascritta, la conoscenza migliorata diventa di nuovo molto.
Quindi, l'utilizzo di conoscenze extra per forzare i tagli precoci è un fattore che porta all'instabilità.(Ma in pratica, ne vale la pena, in quanto è più un problema teorico.)
3. estensioni della ricerca
Quando applicato ad una semplice ricerca su alpha beta, il miglioramento della stessa mossa l'ordinazione non porta per cercare instabilità. La situazione è più complicata negli algoritmi di ricerca del mondo reale che implementano molte estensioni. Alcune di queste estensioni sono sensibili anche all'ordine di movimento.
Un esempio importante è chiamato Late Move Reduction (LMR). Usa il fatto che la qualità degli ordini di movimento è in genere così alta che solo le prime mosse devono essere perquisito a fondo, mentre le altre mosse sono molto probabilmente cattive e verranno cercate solo a una distanza ridotta.
LMR è solo un esempio in cui l'ordine di spostamento rende la ricerca meno ripetibile. Ma ancora una volta, i vantaggi predominano.
4. Quanta instabilità di ricerca è normale?
Non c'è una risposta chiara. In pratica, non è possibile eliminare completamente le instabilità, ma se l'instabilità diventa fuori controllo, la ricerca diventerà inefficiente.
Ovviamente, anche i bug possono essere la causa delle instabilità. Quindi, è un bug nella tua ricerca? Beh, non lo so. Potrebbe essere. :-)
Nota un termine tecnico migliore per "distanza" è "profondità". – SmallChess
Quindi, se si memorizzano valori separati per ciascuna profondità e non si esegue la sovrascrittura, si eliminano le instabilità. –
@ThomasAhle Se non si sovrascrivono mai i valori e si utilizzano solo i risultati memorizzati in cui la distanza corrente corrisponde esattamente alla distanza del negozio, si elimineranno le instabilità.Detto questo, entrambe le ipotesi non sono pratici. In primo luogo, alla fine si esaurirà la memoria, e in secondo luogo, le voci che sono state cercate più a fondo sono solo utili da ignorare. –