How to win Kongming solitaire in 3 attempts feat. software developer
I had an interesting hobby programming adventure recently. My girlfriends parents introduced me to a rudimentary puzzle game. They called it “Kongming”, inspired by a Chinese military strategist. Apparently it is also known as “Peg”. The game was very simple, you’d move marbles over each other in four directions, removing any marbles you hopped over as you go, with the goal being to end up with only one marble left on the board.
I’m pretty bad at this kind of games, and sure enough my first attempt ended with a result not worth mentioning. On my second attempt, I gave it my all to patiently think several moves in advance. I ended up playing for more than 50 minutes until eventually conceding as all my simulations lead to losses (for reference, the average game normally takes around 5 minutes max).
As a software developer, what followed was obvious — I would spend the next couple days writing a program that would tell me if there really wasn’t a way to win the situation I ended up in my second attempt, or alternatively tell me how to win the game.
Now this wasn’t the first time I’d dabbled with computer programs simulating real life games. That, however, doesn’t mean that my methods are sophisticated. Regardless, I thought that my creative novel methods in this project were potentially inspiring and more importantly fun, which is why I’m writing this.
I initially implemented methods for exhausting all possible marble movements from a given state on the board, as well as all the possible moves you could make after each move. This is a so-called brute force method, that quickly gets extremely heavy as the complexity of the game is increased.
The game in question is relatively very simple, for example when compared to chess, that has a multitude of different unit types, movements and can require even up to 100 movements for a game to end. Due to its rules, the Kongming solitaire takes at most 31 moves to finish.
The first thing to establish was a coordinate system for mutual understanding of the game board between me and the program. A simple 2D coordinate system like below did the trick:
The logic of finding every possible move from a given state is relatively simple — for every marble, check if there’s a marble on its left and a spot behind that, rinse and repeat for the three other sides.
This quickly got very fun, I proceeded to write an algorithm that takes a starting state (marble placement on the board), and seemingly infinitely finds all possible movements and drills into them in the same way. The goal was clear — find a series of marble movements that results in just one marble remaining at the end. Furthermore, the algorithm was really quite fast. Initially it was able to simulate roughly 800 000 marble movements every second (while still being quite merciful on my laptop CPU). This is where Kongming first surprised me with its complexity — the process ran on and on, up to several hours, at best going as far as thousands of millions simulated movements (>5 000 000 000), yet not a single victory was uncovered! Did I give up this project that was dumb from minute 0? No! I don’t have anything better to do during my winter vacation anyway!
Another important simplifying factor in the rules of Kongming is that every move reduces the number of marbles left. This means that there is no fear of infinite simulations (for example, in chess the program could move a soldier back and forth for 1000s of turns straight, no issue). So, what was the issue? Why even billion marble movements was not enough to find even a single winning scenario? The answer turned out to be the obvious — the game really was that complicated, or maybe better to say that the brute force method really is that bad.
The next idea that came to me was to get rid of extra simulations by skipping simulations of board states that had already been simulated. In Kongming, it is rather easy to end up in fundamentally or exactly identical situations even when moving marbles in different order. When it comes to the brute force method, skipping early movements that would lead into several branches of simulations can be extremely powerful!
To do this, I implemented a 2D transformation matrix logic for the simulated Kongmin boards, capable of arbitrarily rotating and flipping a set of marbles. With this, I could even skip mirrors and rotations of previously simulated board states.
While I was momentarily happy with my code working beautifully, it turns out that there is an incredibly large number of different arrangements of marbles on the Kongming board and that running CPU driven transformations on them is really heavy… and slow. So, I had “upgraded” my blazing fast simulator into a snail that skipped a good 80% of simulations (nice!!), but was still a snail and performed worse than the starting point.
This was a good example of the dreaded premature optimization, where you think that you have a bright idea that fixes your issues but ends up performing worse. However, it did give me some resources for the next iteration — I noticed that a large majority (>95%) of the skips were done for exactly identical states, rather than some mirror or rotation of a previous state. Exact identical state comparisons were a lot faster than the transforms, so this was good intel — if I compromised by just leaving the transformations out, maybe it would work great?
It didn’t work great. Turns out that comparing a list of marbles (2–32) to a reaaally long list of lists of marbles (up to millions of unique stored states) is, once again, really slow. The brute force method lives to its name. Then, I had a bright idea — in my program, the state of the board was described like this:
This means that the board state is described as a list of present marbles, where each marble is described as a X and Y coordinate. As previously established, the board has a limited set of slots — the X and Y coordinates can vary between 0 and 6. My bright idea was to wrap this same information into a binary sequence, as in a list of 0's and 1’s. 1 means that there is a marble, and 0 means that there is no marble.
The cool thing here is that computers understand everything in binary. If you ask a computer what is the binary sequence that contains information of all 49 slots of the Kongming board, it’ll be just a single number. I won’t delve into the basics of binary system in here, but this approach allows describing any unique state of the game board as a single number.
This has two amazing effects on the Kongming program; first, checking if two states are exactly identical is as simple as checking if A is equal to B. Before, this was a somewhat heavy algorithm (not really “heavy”, still took less than 0.1 milliseconds, but if you repeat it a billion times then that takes quite a long time).
Secondly, it allows us to use a really powerful method for finding a previously encountered identical board state — binary search. Let’s check some background information first; as mentioned before, the 2nd version of the program was severely bottle-necked by how long it takes to check if the program had already simulated a particular board state. Doing this, however, is very important due to the exponentially increasing complexity of brute force simulations. Again, the reason why this was so slow was 1) there was as many as millions of previous states to compare, 2) comparing two states was somewhat slow.
Binary search to the rescue! Binary search is a creative operation that can be used on sorted lists to very efficiently find the location of a value in a long list, or if it doesn’t exist, the location where that value should be for the list to remain sorted (see illustration how it works). Long story short; each board state is a number, previously simulated board states are saved in a long, sorted list of numbers, and binary search allows very fast lookup if a given board state is already simulated as well as keeping the list sorted.
So what happened? All this essentially combined the best things in the initial approach (lots of simulations really fast) and the second one (skipping duplicate simulations). Did it work?
Yes, it worked. After running the program for roughly 5 minutes, the console filled with never before seen messages informing that a winning scenario had been found. And I was ecstatic.
Only a little bit later, the console started bursting out with new win scenarios — the program had finally blindly wandered into the first move sequences that would win the game.
At this point, I run across the house to get the game board in order to test if the program actually worked. I had made the program so that it tracks the moves leading to a win and saves the sequence to a JSON file that I could manually replicate on the board.
This definitely wasn’t a great user experience — it took closer to 10 minutes to carefully decipher the 31 moves from the computer screen to the physical board. But damn, it worked on first attempt!
Thus concludes the story of how I beat Kongming solitaire in three attempts — first attempt 10 minutes, second 1 hour and finally the win took about 4 days.
Code can be found in my GitHub.
