RYG: procedimiento minimax

Ya somos capaces de saber si estamos ante una hoja del árbol o ante un tablero intermedio. En el primer caso evaluamos con la función de evaluación; en el segundo caso aplicamos el máximo o el mínimo, según el turno de juego.

Y esto es, precisamente, el procedimiento minimax, que se materializa en la nueva rutina “miniMax” del fichero “EvalTableros.asm”. Una vez más, será una rutina recursiva.

Rutina “miniMax”:

Empezamos analizando si el tablero tiene hijos o no con “dameNumHijos”:

Rutina miniMax - parte1

Si no tiene hijos, estamos ante una hoja y, por tanto, aplicamos la función de evaluación con “evaluaTablero”:

Rutina miniMax - parte2

Y si sí tiene hijos, estamos ante un nodo intermedio, lo que significa que tenemos que aplicar el valor máximo o mínimo en función del turno de juego:

Rutina miniMax - parte3

El turno de juego lo obtenemos con la rutina “dameDatosBasicos” (aunque también podríamos hacer una nueva rutina “dameTurno”) y, en función del turno, llamamos a “maxHijos” si es el turno del ratón o “minHijos” si es el turno de los gatos.

Estas últimas rutinas no son más que una forma de estructurar un poco más la rutina “miniMax”, para que no salga demasiado larga o compleja. Se revisan a continuación.

Rutina “minHijos”:

Recordemos que estamos ante un tablero intermedio, no ante una hoja, y que es el turno de los gatos. Por tanto, los gatos elegirán el hijo con menor puntuación.

Para ello, recorremos los hijos con “dameHijo” y llamamos recursivamente a “minimax” para cada uno de ellos:

Rutina minHijos - parte1

Posteriormente, cuando todos los hijos están ya evaluados recursivamente, nos quedamos con la menor puntuación con “minValorHijos”:

Rutina minHijos - parte2

Rutina “maxHijos”:

Esta rutina es totalmente análoga a “minHijos”. Igualmente, es una rutina instrumental, cuyo objetivo no es tanto abstraer una funcionalidad autocontenida como simplificar “miniMax”.

Igual que “minHijos”, recorre los hijos del tablero intermedio, llama recursivamente a “miniMax” para cada uno de ellos y, cuando todos los hijos están ya evaluados, se queda con el máximo al ser ahora el turno del ratón.

Nuevo programa principal “RYG.asm”:

Para poner en funcionamiento el nuevo procedimiento minimax ya sólo queda modificar el programa principal “RYG.asm”, y más concretamente su rutina “evaluaArbolJugadas”, deja de llamar a “evaluaArbol”, que evaluaba todos los tableros de forma independiente, y pasar a llamar a “miniMax”.

Es decir, este cambio:

Rutina evaluaArbolJugadas - minimax

Si ahora probamos la versión 13 del proyecto, veremos que las hojas del árbol se siguen evaluando conforme a los criterios posicionales definidos (fila y número de movimientos del ratón), pero que los tableros intermedios se evalúan conforme a la puntuación de los hijos y de quién es el turno (ratón o gatos).

Por ejemplo, si probamos con un árbol de profundidad dos, tras construir, evaluar y pintar el árbol completo, nos sale esta raíz:

Minimax - raíz

Es decir, el tablero raíz es el resultado de que el usuario haya movido el ratón desde (7, 3) hasta (6, 2). Este tablero, tiene siete hijos correspondientes a los siete posibles movimientos de los gatos. Las direcciones de los hijos son $1ea1, $1ef9, …, $20b1.

Si evaluamos el tablero atendiendo a los criterios posicionales, saldría:

  • Valor de partida => $80 puntos.
  • Fila del ratón = 6 => +1 puntos.
  • Movimientos del ratón = 4 => -0 puntos.

Es decir, el valor del tablero sería $81. De hecho, este es el valor que salía con la versión 12 del proyecto. Entonces… ¿por qué ahora sale el valor $82? Pues porque ahora no estamos evaluando ese tablero atendiendo a la función de evaluación o los criterios posicionales, sino en función del procedimiento minimax.

De hecho, el árbol de juego de profundidad dos es así:

Minimax - raíz2

Partiendo de la raíz $1e49 se observan los siete hijos en $1ea1, $1ef9, …, $20b1. Estos siete hijos son los siete movimientos posibles de los gatos. A su vez, cada uno de los hijos tiene otros cuatro nietos, correspondientes a los cuatro movimientos del ratón. En total, 1 raíz + 7 hijos + 7×4 nietos = 36 tableros.

En el nivel más bajo, el ratón elegiría su mejor movimiento, es decir, el que maximiza el valor. Por eso entre $82 y $7e se elige $82. Y luego los gatos también elegirán su mejor movimiento, que en su caso será el minimice el valor. En este caso particular todos los hijos valen $82, así que el mínimo también es $82. Esto es habitual al comienzo de las partidas, donde todos los tableros analizados son más o menos parecidos. En un caso más general los hijos tomarán valores distintos e igualmente habrá que elegir entre ellos.

Total, al final la valoración que el procedimiento minimax lleva hasta la raíz es $82, en vez de $81 que sería la valoración posicional, y el movimiento que eligen los gatos (el C64) es el que lleva al hijo que toma ese valor. Pero esta decisión la tomaremos ya en la entrada siguiente.


Código del proyecto: RYG13

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s