El Árbol de Ajedrez y el Algoritmo de MiniMax

Cuando el juego de ajedrez se inicia las blancas eligen uno entre 20 movimientos posibles. Siguiendo el movimiento de las blancas, las negras tienen 20 opciones de respuesta cualquiera haya sido la elección de las blancas.

De acuerdo a esto, 400 posiciones distintas pueden surgir sólo de la primera jugada de una partida de ajedrez. Luego de 2 jugadas el número de posiciones posibles crece sobre las 20.000, llegando a una cifra astronómica luego de varias jugadas más. El "árbol de ajedrez" posee más posiciones que la cantidad de átomos presentes en la via láctea. De acuerdo al reglamento del juego una partida es tablas (empate) si transcurren 50 jugadas sin que se haya realizado algún movimiento de peón y sin que se haya producido algún cambio de pieza, por lo cual según algunos cálculos una partida de ajedrez puede durar como máximo 3150 jugadas [6], por lo que el árbol de variantes puede tener una cantidad de posiciones limitada a esta cantidad.

Si fuese posible examinar el árbol por completo, buscando todas las líneas de juego y sus conclusiones sería posible determinar cuál es el mejor movimiento inicial. Sin embargo, en la práctica el árbol es demasiado extenso para considerar este mecanismo. Incluso el determinar el mejor movimiento buscando en el árbol de variantes a partir de una avanzada posición de medio juego resulta imposible. Lo mejor que puede realizarse es buscar en un sector limitado del árbol de variantes, esperando obtener suficiente información con tal de decidir correctamente cual es el mejor movimiento.

En los inicios de 1970 la búsqueda en árboles de variantes alcanzaba la cantidad aproximada de 200 posiciones por segundo. Hoy (año 2003), DEEP BLUE busca en 2.000.000 de posiciones por segundo. Los mejores programas logran examinar todas las secuencias de movimientos con una profundidad de 8 a 10 movidas en el árbol (4 a 5 jugadas por bando).

Líneas de juego cruciales como jaques y capturas tienen una profundidad de búsqueda aún mayor. En la jerga de programas de ajedrez, una búsqueda de fuerza bruta de 6 movimientos significa una búsqueda de todos los movimientos posibles para cada bando hasta una profundidad de 6 niveles (3 jugadas por bando) y con mayor profundidad en líneas altamente tácticas.

Para un árbol de variantes dado, el algoritmo minimax entrega una regla para decidir qué movimiento realizar frente a una posición dada. El algoritmo comienza calculando el valor numérico o puntaje para la posición al final de cada variante. Estas posiciones son denominadas Posiciones Terminales y su puntaje es calculado por una Función de Evaluación. La función de evaluación intenta medir cuan buena es la posición para el primer jugador. Un puntaje positivo significa que la computadora tiene ventaja, un puntaje negativo significa que su oponente tiene ventaja.

El algoritmo entiende que el objetivo del primer jugador es llevar al juego a una posición en la cual maximice su puntaje, mientras que el objetivo del rival es el opuesto, lograr una posición que sea mínima en puntaje. Esto es equivalente a plantear que en niveles similares del árbol de variantes el algoritmo Minimax asignará a cada posición no terminal un puntaje igual al máximo puntaje de alguna de las posiciones sucesoras. En otras palabras, la computadora tomará el movimiento que le reporta el mayor beneficio para el movimiento siguiente. En los niveles impares donde juega el oponente el algoritmo asignará a cada posición no terminal un puntaje igual al mínimo de las posiciones sucesoras. Dado que los puntajes de las posiciones sucesoras de una posición no terminal deben ser conocidos con tal de dar un puntaje a esa posición los puntajes de las posiciones terminales deben ser determinados primero y luego los puntajes de las posiciones restantes hasta llegar a la posición raíz.

En juegos de cálculo extenso como el ajedrez los programas pueden examinar sólo una parte del árbol de variantes sin llegar hasta el final del juego. En estos casos los programas buscan hasta un cierto limite de nodos, estimando en ellos las posibilidades de ganar de cada bando mediante la función de evaluación.

Figura: Ejemplo de aplicación del algoritmo minimax.

Existen varios algoritmos que ayudan a mejorar la eficiencia del Minimax. Uno de ellos es la poda Alfa-Beta, bajo la cual el programa debe buscar sólo aproximadamente la raíz cuadrada del numero de nodos que debería buscar sin esta implementación. Otras implementaciones incluyen las tablas de transposición las cuales guardan la información de posiciones ya examinadas. Ambas técnicas son analizadas en puntos siguientes.

Desafortunadamente el algoritmo minimax es de un orden O(bn) donde b (factor de anchura) es el número de movimientos legales disponibles en promedio en cualquier momento y n(profundidad) es el número de movimientos que se calculan, donde un movimiento es una movida de un bando. Este número crece en forma exponencial a medida que la profundidad aumenta, por lo cual una considerable cantidad de trabajo ha sido hecha con tal de desarrollar algoritmos que minimicen el esfuerzo realizado en buscar movimientos a una determinada profundidad.