RYG: estructura de datos del tablero

Lo primero que hace falta para empezar a trabajar es una estructura de datos que permita almacenar un tablero, ya que los tableros van a ser nuestra materia prima.

Como hemos comentado anteriormente, lo más básico es tener una matriz de 8 x 8, pero hacen falta más cosas:

  • El nivel: la profundidad del tablero en el árbol de juego.
  • El turno: si le toca mover al ratón o a los gatos.
  • El valor: el resultado de la función de evaluación o del procedimiento minimax, según sea una hoja o un tablero intermedio.
  • El padre: el tablero del que procede este tablero.
  • Los hijos: los tableros que proceden de este tablero.
  • La matriz: el tablero propiamente dicho.

De este modo, podemos diseñar una estructura de datos así (ver fichero “Tableros.asm”):

Estructura datos tablero

En total son 85 bytes que se reparten así:

  • Nivel: Es el nivel de profundidad que ocupa el tablero en el árbol de juego. Con un byte será suficiente.
  • Turno: Es el turno, es decir, si le toca mover a ratón ($01) o gatos (-1 = $ff). Nuevamente, con un byte será suficiente.
  • Valor: Es el valor que la función de evaluación o el procedimiento minimax asignan al tablero. Será suficiente con un byte.
  • Padre: El tablero en curso procederá de un tablero padre. Ese tablero padre será otra estructura de 85 bytes. Con tener la dirección de memoria de su primer byte (su comienzo) será suficiente. Para esa dirección necesitamos dos bytes, el byte “lo” y el byte “hi”.
  • Hijos: El tablero en curso podrá dar lugar, como mucho, a ocho tableros hijo (un ratón puede moverse a un máximo de cuatro casillas, y cada gato a un máximo de dos). Por tanto, necesitaremos ocho direcciones de memoria para llevar control de toda la progenie. Como en el caso del padre, cada dirección tendrá su byte “lo” y su byte “hi”.
  • Tablero: Es una matriz de 8 x 8 para especificar la posición de las piezas sobre el tablero. Equivale a una secuencia de 8 x 8 = 64 bytes. Codificaremos con $00 las casillas vacías, con $01 el ratón, y con -1 = $ff los gatos.

En definitiva, un tablero será una estructura de datos de 85 bytes que vendrá especificada por la dirección de memoria de su primer byte (el nivel). Conociendo la dirección de ese primer byte, y utilizando el modo de direccionamiento indirecto – indexado, es posible acceder a cualquiera de los campos del tablero:

Tableros en memoria

En particular, usando el puntero al padre y los punteros a los hijos es posible navegar por el árbol de juego, tanto hacia arriba (hacia la raíz) como hacia abajo (hacia las hojas).

Cuando una dirección no esté definida (ej. el padre o algún hijo), usaremos la dirección $0000 para indicarlo.

Más adelante meteremos una pequeña variación en esta estructura de datos porque no es muy práctico que ocupe 85 bytes. Sería mucho más práctico que ocupara 88 bytes porque, al ser un múltiplo de 8 (88 = 11 x 8), se facilita mucho la visualización de los tableros en el depurador de CBM prg Studio durante la fase de depuración del programa. Para esto, llega con meter un relleno o prefijo de tres bytes que, además, tiene la ventaja de marcar la frontera en memoria entre tableros si se elige un patrón fácilmente reconocible de forma visual.


Código del proyecto: RYG01 

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