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.

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:

• The sowing ends in your own kalaha: It is your turn to move again.
• The sowing ends in an empty pit on your own side: All stones in the opposite pit (on the opponent's side) along with the last stone of the sowing are placed into your kalaha and your turn is over.
• Otherwise (the sowing ends on the opponent's side or in a nonempty pit on your own side): Your turn is over.

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:

		1	2	3	4	5	6
	1	D	L	W	L	W	D
	2	W	L	L	L	W	W
	3	D	W	W	W	W	L
	4	W	W	W	W	W	D
	5	D	D	W	W	W	W
	6	W	W	W	W	W	W

Play!

Try to beat the perfectly playing computer: Play (requires a modern browser and a good internet connection).

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.