RYG: procedimiento minimax – rutinas previas #Programación retro del Commodore 64

En su momento ya introdujimos el procedimiento minimax. Como dijimos, este procedimiento es pura lógica, es asumir que igual que tú (ratón) quieres la mejor jugada para ti (la de mayor puntuación), tu contrincante (los gatos) querrán la mejor jugada para sí (la de menor puntuación). De ahí el nombre "minimax".

Por tanto, no tenemos que evaluar todos los tableros del árbol aisladamente unos de otros, como hemos hecho. Sólo tenemos que evaluar las hojas del árbol y, a partir de ahí, aplicar el procedimiento minimax (obtener el máximo o el mínimo, según el turno de juego) para llevar estas evaluaciones hasta la raíz del árbol.

Minimax2

Aplicando este procedimiento evaluaremos todo el árbol, es decir, todos sus tableros, pero poniendo en relación unos con otros. De poco valdría que el C64 eligiera una siguiente jugada en apariencia muy buena, si N jugadas más allá finalmente resulta ser muy mala. Al contrario, si hemos generado el árbol completo (hasta una profundidad N) es para poder "mirar más allá" de la siguiente jugada.

La suerte es que ya tenemos la base del procedimiento minimax: la rutina "evaluaArbol". Con algunas pequeñas modificaciones será suficiente para construir una nueva rutina "miniMax". Pero vayamos por partes:

Rutina "dameNumHijos":

Lo primero que vamos a hacer es desarrollar es una rutina "dameNumHijos". Esta rutina nos resultará útil para saber si estamos ante una hoja del árbol (número de hijos = 0) o en un tablero intermedio (número de hijos > 0). Es decir, nos servirá para saber si tenemos que evaluar el tablero con la función de evaluación o con el procedimiento minimax.

La nueva rutina "dameNumHijos" la meteremos en el fichero "Tableros.asm" y, como ya tenemos una rutina "dameHijo" que nos permite recuperar el hijo enésimo, nos apoyaremos en ella:

Rutina dameNumHijos

La rutina es básicamente un bucle desde Y = 0 hasta Y = 7. Para cada valor del registro Y se pide el hijo Y-ésimo llamando a "dameHijo". Si el resultado es la dirección $0000 hemos terminado, porque los hijos de un tablero se van rellenando por orden (0, 1, 2, …). Si el resultado no es $0000 incrementamos Y, pasando al siguiente hijo e indirectamente incrementando la cuenta de hijos (que llevamos en Y). Si llegamos a Y = 8 necesariamente hemos terminado porque el máximo de hijos de un tablero es ocho.

Una cosa curiosa es que la dirección del hijo Y-ésimo tendrá dos partes, la parte "hi" y la parte "lo". En teoría, deberíamos contrastar ambas contra $00 para saber si existe el hijo (<> $0000) o si no existe (= $0000). En la práctica, llega con comparar la parte "hi" contra $00 puesto que, como no usamos la página cero para almacenar el árbol, si hi = $00 es indicio suficiente de que el hijo no existe.

Rutina "minValorHijos":

El procedimiento minimax se basa en elegir el hijo de mínima puntuación cuando juegan los gatos o el de máxima puntuación cuando juega el ratón. Por tanto, vamos a necesitar una rutina que identifique al hijo de mínima puntuación (este apartado) y otra que identifique al hijo de máxima puntuación (apartado siguiente).

En realidad, ni siquiera es necesario identificar el hijo de mínima / máxima puntuación, en el sentido de saber cuál es ese hijo o qué posición ocupa en la tabla de hijos de un tablero. En realidad, es suficiente con ser capaces de obtener esa puntuación mínima / máxima y asignarla al tablero padre. Así que esto es lo que vamos a hacer.

Cuando tienes una lista de valores, por ejemplo, $80, $87 y $7c, una forma de obtener el mínimo es partir del valor máximo posible, que en el caso de un byte sería $ff, e ir comparando los valores contra ese mínimo. Si el valor actual es menor que el mínimo hasta ahora, te quedas con el nuevo mínimo; si el valor actual es mayor que el mínimo hasta ahora, no haces nada. Veamos:

  • Partimos de mínimo = $ff.
  • ¿Es $80 menor que $ff? Sí, por tanto, mínimo = $80.
  • ¿Es $87 menor que $80? No, por tanto, no hacemos nada.
  • ¿Es $7c menor que $80? Sí, por tanto, mínimo = $7c.

De este modo, terminamos con el valor mínimo ($7c). Y ahora en versión rutina "minValorHijos" del fichero "Tableros.asm":

Partimos del máximo valor posible:

Rutina minValorHijos - parte1

Recorremos los hijos con "dameHijo", obtenemos su valor con "dameValor", y vamos comparando el valor de los hijos contra el mínimo hasta ahora:

Rutina minValorHijos - parte2

Finalmente, ya con el valor mínimo de los hijos identificado, lo fijamos como valor del padre con "fijaValor":

Rutina minValorHijos - parte3

Las rutinas "dameValor" y "fijaValor" son nuevas también, y permiten obtener y fijar el valor de un tablero sin tener que obtener / fijar todos sus datos básicos (nivel, turno y valor). Son sencillas, y también están en "Tableros.asm".

Gracias a que manejamos valoraciones que son siempre positivas (valor neutro $80) la comparación de valores puede hacerse fácilmente con las instrucciones "cmp" y "bcs". La comparación de valores hubiera sido notablemente más complicada en caso de usar valoraciones positivas y negativas.

Rutina "maxValorHijos":

Esta rutina es totalmente análoga a la "minValorHijos" ya vista. La principal diferencia es que ahora buscamos el valor máximo y, por tanto, partimos del valor mínimo posible que, en el caso de un byte, es $00:

Rutina maxValorHijos - parte1

Otra diferencia es que ahora la comparación de valores la hacemos con las instrucciones "cmp" y "bcc":

Rutian maxValorHijos - parte2

Por lo demás, son rutinas casi idénticas. Nuevamente, el hecho de usar valoraciones siempre positivas simplifica la comparación y la obtención del máximo.

Con estos mimbres ya somos capaces de hacer el cesto (procedimiento minimax), pero como esta entrada ya ha sido demasiado larga lo dejamos para la siguiente.


Código del proyecto: RYG13


Editar

Josepzin

No hay comentarios:

Publicar un comentario