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

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s