Kalaha with the Minimax Decision Rule

Kalah, also called Kalaha or Mancala, is a game in the mancala family invented in the United States by William Julius Champion, Jr in 1940. The game favors the starting player, who will always win the three-seed to six-seed versions with perfect play.

The computer simulates several moves in advance and minimizes its loss. The strategy is the Minimax decision rule. More details on the strategy and game analysis here.

This perfect play implementation by Anders Carstensen uses a database of opening moves.

Our implementation is a mere programming exercise. We compute the Minimax solution until a certain depth, but do not access a database of opening moves. As an advantage, the implementation covers popular variations of the game and different initial conditions.

In order to play against the computer, our software features a simple graphical user interface:

Once is an accident.
Twice is coincidence.
Three times is an enemy action.
Ian Fleming
Kalaha with the Minimax Decision Rule (Java 8) Kalaha.zip 27 kB

The user can choose between the variants: Standard, Empty Capture variant, Clockwise, and No Remaining count. The number of initial seeds is configurable.

Als Junge bemerkte ich eines Tages einen Wagen mit Melonen.
Da ich niemand in der Nähe sah, trat die Versuchung an mich heran.
Ich stahl eine Melone und lief weg.
Kaum hatte ich aber hineingebissen, so ergriff mich unwiderstehliche Reue.
Ich rannte zurueck, legte die Frucht auf ihren Platz - und nahme eine reifere!
nach Mark Twain