RYG: árbol de juego – selección de la profundidad

Una vez que hemos sido capaces de generar el primer nivel del árbol de juego, el siguiente paso ya es generar N niveles, tantos como la profundidad de análisis que se pretenda.

Y como la profundidad de análisis suele ser un parámetro de configuración del juego, se le suele pedir al usuario al arrancar. Y ya de paso le vamos a poner un titulillo, aunque sea cosa sencilla.

Por todo ello, en el programa principal, que está en el fichero “RYG.asm” aparecen estas dos llamadas nuevas (“jsr pintaTitulo” y “jsr solicitaProfundidad”):

Título y profundidad

La primera llamada (“jsr pintaTitulo”) es bien sencilla, y se limita a pintar un título:

Rutina pintaTitulo

La segunda llamada (“jsr solicitaProfundidad”) es un poco más compleja, pero tampoco mucho:

Rutina solicitaProfundidad

La rutina pinta una cadena, lee un byte del teclado, pinta un retorno de carro (13), verifica que el byte leído sea mayor o igual que 1 y menor que 6 y, en caso afirmativo, deposita la profundidad en la dirección “prof”. En caso negativo, vuelve a pedir la profundidad.

A estas alturas de la programación todavía no había echado las cuentas de memoria que vimos en la entrada “RYG: programa principal” así que todavía no era consciente de que con la codificación de 88 bytes por tablero el máximo de niveles era tres. Por eso en el programa veréis que se pide una profundidad entre 1 y 5.

Más adelante, cuando veamos la función de evaluación y cómo mejorarla, veremos que otra alternativa –o más bien otra medida complementaria– es meter más niveles de profundidad de análisis, lo que en nuestro caso pasaría inevitablemente por “comprimir” los tableros, porque el C64 tiene muy poca memoria.

Con estas dos pequeñas mejoras del programa principal, el arranque queda así:

Arranque

En la siguiente entrada, ya con la profundidad seleccionada por el usuario en “prof”, intentaremos generar un árbol de juego de esa profundidad, no de un solo nivel.


Código del proyecto: RYG09

RYG: árbol de juego – algunas mejoras

Hace unas pocas entradas, en la versión 7 del proyecto, desarrollamos la rutina “aplicaJugadaGatoHijo”. El ratón tendrá una rutina equivalente un poco más adelante.

Esta rutina permite aplicar una jugada de un gato a un tablero. Pero, en vez de modificar directamente ese tablero, genera un tablero hijo. De este modo, permite ir generando el árbol de juego que hace falta para que el C64 decida su jugada.

Pues bien, entonces decíamos que esta rutina hacía:

<<

  • Saca una copia del tablero de entrada (ahora la raíz del árbol) en un nuevo tablero que será el hijo. Para esto hace falta una nueva rutina de apoyo “copiaTablero” en el fichero “Tableros.asm”.
  • Actualiza el puntero a la memoria libre (libreLo – libreHi), puesto que hemos creado un nuevo tablero en el árbol.
  • Sobre el tablero hijo, aplica el movimiento.
  • Más adelante, enlazará el tablero padre con el tablero hijo, y viceversa, aunque en esta fase del proyecto esto todavía no está implementado.
  • A modo de depuración, y de forma temporal, imprime el tablero hijo.

>>

Lo anterior admite varias mejoras, a saber:

Copia del tablero padre en el hijo:

La rutina “copiaTablero” copia el tablero origen en el destino tal cual. Ahora bien, hay campos del tablero origen, como los hijos, que no tienen sentido en el tablero de destino.

Podemos esperar a que el programa vaya “machacando” esos campos, y dándoles nuevos valores con sentido o, para no crear confusión, inicializarlos en el hijo desde el comienzo.

Por esto último se desarrolla la rutina de apoyo “copiaTableroSinHijos” (fichero “Tableros.asm”), que en el fondo es igual que “copiaTablero” pero inicializando los hijos del destino.

Incrementar nivel y turno:

Más ejemplos de campos que no tiene sentido copiar tal cual del padre al hijo son los campos “nivel” y “turno”. El nivel hay que incrementarlo en uno del padre al hijo. Y el turno hay que ir alternándolo entre ratón y gatos.

Estas modificaciones se podrían hacer en la de rutina de copia (ya sea la original “copiaTablero” o la nueva “copiaTableroSinHijos”). Pero como también hay que hacerlas cuando se aplica una jugada directamente a un tablero, sin dar lugar a un tablero hijo (por ejemplo, cuando el humano decide su jugada y hay que aplicarla al tablero actual), estos cambios se llevan a las rutinas “aplicaJugadaGato” y “aplicaJugadaRaton”.

Ahora estas dos rutinas incluyen una llamada a la nueva rutina de apoyo “incrementaNivelYTurno” (fichero “Tableros.asm”). Como esta rutina no tiene mucho misterio, no abundaremos más en ella.

Vincular padre e hijos:

Para construir un árbol de verdad no sólo hay que generar tableros. Además, hay que vincular el padre con los hijos y al revés.

Vincular un hijo con su padre es fácil porque, como dicen, “padre no hay más que uno” (en realidad, se dice de las madres que es con las que no hay duda 😉 ). Simplemente, se trata de poner la dirección del padre (de momento la raíz) en el campo “padre” de todos los hijos. Para ello se utiliza la rutina de apoyo “fijaPadre”.

Vincular a un padre con sus hijos ya es más complicado, puesto que un padre puede tener varios hijos (hasta ocho). Y algunos hijos estarán “ocupados” y otros no. Por tanto, tampoco resulta muy práctico usar la rutina “fijaHijo”, puesto que esta rutina exige saber qué número de hijo (primero, segundo, …) es el que se quiere fijar.

Por ello, resulta de utilidad desarrollar una nueva rutina “fijaHijoLibre” que, simplemente, va analizando los hijos de un padre hasta dar con el primero libre (valor $0000) y, una vez localizado su número de orden, guarda en él la información del hijo con “fijaHijo”. Ver fichero “Tableros.asm”.

Pintado de tableros con dirección:

Para depurar el árbol vamos a hacer dos cosas:

Y puesto que los padres identifican a sus hijos por sus direcciones, y al revés también, no hay nada más lógico que empezar pintando los tableros por su dirección. Por ello, se mejora la rutina “pintaTablero” (fichero “PintaTableros.asm”) con un nuevo paso “jsr pintaDireccion”.

Resultado final:

Tras todas estas mejoras, si ejecutamos la versión 8 del proyecto, el resultado es:

Primer nivel

Es decir, se van generando las siete jugadas válidas de los gatos, y cada una de ellas se aplica a un tablero hijo, que queda identificado mediante su dirección (ej. $197c), y que queda enlazado con su tablero padre ($1714) que, de momento, y al tener sólo un nivel, es la raíz del árbol.

La ejecución en VICE se puede ir parando si se va pinchando con el ratón sobre la barra de menú de VICE, y se pueden ir comprobando todos los tableros hijo.

También es posible usar el depurador de CBM prg Studio, ejecutar el programa, irse con el visor de memoria a la zona de memoria del entorno de la raíz ($1714), y comprobar que están los tableros:

Primer nivel 2

Si se hace esto, hay que tener cuidado con las impresiones por pantalla porque el depurador de CBM prg Studio no incluye por defecto en su mapa de memoria las rutinas del Kernal como “chrout”. Por ejemplo, se pueden comentar o saltar.


Código del proyecto: RYG08

RYG: árbol de juego – nueva validación de jugadas

Una vez ampliados los tableros a 88 bytes, y alineados los datos en el visor de memoria, hay que seguir depurando el programa.

Una cosa que llama la atención de la versión 7 del proyecto, aparte de que se mete en un bucle, es que uno de los gatos desparece del tablero:

Bucle infinito

Esto nos puede llevar a pensar que la validación de las jugadas no es correcta. Recordemos que básicamente validábamos dos cosas (aparte de que el movimiento de la pieza era conforme a las reglas del juego):

  • Que la casilla de destino caía dentro del tablero.
  • Que la casilla de destino estaba vacía.

Quizás lo que ocurre no es tanto que ha desparecido un gato, sino que hay dos superpuestos en la misma casilla. Es decir, quizás está fallando la validación de las jugadas.

Y efectivamente, cuando hicimos la validación de jugadas ya adelantamos un presagio que de momento no hemos cumplido:

<<La rutina anterior tiene una limitación que de momento es aceptable: sólo trabaja sobre el tablero actual (que está implícito). Pero cuando construyamos el árbol de juego para que el C64 juegue por los gatos hará falta validar jugadas sobre un tablero arbitrario del árbol. Llegados ese momento habrá que mejorarla.>>

Por tanto, tenemos que mejorar la rutina de validación de jugadas que, recordemos, es común para ratón y gatos (fichero “GenJugadasRaton.asm”). La principal mejora es hacerle llegar el tablero contra el que hacer la validación, es decir, el tablero contra el que mirar si la posición de destino está vacía u ocupada. La validación de límites es independiente del tablero.

La nueva rutina “validaJugada” pasa a tener esta definición (recibe un tablero como parámetro de entrada):

Rutina validaJugada nueva - definición

Y lo que cambia es la parte en que valida si el destino está vacío u ocupado, que lógicamente pasa a utilizar el tablero que recibe como parámetro:

Rutina validaJugada nueva - ocupado

Por supuesto, no llega con cambiar la rutina “validaJugada” para que reciba un tablero. También hay que cambiar las rutinas que, bien de forma directa o indirecta, llaman a aquella. Ahora deberán pasar un tablero como parámetro.

Con este cambio, la versión 8 del proyecto ya debería funcionar y generar bien el primer nivel del árbol. No obstante, la versión 8 recoge algunos otros cambios variopintos que, por no alargar esta entrada, se recogerán en la siguiente.


Código del proyecto: RYG08

RYG: árbol de juego – tableros de 88 bytes

El primer intento de depurar el programa debe consistir en ir a la zona de memoria donde están el tablero actual y el árbol de juego, y revisar su contenido. Más concretamente, en la versión 7 del proyecto:

  • El tablero actual está en $14e9.
  • El puntero a la memoria libre está en $153e – $153f.
  • La raíz del árbol está en $1540.

Pues bien, si depuramos el programa con el debugger de CMB prg Studio (menú Debugger > Debug Project), y más concretamente abrimos el visor de memoria y nos vamos al tablero actual (dirección $14e9), veremos algo así:

Visor memoria

Es decir:

  • En la dirección $14e9 comienza el tablero actual, que ocupa 85 bytes.
  • En las direcciones $153e – $153f está el puntero a la memoria libre, que toma el valor $15ea, es decir, a partir de la dirección $15ea ya no hay tableros.
  • En la dirección $1540, que actualmente toma el valor $00, empieza la raíz del árbol.

La primera conclusión al ver esto es que es muy difícil depurar nada. Si los tableros ocuparan 88 bytes, en vez de 85, ocuparían un número entero de filas en el visor de memoria (88 = 11 x 8), lo que facilitaría mucho la depuración de la memoria.

Por ello, la primera medida que vamos a tomar es ampliar la estructura de datos del tablero para hacerla pasar de 85 a 88 bytes. De este modo los tableros nos saldrán alineados en el visor.

No necesitamos guardar más variables. Se trata, simplemente, de alinear los datos. Por ello, si además metemos un patrón fácilmente reconocible, por ejemplo, el prefijo $aa – $aa – $aa, no sólo conseguimos alinear los datos en el visor, sino que además metemos un patrón que es fácilmente reconocible visualmente, lo que nos facilita identificar donde termina un tablero y empieza el siguiente.

Por todo lo dicho, finalmente la estructura de datos para manejar tableros queda así (ver prefijo $aa – $aa – $aa):

Tablero 88 bytes

Lógicamente, también hay que actualizar todas las rutinas que manejan tableros (fichero “Tableros.asm”), ya que las posiciones (offsets) de las variables respecto del comienzo del tablero se incrementan en 3 bytes.

Para que el puntero a la memoria libre (libreLo – libreHi) no estropee el alineamiento entre el tablero actual y los tableros del árbol, también se introducen algunos bytes extra en “Arbol.asm”:

Bytes extra

De este modo, en la versión 8 del proyecto los tableros ya aparecen alineados en el visor de memoria, lo que facilita mucho la depuración:

Memoria tras 88

En esta imagen ya es más fácil identificar el tablero actual ($16b4), el puntero a la memoria libre ($170c – $170d), seis bytes $bb de relleno ($170e – $1713), y la primera parte de la raíz del árbol de juego ($1714), que es copia del tablero actual.


Código del proyecto: RYG08

RYG: árbol de juego – generación del primer nivel

Ahora que ya tenemos la capacidad de generar los tableros hijo de un tablero dado, al menos cuando mueven los gatos (rutina “aplicaJugadaGatoHijo”), ya estamos en disposición de generar el primer nivel del árbol de juego. Para ello, lo que vamos a hacer es modificar el programa principal “RYG.asm” con un paso adicional:

Programa principal - primer nivel

Este nuevo paso es la instrucción “jsr arbolJugadasGatos”, y la nueva rutina “arbolJugadasGatos” hace esto:

Rutina arbolJugadasGatos

Es decir:

  • Copia el tablero actual a la raíz del árbol (“jsr copiaActualRaizArbol”).
  • Incrementa el puntero a la memoria libre en 85 bytes, porque la raíz del árbol ya pasa a estar ocupada por la copia del tablero actual.
  • Recorre los cuatro gatos y, para cada uno de ellos, llama a “arbolJugadasGato”.

Por su parte, la rutina “arbolJugadasGato” tiene dos partes. La primera es así:

Rutina arbolJugadasGato - parte1

Es decir:

  • Localiza el gato en el tablero.
  • Convierte su posición en formato offset a (fila, columna).
  • Y genera las jugadas válidas de ese gato.

Y la segunda parte es así:

Rutina arbolJugadasGato - parte2

Es decir:

  • Recorre las jugadas válidas del gato (0, 1 o 2 jugadas como mucho).
  • Y genera un tablero hijo al que se aplica esa jugada.

Al final, al llamar cuatro veces a “arbolJugadasGato”, una vez para cada gato, lo que deberíamos tener es el primer nivel del árbol de juego. Y como, además, según vamos generando los tableros hijos los imprimimos (sólo temporalmente y para depurar), el resultado es que el primer nivel del árbol debería verse por la pantalla.

Ensamblamos y ejecutamos en VICE. Se pinta el tablero inicial y, como humanos, se nos pide la jugada del ratón. Elegimos una cualquiera (ej. la 00), vemos que efectivamente se aplica y el ratón avanza, y, oh sorpresa, el programa se mete en un bucle infinito del que no sale. ¡¡Y encima desaparece un gato!!

Bucle infinito

¿Qué pensabais? ¿Que iba a funcionar bien a la primera? Ya empiezan los típicos problemas. A ver quién depura esto ahora… 🙂


Código del proyecto: RYG07

RYG: árbol de juego – generar tableros hijo

Ya sabemos generar las jugadas válidas del ratón y los gatos. También sabemos dónde y cómo vamos a almacenar el árbol de juego. Por tanto, el siguiente paso es empezar a construirlo.

Supongamos que acaba de jugar el humano. El humano ha seleccionado una jugada del ratón y ésta se ha aplicado al tablero actual dando lugar a un tablero actual modificado.

Ahora le toca mover al C64 y, para decidir su jugada, hay que conformar y evaluar el árbol de juego. El árbol va a tener varios niveles de profundidad, pero no vamos a abordar todos los niveles de golpe. Vamos paso a paso; empecemos por el primero.

Para generar el primer nivel del árbol de juego, los hijos de la raíz, hay que:

  • Copiar el tablero actual a la raíz del árbol de juego.
  • Recorrer los cuatros gatos, desde el 0 hasta el 3.
  • Para cada gato, localizarlo sobre la raíz (rutina “dameGato”) y generar sus movimientos válidos (rutina “generaJugadasValidasGato”).
  • Y, en vez de pintar las jugadas de los gatos, como en una entrada anterior, aplicar (*) cada jugada o movimiento al tablero raíz.

Pero cuidado con una cosa (*). Ahora no se trata de “aplicar la jugada” en el sentido de modificar la raíz del árbol o el tablero actual. Eso lo haremos más adelante, cuando el C64 haya decidido qué jugada le interesa más. Ahora estamos en un momento previo, construyendo el árbol que le permita tomar esa decisión.

Por tanto, ahora no queremos modificar la raíz del árbol, sino que queremos generar un tablero hijo por cada jugada posible. Por ello, vamos a desarrollar una nueva rutina “aplicaJugadaGatoHijo” que será similar a la rutina “aplicaJugadaGato” pero que, en vez de modificar el tablero de entrada, lo que hace es todo lo que sigue:

  • Saca una copia del tablero de entrada (ahora la raíz del árbol) en un nuevo tablero que será el hijo. Para esto hace falta una nueva rutina de apoyo “copiaTablero” en el fichero “Tableros.asm”.
  • Actualiza el puntero a la memoria libre (libreLo – libreHi), puesto que hemos creado un nuevo tablero en el árbol.
  • Sobre el tablero hijo, aplica el movimiento.
  • Más adelante, enlazará el tablero padre con el tablero hijo, y viceversa, aunque en esta fase del proyecto esto todavía no está implementado.
  • A modo de depuración, y de forma temporal, imprime el tablero hijo.

Los parámetros de la rutina son así (el tablero padre, el tablero hijo, la posición actual del gato y su nueva posición):

Rutina aplicaJugadaGatoHijo - params

La copia de la raíz al tablero hijo es así (se apoya en la nueva rutina de apoyo “copiaTablero”):

Rutina aplicaJugadaGatoHijo - copia

La actualización del puntero a memoria libre es así (básicamente suma 85 bytes):

Rutina aplicaJugadaGatoHijo - puntero

La aplicación del movimiento es así (se apoya en “aplicaJugadaGato”, pero actuando sobre el tablero hijo):

Rutina aplicaJugadaGatoHijo - aplicar

Las previsiones pendientes de implementar son así:

Rutina aplicaJugadaGatoHijo - previsiones

Y, por último, la impresión del tablero hijo (para depurar) es así:

Rutina aplicaJugadaGatoHijo - pintar

Con esta nueva rutina “aplicaJugadaGatoHijo” ya deberíamos ser capaces de generar el primer nivel del árbol, es decir, esta parte (ver rojo):

Arbol de juego - primer nivel

Para ello, lógicamente, habrá que invocar esta nueva rutina desde algún sitio del programa principal (fichero “RYG.asm”). Pero como esta entrada ya ha sido demasiado larga, lo dejamos para la siguiente.


Código del proyecto: RYG07

RYG: árbol de juego – memoria

Hasta ahora sólo teníamos el “tablero actual”, es decir, la estructura de datos que lleva control de en qué situación (en qué tablero) se encuentra el juego. Esto lo hacíamos así en el fichero “Arbol.asm”:

Tablero actual

Puede parecer un poco tonto definir una etiqueta “tableroActual” y no hacer nada más, pero no lo es. Usando tableroActual (parte “hi”) se puede definir un puntero a esa zona de la memoria y, mediante rutinas como “inicializaTablero” se puede configurar ahí un tablero (85 bytes) en su situación inicial:

Rutina incializaTableroActual

A partir de ese momento, se puede trabajar con ese “tablero actual”, generando los movimientos del ratón, preguntando al usuario cuál desea, aplicando ese movimiento al tablero, generando los movimientos para los gatos, etc.

Aquí podemos ver con el debugger el contenido de la memoria a partir de la etiqueta “tableroActual”, que en la versión 6 del proyecto es la dirección $1346:

Tablero actual debugger

Mirando con atención se pueden identificar el nivel ($00), el turno ($01), el valor ($00), el padre ($0000), los hijos ($0000, …, $0000) y, finalmente, el tablero propiamente dicho, donde están los gatos ($ff) y el ratón ($01).

Y todo ello con el objetivo de llevar el control de la situación actual de la partida.

Pero ahora tenemos otro objetivo: generar un árbol de juego. Y ese árbol de juego va a consistir en una serie de tableros (bloques de 85 bytes) ubicados uno a continuación del otro, y enlazados entre sí usando los punteros de padre e hijos. Esquemáticamente sería así:

Tableros en memoria

Por tanto, necesitamos varias cosas:

  • Reservar 85 bytes para el tablero actual, asegurándonos de que no son pisados por nadie.
  • Una zona de memoria en la que meter tableros (bloques de 85 bytes) enlazados entre sí mediante punteros y conformando un árbol.
  • La zona de memoria del árbol debe poder crecer según se vayan generando más tableros. Y no debe pisar zonas del sistema como el intérprete de BASIC (a partir de $a000).
  • Y, una vez tomada una decisión de juego por el C64, la zona de memoria del árbol debe poder reutilizarse para las jugadas siguientes.

Esto lo logramos con un nuevo fichero “Arbol.asm” así:

Tablero actual y árbol

Es decir:

  • Reservamos 85 bytes de forma expresa para el tablero actual. Antes no había una reserva expresa; estaba implícita.
  • Reservamos dos bytes para un puntero libreLo – libreHi, que nos va a indicar cuál es el primer byte de memoria que está libre para almacenar nuevos tableros que se vayan generando.
  • Tras el puntero libreLo – LibreHi viene la raíz del árbol, es decir, el primer tablero del árbol de juego. La raíz la copiaremos desde el tablero actual al comienzo de generar el árbol.

Por tanto, la memoria irá evolucionando así:

Tableros en memoria 2

Es decir:

  • Primero el código del juego, que empieza en $801.
  • Luego el tablero actual con la situación de la partida.
  • Luego el puntero a la memoria libre, que se irá actualizando según se generan tableros.
  • Luego la raíz del árbol de juego, que se copiará desde el tablero actual al empezar a conformar el árbol.
  • Luego los tableros hijo, los tableros nieto, etc., así hasta el nivel de profundidad establecido.
  • Por último, la memoria libre, que irá decreciendo según se van generando tableros, y volverá a crecer cuando el C64 tome una decisión de juego.

Por esta estructura de tableros se puede navegar de padres a hijos, siguiendo cualquiera de los ocho punteros a los hijos que tiene cada tablero. También se puede navegar de hijos a padres, siguiendo el puntero al padre que tiene cada tablero. De hecho, tendremos que navegar por ella para aplicar el procedimiento minimax.


Código del proyecto: RYG07