Intoducción
En este proyecto desarrollé una versión digital del antiguo juego romano Latrones, implementada como una aplicación web utilizando el framework Flask. La lógica del juego fue programada en Python, mientras que la interfaz gráfica fue construida con HTML, CSS y JavaScript. La aplicación permite partidas entre dos jugadores humanos o contra un oponente automatizado, cuyo comportamiento se basa en un algoritmo minimax con poda alpha-beta.
El código fuente completo está disponible en el siguiente repositorio: https://github.com/rj-engineeringde/latrones.git
El siguiente video muestra una demostración en funcionamiento:
¿Por qué Latrones?
Siempre he sentido una fascinación especial por los juegos de lógica determinística como el ajedrez, las damas o el shōgi. Sin embargo, a la hora de embarcarme en un nuevo proyecto de programación, no quería simplemente replicar uno de estos juegos populares. Existen amplios tutoriales en internet que explican en detalle como programar un juego de damas o ajedrez, y esto elimina gran parte del desafío. Al existir ya tantas implementaciones, las cuales pueden ser simplemente copiadas, la tentación de «inspirarse» en estas fuentes es demasiado alta. Al mismo tiempo, reinventar la rueda y prescindir de los tutoriales ya existentes, resulta limitante y ciertamente absurdo. Quería enfrentarme a un reto auténtico, que me obligara a diseñar desde cero la lógica del juego. Esta búsqueda me llevó a descubrir Latrones (o Ludus latrunculorum), un antiguo juego romano cuyas reglas se han perdido en el tiempo, y cuya escasa documentación moderna lo convierte en un candidato perfecto. Las piezas y el tablero han sido hayados en varias excavaciones arqueológicas. Sin embargo, hasta el día de hoy las reglas siguen siendo un misterio, y únicamente existen conjeturas al respecto.
Implementación
El juego fue implementado como una aplicación web utilizando el framework Flask. La lógica del juego se desarrolló en Python, mientras que la interfaz gráfica de usuario se construyó con HTML, CSS y JavaScript. La interfaz permite al usuario interactuar con el tablero y muestra una cuenta regresiva individual para cada jugador. Además, incorporé un menú para reiniciar la partida que permite configurar diversos parámetros, como el tiempo por jugador, el tamaño del tablero, el color del jugador principal y si el oponente será otro jugador o un bot.
Para esta implementación, me he basado en las reglas conjeturadas por el historiador W. J. Kowalski:
Posición inicial
Latrones se juega sobre un tablero rectangular compuesto por casillas cuadradas, visualmente similar al del ajedrez. Sin embargo, a diferencia del ajedrez, el tamaño del tablero no está estandarizado, ya que varía según los hallazgos arqueológicos en los que se ha basado la reconstrucción del juego. En el juego existen dos tipos de fichas: los hombres y el rey. En la posición inicial de la partida, la primera y la última fila del tablero son completamente ocupadas por hombres del respectivo color. En la segunda y en la penúltima fila se posiciona respectivamente un único rey, el cual se sitúa en el centro de la fila. Si el número de columnas es par, el rey se posiciona en la columna central derecha (según el punto de vista del jugador correspondiente). Un jugador gana si captura a todos los hombres oponentes o inmoviliza al rey. El juego finaliza inmediatamente si se cumple una de estas condiciones.
Movimientos
Todas las fichas (hombres y rey) pueden moverse en línea recta vertical u horizontalmente, hasta que encuentren otra ficha (propia o enemiga) que les impida avanzar. El movimiento es similar al de la torre en ajedrez. El rey, sin embargo, dispone de una habilidad adicional: puede saltar por encima de otras fichas. Este salto solo está permitido si todas las casillas saltadas están ocupadas, y el salto termina en la captura de al menos una ficha enemiga (hombre o rey).
Captura lineal
Un hombre es capturado cuando queda rodeado por dos lados opuestos (ya sea horizontal o verticalmente) por fichas enemigas. También es posible capturar grupos enteros de hombres, si el grupo es atrapado linealmente por ambos extremos. Un hombre no puede ser capturado si entra voluntariamente en una posición de captura. La captura solo se ejecuta si el movimiento del oponente la provoca. Si un hombre o rey entra a una posición el la que este se encuentra atrapado linearmente por figuras enemigas, esto omite cualquier captura linear en el el el turno del movimiento.
Captura del rey
El rey no se captura mediante el método anterior. Para capturarlo, debe ser inmovilizado por las cuatro direcciones (arriba, abajo, izquierda y derecha), sin posibilidad de moverse.
Captura por inmovilización en el borde
Cualquier grupo de fichas (incluyendo al rey) puede ser capturado si queda completamente encerrado contra una pared o esquina del tablero y rodeado por piezas enemigas, sin espacio libre para moverse.
En cuanto a la funcionalidad del juego, programé todas las reglas esenciales: la representación del tablero, los movimientos válidos, las capturas, el cambio de turno entre jugadores y la detección del ganador. Para las partidas contra la máquina, desarrollé un oponente automatizado que toma decisiones utilizando el algoritmo minimax con poda alpha-beta. Este algoritmo explora de forma recursiva los posibles movimientos futuros del juego con el objetivo de maximizar las jugadas favorables al bot y minimizar las ventajas del oponente. La poda alpha-beta mejora considerablemente la eficiencia del algoritmo, ya que permite descartar ramas del árbol de decisiones que no pueden influir en el resultado final, lo que permite alcanzar mayor profundidad de análisis en menos tiempo.
Para optimizar el rendimiento, implementé una estrategia que ajusta el orden en que se evalúan los movimientos, de manera que las jugadas más prometedoras (por ejemplo, aquellas que implican capturas) se evalúan primero. Esta estrategia incrementa considerablemente la eficacia de la poda alpha-beta, ya que aumenta la probabilidad de encontrar cortes tempranos en las ramas del árbol de búsqueda. Además, incorporé una técnica de búsqueda iterativa, que consiste en realizar múltiples pasadas sucesivas de minimax con profundidades crecientes. Aunque esto implica repetir cálculos en cierto grado, ofrece dos ventajas clave:
- Mejora la calidad del orden en que se evalúan los movimientos, lo que a su vez acelera la ejecución del algoritmo.
- Permite establecer un límite de tiempo para la decisión del bot, aprovechando los resultados de búsquedas previas con menor profundidad, y garantizando así una respuesta dentro de un margen de tiempo definido.
Mejoras en la velocidad de ejecución
Cuando terminé de implementar la lógica del bot que utiliza el algoritmo minimax con poda alpha-beta, el rendimiento del juego era funcional, pero inaceptable en términos de tiempo de respuesta. En particular, calcular el primer movimiento de la partida con una profundidad de búsqueda de 3 en un tablero de 8×8 tardaba aproximadamente 20 segundos, lo cual hacía la experiencia contra el bot prácticamente injugable. En posiciones más avanzadas de la partida, donde el número de posibles movimientos aumenta, el tiempo de ejecución de cada turno del bot era aún más elevado.
Al analizar el código, entendí que uno de los principales cuellos de botella estaba en la representación del tablero y las estructuras de datos utilizadas. Originalmente, el tablero se representaba como una lista de listas, donde cada celda contenía una referencia a una instancia de la clase “Piece”. Aunque esta estructura es intuitiva y funciona bien para partidas entre dos jugadores humanos, se vuelve extremadamente ineficiente cuando el bot debe evaluar miles de posibles estados. Las iteraciones constantes sobre estructuras dinámicas y el overhead asociado al uso de clases ralentizan drásticamente el proceso. Dado que varias funciones son llamadas más de un millón de veces durante un solo turno del bot, esta ineficiencia se vuelve acumulativa y crítica. A pesar de haber implementado ya gran parte del código utilizando esta estructura, decidí que no tenía otra opción que rehacer la representación del tablero si quería mejorar el rendimiento de forma significativa. Esto implicó adaptar la mayoría de las funciones implementadas acorde.
Después de investigar diferentes enfoques, opté por una representación binaria del tablero. Este método asigna una variable binaria a cada grupo de piezas: hombres blancos, hombres negros, reyes blancos y reyes negros. Cada bit de la variable corresponde a una casilla del tablero. Si el bit está activado (valor 1), la casilla está ocupada por la correspondiente pieza. En caso contrario (valor 0), la casilla está libre u ocupada por otra pieza. De esta manera, la representación de un tablero de 8×8 únicamente requiere de cuatro variables tipo Int64. Las evaluaciones y modificaciones en el tablero (movimientos, capturas, detectión de piezas, etc.) pueden realizarse mediante operadores lógicos, los cuales son altamente eficientes.
Tras implementar esta representación, logré reducir el tiempo de cálculo del movimiento inicial de la partida (con profundidad 3 en un tablero de 8×8) a aproximadamente 3 segundos, lo que ya supuso una mejora notable respecto a los 20 segundos iniciales. Sin embargo, todavía no estaba satisfecho con el rendimiento. Sabía que era posible optimizar aún más el cálculo.
Experimenté con caching en funciones donde los parámetros de entrada eran simples y repetitivos. Sin embargo, como muchas de las funciones requieren el estado completo del tablero, el cache resultó poco efectivo. Apliqué la memorización solo en funciones con poca variabilidad en los inputs, lo cual mejoró ligeramente la velocidad, pero no de forma significativa. También probé con Numba, una herramienta de compilación JIT para Python, pero me encontré con limitaciones: ciertas funciones esenciales como bit_count() y divmod() no eran compatibles o generaban errores. Dado que estas funciones son altamente optimizadas para operaciones binarias, preferí conservarlas y descartar este enfoque.
Una observación interesante fue que incluso asignaciones simples como “bit_mask = 1 << bit_idx“ realizadas millones de veces tenían un impacto significativo en el tiempo de ejecución. Esto se debe a que Python tiene una velocidad de ejecución muy lenta en comparación con lenguages de más bajo nivel como C o C++. Por ello, reestructuré el código para reducir al mínimo las conversiones entre índices y máscaras de bits. En la medida de lo posible, pasé directamente las máscaras en lugar de los índices de posición. También definí variables que estaban siendo calculadas repetidamente (como el tamaño del tablero) globalmente para reducir el número de cálculos requerido.
A pesar de estos cambios, el impacto sobre el tiempo de ejecución fue limitado. Como resultado, la generación del primer movimiento del bot (con profundidad 3 en un tablero 8×8) bajó a aproximadamente 2 segundos. En fases más avanzadas de la partida, con las piezas más distribuidas y una mayor complejidad combinatoria, el tiempo por movimiento era algo más alto, aunque ya muy lejos de los 20 segundos iniciales.
Llegado a este punto, tuve que asumir que únicamente habían dos maneras de seguir reduciendo significativamente el tiempo de ejecución: Reescribir el código entero en C++ u otro lenguaje de programación más eficiente que Python o reducir el número de evaluaciones por turno. Debido a que ya había modificado el código muchas veces, me decanté por la segunda opción y decidí optimizar la profundidad de la evaluación.
El cálculo del score implementado para el algoritmo minimax se basa en dos parámetros: las capturas realizadas y el número de posibles movimientos por jugador. Para determinar el impacto que cada posible movimiento tiene sobre la mobilidad del jugador, no es necesario llegar a una profundidad de 3. Con evaluar el siguiente turno (profundidad 1) o los dos turnos posteriores (profundidad 2), la estimación de la movilidad adquirida ya es bastante apropiada. Por este motivo definí una profundidad estandar de 2, lo cual reduce drasticamente el número de evaluaciones. Sin embargo, en caso de realizarse una captura, sí que es importante evaluar los movimientos posteriores a esta, ya que eventualmente exista una opción de captura en el turno posterior al evaluado. Por ello añadí una extensión en la profundidad del algoritmo minimax en caso de realizarse alguna captura. En tal caso, los movimientos posteriores se evaluan hasta llegar a uno de los siguientes estados:
- El algoritmo minimax alcanza una profundidad de 4
- Algún jugador gana
- No es posible capturar ninguna pieza en el turno posterior al evaluado
Esta adaptación en el nivel de profundidad logró reducir el tiempo de ejecución en el primer movimiento (tablero de 8×8) a aproximadamente 0,1-0,2 segundos. El nivel de juego del bot no se vió afectado negativamente de forma notoria en comparación con la versión anterior (profundidad estática de 3).
LLegado a este punto, la velocidad de ejecución me resultó satisfactoria y decidí dar el proyecto como finalizado. Por supuesto, aún existen numerosas mejoras posibles — como la implementación de una estrategia de juego más elaborada, o la programación de las funciones más críticas en C/C++ —, pero el salto de rendimiento ya ha hecho que la experiencia contra el bot sea mucho más fluida y decidí que era el momento de enfrentarme a un nuevo reto.