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

^{56}, which is approximately 10

^{39}.

If we use the mean value 7 for the branching factor, the estimated tree size is 7

^{56}, or approximately 2 x 10

^{47}.

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

^{42}. (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.

## No comments:

## Post a Comment