Árbol de juego / actualización del tablero I

Recapitulando, ya sabemos:

• Cómo representar el tablero en memoria del C64.
• Como inicializar e imprimir el tablero.
• Cómo generar jugadas para ambos bandos.
• Cómo calcular el hash de un tablero.
• Cómo guardar el mejor movimiento asociado a un tablero en una tabla hash, reduciendo el impacto de las colisiones mediante un lock.

Por tanto, parece lógico que los siguientes pasos deberían ser:

• Desarrollar el árbol de juego hasta una profundidad N.
• Evaluar las hojas del árbol.
• Llevar esa evaluación hacia la raíz aplicando minimax.
• En cada tablero del árbol, seleccionar la mejor jugada del bando que mueva y almacenarlo en la tabla hash.

De este modo, al terminar el proceso, en la tabla hash (en realidad, en las tablas hash, puesto que hay una por bando) quedará almacenada la variante principal. Es decir, quedará almacenada la línea de juego que, según el C64, es la mejor secuencia de jugadas para ambos bandos con la información conocida.

Desarrollar el árbol de juego:

Para “desarrollar el árbol de juego” vamos a generar y aplicar movimientos, pero no vamos a almacenar en memoria el árbol de jugadas completo. Este enfoque consumiría demasiada memoria. Lo que vamos a hacer, en cambio, es ir aplicando movimientos al tablero “board” y luego ir deshaciéndolos.

Es decir, desde un punto visual es como si fuéramos moviendo el tablero o la variante actual por el árbol de jugadas (1º, 2º, 3º, 4º, …):

Cuando la variante actual esté en las hojas del árbol invocaremos la función de evaluación (a detallar más adelante) para evaluar los tableros, y cuando esté en un nodo intermedio calcularemos el máximo o el mínimo de las evaluaciones de los tableros hijo, según el bando al que le toque mover (minimax).

Al final lo que hacemos es recorrer el árbol de juego “en profundidad”: primero la primera rama hasta su máxima profundidad, luego la segunda rama hasta su máxima profundidad, y así sucesivamente hasta la última rama. Y lo mejor de todo es que no necesitamos almacenar en memoria todos los tableros del árbol a la vez. Llega con un único tablero (“board”) sobre el que vamos aplicando y deshaciendo movimientos.

Deshacer movimientos:

Lógicamente, para poder deshacer un movimiento tenemos que saber cuál fue el último movimiento que se aplicó. Sólo el último movimiento se puede deshacer. Para esto se utiliza la lista “game_list” del fichero “Init.asm”.

“game_list” es similar a “move_list”, pero en vez de almacenar los movimientos posibles a partir de un tablero, almacena los movimientos jugados en el pasado, de modo que el último movimiento de “game_list” es el único que se puede deshacer. “game_list”, igual que “move_list”, es doble en realidad, ya que los movimientos tienen un origen y un destino. Por tanto, tenemos “game_list_start” y “game_list_dest”.

Veamos cómo actualizar el tablero para ir recorriendo el árbol de juego.

Rutina “updatePiece”:

La rutina “updatePiece” forma parte de un nuevo fichero “Update.asm”. En este fichero van a estar todas las rutinas relativas a la actualización del tablero, es decir, relativas a aplicar y deshacer movimientos.

Es decir, esta rutina básicamente:

• Añade una pieza (“upPiece”) a la casilla de destino (“upDest”).
• Y mete vacío (“#PIECE_EMPTY”) en la casilla de origen (“upStart”).

Pero además de eso, llama a la rutina “updateHash” para actualizar el hash y el lock del tablero como consecuencia de la pieza movida (recordemos que el hash y el lock se derivan de las piezas y sus posiciones).

La rutina “updateHash”, que es del fichero “Hash.asm”, es muy similar a la ya vista “getHash”. “getHash” calcula el hash del tablero teniendo en cuenta todas sus piezas; “updateHash” actualiza el hash y el lock del tablero teniendo en cuenta la pieza de una posición concreta.

De hecho, “updatePiece” llama dos veces a la rutina “updateHash”:

• La primera vez con la pieza que se mueve (“upPiece”) y la casilla de origen (“upStart”). Esto es para reflejar en el hash y en el lock que la pieza ya no está en la casilla de origen.
• Y la segunda vez con la pieza que se mueve (“upPiece”) y la casilla de destino (“upDest”). Esto es para reflejar en el hash y en el lock que la pieza ahora está en la casilla de destino.

Con todos estos mimbres (lista de jugadas “game_list” y rutina “updatePiece”) ya es posible abordar las rutinas para hacer y deshacer movimientos. Pero esto ya lo haremos en la siguiente entrada.

---

Código del proyecto: RYG3-05