| Ranks | Two |
|---|---|
| Sowing | Single lap |
| Region | United States, Germany |
Kalah, also called Kalaha or Mancala, is a game in the mancala family invented by William Julius Champion Jr (USA) in 1940. This game heavily favors the starting player, who will always win the three-seed to six-seed versions with perfect play. This game is sometimes also called "Kalahari", possibly by false etymology from the Kalahari desert in Namibia.
As the most popular and commercially available variant of mancala in the West, Kalah is also sometimes referred to as Warri or Awari, although those names more properly refer to the game Oware.
An electronic version of the game, called Bantumi, was included on the Nokia 3310. The handset went on to sell 126 million units making Bantumi the best selling version of the game.
The game requires a Kalah board and 36 seeds or counters. The board has six small pits, called houses, on each side; and a big pit, called a Kalah or store, at each end. Many games sold commercially come with 48 seeds or counters, and the game is started with four seeds in each house.
The object of the game is to capture more seeds than one's opponent.
Example turn
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 seeds from both his house and the opposite house of his opponent and moves them to his store. The player's turn ends.
It is possible for the game to end in a draw, with 18 seeds each.
Mark Rawlings (Gaithersburg, Maryland; USA) has written a computer program to extensively analyze both the "standard" version of Kalah and the "empty capture" version, which is the primary variant. The analysis was made possible by the creation of the largest endgame databases ever made for Kalah. They include the perfect play result of all 38,902,940,896 positions with 34 or fewer seeds! In 2015, for the first time ever, each of the initial moves for the standard version of Kalah(6,4) and Kalah(6,5) have been quantified: Kalah(6,4) is a proven win by 8 for the first player and Kalah(6,5) is a proven win by 10 for the first player. In addition, Kalah(6,6) with the standard rules has been proven to be at least a win by 4. Further analysis of Kalah(6,6) with the standard rules is ongoing.
For the "empty capture" version, Geoffrey Irving and Jeroen Donkers (2000) proved that Kalah(6,4) is a win by 10 for the first player with perfect play, and Kalah(6,5) is a win by 12 for the first player with perfect play. Anders Carstensen (2011) proved that Kalah(6,6) was a win for the first player. Mark Rawlings (2015) has extended these "empty capture" results by fully quantifying the initial moves for Kalah(6,4), Kalah(6,5), and Kalah(6,6). With searches totaling 106 days and over 55 trillion nodes, he has proven that Kalah(6,6) is a win by 2 for the first player with perfect play. This was a surprising result, given that the "4-seed" and "5-seed" variations are wins by 10 and 12, respectively. Kalah(6,6) is extremely deep and complex when compared to the 4-seed and 5-seed variations, which can now be solved in a fraction of a second and less than a minute, respectively.
The endgame databases created by Mark Rawlings were loaded into RAM during program initialization (takes 17 minutes to load). So the program could run on a computer with 32GB of RAM, the 30-seed and 33-seed databases were not loaded.
Endgame database counts: seeds position count cumulative count ------------------------------------------- 2-25 1,851,010,435 1,851,010,435 26 854,652,330 2,705,662,765 27 1,202,919,536 3,908,582,301 28 1,675,581,372 5,584,163,673 29 2,311,244,928 7,895,408,601 30 3,158,812,704 11,054,221,305 31 4,279,807,392 15,334,028,697 32 5,751,132,555 21,085,161,252 33 7,668,335,248 28,753,496,500 34 10,149,444,396 38,902,940,896 -------------------------------------------
For the following sections, bins are numbered as shown, with play in a counter-clockwise direction. South moves from bins 1 through 6 and North moves from bins 8 through 13. Bin 14 is North's store and bin 7 is South's store.
<--- North
------------------------
13 12 11 10 9 8
14 7
1 2 3 4 5 6
------------------------
South --->
Starting position with 4 seeds in each bin:
<--- North
------------------------
4 4 4 4 4 4
0 0
4 4 4 4 4 4
------------------------
South --->
The following tables show the results of each of the 10 possible first player moves (assumes South moves first) for both the standard rules and for the "empty capture" variant. Note that there are 10 possible first moves, since moves from bin 3 result in a "move-again." Search depth continued until the game ended.
Standard Rules: move result perfect play continuation ------------------------------------------------------- 1 lose by 14 10 13 3 9 13 12 1 13 11 5 13 2 lose by 10 10 13 5 9 13 8 4 10 13 8 5 3-1 lose by 6 10 11 2 13 1 12 1 13 9 4 12 3-2 tie 10 13 5 9 13 8 3 11 1 13 10 3-4 win by 2 10 9 13 2 1 12 3 5 8 12 13 3-5 win by 4 9 10 2 5 12 1 2 11 2 13 5 3-6 win by 8 9 8 2 12 6 5 11 6 1 6 5 4 lose by 2 10 12 2 4 13 1 5 9 13 12 13 5 lose by 8 10 9 11 2 5 10 1 8 4 12 5 6 win by 4 9 12 2 6 1 11 4 10 6 5 13 -------------------------------------------------------
"Empty Capture" Variant: move result perfect play continuation ------------------------------------------------------- 1 lose by 14 10 13 4 9 13 11 2 13 8 13 10 2 lose by 8 10 13 5 9 13 8 4 10 13 9 5 3-1 lose by 8 10 11 4 9 12 2 10 5 11 12 9 3-2 lose by 2 10 13 5 9 13 8 3 11 5 13 10 3-4 win by 2 10 9 13 2 1 12 3 5 8 12 13 3-5 win by 4 9 11 2 4 8 12 5 13 5 11 4 3-6 win by 10 9 8 4 11 6 2 6 4 9 5 13 4 lose by 2 10 12 2 5 9 8 12 9 4 10 11 5 lose by 6 10 9 11 4 8 13 5 6 4 12 6 6 win by 4 9 12 2 6 1 11 4 10 6 5 13 -------------------------------------------------------
Starting position with 5 seeds in each bin:
<--- North
------------------------
5 5 5 5 5 5
0 0
5 5 5 5 5 5
------------------------
South --->
The following tables show the results of each of the 10 possible first player moves (assumes South moves first) for both the standard rules and for the "empty capture" variant. Note that there are 10 possible first moves, since moves from bin 2 result in a "move-again." Search depth continued until the game ended.
Standard Rules: move result perfect play continuation ------------------------------------------------------- 1 lose by 10 9 11 4 8 13 2 9 6 3 11 13 2-1 lose by 4 9 10 2 12 1 11 3 12 8 11 1 2-3 win by 10 10 1 6 9 5 13 6 2 8 4 13 2-4 win by 10 8 11 1 6 9 2 13 11 4 12 6 2-5 win by 8 8 10 1 6 9 5 13 12 2 13 11 2-6 tie 8 11 1 6 3 11 6 5 12 6 8 3 win by 2 9 8 12 1 4 11 2 12 10 4 3 4 win by 2 8 11 1 5 12 3 10 5 2 11 6 5 win by 2 8 12 1 4 9 2 12 4 9 3 11 6 tie 8 12 1 6 4 10 6 2 11 4 3 -------------------------------------------------------
"Empty Capture" Variant: move result perfect play continuation ------------------------------------------------------- 1 lose by 10 9 12 6 8 12 11 2 8 6 5 12 2-1 lose by 6 9 10 2 12 4 8 9 3 10 11 3 2-3 win by 12 8 10 1 6 10 5 13 9 6 4 11 2-4 win by 8 8 9 1 6 11 4 13 10 4 13 9 2-5 win by 8 8 10 1 6 9 5 13 12 3 13 6 2-6 lose by 2 8 11 1 6 5 9 6 3 11 12 5 3 win by 2 9 8 12 1 4 11 2 10 4 5 10 4 tie 8 11 1 5 12 3 9 5 2 11 3 5 tie 8 10 1 4 12 5 11 2 9 4 13 6 tie 8 12 1 6 4 9 6 2 12 6 5 -------------------------------------------------------
Starting position with 6 seeds in each bin:
<--- North
------------------------
6 6 6 6 6 6
0 0
6 6 6 6 6 6
------------------------
South --->
The following tables show the results of each of the 10 possible first player moves (assumes South moves first) for the "empty capture" variant and the current status of the results for the standard variation. Note that there are 10 possible first moves, since moves from bin 1 result in a "move-again." Search depth for the "empty capture" variant continued until the game ended.
"Standard" Variant: (Results are still being computed by Mark Rawlings.) move result ------------------------------------------------------- 1-2 win, by at least 2 1-3 win, by at least 4 1-4 1-5 1-6 2 3 4 5 6 loss, by at least 2 -------------------------------------------------------
"Empty Capture" Variant: move result perfect play continuation ------------------------------------------------------- 1-2 win by 2 10 3 12 4 8 6 10 11 6 3... 1-3 win by 2 11 1 8 2 10 6 8 3 11 5... 1-4 tie 10 3 12 5 10 3 9 1 12 3... 1-5 tie 9 4 8 3 10 2 10 4 1 9... 1-6 tie 10 4 9 6 3 11 6 8 2 10... 2 win by 2 12 4 10 1 12 8 1 11 3 9... 3 tie 10 5 12 4 11 1 12 8 4 3... 4 tie 10 3 11 1 9 5 11 2 10 8... 5 tie 10 3 11 4 12 2 11 4 10 5... 6 loss by 2 10 3 8 6 4 13 1 10 13 8... -------------------------------------------------------
A breakdown of the 55+ trillion nodes searched to solve the "empty capture" variant of Kalah(6,6):
move time (sec) nodes searched ---------------------------------------- 1-2 305,791 2,214,209,715,560 1-3 403,744 2,872,262,354,066 1-4 401,349 2,335,350,353,288 1-5 317,795 1,886,991,523,192 1-6 392,923 2,313,607,567,702 2 1,692,886 9,910,945,999,186 3 1,296,141 7,398,319,653,760 4 1,411,091 9,623,816,064,478 5 1,607,514 9,318,824,643,697 6 1,354,845 7,824,794,014,305 ---------------------------------------- total 9,184,079 55,699,121,889,234