Programming is magic, or how I wrote a Kalaha solver

I spent an evening doing recreational programming, and the results exploded my brain like this:

I’ve been programming for years, and I guess, at some point, the process becomes somewhat ordinary. But yesterday evening I wanted to program a small solver for a simple board game to see if there is more to it, and boy, did it surprise me! Programming really is magic sometimes…

The board game

Some time ago, when I was picking up my kid from school, I noticed that she was playing a board game that looked familiar. I then remembered that back when I lived in Russia, I had this game at home — it was called Mancala. Here in Sweden, it goes under the name Kalaha and uses slightly different rules.

Note: to be precise, Mancala is a family of games that is thousands of years old. Kalaha is a relatively modern game from the Mancala family. The variant that we’ve been playing is a “Seed on Kalah” as described on the wiki page. I’m not going to focus on the rules since the post is about the magic of programming, but I’d like to share this image of the game board if you are not familiar:

Kalaha is played by moving marbles between pits. The tactile experience is very satisfying, and the game is easy to play!

The question

We’ve bought the game and have been playing it at home for a while.

Here is how I would describe the typical playing experience: each player’s turn last from 10 seconds to a minute, where the player moves several marbles and then either gets a small dopamine hit by scoring a point and getting to make another move, or gets… uhh.. the opposite of dopamine hit where the player’s marble ends up in an empty pit, and then the turn switches to another player. At the end of the game, the difference in score between players is not too big. Typically, out of the total 48 points, the winner finishes with 1-8 extra points.

There is a somewhat simple strategy you can figure out while playing the game that prioritises some moves over others. Then I started wondering, is there more to the game? What should be the strategy for playing the game? The game doesn’t seem to have too much emergent complexity in it like chess or go, but is that it?

Searching for an answer

I could try asking ChatGPT or Perplexity to see if there are other, better strategies to play Kalaha, but for some reason, I decided to try to find it myself. First, there are many variations of the game, so it could be hard to find the info about the right ruleset. Second, I thought it would be fun to try to code the game myself.

As usual, using Clojure for a small experiment is a joy. I can build the thing step by step in the REPL, where I always see the results and my progress so far immediately. The game state is a small hash map with some numbers in it. After some head scratching, I’ve got a function that performs a move given a player’s choice of a pit. That felt nice! I’m not going to discuss the code, but if you are curious about it, the whole implementation is here — just 75 lines of code!

As is usual with Clojure, the code that performs the work is a pure function that takes immutable data and returns immutable data. This made it easy to take a particular board state and start exploring the moves that I can make. At this point, I didn’t know what I was going to discover, so I just wanted to see what’s possible. Can I enumerate all possible moves? When it’s your turn, you can pick 1 of 6 pits to make a move. But then, depending on the board configuration, you might get lucky and get to make another move. So I tried enumerating all possible first moves. 26278 possibilities?.. Huh, interesting… To be honest, I expected less for a first move, let’s see what’s in there…

The discovery

Then I’ve got my list of possible moves, I thought: what’s the highest scoring first move? So I sorted the results and then… what? 43 points of a total possible 48? What?! And I get to make a move 26 times per turn, when typically it’s 1 to 3? Impossible! Unbelievable! Must be a mistake! I need to check it myself on the real board! What???

I reached out for the board game and tried to reproduce the move by hand. The code I wrote reported which pits I need to pick during the turn to make a move, so I started carefully reproducing the weird move. It turned out to be the most surreal experience playing the game. My turn lasted around 10 minutes. I was trying to understand the logic behind selecting the pits, but could not. It would ignore moves that I would consider obvious. And somehow it kept hitting the score and continued getting more moves until the board was almost empty. Wow! The code was correct; it’s possible to completely destroy your opponent on the first turn. By the end of it, I was shaken — there is no way I could have found it by playing the game. Perhaps I could intuitively discover some prefix of this turn by experimenting, but not this…

And what’s amazing is that all I did was just simple programming! There was no complex engineering, no advanced algorithms, just a small data structure, a simple algorithm, and some collection processing. And somehow it produced a result that surprised me and completely caught me off-guard. Wow! This is magical!