Kalah

Computer analysis of Kalah(6,6) with the "empty capture" rule

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 several minutes, 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 database 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 tablebases 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    
-------------------------------------------