MTD (f) es un algoritmo de búsqueda minimax desarrollado en 1994 por Aske Plaat , Jonathan Schaeffer , Wim Pijls y Arie de Bruin . Los experimentos con ajedrez , damas y programas Othello con calidad de torneo muestran que es un algoritmo minimax altamente eficiente. El nombre MTD (f) es una abreviatura de MTD (n, f) (controlador de prueba de memoria mejorada con nodo n y valor f ). Es una alternativa al algoritmo de poda alfa-beta . [1]
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 alfa-beta llamadas, siempre que alfa-beta utilizara almacenamiento, como una tabla de transposición que funcione bien .
El nombre MTD (f) significa controlador de prueba mejorado con memoria, que hace referencia al algoritmo de prueba de Judea Pearl , que realiza búsquedas de ventana cero. MTD (f) se describe en profundidad en la tesis doctoral de Aske Plaat de 1996.
Búsquedas de ventana cero
MTD (f) obtiene su eficiencia realizando solo búsquedas alfa-beta de ventana cero, con un límite "bueno" (beta variable). En NegaScout , la búsqueda se llama con una ventana de búsqueda amplia, como en AlphaBeta (root, −INFINITY, + INFINITY, depth), por lo que el valor de retorno se encuentra entre el valor de alfa y beta en una llamada. 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.
Actuación
NegaScout llama a las búsquedas de ventana cero de forma recursiva . MTD (f) llama a las búsquedas de ventana cero desde la raíz del árbol. Se ha demostrado que las implementaciones del algoritmo MTD (f) son más eficientes (buscar menos nodos) en la práctica que otros algoritmos de búsqueda (por ejemplo, NegaScout) en juegos como ajedrez [1] , damas y Othello. Para que los algoritmos de búsqueda como NegaScout o MTD (f) funcionen de manera eficiente, la tabla de transposición debe funcionar bien. De lo contrario, por ejemplo, cuando se produce una colisión de hash, se volverá a expandir un subárbol. Cuando se utiliza 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 utilizar valores separados para f para iniciar la búsqueda. 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.
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. Debido a que MTD (f) solo usa búsquedas de ventana cero, mientras que Alpha-Beta y NegaScout también usan búsquedas de ventana amplia, MTD (f) es más eficiente. 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] [6]
Se sugieren algoritmos recientes como Best Node Search para superar 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
- ^ 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 .