Kalah

For the village in Iran, see Kalah, Iran. For other uses, see Kala (disambiguation).

Kalah
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.

Equipment

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.

Object

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.

Rules

1. At the beginning of the game, three seeds are placed in each house. This is the traditional method.
2. Each player controls the six houses and their seeds on the player's side of the board. The player's score is the number of seeds in the store to their right.
3. Players take turns sowing their seeds. On a turn, the player removes all seeds from one of the houses under their control. Moving counter-clockwise, the player drops one seed in each house in turn, including the player's own store but not their opponent's.
4. If the last sown seed lands in the player's store, the player gets an additional move. There is no limit on the number of moves a player can make in their turn.
5. If the last sown seed lands in an empty house owned by the player, and the opposite house contains seeds, both the last seed and the opposite seeds are captured and placed into the player's store.
6. When one player no longer has any seeds in any of their houses, the game ends. The other player moves all remaining seeds to their store, and the player with the most seeds in their store wins.

It is possible for the game to end in a draw, with 18 seeds each.

Variations

• A common, more challenging variation is to begin with four, five or six seeds in each house, rather than three. Four-, five- and six-seed Kalah have been solved, with the starting player always winning with perfect play, as in three-seed Kalah. Thus some web sites have implemented the game with the pie rule to make it fair.
• An alternative rule has players sow in a clockwise direction, requiring more stones to be sowed in a single turn to reach the store.
• The "Empty Capture" variant: If the last sown seed lands in an empty house owned by the player, even if the opposite house is empty, the last seed is captured and placed into the player's store.
• An alternative rule does not count the remaining seeds as part of the opponent's score at the end of the game.

Computer analysis of Kalah(6,4)

Mark Rawlings (Gaithersburg, Maryland; USA) has analyzed all of the initial moves for Kalah(6,4) using both the standard rules and the "empty capture" variant (2015). He has created 39 GB of endgame databases (all positions with 34 or fewer seeds) for each. With the use of these endgame databases, any position in Kalah(6,4) can be solved in just a fraction of a second. The initial move for the "empty capture" variant was quantified as a win by 10 for the first player by Geoffrey Irving and Jeroen Donkers in 2000, but the magnitude of the win for Kalah(6,4) using the standard rules had not been previously quantified.

Bins are numbered as follows, 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
-------------------------------------------------------

Computer analysis of Kalah(6,6)

Mark Rawlings, of Gaithersburg, MD, has quantified the magnitude of the first player win in Kalah(6/6) with the "empty capture" rule (October 2015). After creation of 39 GB of endgame databases (all positions with 34 or fewer seeds), searches totaling 106 days of CPU time and over 55 trillion nodes, it was proven that, with perfect play, the first player wins by 2.

This was a surprising result, given that "4-seed" Kalah(6/4) is a win by 10 and "5-seed" Kalah(6/5) is a win by 12. 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.

Bins are numbered as follows, 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 6 seeds in each bin:

       <--- North
 ------------------------    
   6   6   6   6   6   6     
                             
   0                   0    
                            
   6   6   6   6   6   6      
 ------------------------     
         South --->

The following table shows the results of each of the 10 possible first player moves (assumes South moves first). Note that there are 10 possible first moves, since moves from bin 1 result in a "move-again." Search depth continued until the game ended.

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...  
-------------------------------------------------------

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 

Endgame databases were developed for all positions with 34 or fewer seeds. Endgame databases 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.

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	
-------------------------------------------

External links

• The Elliott Avedon Museum and Archive of Games article on Kalah
• Jeroen Donkers Kalah page.
• Play Kalah online.