Cómo usar tablas de transposición con MTD (f)

Question

Escribo una IA para un juego de cartas y después de algunas pruebas descubro que el uso de MTD (f) en mi algoritmo alfa beta - una serie de búsquedas en la ventana cero - es más rápido que simplemente usar alfa-beta por sí mismo.

La DMT (f) algoritmo se describe bien aquí http://people.csail.mit.edu/plaat/mtdf.html

El problema que tengo es que para cada pasada en el MTD (f) de búsqueda (por cada una conjetura) que no vuelva a usar cualquiera de las posiciones anteriores He almacenado aunque la escritura en el enlace sugiere que debería (de hecho, borrar la tabla entre iteraciones acelera el algoritmo).

Mi problema es que cuando almaceno una posición y un valor en mi tabla de transposición, también almaceno los valores alfa y beta para los que es válido. Por lo tanto, un segundo pase a través del árbol con una conjetura diferente (y, por lo tanto, alfa y beta) no puede reutilizar ninguna información. ¿Es esto lo que se espera o me estoy perdiendo algo fundamental aquí?

Por ejemplo, si para alpha = 3 beta = 4 llegamos a un resultado de 7 (obviamente un punto de corte) ¿debo guardar eso en la tabla como válido para alpha = 3 a beta = 6? O beta = 7?

Answer 1

Su problema se reduce a la comprensión conceptual de cómo usar una tabla de transposición junto con una búsqueda alfa beta. Este fue un gran problema al que me encontré también, y después de mirar alrededor descubrí this discussion que me explicó el concepto de forma más natural que cualquier artículo que había leído sobre el tema.

Básicamente no puede tratar todos los resultados alfa-beta de la misma manera porque cuando se produce un corte, el resultado solo representa un límite, y no el verdadero valor minimax. Se ha demostrado que el uso de límites siempre le dará siempre el siguiente mejor estado, pero posiblemente sin tener el puntaje exacto. Cuando almacena el estado desde un punto de corte, debe tratarlo como un límite y tratar de mejorarlo en el próximo pase. Esto a menudo evaluará el mismo nodo varias veces, pero mejorará continuamente el puntaje real según sea necesario.

Here is a good example de una implementación más completa de los conceptos enumerados en el artículo previamente vinculado. Desplácese a la página 14.