Assembly in one step

En este blog encontraréis montones de referencias útiles sobre C64. Al comienzo del blog tenéis una selección muy completa, pero no son las únicas, ya que en sucesivos “posts” he ido incluyendo más y más referencias:

Y como no paro de toparme con nuevas referencias de interés, aquí va una nueva que me ha parecido interesante:

“Assembly in one step” es un breve tutorial en inglés sobre programación del 6502. No es una mera revisión de sus instrucciones, sino que incluye:

  • Una descripción de la arquitectura del 6502.
  • Los modos de direccionamiento.
  • El juego de instrucciones.
  • Algunos programas de ejemplo.

Todo ello lo hemos revisado en este blog, y seguramente más a fondo, pero siempre está bien conocer fuentes nuevas y darle un repaso a los temas importantes.

C64 Debugger

C64 Debugger es un completo depurador para C64. No es el único disponible; por ejemplo, CBM prg Studio también tiene su propio depurador integrado.

El instalable de C64 Debugger está disponible en la dirección https://sourceforge.net/projects/c64-debugger/files/. Desde ahí se puede descargar en formato ZIP, siendo la versión actual la 0.64.58.6.

El contenido del ZIP para Windows es algo así:

En realidad, no hace falta instalar nada. Para poder usar C64 Debugger llega con extraer el contenido del ZIP a una carpeta, por ejemplo, a la carpeta “C64 Debugger” del Escritorio, y luego crear un acceso directo al ejecutable C64Debugger.exe.

Si ejecutamos C64Debuger.exe, bien directamente o bien vía el acceso directo, aparece una ventana como la siguiente:

En esta ventana pueden verse las siguientes zonas:

  • A la izquierda, la “vista de desensamblado”, que muestra parte de la memoria del C64 en formato desensamblado, es decir, interpretando el contenido como instrucciones de código máquina. Además, por defecto, muestra la instrucción que se está ejecutando en cada momento, es decir, la instrucción apuntada por el contador de programa.
  • En el centro y arriba, la “vista de mapa de memoria”, que es un rectángulo en modo bitmap que muestra el contenido de la memoria del C64 (cada pixel representa un byte). Aquí la clave es el color de cada pixel, que sirve para interpretar el contenido de la memoria y si se están ejecutando operaciones de lectura (azul) o de escritura (rojo).
  • En el centro y abajo, la “vista de volcado de datos”, que es otro rectángulo que muestra el contenido hexadecimal de parte de la memoria del C64. Además, a la derecha del hexadecimal puede verse, también, la interpretación de esos valores como códigos de pantalla.
  • A la derecha y arriba, se ven los registros del microprocesador.
  • Debajo de los registros, se ve la RAM de pantalla en formato visible, como se vería en la pantalla del C64.

Todo esto se llaman “vistas”, y se pueden cambiar mediante los múltiples atajos de teclas que tiene C64 Debugger (ver fichero C64 Debugger shortcuts v06458.xlsx). También se puede cambiar el foco de una vista a otra, haciendo click con el ratón, y así manipular el contenido de las mismas.

Y como saberse todos estos atajos es casi imposible, conviene acompañar el C64 Debugger con un par de productos complementarios:

El manual de usuario en PDF puede descargarse de la misma página https://sourceforge.net/projects/c64-debugger/files/, si bien el último manual disponible es para la versión 0.64.56 de C64 Debugger:

Por último, una opción muy interesante es la interfaz gráfica o GUI para C64 Debugger. Esta interfaz gráfica añade botones para poder ejecutar las diferentes opciones y vistas de C64 Debugger:

Puede descargarse en formato ZIP desde la página http://bit.ly/C64DebugGUI e, igual que C64 Debugger, no requiere instalación como tal. Llega con extraer el contenido del ZIP a una carpeta y ejecutar C64DebuggerGUI.exe. De hecho, C64DebuggerGUI incluye C64 Debugger en su ZIP.

El principal problema es que, que se sepa, C64 Debugger GUI se quedó en la versión 0.64.2 de C64 Debugger, y no ha sido actualizado desde entonces. Una pena porque resultaba muy útil…

Nuevo libro: Programación Retro del Commodore 64 Volumen III

Tras el éxito de los volúmenes I y II, acaba de publicarse en Amazon el nuevo libro “Programación Retro del Commodore 64 Volumen III”:

Son 193 páginas que describen en detalle cómo programar en ensamblador un juego de tablero, es decir:

  • La representación del tablero.
  • La generación de jugadas.
  • El árbol de juego.
  • La función de evaluación.
  • La búsqueda minimax.
  • La búsqueda alfa-beta (con poda).
  • La profundización iterativa.
  • La ordenación de movimientos.
  • Las tablas de historia.
  • Etc.

El libro está disponible en los principales portales de Amazon:

Yo lo he pasado fenomenal escribiéndolo, así que espero que lo paséis igual de bien leyéndolo y, sobre todo, adaptando las ideas a vuestros propios proyectos con el C64.

Commodore 128, Commodore 65 y Mega65

Casi todos los aficionados al C64 conocemos su sucesor natural, el C128:

El C128 se lanzó en 1985 –el C64 en 1982–, y se caracterizaba por:

  • Tener dos procesadores, un MOS 8502 y un Z80.
  • Tener 128 KB de RAM.
  • Soportar BASIC 2.0, BASIC 7.0 y CP/M.

Y, por encima de todo, el C128 era compatible con el C64, en el sentido de que casi todo el software del C64 se podía ejecutar en el C128, entrando éste en “modo C64”.

Menos conocido que el C128 fue el C65. De hecho, el C65 fue un prototipo de finales de los 80 que no llegó al mercado:

Las características principales del C65 eran:

  • Tener un procesador MOS 65CE02.
  • Tener 128 KB de RAM.
  • Soportar BASIC 2.2 y BASIC 10.0.
  • Tener una unidad de disquetes de 3,5 integrada.

El C65 también tenía previsto un “modo 64” para poder ejecutar el software del C64.

Pues bien, aunque ya lleva tiempo por ahí, recientemente he podido conocer un proyecto llamado Mega65 para reproducir el C65 con FPGA, es decir, con circuitos programables. Algo similar a Ultimate 64, pero para el C65.

El proyecto tiene muy buena pinta, y podéis conocer todos sus detalles en su página web https://mega65.org/.

Eso sí, el Mega65 podía tener un precio un poco más ajustado, porque cuesta cerca de los 800 euros. ¡¡Por ese precio te compras varios C64 auténticos de segunda mano!!

Sugerencias para el lector

El proyecto lo damos por terminado con su versión 11 aunque, por supuesto, admite muchas mejoras. Aquí van algunas sugerencias para el lector que tenga interés:

  • Calcular y mostrar unos contadores de podas alfa y beta.
  • Mostrar el registro de jugadas (tabla “game_list”).
  • Guardar el registro de jugadas a cinta o disco, y permitir su carga.
  • Mejorar la función de evaluación con más criterios, por ejemplo, para identificar y evaluar de forma adecuada situaciones de fin de partida.
  • Implementar algoritmos de ordenación de movimientos más eficientes.
  • Añadir un “libro” con comienzos y/o finales de partida.
  • Adaptar las ideas comentadas a otros tipos de juegos de tablero, por ejemplo, Othello, damas, ajedrez o go.
  • Mejorar la interfaz de usuario, utilizando caracteres personalizados para pintar ratón, gatos, casillas, mensajes, etc.
  • Desarrollar sonidos SID para avisar al usuario de que el C64 ha movido, o que el movimiento que pretende hacer el usuario es ilegal.
  • Utilizar los temporizadores y las interrupciones del CIA1 para poner un límite máximo (ej. X minutos/movimiento) al tiempo de juego del C64.
  • Que el C64 “piense” mientras el humano piensa, asumiendo que éste hará una jugada determinada.
  • Hacer un perfilado del programa mediante herramientas como C64 Debugger, de modo que se identifiquen posibles cuellos de botella y el programa se pueda optimizar.

En fin… las posibilidades son casi infinitas… ¡¡a disfrutarlo!!

HVSW.

Colossus Chess

“Colossus Chess” fue una serie de juegos de ajedrez ganadores de muchos premios durante los 80. Lo programó Martin Bryant y se portó a casi todos los equipos de 8 bits de la época.

Jugué muchas veces contra “Colossus Chess”. Ya no recuerdo si conseguí ganarle en alguna ocasión, pero sí recuerdo haberlo puesto contra las cuerdas más de una vez. Al final, casi siempre cometía algún fallo garrafal, se me revolvía, y me daba un buen repaso.

Aquí os dejo un par de pantallas de una partida reciente. Este es el tablero de juego (tenía una vista 2D y otra 3D):

Y este es el registro de la partida y lo que está pensando la máquina:

El juego tenía muchísimas funcionalidades, entre las que destacan:

  • Tablero de juego con vistas 2D y 3D. Se pueden cambiar los colores. Se puede cambiar la orientación del tablero.
  • Registro de jugadas de la partida en notación algebraica, incluyendo los tiempos de juego de cada jugador.
  • Información sobre el análisis de jugadas que está haciendo Colossus (“lookahed”: profundidad de análisis, “positions”: número de tableros analizados, “current line”: variante actual, “best line”: variante principal, etc.).
  • Evaluación de tableros atendiendo a criterios materiales (número y tipos de piezas), de posición (posición de las piezas en el tablero), y otros.
  • El juego no sólo “piensa” durante su turno, sino que también analiza jugadas mientras piensa el contrincante humano. Para ello, hace una hipótesis sobre la jugada que jugará el humano (“assumed”), y analiza jugadas a partir de esa hipótesis.
  • Se permite alterar la posición de las piezas, para así llevar el tablero a una situación X desde la que se quiera continuar una partida.
  • Se permite deshacer movimientos, por ejemplo, para rectificar errores; también se permite repetir movimientos.
  • Guardar partidas a cinta o disco, y cargarlas de nuevo.
  • Cambiar de bando. Pedir a Colossus que haga una jugada por ti.
  • Que Colossus juegue contra sí mismo.
  • Aplicar una base de datos de aperturas y finales de partida.
  • Repetir una partida, en el sentido de reproducir todos los movimientos del registro de jugadas, desde el primero hasta el último.
  • Modificar los parámetros de configuración del juego: si Colossus usa o no la base de datos de aperturas / finales, si Colossus “piensa” o no durante el turno del contrincante, la profundidad de análisis del árbol de jugadas, etc.
  • Etc.

En definitiva, un juego completísimo e imbatido cuando se midió contra programas similares en otros equipos de 8 bits (Apple II, Spectrum, Atari, etc.).

Ahora que hemos intentado acercarnos un poco a la programación de este tipo de juegos, podemos hacernos una idea de la grandísima dificultad que suponen.

Tablas de historia II

Ahora que ya hemos definido las tablas de historia, y sabemos manejarlas con las rutinas “newHistory”, “getHistory” e “incHistory”, vamos a usarlas. Esto se describen en los apartados siguientes:

Novedades en la rutina “thinkIter”:

En la rutina “thinkIter”, que es la que aplica la profundización iterativa, lo que vamos a hacer es inicializar las tablas de historia, para lo cual llamamos a “newHistory”:

Como se puede observar, después de preparar el proceso de búsqueda con “newPosition”, y antes de empezar la profundización iterativa que va desde X=0 hasta X=max_depth-1, aparece una nueva llamada a “newHistory”. Esta llamada es la que borra las tablas de historia.

Novedades en la rutina “search”:

Por otro lado, en la rutina “search”, tanto en la rama dedicada a la búsqueda del ratón “searchMouse”, como en la rama dedicada a la búsqueda de los gatos “searchCats”, aparecen sendas llamadas a “incHistory”:

La llamada a “incHistory” se produce después de llamar a “addHashPosMouse”, es decir, después de insertar el movimiento (admStart, admDest) en la tabla hash. Esta nueva llamada sirve para incrementar el valor de historia asociado al movimiento elegido, y el incremento puede ser de un punto o de tantos puntos como la profundidad “depth”, que es lo que está programado actualmente.

Novedades en la rutina “addMove”:

Esto ya es lo último, y consiste en generar los movimientos no con puntuación cero, como hasta ahora, sino con una puntuación igual a la de las tablas de historia:

De este modo, cuando los movimientos se desarrollan y prueban en “search”, debido a la llamada a “sort”, primero se desarrollan aquellos que tienen mayor puntuación.

Esta reordenación de movimientos debería tener un efecto positivo en la poda, en el sentido de podar más, pero no debería cambiar los movimientos que se deciden o eligen para cada tablero y para una profundidad dada.

En la práctica, sí puede haber pequeños cambios entre los movimientos que elige la versión del proyecto sin tablas de historia (versión 10) y los movimientos que eligen la nueva versión con tablas de historia (versión 11), pero siempre cambiando entre movimientos que dan lugar a tableros con la misma puntuación. Esto es, simplemente, un pequeño efecto secundario de la reordenación de movimientos.

Otras novedades:

Además de las novedades ya comentadas, hay algunas otras pequeñas novedades relacionadas con las tablas de historia, pero son de entidad menor:

  • En el fichero “Display.asm” hay una nueva rutina “displayHistory” para mostrar el contenido las tablas de historia.
  • En el fichero “Main.asm” hay un nuevo comando especial “.F” para mostrar el contenido de las tablas de historia. Llama a la rutina “displayHistory” anterior, y se usa para depuración.
  • La rutina “addHashMove”, que suma #HASH_SCORE a la puntuación de los movimientos que están en las tablas hash, ahora aplica un tope de 255 ya que, al sumarse en ocasiones también los valores de las tablas de historia, podría superarse ese valor (acarreo).

Mejora en la poda:

El objetivo de todo esto de las tablas de historia es mejorar la ordenación de los movimientos y, por tanto, la poda. Por tanto, no deberíamos concluir esta sección sin comprobar si lo hemos logrado.

En la versión 10 del proyecto, con una profundidad de análisis de 8 niveles, ante el movimiento E1F2, el C64 analizaba $29F8 = 10.744 tableros, lo cual ya era un 40% menos que con la versión 9 ($4535 = 17.717 tableros).

Veamos ahora con las tablas de historia, es decir, con la versión 11 del proyecto:

Es decir, ahora se desarrollan $DCF = 3.535 tableros, lo cual es un 67% menos que con la versión 10 ($29F8 = 10.744) y un 80% menos que con la versión 9 ($4535 = 17.717). Como se puede ver, la reducción es muy notable.


Código del proyecto: RYG3-11

Tablas de historia

Las tablas de historia son una forma adicional de mejorar la ordenación de movimientos y, por tanto, la poda alfa – beta.

La idea básica es definir una tabla de doble entrada (origen, destino) o, lo que es lo mismo, 64 tablas (con 64 destinos cada una), una tabla por cada casilla origen. Por eso hablamos de “tablas de historia”.

Cada vez que un movimiento (origen, destino) se inserta en la tabla hash, además, se incrementa el valor (origen, destino) en la tabla de historia correspondiente. Ese incremento puede ser de un punto o, mejor, de tantos puntos como la profundidad de análisis a la que se produzca la inserción (“depth”).

Posteriormente, cuando la rutina “gen” genera los movimientos, en vez de nacer todos con puntuación 0, pueden nacer con una puntuación igual a la que figure en las tablas de historia.

En el fondo es algo como decir, “si este movimiento fue bueno en el pasado, es probable que vuelva a serlo ahora y, por tanto, voy a desarrollarlo antes”. No se trata de dar ese movimiento por bueno, o de seleccionarlo como mejor movimiento; se trata, simplemente, de desarrollarlo antes que otros confiando en que vuelva a ser bueno y que mejore la poda.

Por último, las tablas de historia pueden inicializarse al comienzo de la partida e ir dándoles valor y utilizándolas durante toda la partida o, según el caso, inicializarlas con cada nuevo movimiento o proceso de búsqueda. En un juego como el ratón y el gato no es probable que un movimiento que fue bueno hace N jugadas vuelva a ser bueno ahora, así que mejor inicializar las tablas de historia en cada proceso de búsqueda.

Desde el punto de vista del código ensamblador, las principales novedades se concentran en un nuevo fichero “History.asm”. Este fichero contiene:

  • La definición de las 64 tablas de historia (una por cada casilla origen).
  • Unos punteros para acceder a las tablas anteriores.
  • La rutina “getHistory” que, dado un movimiento, consulta su puntuación en las tablas de historia.
  • La rutina “incHistory” que, dado un movimiento, incrementa su puntuación en las tablas de historia.
  • La rutina “newHistory” que inicializa las tablas de historia.

Todo esto se revisa a continuación:

Tablas de historia:

Hay 64 tablas de historia, una por cada casilla origen. Y cada tabla de historia tiene 64 posiciones, una por cada casilla destino. Es decir, las tablas de historia ocupan 64 x 64 = 4 KB.

Teniendo en cuenta que no todos los orígenes son posibles, ni tampoco todos los destinos, dado que el ratón y los gatos siempre se mueven por casillas negras (marcadas con “X”), las tablas de historia se podrían compactar. Sin embargo, por facilidad de programación, dado que las posiciones origen y destino se determinan con un índice entre 0 y 63, se van a mantener así.

Podríamos definir las 64 tablas una detrás de otra, en plan:

Sin embargo, esto daría bastante trabajo y ocuparía bastante espacio en el fichero “History.asm”. Por ello, vamos a usar una funcionalidad muy interesante de CBM prg Studio, que consiste en usar directivas:

Esto lo que viene a decir es:

  • Empezando en index = 0.
  • Y terminando en index = 63.
  • Mete una tabla history_index, donde “index” se sustituye por su valor.

De este modo acabamos con 64 tablas de historia, desde history_0 (para la casilla origen 0) hasta history_63 (para la casilla origen 63). Cada tabla de historia tiene 64 destinos posibles.

Esto se puede comprobar fácilmente en el “assembly dump” al ensamblar con Ctrl + F5 desde CBM prg Studio:

Por tanto, hemos definido 64 tablas. Veamos cómo acceder a ellas.

Punteros para acceso a las tablas de historia:

Dado un movimiento (origen, destino), tendremos que acceder a la tabla de historia de ese origen, ya sea para incrementar o para leer el valor del destino en esa tabla.

Esto lo vamos a lograr con una técnica similar:

De este modo conseguimos dos tablas:

  • Una llamada “histLo” con las partes low (partes menos significativas) de los punteros de acceso a las tablas de historia.
  • Otra llamada “histHi” con las partes high (partes más significativas) de los punteros de acceso a las tablas de historia.

De este modo, accediendo a ese par de tablas usando la casilla origen como índice podemos fácilmente componer un puntero (lo, hi) para acceder a la tabla de historia correspondiente.

Aquí puede verse que al ensamblar con Ctrl + F5, efectivamente, se ha formado una tabla con las partes low (<) de los punteros y otra con las partes high (>):

Rutina “getHistory”:

Con las piezas anteriores resulta fácil leer o escribir en las tablas de historia. Por ejemplo, para leer el valor de historia del movimiento (start, dest) se utilizaría la rutina “getHistory”, que es así:

Esta rutina:

  • Carga la posición origen “ghStart” en el índice Y.
  • Usando Y / “ghStart” como índice, lee la parte low del puntero de acceso a la tabla de historia. Este valor lo graba en $fb.
  • Usando Y / “ghStart” como índice, lee la parte high del puntero de acceso a la tabla de historia. Este valor lo graba en $fc.
  • Carga la posición destino “ghDest” en el índice Y.
  • Usando el direccionamiento indirecto – indexado (lda ($fb),y), es decir, usando $fb – $fc como puntero base y sumando Y / “ghDest”, accede al valor de historia.

En este caso el valor de historia se devuelve directamente en el acumulador, porque se va a usar desde ahí. En otras rutinas este valor se hubiera guardado en una variable “ghScore” o similar.

Rutina “incHistory”:

Para incrementar el valor de historia la rutina es muy similar a la anterior:

Las ideas son muy parecidas, es decir, se monta un puntero a la tabla de historia correspondiente con ($fb – $fc), siendo las principales diferencias:

  • Se lee el valor de la tabla de historia con lda($fb),y, pero además se suma con adc la puntuación pasada en el parámetro “ihAdd”.
  • Si el resultado de la suma excede $ff = 255, se topa a 255.
  • El nuevo valor resultante se guarda en la tabla de historia con sta($fb),y.

En definitiva, se incrementa el valor de la tabla de historia en “ihAdd”, pero a su vez se pone un tope de $ff = 255.

Rutina “newHistory”:

La rutina “newHistory” sirve para inicializar las tablas de historia. Esto puede hacerse al comienzo de la partida o, como vamos a hacer, al comenzar el proceso de búsqueda alfa – beta.

Como se puede ver, esta rutina es un doble bucle:

  • El bucle exterior va desde X=0 hasta X=63.
  • Lo primero que hace es preparar un puntero ($fb – $fc) a la base de la tabla de historia X.
  • El bucle interior va desde Y=0 hasta Y=63, es decir, recorre las 64 posiciones de la tabla de historia X.
  • En cada una de esas 64 posiciones se almacena un 0 (sta($fb),y).

Esta rutina también se puede optimizar puesto que, como ya se ha dicho, hay posiciones (las casillas blancas o marcadas con “.”) que no se usan como origen ni como destino y, por tanto, no hace falta inicializarlas. Esto es especialmente cierto en el caso de las casillas origen, porque de forma directa te ahorras inicializar la mitad de las tablas de historia (porque no se usan).

Con esto acabamos la descripción de las tablas de historia, aunque ahora falta utilizarlas, cosa que ya haremos en la entrada siguiente.


Código del proyecto: RYG3-11

Ordenación de movimientos

Si recordamos, en alguna entrada anterior introdujimos el concepto de “profundización iterativa”, que consiste en no buscar directamente a la profundidad de análisis configurada, sino empezar por profundidad uno, luego dos, luego tres, etc., hasta llegar a la profundidad configurada. Y todo ello con el objeto de mejorar la ordenación de los movimientos y, por tanto, optimizar la poda alfa – beta.

Aunque los movimientos se generen e inserten en “move_list” con un orden arbitrario, que en nuestro caso es y va a seguir siendo suroeste – sureste – noreste – noroeste (ver rutina “gen”), eso no quiere decir que esos movimientos tengan que desarrollarse en ese mismo orden. Pueden reordenarse en función del algún criterio antes de desarrollarlos recursivamente. Y esto es, precisamente, lo que vamos que vamos a hacer en esta entrada, de modo que saquemos provecho de la profundización iterativa.

Movimientos con puntuación:

Lo primero que vamos a hacer es asignar a los movimientos una puntuación, de modo que desarrollemos primero aquellos movimientos de mayor puntuación. Es importante no confundir la puntuación de los movimientos con la puntuación o evaluación de los tableros, que sirve para que elegir qué tableros son mejores.

De este modo, los movimientos de “move_list” pasan de tener un origen y un destino a tener un origen, un destino y una puntuación:

Como se puede ver, ahora los movimientos tienen:

  • “move_list_start”: origen.
  • “move_list_dest”: destino.
  • “move_list_score”: puntuación (nuevo).

Por otro lado, la rutina que genera los movimientos permitidos a partir del tablero actual, es decir, la rutina “gen”, sigue generando los movimientos en el mismo orden (suroeste – sureste – noreste – noroeste), pero ahora los genera con una puntuación inicial de cero. Ver su subrutina “addMove”:

Esta puntuación inicial la modificaremos más adelante, de modo que podamos reordenar los movimientos y desarrollar primero los mejores, de modo que se optimice la poda.

Aprovechar la profundización iterativa:

Ahora es cuando por fin vamos a aprovechar la profundización iterativa. Si un movimiento ha sido bueno en alguna iteración anterior, por ejemplo, porque ha dado lugar a una poda alfa o beta, estará en la tabla hash desde esa iteración.

Por tanto, en las rutinas “searchMouse” y “searchCats”, después de generar los movimientos posibles con “gen”, vamos a llamar a una nueva rutina “hashMove”:

Esta nueva rutina “hashMove” hace esto:

Es decir, “hashMove” busca el tablero actual, aquel para el que “gen” ha generado los movimientos posibles, en la tabla hash de ratón o gatos, según el turno, y, si el tablero está en la tabla hash, llama a la rutina “addHashMove”:

La rutina “addHashMove”, por su parte, recorre los movimientos generados por “gen”, es decir, los movimientos posibles a partir del tablero actual, y, al que coincida con el movimiento almacenado en la tabla hash (hash_start, hash_dest), que se supone que es el mejor movimiento, le suma a su puntuación el valor “#HASH_SCORE”.

Dicho de forma sencilla, de todos los movimientos posibles a partir del tablero actual, si alguno está en la tabla hash proveniente de alguna iteración anterior (profundización iterativa), le sumamos “#HASH_SCORE” a su puntuación, lo que (en breve) va a hacer que se desarrolle antes.

“#HASH_SCORE” es una nueva constante definida en el fichero “Globals.asm” e inicialmente toma el valor de 10.

Ordenación de movimientos antes de desarrollarlos:

Los movimientos ya tienen una puntuación (“move_list_score”) y ya sabemos cuándo incrementamos su valor: cuando ese movimiento está en la tabla hash como consecuencia de una iteración anterior de la profundización iterativa.

Ahora falta, por fin, reordenar los movimientos, es decir, desarrollar primero los movimientos con mejor puntación. Esto lo hacemos también en “searchMouse” y “searchCats” con una llamada a la nueva rutina “sort”:

En cada iteración del bucle que prueba y desarrolla cada jugada, es decir, el bucle que empieza en la etiqueta “schMouseAgain” o “schCatsAgain”, vemos la llamada a “sort”:

“Sort” lo que hace es comparar la puntación de la jugada actual con la puntuación de todas las jugadas que quedan por probar / desarrollar y, si alguna tiene puntuación mayor, las reordena en “move_list”, para lo cual se apoya en la rutina auxiliar “shift” (ordenación por inserción):

De este modo, se prueban y desarrollan primero las jugadas con mayor puntuación que, de momento, son aquellas que la profundización iterativa ha decidido que son buenas. Luego se pueden añadir otros criterios para modificar la puntuación y la ordenación, como las tablas de historia.

Mejora en la poda:

Si todo lo que hemos dicho es cierto, que ordenar los movimientos de forma lógica favorece la poda, debería notarse este efecto al comparar la versión anterior del proyecto (versión 9) con la nueva versión (versión 10).

En la versión 9 del proyecto, con una profundidad de 8, se analizaban estos movimientos en la primera jugada de los gatos tras E1F2:

Es decir, se analizaban $4535 = 17.717 nodos. Recordemos que este es el número de nodos acumulado para los ocho niveles, no el valor específico para el octavo nivel.

Sin embargo, con la versión 10 del proyecto, que es la que ya tiene ordenación de movimientos, se analizan estos nodos (también para nivel 8, claro):

Como se puede observar, se han analizado $29F8 = 10.744, que es un 40% menos.

De hecho, una cosa que puede llamar la atención es que los movimientos elegidos no son el mismo. Con la versión 9 del proyecto era el H8G7, mientras que con la versión 10 es el B8A7. Ni la poda alfa – beta ni la ordenación de movimientos deberían tener este efecto. El origen del mismo radica en que en la versión 10 del proyecto se han hecho algunos ajustes en la rutina “search” cuando la puntuación retornada coincide con alfa o beta (cálculo del máximo o mínimo).

Con la versión 10 del proyecto, con una profundidad de 8 niveles o superior, jugando el humano con el ratón y el C64 con los gatos, yo no he conseguido ganarle, lo cual es muy buena noticia. A esa profundidad el C64 tarda menos de minuto y medio en decidir su siguiente jugada.

Por tanto, el proyecto está prácticamente terminado, aunque, por supuesto, admite muchas mejoras.


Código del proyecto: RYG3-10