brainwagon

Previously I wrote a simple program to compute the number of positions that are legal in Checkers. I thought I might perform the same analysis for the game of Awari. The simplest approximation that you can get is by counting the number of ways that n undistinguished stones can be distributed in m distinguished pits. A few minutes scratching (or searching the web) will show you that n undistinguished balls can be distributed in m distinguished pits in comb(n+m-1, m-1) ways. Awari begins with 48 stones and 12 pits, so if we sum all the totals, we’ll get the total number of positions. Well, it is an overestimate. First of all, there are no legal positions in Awari with 47 stones, since the first capture either captures 2 or 3 stones. And, there are many positions in here which cannot occur in the game. For instance, in the real game, the non-moving player can never have stones in every pit (except the first move, of course) because he would have previously had to empty one pit to sow it, and that pit is always skipped when you sow. And these totals don’t include any kind of “reachability” analysis: many nodes can’t be achieved in play.

According to Romein and Bal’s work, there are 889,063,398,406 positions which are reachable in Awari. Writing up my naive totaller gives the following totals:

--------------------
 1                12
 2                78
 3               364
 4             1,365
 5             4,368
 6            12,376
 7            31,824
 8            75,582
 9           167,960
10           352,716
11           705,432
12         1,352,078
13         2,496,144
14         4,457,400
15         7,726,160
16        13,037,895
17        21,474,180
18        34,597,290
19        54,627,300
20        84,672,315
21       129,024,480
22       193,536,720
23       286,097,760
24       417,225,900
25       600,805,296
26       854,992,152
27     1,203,322,288
28     1,676,056,044
29     2,311,801,440
30     3,159,461,968
31     4,280,561,376
32     5,752,004,349
33     7,669,339,132
34    10,150,595,910
35    13,340,783,196
36    17,417,133,617
37    22,595,200,368
38    29,135,916,264
39    37,353,738,800
40    47,626,016,970
41    60,403,728,840
42    76,223,753,060
43    95,722,852,680
44   119,653,565,850
45   148,902,215,280
46   184,509,266,760
48   279,871,768,995
--------------------
   1,171,666,558,334

which indicates that approximately 1/4 of all the positions enumerated here are illegal or unreachable. Still, the ease of indexing using this naive idea may compensate for doing anything more compact but more confusing.