There are some software projects that start with a sensible engineering goal.
This was not one of them.
Back in late July, I started working on a small Nine Men's Morris game for my website. The original idea was fairly straightforward. Make a playable version of the game in Odoo, put it on my website, and eventually add an AI opponent.
The first version of that game was released last month, and at that point I thought the difficult part was probably behind me.
I was wrong.
What started as a small board game turned into a surprisingly deep C++ project involving a pre-calculated database of game states, MinMax search, symmetry reduction, multi-threading, binary file formats, compression, Windows compatibility layers, Linux support, an HTTP API, an Odoo integration, and considerably more code than I ever intended to write for a game about placing nine little pieces on a board.
And, perhaps most importantly, it eventually allowed me to beat the Nine Men's Morris opponents in Assassin's Creed Black Flag Resynced.
So naturally, I consider the project a success.
From a Small Odoo Game to a Proper AI
The first release of Nine Men's Morris on my website was deliberately simple. It provided the board, the rules, and a way to play the game in the browser.
The plan was always to build on that foundation.
The interesting part was that I didn't really want to write a conventional “good enough” board-game AI. Nine Men's Morris is one of those games where the entire game has been solved, meaning that it is possible to determine the outcome of a position with perfect play.
That makes it a particularly nice programming problem.
Rather than teaching a neural network how to play, or writing an evaluation function and hoping it was good enough, I wanted to use the existing solved-game approach behind the Muehle implementation by Thomas Weber.
The Odoo side then became the relatively thin layer on top of that.
Odoo handles the game interface and sends the board position to the external service, while the C++ backend does the considerably more interesting work of figuring out what should happen next.
That separation ended up being useful for another reason: I could keep the website and Odoo code relatively clean while letting the backend be as ridiculous as it needed to be.
The Database Was the Hard Part
The biggest surprise of this project was that the AI itself wasn't really the part that caused me the most trouble.
The database was.
A solved Nine Men's Morris implementation needs to deal with an enormous number of possible positions. Storing and accessing those positions efficiently becomes just as important as calculating them.
The project therefore has a state-addressing system which calculates the various groupings, symmetry mappings, layers and other information needed to map a board position into the pre-calculated data. On startup, those values can be loaded from pre_calculated_vars.dat; if they aren't present, the program calculates them and writes them out for future runs.
This is one of those things that sounds fairly simple until you actually have to make the resulting data portable.
The original software was written around a Windows environment and made use of Windows-specific APIs and assumptions. I wanted the resulting API to run on Linux as a proper web service.
That meant I couldn't simply compile the original code and call it a day.
I had to make the relevant pieces work outside of their original environment.
The Windows Problem
One particularly entertaining part of this was the compression system.
The original implementation uses Microsoft's compression API and the MSZIP compression algorithm. That is perfectly reasonable when your target environment is Windows.
My target environment, however, was Linux.
So instead of abandoning the existing data format, I decided to reproduce the relevant behaviour.
This resulted in a Linux-compatible implementation which uses zlib to reproduce the MSZIP buffer format. The implementation deals with the MSZIP header, chunks, CK signatures, raw DEFLATE streams, little-endian integer encoding, and the 32 KiB dictionary used between chunks.
In other words, I ended up implementing enough of a Windows compression API to make Windows-generated data usable from Linux.
There were also the usual joys of cross-platform data representation.
Windows APIs make extensive use of wide-character strings, and the size and representation of types such as wchar_t aren't something you can casually assume will be identical between platforms. When you're dealing with a binary file format, “it's probably the same” is not a particularly useful compatibility strategy.
A binary file doesn't care about your intentions.
If Windows writes four bytes and Linux expects two, the file is simply broken.
That meant paying considerably more attention to the exact sizes and representations of values being written and read, rather than relying on platform specific assumptions.
This was probably one of the most useful parts of the project from a software engineering perspective. It is very easy to write code that works perfectly on the machine it was written on. Making that code consume the same data correctly on an entirely different operating system is a rather different problem.
Making the API Actually Useful
Once the underlying database and game engine were working, I still needed to make the thing usable as a service.
The backend now has an API bridge which accepts board positions and information about the current player and converts those requests into the underlying game representation. The API can then return information about the state and the moves available to the player.
That means the Odoo module doesn't need to know how the game is solved.
It just needs to ask.
This also gives me a fairly nice architecture:
Browser → Odoo → Nine Men's Morris API → solved game database
The Odoo module remains responsible for the user experience, while the C++ service is responsible for the actual game intelligence.
And because the backend is a standalone project, it isn't tied specifically to Odoo either.
The AI
Underneath all of this is the MinMax implementation.
The AI works through possible moves and evaluates resulting situations, while keeping track of the current state and backing up and restoring states as it searches. The implementation also has its own thread state, allowing the calculation to make use of multiple threads.
The important distinction here is that this isn't intended to be an AI that merely plays reasonably well.
The point of the project is to use the solved game data to play Nine Men's Morris correctly.
That makes the testing rather more satisfying.
A mistake isn't simply “the AI made a bad move”.
If something goes wrong, there's potentially a problem somewhere in the representation of the game, state addressing, database lookup, move generation, or API translation.
Which gives you considerably more places to accidentally spend an evening debugging.
And Then I Had to Test It
Once everything appeared to work, I needed to establish that it actually worked.
The database and AI were tested against themselves, eventually reaching a drawn state as expected.
I also tested it against the TU Graz online Nine Men's Morris player, the original Mad Weasel Muehle implementation that this project was based on, and various other positions and games.
But there was one test that mattered considerably more to me.
The NPC in The Great Inagua
Black Flag Resynced contains a couple Nine Men's Morris minigames around the map, including some opponents that are substantially less forgiving than the average person who has just discovered the rules of the game.
Fifteen Minutes of Being Petty
One of the hardest NPCs in the game gave me a surprisingly difficult match.
For roughly fifteen minutes, it was a genuine back-and-forth.
Neither side was making the kind of obvious mistake that would immediately decide the game, and I was having to actually play carefully rather than simply letting the AI do its thing and watching the opponent collapse.
Eventually, however, I managed to corner it.
The final position reached a particularly satisfying point where I had pieces at J, K and S, while the NPC had pieces at A, E and N.
At that point, the position was effectively toast.
Whatever the NPC did, I had a winning continuation.
The funniest part was that then, after roughly fifteen minutes of the back and forth, the NPC decided to offer a draw.
At exactly the moment where my win was already guaranteed.
Naturally, I declined.
Because what would be the point of spending over a month implementing a mathematically solved Nine Men's Morris engine if I wasn't going to be petty about it?
24,000 Lines Later
Looking back at the project is probably the strangest part.
The original goal was essentially:
“I want a Nine Men's Morris game on my website.”
The API repository alone now contains 23,642 lines of code.
That includes the actual game logic and AI, state-addressing and database handling, the API bridge, utilities and threading code, and the cross-platform compression work required to make the original data usable in a Linux environment.
The Odoo module adds another roughly 2,000 lines.
That's a lot of code for a board game.
It has also taken over a month of my time, starting around the 20-somethingth of July and reaching what I consider release quality today.
There are still some formatting and cleanup jobs I want to do, but functionally, this is where I wanted it to be.
Unless a significant bug appears, I don't expect the next changes to fundamentally alter how the system works.
And that's a pretty satisfying point to reach.
Why Did I Do All This?
There is, of course, a perfectly reasonable technical answer.
I wanted to learn more about C++, work with a solved-game database, understand the original implementation, build something cross-platform, create an API around it, and integrate it into Odoo.
All of those things are true.
But there is also the considerably more honest answer:
I lost too many reals to let myself give up.
And honestly, I think that's one of the great things about programming.
You can encounter some tiny annoyance in your life and think:
“I could just put up with this.”
Or you can think:
“I wonder how much sleep I can miss to make this problem go away?”
The sensible person chooses the first option.
The programmer has already opened their IDE.
In this case, that tiny annoyance resulted in a month-long project, tens of thousands of lines of C++, a Linux implementation of parts of a Windows-specific compression system, a solved Nine Men's Morris database, an HTTP API, an Odoo module, and finally a fifteen-minute victory over a digital opponent in a pirate game.
Was that excessive?
Absolutely.
Was it worth it?
Also absolutely.
A Proper Little Project
This project has ended up being a nice reminder of why I enjoy personal programming projects.
Not every project needs to become a product.
Not everything needs to solve an important business problem.
Sometimes it is enough to find something interesting and follow the rabbit hole.
Nine Men's Morris turned out to be a particularly good rabbit hole because the game itself is deceptively simple. The rules can be explained very quickly, but underneath those rules are combinatorics, symmetry, state-space reduction, database design, search algorithms, compression, binary compatibility and distributed application architecture.
A board with 24 positions ended up being an excellent excuse to explore all of that.
And, as an added bonus, I now have an AI that can beat me at Nine Men's Morris.
More importantly, it can beat the NPC that started this entire mess.
What's Next?
For the moment, I'm calling this project finished.
The Nine Men's Morris Odoo module is available on my website, with the AI provided by the external C++ API.
The source for both projects is available publicly on GitHub:
- Nine Men's Morris for Odoo: github.com/AustinATTS/nine-mens-morris
- Nine Men's Morris API: github.com/AustinATTS/nine-mens-morris-api
And the video of my attempt in Black Flag can be found on YouTube:
There are still some cosmetic improvements I'd like to make, and naturally I'll fix anything genuinely broken if it turns up.
But I'm not currently planning to spend another month reinventing the entire project just because I can, University work will probably end up taking all my time instead.