MTD (f) es un algoritmo de búsqueda de árbol de juego alfa-beta modificado para usar los límites de búsqueda inicial de 'ventana cero' y la memoria (generalmente una tabla de transposición ) para reutilizar los resultados de búsqueda intermedios. MTD (f) es una forma abreviada de MTD (n, f) que significa controlador de prueba mejorado con memoria con nodo 'n' y valor 'f'. [1] La eficacia de este paradigma depende de una buena suposición inicial y la suposición de que el valor minimax final se encuentra en una ventana estrecha alrededor de la suposición (que se convierte en un límite superior / inferior para la búsqueda desde la raíz). La estructura de la memoria se utiliza para guardar una suposición inicial determinada en otro lugar.
MTD (f) se introdujo en 1994 y suplantó en gran medida a NegaScout (PVS), el paradigma de búsqueda previamente dominante para el ajedrez , las damas , el othello y otros autómatas del juego.
Origen
MTD (f) se describió por primera vez en un Informe técnico de la Universidad de Alberta escrito por Aske Plaat, Jonathan Schaeffer, Wim Pijls y Arie de Bruin, [2] que más tarde recibiría el premio ICCA Novag a la mejor publicación de ajedrez informático en 1994/1995. El algoritmo MTD (f) se creó a partir de un esfuerzo de investigación para comprender el algoritmo SSS * , un algoritmo de búsqueda del mejor primero inventado por George Stockman en 1979. [3] Se encontró que SSS * era equivalente a una serie de Alpha-beta poda | llamadas alfa-beta, siempre que alfa-beta utilizara almacenamiento, como una tabla de transposición.
El nombre MTD (f) significa controlador de prueba mejorado con memoria, que hace referencia al algoritmo de prueba de Judea Pearl , [ cita requerida ] que realiza búsquedas de ventana cero. MTD (f) se describe en profundidad en la tesis doctoral de Aske Plaat de 1996. [ cita requerida ]
Búsquedas de ventana cero
Una búsqueda de "ventana cero" es una búsqueda alfabeta cuyos límites superior e inferior son idénticos, o difieren en una unidad, de modo que se garantiza que el valor de retorno se saldrá de los límites (o en un caso excepcionalmente afortunado, será igual al límite).
MTD (f) obtiene su eficiencia realizando solo búsquedas alfa-beta de ventana cero, con un límite "bueno" previamente determinado (es decir, beta). En MTD (f), AlphaBeta falla alto o bajo, devolviendo un límite inferior o un límite superior en el valor minimax, respectivamente. Las llamadas de ventana cero provocan más cortes, pero devuelven menos información, solo un límite en el valor minimax. Para encontrar el valor minimax, MTD (f) llama a AlphaBeta varias veces, convergiendo hacia él y finalmente encontrando el valor exacto. Una tabla de transposición almacena y recupera las partes del árbol buscadas anteriormente en la memoria para reducir la sobrecarga de volver a explorar partes del árbol de búsqueda. [4]
Pseudocódigo
la función MTDF (root, f, d) es g: = f límite superior: = + ∞ límite inferior: = −∞ while lowerBoundhacer β: = max (g, límite inferior + 1) g: = AlphaBetaWithMemory (raíz, β - 1, β, d) si g <β entonces límite superior: = g demás límite inferior: = g volver g
f
- Primero adivine por el mejor valor. Cuanto mejor, más rápido converge el algoritmo. Podría ser 0 para la primera llamada.
d
- Profundidad para recorrer. Se puede realizar una búsqueda iterativa de profundización primero en profundidad llamando
MTDF()
varias veces con incrementosd
y proporcionando el mejor resultado anterior enf
. [5]
AlphaBetaWithMemory
es una variación de Alpha Beta Search que almacena en caché los resultados anteriores.
Descripción
MTD (f) llama a las búsquedas de ventana cero desde la raíz del árbol. MTD (f) depende de una tabla de transposición para funcionar de manera eficiente. [6]
Las búsquedas de ventana cero llegan a un punto de corte antes que las búsquedas de ventana amplia. Por lo tanto, son más eficientes, pero, en cierto sentido, también menos tolerantes que las búsquedas de ventana amplia. Sin embargo, las ventanas de búsqueda más amplias son más tolerantes para los motores con grandes oscilaciones pares / impares y funciones de evaluación detalladas. Por esta razón, algunos motores de ajedrez no se han cambiado a MTD (f).
En pruebas con programas de calidad de torneo como Chinook (damas), Phoenix (ajedrez) y Keyano (Othello), el algoritmo MTD (f) superó a todos los demás algoritmos de búsqueda. [4] [7] Se sugiere que algoritmos recientes como Best Node Search superen a MTD (f).
Referencias
- ^ Johannes Fürnkranz; Miroslav Kubat (2001). Máquinas que aprenden a jugar . Editores Nova. págs. 95–. ISBN 978-1-59033-021-0.
- ^ "Estrategias adaptativas de MTD-f para juegos reales" . Universidad de Agricultura y Tecnología de Tokio. K SHIBAHARA y col.
- ^ Teófilo González; Jorge Díaz-Herrera; Allen Tucker (7 de mayo de 2014). Manual de Computación, Tercera Edición: Ciencias de la Computación e Ingeniería de Software . Prensa CRC. págs. 38–. ISBN 978-1-4398-9853-6.
- ^ a b Plaat, Aske; Jonathan Schaeffer; Wim Pijls; Arie de Bruin (noviembre de 1996). "Mejor primero algoritmos Minimax de profundidad fija" . Inteligencia artificial . 87 (1–2): 255–293. doi : 10.1016 / 0004-3702 (95) 00126-3 .
- ^ https://people.csail.mit.edu/plaat/mtdf.html
- ^ Cuando se usa MTD (f) en programas que sufren un pronunciado efecto impar-par, donde la puntuación en la raíz es más alta para profundidades de búsqueda pares y más baja para profundidades de búsqueda impares, es aconsejable usar valores separados para f para iniciar la busque lo más cerca posible del valor minimax. De lo contrario, la búsqueda tomaría más iteraciones para converger en el valor minimax, especialmente para funciones de evaluación de grano fino.
- ^ Plaat, Aske; Jonathan Schaeffer; Wim Pijls; Arie de Bruin (noviembre de 1996). "Mejor primero algoritmos Minimax de profundidad fija" . Inteligencia artificial . 87 (1–2): 255–293. doi : 10.1016 / 0004-3702 (95) 00126-3 .