Malom:
Ultra-Strong and Extended Solutions for Nine Men’s Morris, Morabaraba, and Lasker Morris

Gábor Danner, Gábor E. Gévay
gabor dot dan
cucc
ner at gmail dot com, gg
cucc
ab90 at gmail dot com

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 solutionThe Morabaraba variant with the ultra-strong solutionThe Lasker variant with the ultra-strong solution
The standard variant with the ultra-strong solutionThe Morabaraba variant with the strong solutionThe 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.

Solving games is possible on several levels:

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).

Computed databases

We computed extended and ultra-strong solutions for all three variants. The databases are available as torrents, because they are very large. We have provided torrents only for the ultra-strong solutions, but you can ask in email for the extended ones. Malom has an option to play only strongly from the ultra-strong databases. (And also includes a non-perfect (heuristic) alpha-beta AI for the standard variant.)

The program which can use the databases for playing the game is included with the databases (program version 1.1.0). .NET Framework 4.5 is required for running the program. The name of the executable file is _Malom.exe (the underscore is to make it appear at the beginning of the file list, when sorted by name). The program uses about 1 GB of memory. Malom works only on 64-bit Windows. For more details, see Readme.txt.

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

The program for playing with the databases is included in the torrents, but we also provide it here separately: Malom_binaries_1.1.0.zip.
You should download this zip in two cases:

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

The source code (malom_source_1.1.0.zip) is available under the GPLv3. It is a Visual Studio 2013 solution with five projects (VS Express editions might not work): For further details, see Readme.txt. Running the computations requires even more RAM: at least 4 GB for the strong solutions, and 8 GB for ultra-strong. (We used a 16 GB and a 20 GB machine, which makes the computations run faster, because more instances of the solver can be run in parallel.) Additionally, computing the databases requires a computer that has the POPCNT instruction. (These include all Intel CPUs since the first Core i5 and i7, and AMD CPUs since the Barcelona microarchitecture.)

.secval files

If you want to use the sources to compute just the ultra-strong solutions without the strong solutions, then you need the values of the subspaces (which were computed from statistics of the strong solutions): secval.7z