Minimax: la larga búsqueda

Nuestro programa ya tiene su motor, un generador de movimientos capaz de calcular todos los movimientos posibles en una posición determinada.

Nuestro siguiente trabajo es conseguir que el programa utilice adecuadamente su generador de movimientos. A esta parte se le suele llamar función de búsqueda.

En esencia se trata de un generador de posiciones: llamando repetidamente al generador de movimientos se llega a unas posiciones finales a las que se les asigna un valor determinado dependiendo de lo buenas o malas que sean para el programa.
Esta parte de los programas no suele ser muy original, casi todos usan un algoritmo clásico introducido por Von Newman que recibe el nombre de MINIMAX.

La misión de este algoritmo es construir el árbol de variantes y elegir entre todas las ramas la más beneficiosa para el programa. Para ver cómo funciona usaremos como ejemplo la posición inicial de una partida.

Es el turno de juego del programa, que lleva las blancas.
Lo primero que hacemos es llamar al generador para obtener la lista de todos los movimientos posibles en la posición. Como resultado de esta primera llamada al generador tendremos una lista que contendrá las jugadas a3,a4,b3,b4,Cf3,etc. hasta 20 que son las posibles jugadas que tienen a su disposición las blancas desde la posición de salida.

A continuación tenemos que procesar esta lista. Se trata de realizar cada una de estas jugadas en el tablero. Cada vez que reproducimos una jugada de la lista en el tablero obtenemos una nueva posición. Estas posiciones resultantes nos las guardamos en otra lista y volvemos la jugada atrás en nuestro tablero virtual antes de hacer la siguiente.

Al acabar la lista de movimientos tenemos como resultado tantas posiciones como jugadas posibles teníamos para realizar, posiciones que hemos tenido la precaución de guardarnos en memoria para seguir desarrollando el árbol.

Bien, tras esta primera pasada tenemos como resultado 20 posiciones. ¿Qué haremos con ellas?

Pues lo mismo que hemos hecho con la posición inicial que nos ha servido de punto de partida en este ejemplo: cada una de ellas se le pasa al generador de movimientos para obtener la lista de movimientos posibles.

Y con esta nueva lista de movimientos posibles repetimos el proceso anterior: las realizamos sobre el tablero y llamamos al generador de movimientos.

Recordemos que cuando hablamos de realizar y volver jugadas atrás lo que hacemos realmente es cambiar el valor de las casillas de nuestra matriz numérica.

Por ejemplo, donde había un 1 que significa un peón ponemos un 0 para indicar que la casilla ha quedado vacía. Para volver la jugada atrás volvemos a poner un 1 en la casilla original. Estas operaciones deben estar optimizadas para ser muy rápidas, porque se van a repetir millones de veces durante el proceso de búsqueda.

¿Y Cuándo termina este proceso? Para desarrollar esta parte del programa se utiliza una técnica de programación llamada recursividad, que básicamente significa que una parte del código se llama a sí misma en un proceso sin fin.

Resulta necesario por tanto cortar la búsqueda en algún punto, normalmente cuando se agota el tiempo asignado para esa búsqueda, pero también es posible que el programa siga buscando hasta una profundidad determinada, cancelando el proceso cuando se alcance.

De esta forma se construye el árbol de variantes, pero aún no tenemos ni idea de cual es la mejor jugada. Para esto tenemos que utilizar la función de evaluación. Aunque luego volveremos a hablar de esta parte, de momento nos quedamos con la idea de que es una parte del código que asigna un valor numérico a una posición.
El caso más sencillo posible sería una función de evaluación que simplemente sumara el valor material de las piezas (peones 1, alfiles y caballo 3, torres, 5, etc) y devolviera un valor resultado de valor material de un bando menos valor material del bando contrario..

A la función de evaluación se le pasan únicamente las posiciones terminales, y esto es muy importante: sólo las posiciones finales del árbol se evalúan. Los nodos anteriores adquieren valor según sus nodos hijos.

El truco para que todo esto funcione es que cada nodo toma el valor del máximo de sus nodos hijos si es el turno de juego del programa, o del mínimo en caso de que sea el turno de juego del rival.

De este hecho toma su nombre el algoritmo: maximizar y minimizar alternativamente en cada nivel, según cambia el turno de juego.