Generación de jugadas I

Para generar las jugadas o movimientos necesitamos varios elementos:

• Las direcciones de movimiento.
• Las tablas de movimientos de ratón y gatos.
• La lista de movimientos generados.

Vamos a verlos poco a poco:

Direcciones de movimiento:

Tanto el ratón como los gatos se mueven en diagonal. El ratón puede moverse en las cuatro direcciones diagonales, mientras que los gatos sólo hacia abajo.

Estas cuatro direcciones de movimiento, que llamamos DIR_SW = 0 = suroeste, DIR_SE = 1 = sureste, DIR_NE = 2 = noreste y DIR_NW = 3 = noroeste, las definimos como constantes en “Globals.asm”:

Los valores 0, 1, 2 y 3 nos servirán como índice para leer los movimientos, es decir, la casilla de destino, de las tablas de movimientos de ratón y gatos.

El orden de las direcciones es arbitrario, pero como ratón y gatos comparten la posibilidad de moverse en las direcciones DIR_SW y DIR_SE, lo lógico es que estas direcciones tomen los valores 0 y 1.

Tablas de movimientos de ratón y gatos:

En el fichero “Init.asm” es donde recogemos las variables principales (“side”, “ply”, “hpy”, “nodes”, etc.) y las estructuras de datos principales (“board”, “init_board”, etc.). Entre estas últimas, tenemos las tablas:

• “mouse_moves”.
• “cat_moves”.

La tabla “mouse_moves” recoge los movimientos posibles del ratón. La tabla “cat_moves” recoge los movimientos posibles de los gatos.

Estas tablas se manejan así:

Supongamos que es el turno de ratón. Por tanto, usamos la tabla “mouse_moves”. Supongamos, también, que el ratón está en la casilla E1, es decir, en el índice 4 del tablero. Por tanto, vamos a la fila 4 de la tabla “mouse_moves” y ahí tenemos los 4 movimientos posibles:

Los movimientos posibles, es decir, las casillas de destino del ratón partiendo de la casilla E1 = 4, son:

• DIR_SW = 0 => -1, es decir, no es posible mover en esta dirección.
• DIR_SE = 1 => -1, es decir, tampoco es posible mover en esta dirección.
• DIR_NE = 2 => 13, es decir, la casilla F2.
• DIR_NW = 3 => 11, es decir, la casilla D2.

Por tanto, partiendo de la casilla E1 = 4, el ratón puede moverse a las casillas F2 = 13 y D2 = 11. No puede moverse hacia el sur o hacia abajo, porque se saldría del tablero. Y efectivamente es así:

Si en vez de mover el ratón movieran los gatos el proceso sería totalmente análogo, siendo las principales diferencias que usaríamos la tabla “cat_moves” y que en este caso sólo habría dos movimientos posibles:

Por ejemplo, para la casilla H8 = 63 el único destino posible sería la casilla G7 = 54.

Por supuesto, para que un movimiento sea posible, además de estar registrado en la tabla de movimientos de ratón o gatos, el destino tiene que estar vacío.

Lista de movimientos posibles generados:

Los movimientos posibles generados conforme a las reglas anteriores se guardan en una lista llamada “move_list”. En realidad, como los movimientos tienen una casilla de origen y otra de destino, la lista anterior es doble, “move_list_start” y “move_list_dest”:

Además, recordemos que el juego consiste en generar todos los movimientos posibles a partir de una posición, intentarlos o probarlos, evaluar si el resultado es más o menos favorable, deshacerlos, y finalmente elegir el mejor movimiento posible. Y todo esto, hasta una profundidad N, que es la profundidad de análisis o nivel de juego que haya elegido el usuario.

Por tanto, si en un momento dado el proceso de búsqueda nos ha llevado hasta el tablero de la izquierda, es decir, si la variante actual es esa rama, en la tabla “move_list” necesitaremos tener los tres movimientos posibles desde la posición actual (ply = 0) y, además, los dos movimientos posibles del tablero de la izquierda (ply = 1).

Todo esto se gestiona gracias a la tabla “first_move” que, para una profundidad dada (ply = X), nos dice donde empiezan sus movimientos en “move_list”. Gráficamente sería así:

En definitiva, la tabla “first_move” nos dice dónde empiezan y terminan los movimientos de cada nivel de profundidad. En la figura anterior, los movimientos del tablero actual (ply = 0) empiezan en el índice 0 (s0=>d0, s1=>d1 y s2=>d2) y los movimientos del tablero que se está analizando a profundidad uno (ply = 1), el tablero de la izquierda, empiezan en el índice 3 (s3=>d3 y s4=>d4).

De este modo es posible ir moviendo la variante actual por el árbol, probando movimientos a una profundidad, deshaciéndolos, probando otros movimientos de profundidad menor que estuvieran pendientes de probar, etc.