Intoduction
In this project, I developed a digital version of the ancient Roman game Latrones, implemented as a web application using the Flask framework. The game logic was programmed in Python, while the graphical interface was built with HTML, CSS, and JavaScript. The application allows matches between two human players or against an automated opponent, whose behavior is based on a minimax algorithm with alpha-beta pruning.
The source code is available in the following repository: https://github.com/rj-engineeringde/latrones.git
The following video shows a working demonstration:
Why Latrones?
I have always felt a special fascination for deterministic logic games like chess, checkers, or shōgi. However, when it came to embarking on a new programming project, I didn’t want to simply replicate one of these popular games. There are countless tutorials online that explain in detail how to program a checkers or chess game, which takes away much of the challenge. With so many existing implementations that can be easily copied, the temptation to “draw inspiration” from these sources is simply too high. At the same time, reinventing the wheel by completely ignoring existing tutorials would be limiting and frankly absurd. I wanted to face a real challenge, one that would force me to design the game logic from scratch. This search led me to discover Latrones (or Ludus Latrunculorum), an ancient Roman game whose rules have been lost over time and whose scarce modern documentation makes it a perfect candidate. The game’s pieces and boards have been uncovered in various archaeological excavations. However, to this day, the rules remain a mystery, and only conjectures exist regarding how it was played.
Implementation
The game was implemented as a web application using the Flask framework. The game logic was developed in Python, while the graphical user interface was built with HTML, CSS, and JavaScript. The interface allows the user to interact with the board and displays an individual countdown timer for each player. Additionally, I incorporated a restart menu that allows configuration of various parameters, such as the time per player, the board size, the main player’s color, and whether the opponent will be another player or a bot.
This implementation of the game is based on the conjectured rules proposed by historian W. J. Kowalski:
Starting Position
Latrones is played on a rectangular board made up of square spaces, visually similar to a chessboard. However, unlike chess, the board size is not standardized, as it varies according to archaeological findings on which the game’s reconstruction is based. The game features two types of pieces: the men and the king. In the initial position of the game, the first and last rows of the board are completely occupied by men of the respective color. In the second and second-to-last rows, a single king is placed, positioned at the center of the row. If the number of columns is even, the king is placed in the central right column (from the perspective of the respective player). A player wins by capturing all the opponent’s men or immobilizing the king. The game ends immediately when one of these conditions is met.
Moves
All pieces (men and king) can move in a straight vertical or horizontal line until they encounter another piece (either their own or an opponent’s) that blocks their path. The movement is similar to that of the rook in chess. However, the king has an additional ability: it can jump over other pieces. This jump is only allowed if all the squares being jumped over are occupied, and the jump ends with the capture of at least one enemy piece (man or king).
Linear capture
A man is captured when it is surrounded on two opposite sides (either horizontally or vertically) by enemy pieces. It is also possible to capture entire groups of men if the group is linearly surrounded at both ends. A man cannot be captured if it voluntarily moves into a capture position. Capture only occurs if it is caused by the opponent’s move. If a man or king moves into a position where it is linearly trapped by enemy pieces, any linear captures on that move are disregarded.
King capture
The king is not captured using the previous method. To capture the king, it must be immobilized from all four directions (up, down, left, and right), with no possibility of moving.
Capture by edge encirclement
Any group of pieces (including the king) can be captured if it becomes completely enclosed against a wall or corner of the board and surrounded by enemy pieces, with no free space to move.
Regarding the game’s functionality, I programmed all the essential rules: the board representation, valid moves, captures, turn switching between players, and winner detection. For matches against the machine, I developed an automated opponent that makes decisions using the minimax algorithm with alpha-beta pruning. This algorithm recursively explores possible future moves with the goal of maximizing favorable plays for the bot and minimizing the opponent’s advantages. Alpha-beta pruning significantly improves the algorithm’s efficiency by allowing it to discard branches of the decision tree that cannot affect the final outcome, enabling deeper analysis in less time.
To optimize performance, I implemented a strategy that adjusts the order in which moves are evaluated, so that the most promising plays (for example, those involving captures) are assessed first. This strategy significantly increases the effectiveness of alpha-beta pruning by increasing the likelihood of early cutoffs in the branches of the search tree. Additionally, I incorporated an iterative deepening technique, which involves performing multiple successive passes of minimax with increasing depths. Although this entails some repeated calculations, it offers two key advantages:
- It improves the quality of the move ordering, which in turn speeds up the execution of the algorithm.
- It allows setting a time limit for the bot’s decision-making, leveraging the results of previous shallower searches and thus ensuring a response within a defined time frame.
Performance Optimizations
When I finished implementing the bot logic using the minimax algorithm with alpha-beta pruning, the game’s performance was functional but unacceptable in terms of response time. In particular, calculating the first move of the game with a search depth of 3 on an 8×8 board took approximately 20 seconds, making the experience of playing against the bot practically unplayable. In more advanced positions, where the number of possible moves increases, the bot’s turn execution time was even longer.
After analyzing the code, I realized that one of the main bottlenecks was in the board representation and the data structures used. Originally, the board was represented as a list of lists, where each cell contained a reference to an instance of the “Piece” class. Although this structure is intuitive and works well for games between two human players, it becomes extremely inefficient when the bot has to evaluate thousands of possible states. Constant iterations over dynamic structures and the overhead associated with using classes drastically slow down the process. Since several functions are called more than a million times during a single bot turn, this inefficiency becomes cumulative and critical. Despite having already implemented most of the code using this structure, I decided that I had no choice but to redo the board representation if I wanted to significantly improve performance. This required adapting most of the implemented functions accordingly.
After researching different approaches, I opted for a binary representation of the board. This method assigns a binary variable to each group of pieces: white men, black men, white kings, and black kings. Each bit in the variable corresponds to a square on the board. If the bit is set (value 1), the square is occupied by the corresponding piece. Otherwise (value 0), the square is either empty or occupied by a different piece. In this way, representing an 8×8 board requires only four Int64 variables. Evaluations and modifications on the board (moves, captures, piece detection, etc.) can be performed using logical operators, which are highly efficient.
After implementing this representation, I managed to reduce the calculation time for the initial move of the game (with depth 3 on an 8×8 board) to approximately 3 seconds, which was a significant improvement compared to the initial 20 seconds. However, I was still not satisfied with the performance. I knew it was possible to optimize the calculation even further.
I experimented with caching in functions where the input parameters were simple and repetitive. However, since many functions require the full board state, caching proved to be ineffective. I applied memoization only to functions with low variability in inputs, which slightly improved speed but not significantly. I also tried using Numba, a JIT compilation tool for Python, but encountered limitations: essential functions like bit_count() and divmod() were either unsupported or caused errors. Since these functions are highly optimized for binary operations, I preferred to keep them and discard this approach.
An interesting observation was that even simple operations like “bit_mask = 1 << bit_idx”, performed millions of times, had a significant impact on execution time. This is because Python runs much slower compared to lower-level languages like C or C++. Therefore, I restructured the code to minimize conversions between indices and bit masks. Whenever possible, I passed masks directly instead of position indices. I also defined variables that were being repeatedly calculated (such as the board size) as global variables to reduce the number of required calculations.
Despite these changes, the impact on execution time was limited. As a result, generating the bot’s first move (with depth 3 on an 8×8 board) dropped to approximately 2 seconds. In later stages of the game, with pieces more spread out and greater combinatorial complexity, the time per move was somewhat higher, though still far from the initial 20 seconds.
At this point, I had to accept that there were only two ways to further significantly reduce the execution time: rewriting the entire code in C++ or another programming language more efficient than Python, or reducing the number of evaluations per turn. Since I had already modified the code numerous times, I chose the second option and decided to optimize the evaluation depth.
The score calculation implemented for the minimax algorithm is based on two parameters: captures made and the number of possible moves per player. To determine the impact each possible move has on a player’s mobility, it is not necessary to reach a depth of 3. Evaluating just the next turn (depth 1) or the following two turns (depth 2) provides a fairly accurate estimate of the mobility gained. For this reason, I defined a standard depth of 2, which drastically reduces the number of evaluations. However, if a capture occurs, it becomes important to evaluate subsequent moves because there may be a capture opportunity in the turn following the one being evaluated. Therefore, I added a depth extension in the minimax algorithm when a capture takes place. In such cases, subsequent moves are evaluated until one of the following states is reached:
- The minimax algorithm reaches a depth of 4
- A player wins
- No pieces can be captured in the turn following the one being evaluated
This adaptive depth adjustment managed to reduce the execution time for the first move (on an 8×8 board) to approximately 0.1–0.2 seconds. The bot’s playing strength was not noticeably negatively affected compared to the previous version (static depth of 3).
At this point, the execution speed was satisfactory, and I decided to consider the project complete. Of course, there are still many possible improvements — such as implementing a more sophisticated game strategy or programming the most critical functions in C/C++ — but the performance boost has already made playing against the bot much smoother, and I felt it was time to focus on a new challenge.