Kalah

This material excerpted from "Etudes for Programmers", Charles Wetherell, Prentice Hall, 1978.

Kalah, also known as Mancala, Wari, or Owari, originated in Africa. The Kalah board appears below in its initial configuration. The two players, referred to here as Max and Min, sit at opposing edges of the board. Each player owns the six small pits before them (numbered 1..6 in the diagram) and the larger pit on their right (their Kalah). To start the game, each small pit is filled with some number k of stones, with k=6 a typical value.

Initial Configuration of Kalah Board

Players alternate turns. Play begins with one player removing all stones from one of the player's small pits, and sowing them into other pits in counterclockwise fashion around the board. Sowing begins in the pit to the right of the source pit and includes the player's own Kalah and the opponent's small pits, but not the opponent's Kalah.

It can be advantageous for sowing to continue around the board, back to the player's side. This is referred to as a Looping Move.

In this configuration, it is Max's turn to move. Max will choose to move from Pit 6, performing a Looping Move.

Max has completed the Looping Move. Max's Kalah has been sown twice; Min's Kalah has not been sown.

There are two variations on the basic move. If the last stone falls into one of the moving player's own small nonempty pits and stones were played on the opponent's side during the sowing, the stones in the final pit are used to start a Go-Again Move, just like the original move. A player can have an arbitrarily long chain of go-agains.

In this configuration, it is Max's turn to move. Max will choose to move from Pit 6, performing a Looping Move, with the last stone sown in Max's Pit 3.

Max has completed the Looping Move. Max is permitted to perform a Go-Again move, because a Looping Move caused the last stone to be sown in one of Max's non-empty pits.

Max has completed the Go-Ahead Move. The four stones from Pit 3 have been sown in Pits 4-6 and Max's Kalah.

If the final stone sown falls in one of the opponent's small pits and there are either two or three stones in the pit, the stones are captured, and placed in the moving player's Kalah. Whenever one pit is captured, the preceding pit may be captured if it contains two or three stones as well. Theoretically, a player could completely clear out an opponent's side in one move.

In this configuration, it is Max's turn to move. Max will choose to move from Pit 3. By sowing the last stone in Min's Pit 4, Max will capture the pit, since it will have 3 stones in it.

Max has captured Min's Pit 4. Max's Kalah increased by 4 stones - one from sowing and three from the capture.

The game is over as soon as more than half the stones are in one player's Kalah (notice that once a stone enters a Kalah, it can never leave). If a player who has the move has no stones available, the game ends immediately with all the opponent's stones going into the opponent's Kalah.