Algoritmo MTDf es la abreviatura de MTD(n,f), que a su vez es la abreviatura de “Memory-enhanced Test Driver node n and value f”. El algoritmo que ahora trataremos es un algoritmo de búsqueda en árboles MiniMax usando ventanas nulas y tablas de transposiciones (transposition tables).
Antes de entrar en materia con el algoritmo MTDf, veamos qué es una tabla de transposición.
Una tabla de transposición es una base de datos donde se almacenan los resultados de búsquedas previamente realizadas. Es una forma de reducir drásticamente el espacio de búsqueda con poquísimo impacto negativo.
Por ejemplo, en el juego de ajedrez, durante su búsqueda de fuerza bruta, pueden repetirse una vez tras otra las mismas posiciones, pero desde secuencias distintas de movimientos (estos “estados repetidos” son una “transposición”). Cuando nos encontramos con una transposición, es beneficiosos recordar qué determinamos la última vez. Así ahorraremos repetir de nuevo toda la búsqueda.
Por esta razón, una tabla de transposiciones será una tabla de hash de gran capacidad en la que almacenaremos estados previamente buscados, hasta qué nivel se les realizó la búsqueda, y qué determinamos de éstos. Así pues su acceso tendrá un muy bajo coste constante, pues se accederá mediante hash keys derivadas del estado.
Con la tabla, cada vez que lleguemos a una nueva posición, el programa comprobará la tabla para ver si antes ya se ha analizado esa posición. Si está, se recoge el valor anteriormente asignado a esa posición y se usa directamente. Si no se encuentra, el valor se calculará con la función de evaluación y se insertará esa posición-profundidad-valor en la tabla, por si más adelante reaparece.
Una vez comprendido el concepto de “tablas de transposiciones”, ya nos encontramos en situación de comprender fácilmente lo que hace el algoritmo MTDf en un código de apenas diez líneas.
Función Alfa-Beta en el algoritmo MTDf
En él se usa la función “AlphaBetaWithMemory”, que no es más que una versión de Alfa-Beta que usa tablas de transposiciones. Esta función se encargará de encontrar el valor minimax de cierto nodo. Para buscar el valor necesario, MTDf usará esta función siempre con un tamaño de ventana igual a cero (ventana nula).
MTDf trabajará acercándose como si de un zoom se tratara al valor minimax buscado. Cada llamada a Alfa-Beta retornará un límite superior o inferior del rango donde se encuentra el valor deseado. Estos límites se almacenarán en upperbound y lowerbound, formando un intervalo alrededor del auténtico valor minimax buscado.
Al inicio de la búsqueda, como desconocemos completamente cuál es el valor buscado, los umbrales del intervalo serán más y menos infinito. En cambio, durante las iteraciones, cuando ambos umbrales colisionen (tengan el mismo valor), significará que ya hemos afinado tanto el intervalo que ya tendremos el valor minimax concreto.
Así pues, sin entrar en detalle en la implementación concreta de AlphaBetaWithMemory, el algoritmo MTDf será tan sencillo como lo siguiente:
funcion MTDF(root, f, d) retorna entero g := f;
upperBound := +∞;
lowerBound := -∞;
mientras lowerBound < upperBound hacer si g = lowerBound entonces
β := g+1;
sino
fsi
β := g;
g := AlphaBetaWithMemory(root, β-1, β, d);
si g < β entonces
upperBound := g;
ffuncion
sino
fsi fmientras retorna ( g )
Áreas Relacionadas
Los algoritmos de juegos como minimax, como bien se intuye por el nombre, están directamente relacionados con la “Teoría de Juegos”, que a su vez está relacionada con la filosofía, la biología, las matemáticas, la lógica, la economía, los negocios, las ciencias políticas, las estrategias militares, e incluso programas televisivos como el estadounidense Friend or foe? o el programa catalán Sis a Traïció.
La teoría de juegos es un área de la matemática aplicada que utiliza modelos para estudiar interacciones en estructuras formalizadas de incentivos (que son los juegos) y llevar a cabo procesos de decisión. Sus investigadores estudian las estrategias óptimas así como el comportamiento previsto y observado de individuos en juegos.
Y afortunadamente puede representarse con árboles de juegos y estudiarse con algoritmos de búsqueda en juegos. Es más, algunos investigadores creen que encontrar el equilibrio de los juegos puede predecir cómo se comportarían las poblaciones humanas si se enfrentasen a situaciones análogas al juego estudiado.
Aunque tiene algunos puntos en común con la teoría de la decisión, la teoría de juegos estudia decisiones en entornos donde interaccionan individuos. En otras palabras, estudia la elección de la acción óptima cuando los costes y los beneficios de cada opción no están fijados de antemano, sino que dependen de las elecciones de otros individuos.
Vamos, que indirectamente estamos tratando con individuos que compiten y que según sus movimientos logran un beneficio o una pérdida minimax.
En el siguiente apartado aparecen algunas aplicaciones de dichos algoritmos en campos de la teoría de juegos. Ir ahora mismo