FANDOM


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


Kalah(6,4) Edit

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


Kalah(6,5) Edit

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


Kalah(6,6) Edit

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


Analysis of a Kalah game played between Arty Sandler and Ralf GeringEdit

Note: The game is given here.


Position at move 5:

     Ralf Gering
------------------------   
  4  11   0  11   0   0    
                           
  7                   6   
                          
 11  10  10   1   1   0     
------------------------     
   Arty Sandler to move

In this position, the best move is from bin 4, which will give Ralf a 4 seed victory. However, Arty moves from bin 3, which loses by 10.

After the move from bin 3, Ralf is faced with this position:

  Ralf Gering to move:
------------------------   
  5  12   1  12   1   1     
                            
  7                   7    
                           
 11  10   0   2   2   1      
------------------------      
      Arty Sandler

The best move here is from bin 10, which will preserve the 10 seed victory. However, Ralf moves from bin 11, which reduces his victory margin to 2. Game play continues perfectly for many moves (including an incredible 12-move sequence by Ralf at move 8!) until Arty makes several errors at move 9. Here is the position at Arty's second turn at move 9:

          Ralf
------------------------ 
  0   1   1   1   0   0    
                           
 31                  20   
                          
  0   5   3   1   0   9     
------------------------     
      Arty to move

This is an instructive position, with only 21 seeds remaining, that shows just how complicated Kalah can get. Humans generally look for captures and multiple turn moves. Arty can quickly see a multiple turn sequence of 2, 3, 5, 4, and then a capture moving from bin 6. These moves, however, lose by 8! The best move (which preserves the loss by 2) is from bin 4. [The perfect play sequence from this position begins: 4, 12, 2, 5...]


CopyrightEdit

Adapted from the Wikipedia article, "Kalah" http://en.wikipedia.org/wiki/Kalah, used under the GNU Free Documentation License.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.