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":
Si no tiene hijos, estamos ante una hoja y, por tanto, aplicamos la función de evaluación con "evaluaTablero":
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:
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:
Posteriormente, cuando todos los hijos están ya evaluados recursivamente, nos quedamos con la menor puntuación con "minValorHijos":
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:
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:
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í:
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
No hay comentarios:
Publicar un comentario