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.

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.