Video game implementation
Kalah was implemented on the PDP-1 in the early 1960s,[3] and was able to out-play experienced human players.[4] Since then, there have been myriad Kalah implementations for various operating systems and platforms, including DOS,[5] and the Nokia 3310.[6]
Board game in the mancala family
Kalah is a modern variation in the ancient Mancala family of games. The Kalah board was first patented and sold in the United States by William Julius Champion, Jr. in the 1950s.[1][2] This game is sometimes also called "Kalahari", possibly by false etymology from the Kalahari Desert in Namibia.[citation needed]
For most of its variations, Kalah is a solved game with a first-player win if both players play perfect games. The pie rule can be used to balance the first-player's advantage.
The game provides a Kalah board and a number of seeds or counters. The board has 6 small pits, called houses, on each side; and a big pit, called an end zone or store, at each end. The object of the game is to capture more seeds than one's opponent.
It is possible for the game to end in a draw.
The player begins sowing from the highlighted house.
The last seed falls in the store, so the player receives an extra move.
The last seed falls in an empty house on the player's side. The player collects the highlighted seeds from both their own house and the opposite house of their opponent and will move them to the store.
Mathematical analysis
As mentioned above, if the last seed sown by a player lands in that player's store, the player gets an extra move. A clever player can take advantage of this rule to chain together many extra turns. Certain configurations of a row of the board can in this way be cleared in a single turn, that is, the player can capture all stones on their row, as depicted on the right. The longest possible such chain on a standard Kalah board of 6 pits lasts for 17 moves. On a general n-pit board, the patterns of seeds which can be cleared in a single turn in this way have been the object of mathematical study.[9] One can prove that, for all n, there exists one and only one pattern clearable in exactly n moves, or equivalently, one and only one clearable pattern consisting of exactly n seeds.
These patterns require arbitrarily long rows of pits and n increases. For example, it can be seen on the right that the unique 5-seed pattern requires only 3 pits, but the 17-seed pattern requires 6 pits. The relationship between the required number of pits and the number of seeds can be described in the following way. Let s(n) denote the minimum number of seeds which requires n pits to clear. Then s ( n ) ∼ n 2 π , {\displaystyle s(n)\sim {\frac {n^{2}}{\pi }},} where the symbol ∼ {\displaystyle \sim } denotes asymptotic equivalence, that is, lim n → ∞ s ( n ) n 2 / π = 1 {\displaystyle \lim _{n\to \infty }{\frac {s(n)}{n^{2}/\pi }}=1} , or equivalently, lim n → ∞ n 2 s ( n ) = π {\displaystyle \lim _{n\to \infty }{\frac {n^{2}}{s(n)}}=\pi } .[9]
