Game complexity

I instrumented Pasang Emas to collect statistics on its games. I set the demo mode to play weak against weak, weak against strong, and strong against strong. The following results were gathered from observing more than 3,000 games and more than 170,000 board positions. The results are not sensitive to the strength of the players.


Branching factors

In the opening stage, exactly 11 possible moves are available for the first player and 10 for the second.

In the kas selection stage, an average of 31 possible moves are available. The number will be less if we "merge" different moves that result in identical situations. Theoretically, the maximum branching factor during this stage is 50. This was indeed witnessed during the experiment.

In the rest of the game, a player has an average of 6 possible moves to choose from at each turn. This is very much less than the theoretical maximum of 40. Indeed, the maximum seen during the experiment was only 26.

Overall, the average branching factor is 7.


Game length

Since there are 118 pieces to capture, and each move is a capture move, the game obviously cannot exceed 118 plies. The longest game seen was 94 plies.

On average, a game takes 56 plies.


Complexity

The mode (12%) of the branching factors is 5. So, we can estimate the size of the game tree (ignoring the "zeroth" move, that of choosing a pattern to start the game) as 5⁵⁶, which is approximately 10³⁹.

If we use the mean value 7 for the branching factor, the estimated tree size is 7⁵⁶, or approximately 2 x 10⁴⁷.

A better estimate is to use the distribution of the branching factors. Here is a breakdown:

	branches		frequency
	1		3%
	2		7%
	3		9%
	4		11%
	5		12%
	6		11%
	7		10%
	8		8%
	9		6%
	10		6%
	11		5%
	12		2%
	13		1%
	14		1%
	15 or more		8%

The above distribution is used in the following Ruby code to estimate the tree size:

    f = [3, 7, 9, 11, 12, 11, 10, 8, 6, 6, 5, 2, 1, 1, 8]
    s = 1
    f.each_with_index { |n, i| s = s * (i+1) ** (n/100.0 * 56) }
    puts s

The above code gives an estimated game tree size of 6 x 10⁴². (Using a more accurate breakdown from the raw data does not significantly change the result).


Average capture

Since there are 118 pieces to capture and the average game length is 56 plies, the average number of pieces captured by a move might be mistakenly taken as 118/56 = 2.1. But this is not the case. About 50% of the games observed during the experiment ended up in suntuk. The average number of pieces captured per move was only 1.9.