RYG: función de evaluación – segunda versión

Bueno, pues vamos a intentar mejorar la función de evaluación para que el C64 juegue mejor. Hasta ahora veníamos considerando estos dos criterios posicionales:

  • La fila del ratón.
  • El número de movimientos del ratón.

Esto se puede ver en la rutina “evaluaTablero” del fichero “EvalTableros.asm”:

Rutina evaluaTablero

Parecen criterios un poco pobres, insuficientes para saber si un tablero es prometedor para el ratón o los gatos, que en el fondo es la información que usa el C64 para decidir su jugada.

Pero podemos observar que, si los gatos consiguieran guardar una fila cerrada, o al menos lo intentaran, sería mucho más difícil para el ratón rebasarlos. Mantener una fila cerrada no será siempre posible, ya que el ratón puede forzar que los gatos rompan la formación acercándose a ellos todo lo posible. Recordemos que en este juego no hay capturas.

Podemos intentar que los gatos guarden una fila cerrada obteniendo la fila mínima de los gatos, la máxima, y calculando la diferencia entre ellos. Si esa diferencia es cero, los gatos tienen que estar en fila; si es uno, no será una fila, pero al menos los gatos no estarán muy dispersos por el tablero; y así sucesivamente.

Total, añadimos la llamada a la nueva rutina “evaluaDifFilasGatos” en “evaluaTablero”:

Rutina evaluaTablero V2

La nueva rutina “evaluaDifFilasGatos” es así:

Rutina evaluaDifFilasGatos

Es decir, calcula la fila máxima con “maxFilaGatos”, la fila mínima con “minFilaGatos”, calcula la diferencia entre máximo y mínimo con la instrucción “sbc” y, el resultado (0, 1, 2, …, 7) lo usa como índice para acceder a la tabla con las evaluaciones parciales. Si la diferencia es 0 la evaluación parcial será $f0 = -16, si la diferencia es 1 será $f8 = -8 y, a partir de ahí, cero. Estas evaluaciones parciales son negativas porque se supone que guardar una fila cerrada, o casi, es una situación que favorece a los gatos.

Para calcular la fila máxima y la fila mínima las rutinas “maxFilaGatos” y “minFilaGatos” hacen básicamente lo mismo que las rutinas equivalentes del procedimiento minimax (máximo valor y mínimo valor), es decir, partir del valor más bajo ($00) o más alto ($ff), ir comparando las filas de los gatos contra ese valor, y quedarse al final con el valor más alto o más bajo de los comparados. Nada nuevo que merezca la pena detallar más.

Si tras este cambio de la versión 16 ensamblamos y jugamos, veremos que el C64 ya juega mejor. El juego no es tan naif como en la versión 15. Parece que el C64 ya juega como con más intención, como con más “mala leche”, buscando tapar las vías de escape. Aun así, todavía es posible ganarle con relativa facilidad, por lo que tendremos que seguir mejorando la función de evaluación.


Código del proyecto: RYG16

RYG: ampliar la RAM disponible

El juego ya esté esencialmente completo: permite que el humano y el C64 jueguen de forma continuada, alternando turnos, y detecta las condiciones de fin de partida.

Ahora bien, si probamos a jugar con la versión 15 del proyecto, da igual que sea con una profundidad de análisis de 1, 2 o 3 niveles, se verá que es relativamente fácil ganar al C64. Por tanto, tenemos que conseguir que el C64 juegue mejor.

Básicamente hay dos formas de conseguir que le C64 juegue mejor:

  • O aumentando la profundidad de análisis.
  • O mejorando la función de evaluación.

Ya hemos comentado varias veces que la profundidad del árbol de juego y la función de evaluación conforman una especie de compromiso. Si el árbol de juego pudiera generarse completo, bastaría con una función de evaluación muy tonta. Pero como el árbol no puede ser completo, porque la memoria es limitada, la función de evaluación tiene que ser más lista, tiene que permitir identificar aquellas ramas del juego que son más prometedoras.

Aumentar la profundidad de análisis:

Para aumentar la profundidad de análisis:

  • O aumentamos la memoria disponible.
  • O compactamos las estructuras de datos.
  • O ambas cosas.

De todo esto ya hablamos largo y tendido en la entrada “RYG: árbol de juego – memoria revisitada”, y ya decidimos entonces no compactar las estructuras de datos (complicaba mucho la programación) pero sí ampliar la RAM disponible. De hecho, quedó pospuesto hasta esta entrada.

Para ampliar la RAM disponible nos aprovechamos de las funciones de configuración del mapa de memoria del C64. Concretamente, actuando sobre el registro R6510 = $0001 podemos activar y desactivar diferentes partes de la memoria del C64:

Bit Nombre bit Si vale 0 Si vale 1
0 LORAM Las direcciones $a000 – $bfff direccionan RAM Las direcciones $a000 – $bfff direccionan la ROM con el intérprete de BASIC
1 HIRAM Las direcciones $e000 – $ffff direccionan RAM Las direcciones $e000 – $ffff direccionan la ROM con el Kernal
2 CHAREN Las direcciones $d000 – $dfff direccionan la ROM con el mapa de caracteres Las direcciones $d000 – $dfff direccionan los chips especiales y la RAM de color

Podemos desactivar el intérprete de BASIC, porque no lo utilizamos. Sin embargo, no podemos desactivar el Kernal, porque sí utilizamos rutinas como “chrout”.

Todo esto lo hacemos con la nueva rutina “ampliaRam”, que llamamos al arrancar el programa, y que básicamente pone a 0 el bit 0 (LORAM) del registro R6510 = $0001:

Rutina ampliaRam

De este modo, ganamos como RAM disponible el rango de direcciones del intérprete de BASIC ($a000 – $bfff = 8 KB), así como el rango $c000 – $cfff = 4 KB que, si bien siempre es RAM, al no estar contiguo hasta ahora con el espacio de trabajo del programa ($0801 – $9fff), no podíamos aprovecharlo fácilmente.

En total, ganamos estos 12 KB:

Memoria - ampliada

Sin embargo, incluso así es insuficiente para ganar otro nivel de análisis (pasar de tres a cuatro niveles) porque, como ya calculamos en su momento, para tres niveles hacían falta 22 KB y para cuatro 90 KB.

Total, nuestra principal esperanza es mejorar la función de evaluación, cosa que haremos en las entradas que siguen.


Código del proyecto: RYG16

RYG: condiciones de fin de partida

El C64 ya es capaz de generar el árbol de juego y decidir la jugada que más le interesa. De hecho, el humano y el C64 ya pueden jugar de forma continuada, alternando turnos.

Por tanto, el siguiente paso es detectar si la partida ha terminado o no, si han ganado el ratón o los gatos. En principio, la partida termina:

  • Cuando el ratón llega a la fila cero. En este caso gana el ratón.
  • Cuando los gatos acorralan al ratón. En este caso ganan los gatos.

Ahora bien, hay otra situación que, aunque improbable, interesa considerar. Supongamos que el ratón rebasa a los gatos, de modo que estos ya no pueden acorralarlo. Lo lógico sería que el ratón continuara directo hasta la fila cero para ganar la partida. Pero si el ratón es juguetón, y se dedica a dar un paso adelante y otro atrás, puede acabar ocurriendo que los gatos, que sólo pueden avanzar, se queden sin capacidad de moverse. En este caso, se considera que también gana el ratón porque ha escapado de los gatos.

Por tanto, son tres las condiciones de fin de partida:

  • Si el ratón ha llegado a la fila cero, gana el ratón.
  • Si los gatos no pueden moverse, también gana el ratón.
  • Si el ratón no puede moverse, ganan los gatos.

Las dos primeras condiciones las valoraremos justo después de mover el ratón. La última condición la valoraremos justo después de mover los gatos.

El ratón ha llegado a la fila cero:

Tras mover el ratón, es decir, tras solicitar al usuario el movimiento que desea, aplicarlo y pintar el tablero, llamamos a la rutina “verificaRatonFila0”:

Rutina verificaRatonFila0 - llamada

La rutina “verificaRatonFila0” verifica en qué fila se encuentra el ratón y, en caso de estar en la fila cero, lo señaliza con el valor $00 en el flag “vrf0”:

Rutina verificaRatonFila0

Al final, si el ratón está en la fila cero se acaba ejecutando “ganaRaton2”, que hace esto:

Rutina ganaRaton2

Es decir, pinta una felicitación, pide la pulsación de una tecla, espera a que se pulse, y termina, tras lo cual vuelve a inicializarse el juego.

Los gatos no pueden moverse:

Si el ratón no ha llegado a la fila cero, entonces llamamos a la rutina “verificaGatos0Jugs”:

Rutina verificaGatos0Jugs - llamada

La rutina “verificaGatos0Jugs” va obteniendo el número de jugadas posibles del ratón 0, el ratón 1, el ratón 2 y el ratón 3. Para ello utiliza la nueva rutina “cuentaJugadasGato”, que cuenta las jugadas del gato indicado (0, 1, 2 o 3).

Si en algún caso el número de jugadas es superior a cero, entonces directamente devuelve falso ($ff en el flag “vg0j”). Si el número de jugadas es cero en todos los casos, entonces devuelve cierto ($00 en el flag “vg0j”):

Rutina verificaGatos0Jugs

Rutina verificaGatos0Jugs - parte2

Al final, igual que cuando el ratón estaba en la fila cero, si el número de movimientos de los gatos es cero se acaba ejecutando “ganaRaton2”, que lógicamente hace lo ya mencionado (felicita al ratón, pide una tecla, e inicializa el juego).

El ratón no puede moverse:

Esta condición es similar a la anterior, pero aplicada al ratón. Si el ratón no ha ganado, el C64 desarrolla y evalúa el árbol de jugadas, decide la jugada que más le interesa, la aplica, pinta el tablero, y llama a “verificaRaton0Jugs”:

Rutina verificaRaton0Jugs - llamada

La rutina “verificaRaton0Jugs” es muy parecida a “verificaGatos0Jugs”, siendo la principal diferencia que sólo hay un ratón frente a cuatro gatos:

Rutina verificaRaton0Jugs

Usando la nueva rutina “cuentaJugadasRaton” contamos el número de jugadas del ratón y, caso de ser cero, lo señalizamos con $00 en el flag “vr0j”.

Al final, si el número de jugadas del ratón es cero se ejecuta “gananGatos2”:

Rutina gananGatos2

Esta rutina, de forma análoga a “ganaRaton2”, pinta un mensaje (ahora es un lamento en vez de una felicitación 😦 ), pide una tecla, espera a que se pulse, y vuelve a inicializar el juego.

Resultado:

El resultado es que se permite el juego continuado de ratón y gatos y, además, ya se detectan las condiciones de final de partida. Por ejemplo, en este caso ha ganado el ratón:

Gana ratón


Código del proyecto: RYG15

RYG: el C64 por fin decide su jugada

¡¡Por fin el C64 va a decidir su jugada!! ¿¿No es emocionante?? 🙂

No sé si seréis conscientes, pero para llegar hasta aquí hemos tenido que recorrer todo este camino:

  • Generar las jugadas o movimientos básicos de los gatos.
  • Generar tableros hijo a partir de un tablero padre, aplicando un movimiento.
  • Generar el primer nivel del árbol de juego.
  • Corregir la validación de jugadas, que tenía errores.
  • Generar un árbol de juego de profundidad N aplicando recursividad.
  • Evaluar tableros aplicando criterios posicionales.
  • Evaluar el árbol de juego completo con la función de evaluación.
  • Pintar el árbol de juego completo con sus evaluaciones y vinculaciones entre tableros.
  • Evaluar las hojas del árbol con la función de evaluación, y llevar estas evaluaciones hasta la raíz con el procedimiento minimax.

Todo este camino es para eso: ¡¡para que el C64 decida su jugada!! El camino ha sido tan largo que es fácil perder la perspectiva…

Gráficamente, la situación en la que nos encontramos es ésta:

Minimax - raíz2

Es decir, tenemos un tablero de partida (raíz del árbol), este tablero tiene una serie de hijos (posibles movimientos de los gatos) y, tras desarrollar el árbol de juego hasta una profundidad N y evaluarlo con minimax, hemos llegado a unas valoraciones para los hijos e, incluso, nos hemos quedado con la menor de ellas (la más beneficiosa para los gatos: $82). Por tanto, ya sólo se trata de algo tan sencillo como optar por el hijo que tenga esa valoración mínima.

En este caso particular se ha producido un empate, porque todos los tableros hijo han sido valorados con $82. Por tanto, podemos optar por el primero de ellos, el último de ellos, elegir uno aleatoriamente, o tomar el que más rabia nos dé.

Si queremos darle emoción al asunto, y que el C64 juegue de una forma más imprevisible, podemos apoyarnos en el Jiffy Clock (posiciones $a0 – $a1 – $a2) para elegir uno de los tableros empatados de forma aleatoria. A estas alturas, y con el objeto de simplificar, optaremos por el primero de los tableros en empate.

Lo importante es no tomar el caso particular por el general. En un caso general, especialmente cuando las partidas estén más avanzadas, el C64 tendrá que elegir entre puntuaciones que serán dispares.

Para optar por el hijo de puntuación mínima hacemos lo siguiente:

Rutina “decideJugadaMin”:

En el fichero “EvalTableros.asm” dotamos una nueva rutina “decideJugadaMin” que, dado un tablero padre evaluado con minimax, determina el hijo que ha dado lugar a esa evaluación, es decir, determina el hijo con menor puntuación.

Primero recuperamos el valor del padre:

Rutina decideJugadaMin - parte1

Y luego recorremos los hijos buscando al que aporta esa valoración:

Rutina decideJugadaMin - parte2

Por último, cuando damos con el hijo que aporta esa valoración (“beq djmFin”), nos quedamos con los datos de ese hijo (número de hijo y dirección):

Rutina decideJugadaMin - parte3

Obsérvese que en caso de empate entre varios hijos estaríamos optando por el primero, puesto que en cuanto encontramos un hijo con la valoración correcta nos quedamos con él. Aquí es donde se podría meter aleatoriedad para darle más emoción al asunto.

Nuevo programa principal “RYG.asm”:

Ahora que ya sabemos localizar al mejor hijo, al predilecto, vamos a optar por él. Para ello, volvemos a modificar el programa principal “RYG.asm”:

Programa principal - decisión

Es decir, tras la evaluación del árbol con minimax:

  • Dejamos de pintar el árbol. Hasta ahora veníamos pintando el árbol para depurar la función de evaluación y el procedimiento minimax.
  • Optamos por la jugada de menor puntuación con “decideJugadaGatos”.
  • Aplicamos esa jugada con “aplicaJugadaDecidida”, igual que en su momento aplicamos la jugada elegida por el usuario humano con “aplicaJugadaSolicitada”.
  • Y cerramos el bucle de juego con “jmp actualiza”, que vuelve a pintar el tablero actual (ya actualizado) y vuelve a pedir la jugada del humano.

Respecto a la rutina “decideJugadaGatos” básicamente es una llamada a la ya presentada “decideJugadaMin”:

Rutina decideJugadaGatos

Y respecto a la rutina “aplicaJugadaDecidida”, consiste en copiar el hijo elegido sobre el tablero actual, el que controla la situación actual de la partida, y hacer alguna labor menor de inicialización:

Rutina aplicaJugadaDecidida

Resultado:

El resultado es la versión 14 del proyecto, que prácticamente ya está terminado. El juego está casi completo, ya que permite jugar al humano y al C64 de forma continuada, una jugada tras otra.

Queda detectar si la partida ha terminado, es decir, si tras un movimiento han ganado el ratón o los gatos. Pero esto ya lo haremos en la entrada siguiente.


Código del proyecto: RYG14

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

RYG: procedimiento minimax – rutinas previas

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 ante 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

RYG: función de evaluación – pintado del árbol

Ya tenemos una función de evaluación (rutina “evaluaTablero”) y una rutina que evalúa recursivamente todos los tableros del árbol (rutina “evaluaArbol”).

Todo esto hay que probarlo, y la mejor manera de probarlo es pintando el árbol de juego con sus evaluaciones, y comprobando que éstas efectivamente responden a los criterios definidos.

Para ello vamos a desarrollar una nueva rutina, llamada “pintaArbol”, que se encargará de pintar el árbol de juego completo. Esta rutina nuevamente será recursiva (se llamará a sí misma), y estará definida en el fichero “pintaTableros.asm”. La llamaremos justo después de construir y evaluar el árbol:

Rutina pintaArbolJugadas - llamada

Rutina pintaArbol - llamada

Hasta ahora teníamos una rutina para pintar tableros (“pintaTablero”), pero no una rutina para pintar el árbol completo (“pintaArbol”). Además, la rutina para pintar tableros la llamábamos sobre la marcha, según se iban generando los tableros (rutinas “aplicaJugadaGatoHijo” y “aplicaJugadaRatonHijo”), lo que tenía como efectos secundarios:

  • No se podían pintar las direcciones de los hijos, porque recién creado un tablero sus hijos todavía no están creados.
  • No se podía pintar la evaluación del tablero, porque primero creamos el árbol completo (sus tableros) y luego lo evaluamos también completo.

En realidad, hasta ahora veníamos llamando a la rutina “pintaTablero” desde “aplicaJugadaGatoHijo” y desde “aplicaJugadaRatonHijo” más como una forma de depurar que los tableros o jugadas se generan bien, que por el interés que tuviera pintar esos tableros.

Sea como fuere, hay que cambiar el enfoque, porque ahora queremos pintar las evaluaciones, lo que nos lleva a:

  • Dejar de llamar a “pintaTablero” desde “aplicaJugadaGatoHijo” y “aplicaJugadaRatonHijo”. En vez de esto pintamos un punto (“.”), lo que pretende transmitir la idea de que el C64 está pensando. Y en realidad lo está haciendo, porque está generando tableros.
  • Empezar a llamar a “pintaArbol” tras construir y evaluar el árbol completo, lo que nos permitirá visualizar las evaluaciones y, ya de paso, también las direcciones de los hijos.

Finalmente, aprovechamos para hacer un pequeño cambio estético, y en vez de pintar los turnos con $01 (ratón) y $ff (gatos), definimos la rutina “pintaTurno”, que pinta los literales “RATON” y “GATOS” respectivamente.

La rutina “pintaArbol” tiene una estructura muy similar a las otras rutinas recursivas que ya hemos visto (“evaluaArbol” y “desarrollaUnNivel”):

  • Primero evalúa si se ha terminado de pintar el árbol.
  • Si no se ha terminado, pinta la raíz del árbol con “pintaTablero”.
  • Y luego recorre los hijos pintándolos también llamándose de forma recursiva.

En esta primera parte evalúa si se ha terminado o continuar:

Rutina pintaArbol - parte1

En esta segunda parte pinta la raíz del árbol actual. Para ello usa “pintaTablero”:

Rutina pintaArbol - parte2

Y, por último, en la tercera parte recorre los hijos y los pinta recursivamente:

Rutina pintaArbol - parte3

Lo importante es el resultado final. Y si ahora ejecutamos el juego con un nivel de profundidad dos, primero aparece “PENSANDO: ……………………………..” mientras se genera el árbol de juego:

Pensando

Y luego, tras generarlo, se pinta el árbol completo (lo que sigue es la pantalla final tras todo el scroll vertical):

Rutina pintaArbol - resultado

En esta imagen se puede observar que:

  • En el turno ya aparece “RATON” o “GATOS” y no $01 o $ff.
  • Ya aparece la evaluación del tablero, que en el caso anterior es de $7e.
  • Ya aparecen las direcciones de los hijos, salvo que el tablero en cuestión sea una hoja del árbol (como el de la imagen anterior), en cuyo caso no tiene hijos y aparecen todos inicializados a $0000.

Lo importante ahora es validar si $7e es la evaluación correcta del tablero conforme a los criterios definidos:

  • Fila del ratón => +0 puntos.
  • Movimientos del ratón => -2 puntos.
  • Evaluación de partida (punto neutro) => $80.

Total = $80 – $02 = $7e. Por tanto, la evaluación es correcta. Y esto mismo se puede comprobar para todos los tableros del árbol generado y pintado.

Y puesto que parece que ya conseguimos evaluar bien, el siguiente paso será el procedimiento minimax.


Código del proyecto: RYG12

RYG: función de evaluación – evaluación del árbol completo

Ahora que ya tenemos la función de evaluación, vamos a aplicarla.

Lo suyo sería aplicarla sólo sobre las hojas del árbol, y hacer subir las valoraciones mediante el procedimiento minimax. Sin embargo, de momento, vamos a evaluar todos y cada uno de los tableros del árbol. Así podemos comprobar si la rutina funciona bien con un montón de tableros y, de paso, vamos preparando el procedimiento minimax.

Por otro lado, ya comentamos que la evaluación puede hacerse sobre la marcha, según se van generando los tableros, o ya al final, con todo el árbol de juego generado. Y como no pensamos aplicar un procedimiento de poda, vamos a hacerlo al final. Así es más claro.

Rutina “evaluaArbol”:

Para conseguir lo anterior dotamos una nueva rutina “evaluaArbol” en el fichero “EvalTableros.asm”. Esta rutina es recursiva, igual que la que generaba el árbol de juego completo. Recibe un tablero (con sus hijos enlazados) y una profundidad, y hace lo siguiente:

  • Si la profundidad ya es menor que cero, termina.
  • Si la profundidad es cero o mayor:
    • Evalúa el tablero actual.
    • Recorre los tableros hijo y, de forma recursiva, los evalúa (reduciendo previamente la profundidad en uno).

De este modo se consigue evaluar de forma recursiva todo el árbol. Cuando la evaluación llega a las hojas del árbol termina, porque ya no hay más hijos que evaluar.

Esta es la primera parte de “evaluaArbol”, donde se decide si seguir evaluando o terminar ya (profundidad = $ff = -1):

Rutina evaluaArbol - parte1

Esta es la segunda parte de la rutina, donde se evalúa el tablero actual con la rutina ya conocida “evaluaTablero”:

Rutina evaluaArbol - parte2

Y en la tercera parte se recorren los hijos del tablero actual (“jsr dameHijo”), se decrementa la profundidad en uno (“sbc #$01”), y se continúa recursivamente con todos los hijos (“jsr evaluaArbol”):

Rutina evaluaArbol - parte3

Llamada a la rutina “evaluaArbol”:

La rutina “evaluaArbol”, como toda rutina, hay que llamarla para que en la práctica haga algo. Y ya hemos dicho que vamos a llamarla tras generar el árbol completo, es decir, aquí:

Rutina evaluaArbol - llamada

La llamada a “evaluaArbolJugadas” se produce justo después de generar el árbol de juego (“jsr desarrollaArbolJugadas”). Y “evaluaArbolJugadas” es básicamente una simple llamada a la recién presentada “evaluaArbol”:

Rutina evaluaArbolJugadas

Puede que llame la atención también la llamada “jsr pintaArbolJugadas”, pero su propósito lo comentaremos ya en la entrada siguiente.


Código del proyecto: RYG12

RYG: función de evaluación – primera versión

La función de evaluación es una funcionalidad nueva. Por tanto, vamos de dotarla en un fichero nuevo: “EvalTableros.asm”. En este fichero encontramos:

Rutina “evaluaTablero”:

La rutina principal de este nuevo fichero es “evaluaTablero”:

Rutina evaluaTablero

Esta rutina recibe un tablero y devuelve su valor. Para ello:

  • Inicializa la evaluación al valor neutro $80.
  • Evalúa la posición del ratón con la rutina “evaluaFilaRaton”.
  • Evalúa la movilidad del ratón con la rutina “evaluaMovsRaton”.

La rutina no sólo devuelve el valor en la variable “etValor”. Además, lo almacena en el propio tablero evaluado llamando a “meteValorTablero”. Recordemos que uno de los campos de todo tablero es el campo “valor”.

Rutina “evaluaFilaRaton”:

La fila del ratón es el primer criterio posicional. Como ya adelantamos, vamos a evaluarla así:

  • Situaciones favorables al ratón:
    • Ratón en fila 7 => +0 puntos
    • Ratón en fila 6 => +1 puntos
    • Ratón en fila 5 => +2 puntos
    • Ratón en fila 4 => +3 puntos
    • Ratón en fila 3 => +4 puntos
    • Ratón en fila 2 => +5 puntos
    • Ratón en fila 1 => +6 puntos
    • Ratón en fila 0 (gana el ratón) => +32 puntos = $20

Esto es fácil de implementar con una tabla de datos que, en función de la fila ocupada por el ratón, devuelve la evaluación:

Rutina evaluaFilaRaton

Para hacer esto, la rutina:

  • Localiza el ratón sobre el tablero con “dameRaton”.
  • Convierte el offset del ratón en (fila, columna).
  • Usando la fila como índice, accede a la tabla con las valoraciones.
  • Suma la nueva valoración a la de partida ($80).

Rutina “evaluaMovsRaton”:

La movilidad del ratón es el segundo criterio posicional. Como ya dijimos, también, vamos a evaluarlo así:

  • Situaciones favorables a los gatos:
    • Ratón con 4 movimientos => -0 puntos
    • Ratón con 3 movimientos => -1 puntos = $ff
    • Ratón con 2 movimientos => -2 puntos = $fe
    • Ratón con 1 movimientos => -3 puntos = $fd
    • Ratón con 0 movimientos (ganan los gatos) => -32 puntos = $e0

Esto también se puede resolver con una tabla de datos, pero requiere un poco más de trabajo, porque previamente hay que calcular cuántos movimientos admite el ratón en el tablero evaluado.

Por ello, la rutina es así (primera parte):

Rutina evaluaMovsRaton - parte1

Es decir:

  • Localiza el ratón sobre el tablero.
  • Convierte el offset del ratón en (fila, columna).
  • Y genera las jugadas válidas del ratón.

Posteriormente, la rutina sigue así (parte 2):

Rutina evaluaMovsRaton - parte2

Es decir:

  • Cuenta las jugadas válidas del ratón con el registro Y.
  • Usando Y como índice, accede a la tabla con las valoraciones.
  • Suma la nueva valoración a la anterior ($80 + fila del ratón).

De este modo, ya tenemos la valoración completa, al menos en lo que respecta a esta primera versión de la función de evaluación.

Pero, además de devolver el valor con “etValor”, resulta cómodo tenerlo a mano en el propio tablero evaluado, motivo por el que “evaluaTablero” termina llamando a “meteValorTablero”.

Rutina “meteValorTablero”:

La rutina que almacena el valor en el tablero evaluado es así:

Rutina meteValorTablero

Y como el valor forma parte de la terna que hemos llamado “datos básicos” (nivel, turno y valor), la rutina:

  • Utiliza “dameDatosBasicos” para obtener la terna.
  • Y utiliza “fijaDatosBasicos” para volver a fijar la terna, previo cambio del valor original (“ddbValor”) por el nuevo valor (“etValor”).

En alguna versión posterior del proyecto haremos una rutina más directa (“fijaValor”) que permita cambiar sólo el valor sin tanto trasiego de datos.

Y con esto la versión 12 del proyecto ya tiene su primera versión de la función de evaluación. Pero falta aplicarla a un tablero o conjunto de tableros, cosa que ya haremos en la siguiente entrada.


Código del proyecto: RYG12

RYG: función de evaluación – cuestiones previas

De las cuatro piezas fundamentales de todo juego de tablero:

ya tenemos las dos primeras. Yo creo que con esto ya hemos alcanzado la cima del proyecto y a partir de ahora ya es todo un poco más cuesta abajo.

El siguiente paso, por tanto, es la función de evaluación. La función de evaluación es una rutina que recibe un tablero y devuelve cómo de bueno o malo es para ratón y gatos.

Criterios de evaluación:

Las funciones de evaluación, como ya comentamos, suelen tener en cuenta:

  • Criterios materiales.
  • Y criterios posicionales.

Los criterios materiales tienen que ver con las piezas que quedan sobre el tablero y las que ya se han “comido”. Pero como en el juego del ratón y los gatos no hay capturas, no tiene sentido aplicar criterios materiales. Siempre habrá las mismas piezas sobre el tablero.

Y los criterios posicionales tienen que ver con la posición de las piezas: si tienen más movilidad, menos movilidad, si han llegado o están cerca del objetivo, si su posición es más ofensiva, más defensiva, etc. Todos los criterios que aplicaremos aquí serán posicionales.

Empezaremos haciendo una función de evaluación sencilla, con pocos criterios posicionales, y la iremos mejorando con sucesivas versiones.

Evaluación y procedimiento minimax:

En principio, la función de evaluación se aplica sólo sobre las hojas del árbol de juego, es decir, sobre los tableros de máxima profundidad. Y, a partir de ahí, las evaluaciones se van haciendo subir por el árbol de juego mediante el procedimiento minimax.

Sin embargo, debemos ir poco a poco. Así que en una primera versión haremos una función de evaluación sencilla y la aplicaremos sobre todos los nodos (tableros) del árbol de juego. Esto nos permitirá dos cosas:

  • Probar bien la función de evaluación, ya que tendremos muchos tableros de ejemplo sobre los que probarla (todos los del árbol).
  • Y preparar la base del procedimiento minimax, que sí tiene que trabajar sobre todos los tableros del árbol.

Cuándo evaluar:

Respecto a cuándo evaluar, básicamente hay dos opciones:

  • O generar todo el árbol completo y luego evaluar.
  • O evaluar los tableros según se van generando.

La primera opción es más sencilla y es la que vamos a aplicar. Es más sencilla porque el tipo de evaluación depende de que el tablero sea una hoja del árbol o un nodo intermedio. En el primer caso se aplica la función de evaluación propiamente dicha; en el segundo caso se aplica el procedimiento minimax. Y esta distinción (hoja o nodo intermedio) es más fácil de hacer teniendo el árbol completo que sobre la marcha.

La segunda opción es un poco más compleja, pero es necesaria si se quiere aplicar un procedimiento de poda. No tendría sentido generar el árbol completo para luego podar algunas ramas, ya que ya se habría incurrido en el coste de generarlas.

Valores de las evaluaciones:

El objetivo de la función de evaluación es devolver un número que diga cómo de bueno o malo es un tablero para el ratón y los gatos. El valor absoluto es lo de menos; lo importante es que, si se compara la evaluación de un tablero T1 con la de otro tablero T2, quede claro qué tablero es más favorable para el ratón (o los gatos) y qué tablero es más desfavorable.

Por ello, tenemos bastante libertad para elegir el rango de valores para las evaluaciones. Supongamos que decidimos usar un byte (256 valores distintos).

Puesto que el ratón se señaliza sobre el tablero con el valor $01 (positivo) y los gatos con el valor $ff = -1 (negativo), una primera opción intuitiva sería asignar valoraciones positivas para lo que favorece al ratón y perjudica a los gatos, y valoraciones negativas para lo que favorece a los gatos y perjudica al ratón.

Criterios posicionales

Por ejemplo, algo así (recordemos que el objetivo del ratón es llegar a la fila cero, y el objetivo de los gatos es acorralar al ratón):

  • Situaciones favorables al ratón:
    • Ratón en fila 7 => +0 puntos
    • Ratón en fila 6 => +1 puntos
    • Ratón en fila 5 => +2 puntos
    • Ratón en fila 4 => +3 puntos
    • Ratón en fila 3 => +4 puntos
    • Ratón en fila 2 => +5 puntos
    • Ratón en fila 1 => +6 puntos
    • Ratón en fila 0 (gana el ratón) => +32 puntos = $20
  • Situaciones favorables a los gatos:
    • Ratón con 4 movimientos => -0 puntos
    • Ratón con 3 movimientos => -1 puntos = $ff
    • Ratón con 2 movimientos => -2 puntos = $fe
    • Ratón con 1 movimientos => -3 puntos = $fd
    • Ratón con 0 movimientos (ganan los gatos) => -32 puntos = $e0

Sin embargo, manejar números negativos en ensamblador no es fácil. No es fácil compararlos, no es fácil calcular el máximo ni el mínimo (procedimiento minimax), al operar con ellos se puede producir desbordamiento, es decir, al sumar dos números positivos el resultado puede ser aparentemente negativo (situación señalizada con el flag V), etc.

Por todo ello, y dado que los valores absolutos de las evaluaciones son lo de menos, simplifica bastante la vida tomar un valor intermedio en el rango 0 – 256 como valor neutro y, a partir de ahí, tomar valores por debajo para situaciones que favorecen a los gatos y valores por encima para situaciones que favorecen al ratón. En nuestro caso en particular vamos a tomar $80 = 128 como ese valor neutro y, a partir de ahí, sumaremos o restaremos, pero siempre manejaremos números positivos.

Evaluaciones

Con todos estos comentarios previos ya estamos listos para abordar la primera versión de la función de evaluación, cosa que ya dejamos para la siguiente entrada.