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.

RYG: árbol de juego – memoria revisitada

En la entrada “RYG: programa principal” ya hicimos una estimación de la profundidad de análisis que puede tener el juego. Si actualizamos aquellos cálculos para tableros de 88 bytes quedan así:

  • 1 nivel => 88 bytes x 8 movimientos = 704 bytes.
  • 2 niveles => 88 bytes x 8 x 4 = 2816 bytes.
  • 3 niveles => 88 bytes x 8 x 4 x 8 = 22528 bytes.
  • 4 niveles => 88 bytes x 8 x 4 x 8 x 4 = 90112 bytes.

Por tanto, para trabajar con 4 niveles de profundidad necesitaríamos unos 90 KB. Y lógicamente el C64 no los tiene.

Pero es que, además, como la versión 10 del proyecto ya es capaz de generar el árbol de juego completo, podemos comprobarlo empíricamente:

Árbol de profundidad 3:

Si el usuario pide el árbol de profundidad 3, el último tablero que se genera después de unos minutos de “pensar” es éste:

Arbol profunidad 3

La dirección $6100 todavía está por debajo de la dirección de base del intérprete de BASIC, es decir, $a000.

De hecho, si de $6100 restamos $19d8, que es el valor que toma la etiqueta “raizArbol” en esta versión del proyecto, el resultado es $6100 – $19d8 = $4728 = 18216 bytes. Es decir, 18216/88 = 207 tableros. En realidad 208, si incluimos también el último tablero, el que empieza en $6100.

Esto viene a ser casi lo mismo que 8 movimientos de los gatos x 4 movimientos del ratón x 8 movimientos de los gatos = 256 tableros, si no fuera porque no siempre los gatos tienen ocho movimientos ni el ratón cuatro. A veces tienen menos. Todo encaja.

Árbol de profundidad 4:

Sin embargo, si el usuario pide el árbol de profundidad 4, a partir de $a000 se generan tableros así:

Arbol profundidad 4

Obsérvese que el tablero no está bien generado, pero el programa tampoco “casca” de momento. El motivo es el modelo de “RAM bajo ROM” del C64. Por encima de la dirección $a000, los “sta” operan sobre RAM, pero los “lda” leen de ROM. El resultado es que los tableros no están bien, pero el programa como tal tampoco falla.

Y a partir de $d000, es decir, cuando ya llegamos al VIC, se empieza a ver esto:

Arbol pisando VIC

Esto es porque los “sta” que vamos ejecutando para generar el árbol van modificando los registros del VIC y, en particular, cambian los modos gráficos.

Por último, el VICE se acaba quedando “tostado”.

Alternativas:

Ante esta situación, tenemos varias alternativas:

  • Conformarnos con tres niveles de profundidad.
  • Ampliar la memoria disponible desactivando la ROM del intérprete de BASIC y la del Kernal.
  • Aprovechar más la memoria disponible diseñando estructuras de datos más compactas.

Estas medidas no son necesariamente excluyentes; pueden ser complementarias.

Conformarse con tres niveles de profundidad es perfectamente posible, especialmente si la función de evaluación es buena. Como ya se comentó en la entrada “La función de evaluación” el árbol de juego y la función de evaluación conforman un compromiso. Si el árbol de juego pudiera ser ilimitado, la función de evaluación podría ser muy tonta (llegaría con que detectara que un bando gana). Contrariamente, dado que el árbol normalmente tendrá que ser limitado, hará falta una función de evaluación “fuerte” que sirva para valorar cómo de prometedora es una línea de juego.

Por otro lado, uno de los fuertes del C64 es su capacidad para configurar su memoria. Efectivamente, actuando sobre los bits del registro R6510 = $0001 es posible ampliar la RAM disponible desactivando el intérprete de BASIC ($a000 – $bfff) y el Kernal ($e000 – $ffff). En nuestro caso, es posible desactivar el intérprete de BASIC, puesto que no lo usamos, pero sí usamos rutinas del Kernal como “chrout”.

Por último, es posible diseñar estructuras de datos más compactas. Por ejemplo, en vez de usar una matriz de 8 x 8 = 64 bytes para guardar el tablero, es posible guardar información equivalente con sólo 5 bytes:

  • 1 byte = offset respecto a la casilla (0, 0) del ratón.
  • 1 byte = offset respecto a la casilla (0, 0) del gato 1.
  • 1 byte = offset respecto a la casilla (0, 0) del gato 4.

Con sólo 5 bytes has resuelto la misma papeleta que antes resolvías con 64. Y se pueden tomar medidas similares con el resto de campos que acompañan a un tablero (nivel, turno, valor, padre e hijos).

El problema de hacer esto es que se te complica la programación, por ejemplo, la generación de jugadas. Generar jugadas sobre un tablero de 8 x 8 es relativamente fácil; basta con sumar los incrementos / decrementos permitidos por las reglas de juego en las coordenadas (X, Y) de las piezas. Pero si en vez de tener las posiciones (X, Y) tienes el offset respecto al origen…

Una posibilidad es guardar los tableros en RAM en formato comprimido, pero trabajar con ellos (ej. generar jugadas) en formato descomprimido. Ganas espacio, pero pierdes capacidad de cómputo en comprimir / descomprimir tableros.

Conclusiones:

Sea como fuere, las medidas que vamos a aplicar a nuestro caso son dos:

  • Vamos a limitar el número de niveles a tres.
  • Vamos a ampliar la RAM disponible desactivando el intérprete de BASIC.

La primera medida la tomamos ya en la versión 11 del proyecto.

La segunda media la aplicamos en alguna versión posterior, casi más por ponerla en práctica que por su efectividad, puesto que ganar los $bfff – $a000 = 8 KBytes del intérprete de BASIC tampoco es suficiente para alcanzar un nivel extra de profundidad.

El siguiente paso será ya la función de evaluación. ¿Conseguiremos que sea lo suficientemente fuerte como para compensar un árbol de profundidad limitada?


Código del proyecto: RYG11

RYG: árbol de juego – recursividad y ensamblador

En los lenguajes de programación de alto nivel (C, Java, etc.) las llamadas a rutinas, funciones, procedimientos, métodos, o como queramos llamarlo, se implementan mediante una pila de llamadas. Una pila es una estructura de datos LIFO – List In First Out, es decir, el último dato que se mete en la pila tiene que ser el primero en salir:

Pila

Las pilas las podemos pintar creciendo o apilando hacia arriba o hacia abajo. Lo más natural resulta pintarlas creciendo hacia arriba, ya que en la naturaleza las cosas se apilan así (la gravedad tira hacia abajo 😉 ), pero también se pueden pintar al revés. De hecho, hay pilas como la del C64 (página uno) que crecen desde direcciones más altas (que se suelen pintar arriba) hacia direcciones más bajas (que se suelen pintar abajo). Pero da igual cómo las pintemos, creciendo hacia arriba o hacia abajo, lo realmente importante es su funcionamiento LIFO:

Pilas

En cualquier caso, en la pila de llamadas se mete, por cada función llamada:

  • La dirección de retorno: Esto permite continuar la ejecución del programa en el sitio correcto cuando termine la función.
  • Los parámetros con que fue llamada la función.
  • Variables y constantes de carácter local a la función.

Si ahora aplicamos esto a una función recursiva, es decir una función que se llama a sí misma, la pila tendría una apariencia así:

Pila - función recursiva

Lo que es importante observar es que cada llamada a la función recursiva tiene su propia copia de los parámetros de entrada. Por tanto, el programa no se pierde: sabe qué función está ejecutando, con qué parámetros, y dónde volver o continuar.

Sin embargo, si llevamos esto al C64, su pila (página uno), y las llamadas a rutinas en ensamblador con “jsr”, lo primero que observamos es que los parámetros no se pasan a las rutinas mediante la pila (aunque se podría hacer). Lo normal es pasar los parámetros:

  • Mediante los registros del microprocesador (acumulador, registro X y registro Y).
  • O mediante posiciones de memoria, ya sean de la página cero o de cualquier otra página.

Las rutinas del Kernal suelen funcionar pasando parámetros en los registros del microprocesador. A mí me parece más claro, y por tanto me gusta más, usar posiciones de memoria.

Lo importante es observar que, si se usan posiciones de memoria (o registros del microprocesador), no hay una copia de los parámetros por cada llamada a la rutina recursiva. Todas las llamadas comparten las mismas posiciones de memoria y, por tanto, según se van produciendo las llamadas recursivas unos valores de entrada van “machacando” a los anteriores. Esto puede hacer que las rutinas recursivas “se pierdan”.

Y esto es, precisamente, lo que ocurría en la entrada anterior. Y por este motivo el árbol de juego no se generaba de forma completa, sino que sólo se generaba en su máxima profundidad (la elegida por el usuario) en la primera rama, quedándose incompletas el resto de ramas.

La solución pasa porque los parámetros de entrada a la rutina “desarrollaUnNivel” no sean posiciones de memoria simples, sino tablas. De este modo, si usamos la profundidad (que es la variable que sirve para controlar las sucesivas llamadas recursivas y cuándo se ha llegado al final) como índice para acceder a estas tablas, cada ejecución de la rutina puede acceder a los parámetros de entrada que le corresponden:

Rutina desarrollaUnNivel - tablas

Al cambiar la definición de la rutina (sus parámetros de entrada) lógicamente hay que adaptar las llamadas a la misma, tanto desde el programa principal “RYG.asm” como las llamadas recursivas que se hace a sí misma.

Y con esta solución la versión 10 del proyecto ya no “se pierde” y el árbol de juego se genera de forma completa independientemente del nivel de profundidad elegido por el usuario (1, 2 ó 3):

Arbol completo prof2

El siguiente paso ya será evaluar el árbol de juego, para que el C64 pueda tomar una decisión sobre qué jugada realizar. Pero antes de eso haremos algunas reflexiones sobre la memoria que ocupa el árbol, cuántos niveles de profundidad admite, cómo se podrían admitir más niveles, etc.


Código del proyecto: RYG10

RYG: árbol de juego – resto de niveles

Desde la entrada “RYG: árbol de juego – generación del primer nivel” ya somos esencialmente capaces de generar el primer nivel del árbol de juego, aunque luego hemos tenido que depurar y meter algunas correcciones y mejoras.

La principal novedad de aquella entrada era la rutina “arbolJugadasGatos” que:

  • Copiaba el tablero actual a la raíz del árbol.
  • Recorría los cuatro gatos y, para cada uno de ellos, llamaba a la rutina “arbolJugadasGato”.
  • La rutina “arbolJugadasGato”, a su vez, generaba tableros hijo con las jugadas válidas de cada gato.

Ahora toca generar el segundo nivel del árbol (y los siguientes). En el segundo nivel vuelve a ser turno del ratón. Por tanto, necesitaremos una rutina “arbolJugadasRaton” equivalente a “arbolJugadasGato”, es decir, una rutina que genere tableros hijo con las jugadas válidas del ratón.

Y ahora se trata de repetir el proceso de generación de jugadas / tableros hijo tantas veces como indique la profundidad de análisis seleccionada. Y lógicamente hay que ir alternando quién mueve, gatos o ratón:

  • Copiar el tablero actual en la raíz del árbol.
  • Partiendo de la raíz, generar las jugadas / tableros hijo de los cuatro gatos.
  • Partiendo de los tableros hijo, generar las jugadas / tableros hijo del ratón.
  • Partiendo de los tableros nieto, generar las jugadas / tableros hijo de los cuatro gatos.
  • Partiendo de los tableros bisnieto, generar las jugadas / tableros hijo del ratón.
  • Y así hasta la profundidad indicada.

Y esto, precisamente, podemos conseguirlo con una rutina recursiva. Algo así:

  • Copiar el tablero actual en la raíz del árbol.
  • RutinaRecursiva(tablero, profundidad):
    • Si la profundidad ha llegado a cero, termina.
    • Si es turno de los gatos:
      • Genera las jugadas / tableros hijo de los cuatro gatos.
      • Recorre todos los tableros hijo.
      • Para cada tablero hijo, llama a RutinaRecursiva(tablero-hijo, profundidad-1).
    • Si es turno del ratón:
      • Genera las jugadas / tableros hijo del ratón.
      • Recorre todos los tableros hijo.
      • Para cada tablero hijo, llama a RutinaRecursiva(tablero-hijo, profundidad-1).

Como se puede observar, “RutinaRecursiva” efectivamente es recursiva, puesto que se llama a sí misma. Se va llamando a sí misma cada vez con menos profundidad (profundidad, profundidad-1, profundidad-2, profundidad-3, …). Y cuando la profundidad llega a cero, termina. De este modo, es capaz de generar todo el árbol de juego hasta la profundidad seleccionada por el usuario, y alternando los turnos de movimiento.

En la práctica, en la versión 9 del proyecto esto se plasma en las rutinas:

Rutina “desarrollaArbolJugadas”:

Esta rutina es así:

Rutina desarrollaArbolJugadas

Es decir, trazas de depuración aparte (llamada a “pintaTablero”), esta rutina:

  • Copia el tablero actual en la raíz del árbol.
  • Lógicamente, incrementa el puntero a la memoria libre, puesto que la raíz del árbol ocupa memoria.
  • Llama a la rutina recursiva “desarrollaUnNivel” pasando como tablero de partida la raíz y como profundidad la elegida por el usuario (“prof”).

Rutina recursiva “desarrollaUnNivel”:

Esta rutina, nuevamente contiene trazas de depuración (llamadas a “pintaHex”). Al margen de eso, primero comprueba si la profundidad ha llegado a cero:

Rutina desarrollaUnNivel - prof

Si la profundidad ha llegado a cero termina (instrucción “rts”). Si no ha llegado a cero, genera otro nivel del árbol (etiqueta “dunOtroNivel”).

Para generar otro nivel, lo primero es determinar el turno de juego con la rutina “dameDatosBasicos”:

Rutina desarrollaUnNivel - turno

Si el turno es de los gatos se ejecuta el código bajo la etiqueta “dunGatos”; si el turno es del ratón se ejecuta el código bajo la etiqueta “dunRaton”. En ambos casos el código es muy parecido, así que sólo veremos el de los gatos:

Rutina desarrollaUnNivel - dunGatos

Es decir:

  • Genera las jugadas válidas / tableros hijo con “arbolJugadasGatos”.
  • Recorre los tableros hijo (hasta un máximo de ocho).
  • Se llama a sí misma pasando como parámetros el tablero hijo y profundidad – 1.

Si se revisa la parte que sigue a la etiqueta “dunRaton” es totalmente análoga:

  • Genera las jugadas válidas / tableros hijo con “arbolJugadasRaton”.
  • Recorre los tableros hijo.
  • Se llama a sí misma pasando como parámetros el tablero hijo y profundidad – 1.

Al llamarse a sí misma sobre cada tablero hijo (y con profundidad – 1) lo que se consigue es seguir poblando el árbol recursivamente.

Resultado:

Si se prueba la versión 9 del proyecto se verá que, con profundidad uno, el programa funciona perfectamente: genera bien los 7 tableros con los movimientos válidos de los gatos (nivel 1).

Sin embargo, si se prueba con profundidad 2 (o superiores), se verá que se generan bien los 7 tableros con los movimientos de los gatos (nivel 1), pero los movimientos subsiguientes del ratón (nivel 2) sólo se generan para el primer movimiento de los gatos. Es decir, algo así:

Arbol de juego - recursividad

El motivo radica en que hacer funciones recursivas en lenguajes de alto nivel como C o Java es algo más fácil, pero en ensamblador hay que tomar precauciones adicionales. En la entrada siguiente veremos por qué.


Código del proyecto: RYG09

RYG: árbol de juego – recursividad

En matemáticas una función recursiva es una función que se define en términos de sí misma. Hay muchos ejemplos, pero uno típico es la secuencia de Fibonacci, que se define así:

F(N) = F(N-1) + F(N-2)

Es decir, el número de Fibonacci de orden N es la suma de los números de órdenes N-1 y N-2. Como se puede observar, la secuencia se define en términos de sí misma.

Para que la definición esté completa hace falta una condición inicial, es decir, hace falta indicar el valor de los dos primeros números de Fibonacci, que son:

F(0) = 0
F(1) = 1

De este modo, es fácil calcular:

F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
F(7) = F(6) + F(5) = 8 + 5 = 13
…

En programación, igualmente, una función recursiva es una función que se llama a sí misma. Por ejemplo, el siguiente programa en C incluye la función recursiva int fibonacci(int n) que permite calcular la serie de Fibonacci:

Fibonacci

Es importante empezar la función recursiva verificando las condiciones de terminación (¿n==0? ¿n==1?), porque si no se corre el riesgo de que el programa se meta en un bucle infinito.

Cuando un problema es de naturaleza recursiva, su programación de forma recursiva también suele resultar natural. No obstante, casi todo lo que se puede programar de forma recursiva también se puede programar de forma iterativa, es decir, usando bucles. Por ejemplo, la versión iterativa del mismo programa en C sería así:

Fibonacci-iter

¿Y todo esto a santo de qué viene? Pues que un árbol es una estructura de datos recursiva. Así que vamos a usar funciones recursivas para generar el árbol de juego.

¿Y se pueden hacer rutinas recursivas en ensamblador? Pues no es muy habitual, pero poderse se puede, y lo vamos a demostrar en las entradas que siguen.

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