RYG: tableros más compactos – cambios en el código

Los cambios en el diseño del tablero tienen su impacto en el código del juego. Además de una reducción obvia en el tamaño de la estructura de datos (de 88 a 29 bytes) hay un cambio en el enfoque de los datos: antes teníamos una matriz de 8×8 casillas que podían estar vacías, ocupadas por un ratón o por gatos; ahora tenemos directamente la posición de los cinco protagonistas y todo lo demás se presupone vacío.

Lógicamente tienen que cambiar cosas en el código como la forma de generar las jugadas o la forma de evaluar los tableros. Sin embargo, como veremos más adelante, y sorprendentemente, los cambios son mucho más acotados de lo que podría parecer en un principio.

Nuevo tablero actual:

Si la estructura de datos del tablero cambia, lo primero que cambia es el tablero actual, el que controla la situación actual de la partida (ver fichero “Arbol.asm”). En vez de tener 88 bytes, tendrá 29.

Nuevas rutinas para el manejo de tableros:

Más importante que lo anterior, también cambian las rutinas que permiten manejar tableros, es decir, las rutinas del fichero “Tableros.asm”. Sorprendentemente, muchas rutinas no cambian porque sólo manejan los datos de los tableros que no hemos tocado (nivel, turno, valor, padre o hijos).

Sin embargo, otras rutinas sí tienen que cambiar:

  • La rutina “inicializaTablero” ya no tiene que rellenar un tablero con 64 casillas vacías. Ahora sólo tiene que fijar las posiciones iniciales del ratón (offset = 59) y los gatos (offsets = 0, 2, 4 y 6), ya que todo lo demás se presupone vacío.
  • Las rutinas “dameContenido” y “fijaContenido” dejan de tener sentido. Ya no tenemos 64 casillas que rellenar con un contenido (#Raton, #Gato o #Vacio). Ahora tenemos cinco bytes con las posiciones (offsets) de ratón y gatos. Estas posiciones se especifican con las nuevas rutinas “fijaPosicionRaton” y “fijaPosicionGato”.
  • Las rutinas “dameOffset” y “dameFilaCol” antes empezaban a contar los offsets desde el comienzo de la estructura de datos. Por tanto, la casilla (0, 0) del tablero recibía el offset 24. Ahora cambiamos el criterio y a la casilla (0, 0) le asignamos el offset 0.
  • Las rutinas “dameRaton” y “dameGato” antes recorrían la matriz de 8×8 casillas para buscar y localizar el ratón o el gato enésimo (su offset). Ahora no hace falta buscar nada; tenemos la información a tiro hecho en los cinco bytes que sustituyen a la matriz de 8×8. Por tanto, esas rutinas se sustituyen por las nuevas rutinas “damePosicionRaton” y “damePosicionGato”.

Y poco más hasta aquí.

Nueva generación de jugadas:

La generación de jugadas del ratón está en el fichero “GenJugadasRaton.asm”. La pieza clave anteriormente eran las tablas con los movimientos permitidos:

Movimientos ratón

Es decir, los cambios en la posición (fila, columna) podían ser:

  • ($ff, $ff) = (-1, -1).
  • ($ff, $01) = (-1, 1).
  • ($01, $01) = (1, 1).
  • ($01, $ff) = (1, -1).

Como ahora no tenemos una matriz de 8×8 posiciones, ni tampoco gestionamos las posiciones en formato (fila, columna), sino en formato offset, esa pieza clave se convierte en esta otra:

Movimientos ratón - offsets

Es decir, el offset del ratón puede variar en:

  • $f7 = -9.
  • $f9 = -7.
  • $09 = +9.
  • $07 = +7.

Estas variaciones corresponden a estos cuatro movimientos (suponiendo que el ratón estuviera en el offset 43):

Movimientos offsets

De este modo, generar los movimientos posibles consiste en tomar el offset actual (43), recorrer las cuatro posiciones de la tabla, e ir sumando:

  • 43-9=34.
  • 43-7=36.
  • 43+9=52.
  • 43+7=50.

En el fondo, muy parecido a lo que ya hacíamos antes, pero manejando variaciones en el offset (-9, -7, +9, +7) en vez de variaciones en filas y columnas.

Otra pieza importante es la validación de las jugadas. Para que éstas sean válidas las reglas son (antes y ahora):

  • Tienen que generarse conforme a las reglas de movimiento de las piezas.
  • El destino tiene que estar vacío.
  • El destino tiene que caer dentro de los márgenes del tablero.

La primera condición se garantiza por la forma de generar las jugadas, partiendo de una tabla (antes tablas) que recogen los movimientos válidos.

La segunda es igual de fácil de comprobar ahora que antes. Antes teníamos la (fila, columna) destino; ahora tenemos el offset destino. Si el offset destino está ocupado por el ratón o algún gato, no será un destino válido. En caso contrario, sí lo será.

Y la tercera condición cambia un poco. Antes comprobábamos si la fila o la columna eran menores que cero o mayores que siete. Ahora tenemos un offset entre 0 y 63, y sumar o restar 7 o 9 puede hacer que se traspasen los bordes del tablero sin detectarlo, si no hacemos nada especial. Por ejemplo, 47-7=40 o 47+9=56:

Movimientos offsets - bordes

Una forma inteligente de impedir estos traspasos es dándose cuenta de que ratón y gatos siempre se mueven por las casillas blancas (offsets en blanco) y, cuando tiene lugar un traspaso ilegal de este tipo, acaban en una casilla negra (ver 40 o 56). Por tanto, llega con validar que el offset de destino es blanco (0, 2, 4, 6, 9, 11, 13, 15, …, 61, 63). Esto se puede hacer con una tabla de offsets válidos:

Offsets válidos

Por lo demás, todas las rutinas de “GenJugadasRaton.asm” (generar jugadas, validar jugadas, generar jugadas válidas, etc.) son esencialmente iguales a las que ya había antes, con la salvedad de que las posiciones de origen y destino se especifican mediante offsets, y no mediante parejas (fila, columna).

Y lo mismo se puede decir de “GenJugadasGatos.asm”.

Otros cambios:

Los cambios principales son los ya comentados: rutinas para manejar tableros y generación de jugadas. En el código surgen más cambios (evaluación de tableros, etc.) pero son cambios derivados de los anteriores.

En particular, el hecho de cambiar las rutinas “dameRaton” y “dameGato”, que buscaban en la matriz 8×8, por las nuevas rutinas “damePosicionRaton” y “damePosicionGato”, que devuelven las posiciones a tiro hecho, implica bastantes cambios en la evaluación de tableros (“EvalTableros.asm”), pero son más estéticos (por el cambio de nombre en las rutinas) que otra cosa.

También hay cambios menores en “PintaTableros.asm”. Antes los tableros tenían una matriz 8×8 que pintar (con “G”, “R” o un “.”). Ahora gráficamente hay que pintar la misma matriz 8×8, porque la representación gráfica del tablero no ha cambiado, pero la información de partida es muy distinta (cinco offsets).

Los cambios en el programa principal “RYG.asm” también se limitan a manejar las posiciones mediante offsets, en vez de mediante filas y columnas, o bien cambios en los nombres de algunas rutinas llamadas. Además, está el cambio obvio de pasar de tres a cuatro niveles de profundidad que, no olvidemos, es el motivo por el que hemos montado todo este lío 🙂 .

Cuatro niveles

Por último, un cambio de presentación. Como ahora podemos analizar hasta cuatro niveles de profundidad, es decir, hasta 1024 tableros, pintar “PENSANDO:” y un punto por cada tablero son muchos puntos. Por ello, se prefiere pintar la dirección del tablero que se está generando. De este modo, consumimos menos pantalla, hacemos menos scroll, tenemos igual idea del avance, y encima sabemos si el árbol consume más o menos memoria:

Nuevo pensando

Todos estos cambios pueden verse en la versión 18 del proyecto. Lo bueno de esta versión es que ya permite hasta cuatro niveles de profundidad.

Ah, y una lección que ganamos: lo más intuitivo para el programador (ej. tener un tablero de 8×8) no es siempre lo más intuitivo ni lo mejor para la máquina.


Código del proyecto: RYG18

RYG: tableros más compactos – mayor profundidad de análisis

Ya llevamos tres versiones de la función de evaluación que permite al C64, junto con el procedimiento minimax, decidir sus jugadas.

En la primera versión, hemos considerado como criterios la fila del ratón y el número de jugadas que puede hacer (incluyendo las situaciones particulares de que la fila del ratón sea cero – en cuyo caso gana el ratón – y de que su número de jugadas sea cero – en cuyo caso ganan los gatos –). En la segunda versión, hemos añadido como criterio que los gatos guarden una formación (una fila o dos). Y en la tercera versión, hemos añadido como criterio detectar si el ratón rebasa a los gatos. Y así deberíamos continuar añadiendo y revisando criterios hasta conseguir que el juego sea lo suficientemente fuerte.

Si a pesar de añadir muchos criterios no se consigue un juego fuerte, una medida complementaria (no sustitutiva) es ampliar la profundidad de análisis. Para ello ya sabemos que necesitamos más memoria y, si no disponemos de ella, hay que aprovechar mejor la disponible. Dicho de otro modo, hay que compactar las estructuras de datos.

Esto ya lo habíamos comentado muchas veces, y hasta ahora nos habíamos resistido por no complicar la programación, pero por fin ha llegado el momento.

Nueva estructura de datos compactada:

Los tableros usados hasta ahora eran así:

  • Cabecera: 3 bytes.
  • Nivel, turno y valor: 3 bytes.
  • Dirección del padre: 2 bytes.
  • Direcciones de los hijos: 2 x 8 = 16 bytes.
  • Tablero propiamente dicho: 8 x 8 = 64 bytes.
  • Total: 88 bytes.

De esos 88 bytes, la gran mayoría (64 bytes, el 73%) son el tablero propiamente dicho, es decir, el escaqueado de 8 x 8 casillas. Por tanto, éste es el gran candidato a una fuerte reducción.

Teniendo en cuenta que sólo tenemos cinco piezas, y que no hay capturas, esos 64 bytes se puede reducir a sólo cinco:

  • Un byte para guardar la posición del ratón.
  • Cuatro bytes para guardar las posiciones de los gatos.

Todas las demás posiciones del tablero, se consideran vacías.

Las posiciones del ratón y los gatos se podrían guardar en formato (fila, columna) pero, puestos a ahorrar memoria, casi mejor guardar los offsets (desplazamientos) respecto a la casilla (0, 0) del tablero, es decir, esto:

Offsets

Es decir, en la posición inicial del juego los offsets serían:

  • Gatos = 0, 2, 4 y 6.
  • Ratón = 59.

De este modo, el tablero compactado queda así:

  • Cabecera: 3 bytes.
  • Nivel, turno y valor: 3 bytes.
  • Dirección del padre: 2 bytes.
  • Direcciones de los hijos: 2 x 8 = 16 bytes.
  • Tablero propiamente dicho: 5 bytes.
  • Total: 29 bytes.

Es decir, hemos conseguido una reducción de 88 – 29 = 59 bytes, del 67%.

Reducciones adicionales:

El tablero se puede seguir compactando. El siguiente candidato por tamaño sería la tabla con las direcciones de los hijos (16 bytes), ya que no todos los tableros tendrán ocho hijos.

Se podría hacer una tabla de tamaño variable, marcando el final de la misma con algún marcador. O se podrían diseñar dos estructuras de datos, una con un máximo de ocho hijos para cuando muevan los gatos y otra con un máximo de cuatro hijos para cuando mueva el ratón.

En cualquier caso, es improbable que ahorrar 4 hijos / 8 bytes, y sólo en algunos tableros, permita ganar niveles adicionales en la profundidad de análisis, especialmente si se tiene en cuenta que el crecimiento del árbol de juego (número de tableros) es exponencial con la profundidad.

También se podría quitar la cabecera (tres bytes), aunque facilita la depuración de los datos y los programas, porque facilita identificar dónde empiezan los tableros en memoria.

Como no parecen opciones muy prometedoras, de momento, nos conformaremos con los tableros de 29 bytes.

Nueva profundidad de análisis:

Con este nuevo tamaño de tablero, las previsiones de consumo de memoria en función de los niveles de profundidad quedan así:

  • 1 nivel => 29 bytes x 8 movimientos = 232 bytes.
  • 2 niveles => 29 bytes x 8 x 4 = 928 bytes.
  • 3 niveles => 29 bytes x 8 x 4 x 8 = 7424 bytes.
  • 4 niveles => 29 bytes x 8 x 4 x 8 x 4 = 29696 bytes.
  • 5 niveles => 29 bytes x 8 x 4 x 8 x 4 x 8 = 237568 bytes.

Por tanto, al compactar los tableros de 88 a 29 bytes conseguimos subir de tres a cuatro niveles en la profundidad de análisis (29 KB). No podemos subir a cinco niveles porque el C64 no tiene esos 237 KB.

Es decir, a la hora de decidir su jugada, ahora el C64 podrá tener en cuenta los efectos de su jugada inmediata, la siguiente jugada del humano, nuevamente la jugada del C64 y, por último, la siguiente jugada del humano.

El número máximo de tableros a analizar por cada jugada será de 8 x 4 x 8 x 4 = 1024 tableros, aunque con frecuencia serán menos porque no siempre serán posibles todas las jugadas que en principio permiten las reglas de movimiento.

Todos estos cambios tienen su impacto en el código. Esto lo veremos ya en la entrada que sigue, aunque se adelanta la versión 18 del proyecto.


Código del proyecto: RYG18

RYG: función de evaluación – más mejoras

Como decíamos, el C64 ya juega mejor. Tras mejorar la formación de los gatos y detectar los rebases, ya es más difícil ganarle. Sin embargo, todavía es posible hacerlo, por lo que el proceso de mejora de la función de evaluación debería continuar.

De hecho, el proceso de mejora de la función de evaluación puede continuar casi indefinidamente. Iterativamente se pueden identificar nuevos criterios, introducirlos en el juego, probarlos y, en función de su contribución a la fortaleza del juego, mantenerlos o retirarlos.

Otra forma de mejorar la función de evaluación sería jugando muchas partidas, ya sea contra un humano o incluso contra sí mismo. Para esto último habría que adaptar un poco el juego, pero tampoco tanto, puesto que el C64 ya “sabe” mover el ratón. En vez de pedir la jugada del ratón al humano, debería decidirla el C64 en base a un árbol de juego, igual que ya hace en el caso de los gatos.

Sea como fuere, cuando el C64 pierda, se deberá identificar el movimiento que ha sido clave en la derrota y, más en particular, el criterio que ha hecho que el C64 se haya decantado por ese movimiento, reduciendo su peso o su puntuación para evitar que se repita. Y si esto (aislar el criterio clave en la derrota y ajustar su peso) fuéramos capaces de hacerlo automáticamente, sin intervención de un programador, ya casi estaríamos hablando de machine learning.

En cualquier caso, la mejora de la función de evaluación es un proceso iterativo y largo. Y si después del proceso no se han conseguido los resultados esperados habría que plantearse alternativas, como ampliar la profundidad de análisis compactando las estructuras de datos.

RetroProgramming Italia – RP Italia

Recientemente he descubierto un grupo que me parece muy interesante. Se trata de RetroProgramming Italia – RP Italia. Es el primer grupo italiano que se ocupa de la programación retro de todos los ordenadores de 8 y 16 bits y, en particular, de nuestro querido Commodore 64.

Os dejo su dirección de Facebook:

https://www.facebook.com/groups/retroprogramming/?ref=share

Se trata de un grupo privado, por lo que deberéis solicitar uniros al grupo.

Aunque las entradas lógicamente están escritas en italiano se entienden bastante bien. Y además el BASIC y el ensamblador del 6510 son lenguajes universales 😉 .

¡¡Que lo disfrutéis!!

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

Hay otro criterio que sería muy interesante introducir en la función de evaluación. En teoría, el ratón gana el juego cuando llega a la primera línea del tablero. Sin embargo, en cuanto el ratón rebase la línea de gatos “ya estará todo el pescado vendido”.

Por tanto, si en la función de evaluación metemos un criterio del tipo “si el ratón rebasa la línea de gatos sumar X puntos” estamos consiguiendo que el C64 identifique las victorias del ratón varios movimientos antes de que se produzcan de forma efectiva.

Para conseguir esto mejoramos la función de evaluación con una nueva llamada “jsr evaluaRatonRebasaGatos”:

Rutina evaluaTablero V3

A su vez, la nueva rutina “evaluaRatonRebasaGatos” es así:

Rutina evaluaRatonRebasaGatos

Es decir, obtiene la fila mínima de los gatos con “minFilaGatos” (rutina ya conocida), la fila del ratón con “dameRaton” y “dameFilaCol” (rutinas ya conocidas), compara ambas (instrucción “cmp”) y, si la fila mínima de los gatos es estrictamente menor (instrucción “bcc”) que la fila del ratón, se decide que no hay rebase. En caso contrario, es decir, si la fila mínima de los gatos es mayor o igual que la fila del ratón, entonces se decide que el ratón ha rebasado a los gatos, y se suman $20 = 32 puntos a la evaluación del tablero.

Esta mejora de la función de evaluación puede verse en la versión 17 del proyecto, que todavía juega un poquito mejor.


Código del proyecto: RYG17

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