MTD(f)

MTD(f) es un algoritmo de búsqueda en árbol de juego alfa-beta modificado para usar límites de búsqueda iniciales de 'ventana cero' y memoria (generalmente una tabla de transposición ) para reutilizar 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 estimación inicial y de la suposición de que el valor minimax final se encuentra en una ventana estrecha alrededor de la estimación (que se convierte en un límite superior/inferior para la búsqueda desde la raíz). La estructura de memoria se utiliza para guardar una estimació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 dominante hasta entonces para el ajedrez , las damas , el othello y otros autómatas de juegos.

MTD(f) se describió por primera vez en un Informe Técnico de la Universidad de Alberta cuyos autores fueron Aske Plaat, Jonathan Schaeffer, Wim Pijls y Arie de Bruin, ^{[ 2 ]} que posteriormente recibiría el premio ICCA Novag a la Mejor Publicación de Ajedrez por Computadora de 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 primero el mejor inventado por George Stockman en 1979. ^{[ 3 ]} Se descubrió que SSS* era equivalente a una serie de llamadas de poda alfa-beta|alfa-beta, siempre que alfa-beta utilizara almacenamiento, como una tabla de transposición.

El nombre MTD(f) significa Controlador de Pruebas con Memoria Mejorada, en referencia al algoritmo de prueba de Judea Pearl , que realiza búsquedas de ventana cero. MTD(f) se describe en detalle en la tesis doctoral de Aske Plaat de 1996.

Una búsqueda de "ventana cero" es una búsqueda alfa-beta cuyos límites superior e inferior son idénticos, o difieren en una unidad, de modo que se garantiza que el valor de retorno caerá fuera de los límites (o, en un caso excepcionalmente afortunado, será igual al límite).

MTD(f) obtiene su eficiencia al realizar únicamente búsquedas alfa-beta de ventana cero, con un límite "bueno" previamente determinado (es decir, beta). En MTD(f), AlphaBeta falla por alto o por bajo, devolviendo un límite inferior o un límite superior para el valor minimax, respectivamente. Las llamadas de ventana cero provocan más cortes, pero devuelven menos información: solo un límite para 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 en memoria las porciones del árbol previamente buscadas para reducir la sobrecarga de volver a explorar partes del árbol de búsqueda. ^{[ 4 ]}

La función MTDF(raíz, f, d) es g := f límite superior := +∞ límite inferior := − ∞ mientras lowerBound < upperBound hacer β := max(g, límite inferior + 1) g := AlphaBetaWithMemory(root, β − 1, β, d) si g < β entonces límite superior := g demás límite inferior := g devolver g

f

Primera estimación para obtener el mejor valor. Cuanto mejor sea, más rápido convergerá el algoritmo. Podría ser 0 en la primera llamada.

d

Profundidad para iterar. Se podría realizar una búsqueda en profundidad iterativa llamando MTDF()varias veces con incremento dy proporcionando el mejor resultado anterior en f. ^{[ 5 ]}

AlphaBetaWithMemoryes una variante de Alpha Beta Search que almacena en caché los resultados anteriores.

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 con ventana cero alcanzan su límite antes que las búsquedas con ventana amplia. Por lo tanto, son más eficientes, pero, en cierto sentido, también menos tolerantes que las búsquedas con ventana amplia. Sin embargo, las ventanas de búsqueda más amplias son más tolerantes para motores con grandes fluctuaciones entre pares e impares y funciones de evaluación de grano fino. Por esta razón, algunos motores de ajedrez no han adoptado MTD(f).

En pruebas con programas de calidad profesional como Chinook (damas), Phoenix (ajedrez) y Keyano (Othello), el algoritmo MTD(f) superó a todos los demás algoritmos de búsqueda. ^{[ 4 ]} Se sugiere que algoritmos recientes como Best Node Search superan a MTD(f).

• Descripción del algoritmo MTD(f)