Ajedrez (paso 10): nace la “inteligencia”: minimax con poda alfa-beta

Nos quedamos en la fase 9 con un sabor de boca agridulce: aunque nuestro programa ya era capaz de seleccionar una pieza y realizar un movimiento (es decir, ya podía jugar al ajedrez contra nosotros), era tan mal jugador como el más bisoño de los principiantes. ¿Qué estaba ocurriendo?

Ocurría que habíamos transmitido poca “inteligencia” (y las c0millas son por lo indefinido del término) al programa. Apenas la suficiente para que seleccionase el mejor movimiento mirando únicamente el estado del tablero tal y como quedaría al hacer ese movimiento. Ese trocito de inteligencia lo denominamos “función de evaluación estática”.

Ahora llega el momento de hacer germinar ese granito de inteligencia que dejamos plantado en la fase 9.

Introducción a las técnicas heurísticas

Se denominan técnicas heurísticas a aquellas que no nos aseguran encontrar una solución perfecta a un problema (en nuestro caso, una solución perfecta sería encontrar un movimiento que nos condujera directa e inevitablemente a ganar la partida de ajedrez), pero sí hallar una solución de la cual se puede esperar que esté entre las mejores soluciones posibles.

Con la solución adoptada en la fase 9, y siempre que la función de evaluación sea lo bastante buena, conseguiremos que el ordenador “piense” sus jugadas siguiendo criterios objetivos, pero cometerá continuamente torpezas como, por ejemplo, no dudar en sacrificar una reina para comer un peón. Esto se debe a que, a diferencia de los jugadores humanos, la máquina no ve más allá del siguiente movimiento, mientras que un humano intentará predecir la reacción de su adversario a su movimiento. Un buen jugador humano, antes de realizar un movimiento, estará pensando en los siguientes dos, tres, cuatro o más movimientos.

Por supuesto, ningún ser humano puede calcular todos los posibles movimientos de las siguientes dos, tres o cuatro jugadas. Ni mucho menos cómo acabará la partida (entonces, el ajedrez no tendría ninguna gracia). Ello se debe a la enorme cantidad de posibilidades que se abren desde cada posición del tablero. Son tantas que ni siquiera un ordenador potente puede evaluarlas TODAS más allá de tres o cuatro movimientos.

Para que se haga una idea, se calcula que el número de posibles combinaciones de piezas después de los diez primeros movimientos es de alrededor de 165.518.829.100.544.000.000.000.000. Un ordenador rapidísimo, capaz de evaluar, por ejemplo, un millón de posiciones por segundo , necesitaría más de 7 billones de años (¡mucho más que la edad del universo!) para generar todas las combinaciones posibles y decidir cual es la mejor.

Señoras y señores… ¡un fuerte aplauso para Minimax!

Ante la imposibilidad de una evaluación exhaustiva de todas las combinaciones posibles de jugadas a partir de un estado concreto, tenemos que conformarnos con un examen parcial. Una buena estrategia para lograr una buena heurística es la técnica minimax, que se puede usar en otros muchos juegos de dos jugadores para hacer que el ordenador “piense”, y que describimos a continuación.

Supongamos que el ordenador maneja a las piezas negras. Lógicamente, su siguiente movimiento debería ser aquél que haga máxima la función de evaluación. Pero debemos tener en cuenta que el contrincante (piezas blancas) responderá con la jugada que haga máxima la función de evaluación para las blancas, es decir, que la convierta en mínima para las negras.

maximo = -99999
para cada movimiento posible del jugador actual sobre "tablero" hacer
inicio
    // Vamos a tratar de hacer este movimiento, a ver qué pasaría
    copiar tablero en tablero2
    realizar el movimiento sobre tablero2
    // Vamos a ver con qué movimiento respondería el contrario. Supondremos que
    // preferirá el que haga la función de evaluación mínima para nosotros
    minimo = 99999
    para cada movimiento_contrario posible del jugador contrario sobre "tablero2" hacer
    inicio
       copiar tablero2 en tablero3
       realizar movimiento_contrario sobre tablero 3
       puntos = evaluar_estado(tablero3)
       si (puntos < minimo)
         minimo = puntos
       fin
    fin (para)

    // Ya hemos encontrado la mejor respuesta del contrario a nuestro movimiento
    // Después de ella, ¿quedamos en una buena situación? Vamos a comprobarlo
    si (minimo > maximo) // Es el mejor (para nosotros) encontrado hasta ahora
    inicio
       maximo = minimo
       mejor_movimiento = movimiento
    fin (si)
fin (para)

Al final del algoritmo, la variable “mejor_movimiento” debe contener el movimiento seleccionado como el más adecuado (en realidad, debe ser un conjunto de cuatro coordenadas, dos de origen y dos de destino). Así ya no aparece el problema de sacrificar una reina para comer un peón. Aunque eso haga máxima la función de evaluación en el siguiente movimiento, la hará mínima dentro de dos movimientos, porque podemos prever que el contrario preferirá comerse nuestra reina, y, por lo tanto, no elegiremos ese camino.

Naturalmente, pudiera ocurrir que el movimiento elegido de esta forma sea equivocado, en el sentido de que no conduzca a una jugada ganadora. Al fin y al cabo, sólo estamos comprobando la respuesta del contrario a cada posible movimiento nuestro, es decir, sólo estamos prediciendo dos movimientos en el futuro. Quizá mirando cinco o seis movimientos más adelante nos diéramos cuenta de que no es rentable, pero eso es imposible por la enorme cantidad de estados del tablero que habría que evaluar. Por eso esta estrategia no nos asegura la victoria ni mucho menos.

Con el algoritmo anterior conseguimos mirar dos movimientos por anticipado: el nuestro y la respuesta previsible del contrario. Esto se puede generalizar para examinar la próximas n jugadas:

función buscar_mejor_movimiento(tablero)
inicio
   maximo = -9999
   para cada movimiento posible del jugado actual
   inicio
       copiar tablero en tablero2
       realizar movimiento sobre tablero2
       puntos = min(tablero2)
       si (puntos > maximo)
       inicio
         maximo = puntos
         mejor_movimiento = movimiento
       fin (si)
   fin (para)
fin (función)

Esta función iniciaría el proceso de búsqueda, eligiendo el movimiento que hace máximo el valor devuelto por el jugador contrario, cuyo “razonamiento” trata de simularse en la función min(),así:

función min(tablero)
inicio
  si (se ha alcanzado la profundidad deseada)
    minimo = evaluar_estado(tablero)
  si_no
  inicio
    minimo = 99999
    para cada movimiento posible del jugador contrario sobre el tablero
    inicio
       copiar tablero en tablero 2
       realizar ese movimiento en tablero2
       puntos = max(tablero2)
       si (puntos < minimo)
          minimo = puntos
    fin (para)
  fin (si_no)
  devolver (minimo)
fin (funcion)

A su vez, la función max() simulará la forma de pensar del judador actual, que tratará de hacer máxima la evaluación, de este modo:

función max(tablero)
inicio
  si (se ha alcanzado la profundidad deseada)
     maximo = evaluar_estado(tablero)
  si_no
  inicio
     maximo = -99999
     para cada movimiento posible del jugador contrario sobre el tablero
     inicio
       copiar tablero en tablero 2
       realizar ese movimiento en tablero2
       puntos = min(tablero2)
       si (puntos > maximo)
         maximo = puntos
    fin (para )
  fin (si_no)
  devolver (maximo)
fin (funcion)

Como vemos, el jugado actual (que maneja el ordenador) trata de hacer máxima la ventaja que obtiene en cada jugada, al tiempo que trata de hacer mínima la ventaja del jugador contrario. Por esa razón esta técnica se denomina minimax.

En la siguiente figura lo expresamos gráficamente. Supongamos que el juego se encuentra en el estado representado en la raiz del árbol, y que le toca mover al ordenador (negras). Cada  posible movimiento conduce al tablero a un estado diferente en el siguiente nivel del árbol. A su vez, cada uno de estos tableros tiene una colección de posibles movimientos que generan otros estados del tablero.

(clic para agrandar)

Los valores asignados a los estados más bajos (hojas del árbol) se obtienen aplicando la función de evaluación estática. El resto de valores se obtienen mediante la regla minimax. El jugador negro elegirá el primer movimiento (el de la rama izquierda), porque le asegura un valor mínimo de 5. Es decir, es el máximo de los valores mínimos del siguiente nivel.

Aplicación del minimax al juego

El algoritmo minimax puede implementarse de diversas formas. Aquí propondremos una, pero usted puede desarrollar otra si lo prefiere.

La función de evaluación estática no es necesario modificarla; es más, se usará en repetidas ocasiones.

Necesitaremos definir la profundidad máxima de búsqueda (que, como dijimos, no debe ser mayor de 3, 4 o, como mucho, 5 movimientos). También necesitamos dos funciones nuevas:

• valorar_posicion_contrario(): dada una posición del tablero (pasada como parámetro) realizará la evaluación estática si ya se ha alcanzado la profundidad máxima de búsqueda (que, por tanto, también se pasará como parámetro) y devolverá esa valoración. Si no se ha alcanzado esa profundidad, se generarán todos los posibles movimientos del jugador contrario y se llamará a la función valorar_posición_propia(), quedándonos con el valor mínimo de todos los que nos devuelva esta función.
• valorar_posicion_propia(): dada una posición del tablero (pasada como parámetro) realizará la evaluación estática si ya se ha alcanzado la profundidad máxima de búsqueda (que, por tanto, también se pasará como parámetro) y devolverá esa valoración. Si no se ha alcanzado esa profundidad, se generarán todos los posibles movimientos del jugador que tiene el turno y se llamará a la función valorar_posición_contrario(), quedándonos con el valor máximo de todos los que nos devuelva esta función.

En definitiva, la función valorar_posición_contrario() se ejecutará en los niveles del árbol correspondientes al jugador contrario (MIN) y valorar_posición_propia() se ejecutará en los niveles del árbol correspondientes al jugador actual (MAX)

Observa que la primera función llama a la segunda y la segunda a la primera, por lo que se produce una recursión doble. El caso base es aquél en el que se alcanza la profundidad máxima preestablecida: entonces se invoca la función de evaluación estática y la recursión termina.

Debe existir una tercera función llamada buscar_mejor_movimiento() o algo similar que se encargue de iniciar el proceso recursivo. Esta función calculará todos los posibles movimientos del jugador actual y, para cada uno de ellos, llamará a valorar_posicion_contrario(), ya que el siguiente movimiento corresponderá al jugador contrario. De todos los valores que nos devuelve esa función, debemos quedarnos con el mayor, considerando que es el mejor movimiento que podemos hacer, ya que maximiza nuestra ventaja y minimiza la del contrario.

Expresado en pseudocódigo:

función buscar_mejor_movimiento(tablero, estado)
inicio
  maximo = -9999
  para todos los movimientos que el jugador actual pueda hacer en “tablero”
  inicio
     copiar tablero en tablero2
     realizar el movimiento en tablero2
     valoracion = valorar_posicion_contrario(tablero2, 1)
     si (valoracion > maximo)
     inicio
       maximo = valoracion
       mejor_movimiento = movimiento_actual
     fin (si)
  fin (para)
fin (función)

función valorar_posicion_contario(tablero, profundidad)
inicio
  si (profundidad == PROFUNDIDAD_MAXIMA)
  inicio
    valoracion = evaluacion_estatica (tablero)
    devolver (valoracion)
  fin (si)
  minimo = 9999
  para todos los movimientos que pueda hacer el jugador contrario en “tablero”
  inicio
     copiar tablero en tablero2
     realizar el movimiento sobre tablero2
     valoracion = valorar_posicion_propia(tablero2, profundidad + 1)
     si (valoracion < minimo)
        minimo = valoracion
  fin (para)
  devolver (minimo)
fin (función)

función valorar_posicion_propia(tablero, profundidad)
inicio
   si (profundidad == PROFUNDIDAD_MAXIMA)
   inicio
      valoracion = evaluacion_estatica (tablero)
      devolver (valoracion)
   fin (si)
   maximo = -9999
   para todos los movimientos que pueda hacer el jugador actual en “tablero”
   inicio
      copiar tablero en tablero2
      realizar el movimiento sobre tablero2
      valoracion = valorar_posicion_contraria(tablero2, profundidad + 1)
      si (valoracion > maximo)
         maximo = valoracion
   fin (para)
   devolver (maximo)
fin (función)

Una mejora: Minimax con poda alfa-beta

La técnica minimax, como hemos dicho, no tiene por qué proporcionarnos el mejor movimiento posible. De hecho, puede provocar un movimiento manifiestamente malo y ante el que cualquier jugador avanzado de ajedrez sonreiría con suficiencia. Aunque, la mayoría de las veces, minimax proporcionará un movimiento razonablemente bueno.

El movimiento será tanto más bueno cuanto más podamos profundizar en el árbol de movimientos. De hecho, se considera que un buen jugador de ajedrez suele prever, aproximadamente, una media de 8 jugadas. Pero, como hemos visto, este árbol se ramifica demasiado y se hace muy pronto incalculable, incluso para los ordenadores más potentes. A este tipo de problemas se les denomina “no computables”, ya que no pueden ser procesados y resueltos en un tiempo razonable.

Pero hay una forma de lograr profundizar más en el árbol, llegando hasta seis, siete o más jugadas en el futuro: utilizando una variación de la técnica minimax denominada minimax con poda alfa-beta.

El minimax con poda se basa en la misma idea que un jugador humano de ajedrez: no es necesario mirar TODOS los estados porque hay algunos que, ya desde el principio y de forma evidente, son malos para el jugador que mueve. Por lo tanto, esas ramas del árbol no es necesario explorarlas porque, por más que descendamos, todos los estados resultarán muy negativos.

Para aplicar este principio a nuestro algoritmo debemos ejecutar la función de evaluación estática en algún nivel intermedio, antes de llegar a las hojas del árbol. Por ejemplo, si estamos explorando 5 jugadas, podemos aplicar la función de evaluación en el nivel 3. En esa jugada, le toca mover al jugador actual (es un nivel de tipo MAX en el algoritmo minimax). Evaluaremos todos los estados del nivel 3 como si fueran los últimos del árbol, y llamaremos al mejor de ellos ALFA.

A partir de entonces sólo seguiremos explorando las ramas del árbol cuyo valor estático en el nivel 3 sea igual ALFA (o, al menos, muy próximo a ALFA). Esto eliminará la gran mayoría de ramas del árbol, por lo que nos será fácil descender hasta el nivel 7 u 8. Si hacemos una segunda poda, podemos explorar niveles muy profundos en un tiempo razonable.

También podemos elegir hacer la poda en un nivel correspondiente al jugador contrario (por ejemplo, el nivel 4, que es de tipo MIN). En ese caso, aplicaremos la función de evaluación estática a todos los estados y elegiremos la menor de todas ellas, llamándola BETA. Podaremos todas las ramas cuyo valor estático sea mayor que ese valor BETA, profundizando en las demás.

Evidentemente, este método tampoco es infalible pues, aunque permite profundizar mucho más en el árbol, es muy posible que en alguna de las podas desechemos una rama que, aunque en ese momento proporciona una valoración pobre, en el futuro nos hubiera conducido a la victoria. A pesar de este riesgo, inherente a todas las técnicas heurísticas (que, recordemos, no pretenden encontrar soluciones infalibles, ya que se usan en problemas para los que es imposible encontrar dichas soluciones), el minimax con poda alfa-beta suele proporcionar mejores resultados que el minimax simple.