Well, the game might be solved … but the challenge is not
This post is part of ChurrPurr.ai, a challenge to design an online strategy game and the AI to master it. Play the latest version of the game here.
Yesterday I wrote my first Medium post, about the strategy game “Churr-Purr” I recently learned, and about my new challenge to program a version of it online, with an AI that can also master the game.
In the post, I wrote about the fun-ness and intrigue posed by this challenge, as Churr-Purr doesn’t seem to exist online, and accordingly there are no pieces of commentary or strategy floating around.
Well … It turns out I was wrong. Sort of.
Shortly after announcing my project, a friend on Facebook commented, “I think it’s a relative of Nine Men’s Morris! https://en.wikipedia.org/wiki/Nine_Men%27s_Morris”
And sure enough, he was right.
It seems that Nine Men’s Morris is a common Western name for a game floating around since at least the Roman Empire.
I also learned from Wikipedia that Nine Men’s Morris is a solved game — one in which players have a forcing sequence for a particular outcome, even assuming perfect-play by the opponent. (Tic-Tac-Toe is a solved game, in which player two can always earn a draw by playing perfectly. Connect Four is also a solved game, in which player one can always force a win by playing perfectly.)
Now, I’m not exactly sure that Churr-Purr is actually solved: As my friend pointed out, there’s a variation in endgame rules for NMM vs. Churr-Purr, and it could make a large difference (in NMM, once a player reaches 3 tokens, a third ‘flying’ stage begins at which players can move their tokens to vacant non-adjacent spots; in Churr-Purr, the spot must always be adjacent).
I did a *very quick* skim of the academic article solving Nine Men’s Morris, and I did seem to confirm they’re discussing a three-stage version. But I’ve decided I don’t want to know any further, as I want to follow the ‘nothing about the game is written online’ aspect of my challenge.
That said, a few folks asked me if I was upset when I learned that Churr-Purr might be solved — and the truth is, I’m not. In fact, I think there are several silver linings of this possible revelation:
- My intuition was pretty good. In a forthcoming post about Churr-Purr’s complexity and how to crack it, I wrote “I suspect that finding out the elements of a solved position in Churr-Purr will be a major insight that powers my AI to success.” I was also in the midst of explaining which positions are solved to another friend when the possible news broke. So, not bad.
- If the game is solved, we have a good benchmark for my AI. Theoretically this AI should never lose, per NMM being solved to a draw. Of course, it’s possible that the Churr-Purr variant is solved for player one forcing a win, given the end-game conditions, in which case this is wrong. Which feeds into …
- Knowing the game might be solved doesn’t affect my creative process or the way by which I design my AI. I don’t have enough certainty that the game is solved, and I certainly don’t have a running AI that has already solved it. I’m still doing this on my own.
- Even if the game is solved, the current bots could use some improvement. I haven’t played NMM online because I don’t want to seed my mind with how a computer plays — but a friend who did reported that he beat a NMM-playing bot. Come on, developers — you can do better than that.
- There could be a vibrant community for Churr-Purr players. One aspect of this challenge that bothered me was that maybe nobody would ever play Churr-Purr except for me, the AI, and the occasional friend I rope into playing me. If folks already play NMM online, and if Churr-Purr turns out not to be solved to a draw, perhaps we can draw folks to this game instead.
Much of life is about perspective, and I’m choosing to take this as an interesting quirk that might even enhance the project. Who knows where the future of Churr-Purr will take us.
Onward and upward.
Read the previous post. Read the next post.
