Come utilizzare le tabelle di trasposizione con MTD (f)

Question

Scrivo un'IA per un gioco di carte e dopo alcuni test ho scoperto che usando MTD (f) sul mio algoritmo alpha beta - una serie di ricerche a zero-window - È più veloce dell'utilizzo di alpha-beta da solo.

L'MTD (f) algoritmo è descritto bene qui http://people.csail.mit.edu/plaat/mtdf.html

Il problema che ho è che per ogni passaggio nell'area di MTD (f) di ricerca (per ogni indovinare) non riutilizzare qualsiasi delle posizioni precedenti L'ho memorizzato anche se la scrittura sul link suggerisce che dovrei (in effetti, azzerare la tabella tra le iterazioni accelera l'algoritmo).

Il mio problema è che quando memorizzo una posizione e un valore nella mia tabella di trasposizione, memorizzo anche i valori alfa e beta per i quali è valido. Pertanto un secondo passaggio attraverso l'albero con un'ipotesi diversa (e quindi alfa e beta) non può eventualmente riutilizzare alcuna informazione. È questo che ci si può aspettare o mi manca qualcosa di fondamentale qui?

Ad esempio se per alpha = 3 beta = 4 arriviamo a un risultato di 7 (ovviamente un cut-off) dovrei archiviare quello nella tabella come valido per alpha = 3 a beta = 6? O beta = 7?

Answer 1

Il tuo problema si riduce alla comprensione concettuale di come utilizzare una tabella di trasposizione lungo una ricerca alfa beta. Anche questo è stato un grosso problema, e dopo aver guardato in giro ho trovato this discussion che mi ha spiegato il concetto in modo più naturale di qualsiasi documento che avevo letto sull'argomento.

Fondamentalmente non è possibile trattare tutti i risultati di alfa-beta allo stesso modo, perché quando si verifica un taglio, il risultato rappresenta solo un limite e non il valore minimox reale. È stato dimostrato che l'utilizzo dei limiti ti darà sempre lo stesso stato successivo migliore, ma probabilmente senza il punteggio esatto. Quando si memorizza lo stato da un taglio, è necessario trattarlo come un limite e cercare di migliorare su di esso al passaggio successivo. Questo spesso valuterà lo stesso nodo più volte, ma migliorerà continuamente sul punteggio effettivo secondo necessità.

Here is a good example di un'implementazione più completa dei concetti elencati nell'articolo precedentemente collegato. Scorrere fino a pagina 14.