Nine Men’s Morris (Mills, Mühle), and its variants, Morabaraba, and Lasker Morris are popular board games. (You can read the rules here, or in our paper.) Here we provide resources (databases, executables, sources, and theoretic background) about solving these games. You can play with the computed databases, or even recompute them, with our program, Malom. For more details on the algorithm, see our paper, which appeared in IEEE Transactions on Computational Intelligence and AI in Games. (You can cite it like this.)

The standard variant with the ultra-strong solution	The Morabaraba variant with the strong solution	The Lasker variant with the strong solution

Solving games

We can define the game-theoretic value of a game state (position) as what will be the outcome (draw or who wins) of the game played from this position, if both players play optimally. A depth-to-win value can also be defined for non-draw game states: this gives the number of moves that will happen until the end of the game if both players play optimally, not just regarding the game-theoretic values, but also in minimizing or maximizing the number of moves to the end, based on whether they are winning or losing. Depth-to-win values are often calculated together with game-theoretic values.

• Ultra-weakly solved: the game-theoretic value of the starting position was obtained by a possibly non-constructive proof, which does not give us any actual strategy to achieve the proven value.
• Weakly solved: the game-theoretic value of the starting position is known, and we also have a strategy to achieve that. (This might require a database with the game-theoretic values for a large subset of the game states.) Checkers, for example, was solved in this sense in 2007.
• Strongly solved: a strategy is known that achieves the game-theoretic value starting from any game state that can be reached from the starting position. This has the effect that it can play perfectly even if mistakes were made on one or both sides.
• Ultra-strongly solved: a strategy is known which increases our chances to achieve more than the game-theoretic value when faced with a fallible opponent (i.e. a player who is not playing perfectly).
• Extended strong solution: We define this as a strong solution for an extended state space, namely, for all the positions reachable from a set of alternative starting positions. This can provide further insight into the game. In our research, we examined the positions that can be obtained from the usual starting position by modifying the number of pieces to be placed by the players.

The standard method for strongly solving games is to calculate a database containing the game-theoretic values of all the game states. A game-playing program can use this database at every move by looking ahead one move, and maximizing the game-theoretic value of the state (from its perspective) after its move. This way the program never makes a mistake: it will always reach the best possible result from any game state.

Ralph Gasser calculated a strong solution for the moving phase of the standard Nine Men’s Morris, and established the game-theoretic value of the game to be a draw. Peter Stahlhacke calculated a strong solution for the Lasker variant.

We calculated the strong solution of Morabaraba (which was previously unsolved). The game-theoretic value of the starting position is win in 49 moves. This means that our program will always win in at most 49 moves when playing white (the first player). On the other hand, you have a chance to win, when the program plays black.

Strong solutions have an important property. Lots of the positions among the theoretical draw positions are weak for one of the players for practical purposes (if he is not a perfect player), meaning that the player is just one small mistake away from getting into a theoretical losing position. In these cases the opponent is usually in an easier situation, because his small mistakes do not affect the game-theoretical value of the position. The program based only on the strong solution completely disregards this phenomenon, and tends to get to these weak positions. In the case of standard Nine Men’s Morris and Lasker Morris, this results in lots of draws, even against novice players. To solve this problem we developed a variant of retrograde analysis to classify the draws and used it to calculate ultra-strong solutions for all three variants.

For a more detailed discussion, see our paper (appeared in IEEE Transactions on Computational Intelligence and AI in Games).

• Standard Ultra-strong Database (12 GB compressed, 78 GB uncompressed)
• Morabaraba (FBD) Ultra-strong Database (41 GB compressed, 324 GB uncompressed) (FBD means that a Full Board results in a Draw)
• Lasker Morris Ultra-strong Database (59 GB compressed, 389 GB uncompressed)

You can download the databases using a BitTorrent client, for example qBittorrent. This is different from a traditional download in that you download the data not from a central server, but from anyone who has the same torrent (and is running a torrent client). (Please do not use iLivid, because it doesn’t seem to work.) We used 7-zip for compression.

If the download isn’t working, then please drop us an email. Since 2018. May 8, we are using a seedbox service for seeding, so it should be working. We happily accept donations to cover our expenses.

Downloading the game program without the databases

• If you would like to try out the GUI without downloading the databases, since this file is much smaller (2746 KB) than the databases. Without the databases, you can play against a heuristic (alpha-beta) AI for the standard variant (which plays much weaker than when using the databases).
• If you have an old version of the program, and you would like to avoid downloading the entire databases again. You can see your version in the Help/About menu. The main differences between the old and new versions are some bugfixes and the free position setup mode: You can set up an arbitrary position directly (without playing to it from the starting position). This is useful if you would like to analyze a specific position. If you would like to play with the databases using the binaries downloaded from here, then you should copy the _Malom.exe and Wrappers.dll files into the directory of the databases (overwriting their old versions).

The current version was uploaded on 2018. March 29, whose main new feature is the free position setup mode. For more details, see the Release Notes.

Source

• Malom_megoldas (C++): the solver program that produces solution (.sec2 files) for a single work unit (one or two subspaces), provided that the subspaces on which the current work unit directly depends on are available. It also does (based on command line options) the verification of single subspaces, and can calculate various statistics.
• Controller (C#): starts the solver for different subspaces automatically, taking the dependencies between them into account.
• Malom3 (VB.Net): the GUI which you can play a game with, using the databases. (And it also contains a heuristic (alpha-beta) AI.)
• Wrappers (C++/CLI): Produces a dll which is used by the Controller and the GUI to access the databases, and to keep track of the dependencies between them (termed sector_graph in the code).
• Analyzer (C++): Aggregates data from the .analyze files produced by the solver for individual subspaces. (This part is a mess, because we were adding features quite randomly. If you would like to extract some statistics that we didn’t compute, then you should probably drop us an email.) It also calculates the values of subspaces (.secval file) from the strong solution’s statistics, which is required for the ultra-strong solution.

.secval files