Solving (6,6)-Kalaha

Kalaha is an abstract strategy game invented in 1940 by William Julius Champion, Jr. The notation (m,n)-Kalaha refers to Kalaha with m pits per side and n stones in each pit. In 2000, Kalaha was solved for all m ≤ 6 and n ≤ 6, except (6,6).

Now, 11 years later, we have solved (6,6)-Kalaha. Supplementary results are on the way.

Rules

Kalaha is played by two people on a board with 6 pits on each side and two stores, called kalahas. We refer to the two players as North and South.

In each pit, there are initially 6 stones. A move is made by taking all stones from a pit on your own side and sowing them one-by-one in counterclockwise direction. Your own kalaha is included in the sowing, but the opponent's kalaha is skipped.

There are three possible outcomes of a turn:

If all pits on your side become empty, the opponent captures all of the remaining stones in his pits. These are placed in the opponent's kalaha and the game is over.

You win the game when you have 37 or more stones in your kalaha. If both players end up with 36 stones, the game is tied.

Variations

  1. If all pits on your side become empty, you capture all of the remaining stones in your opponent's pits.
  2. If your sowing ends in an empty pit on your own side, but the opposite pit has no stones, then you are not allowed to capture the last stone of the sowing.

Results

We have proven that the first player always wins Kalaha with standard rules, variation 1, variation 2, and both variations 1 and 2. This means that we can fill out the last square in the diagram from Geoffrey Irving, Jeroen Donkers, and Jos Uiterwijk's article Solving Kalah from 2000:

123456
1DLWLWD
2WLLLWW
3DWWWWL
4WWWWWD
5DDWWWW
6WWWWWW

Play!

Try to beat the perfectly playing computer: Play (requires a modern browser with Java 1.5 or later).

About the project

This project is part of Anders Carstensen's master's thesis at the University of Southern Denmark, supervised by Kim Skak Larsen. You can contact us at kalaha@krnullus.dk.

This announcement was first published April 14, 2011.