بسم الله الرحمن الرحيم

November 16, 2010

French touch

On three French web sites I discovered three different designs for pasang board.

2 Tours de Jeu, a site documenting rules for strategy games, exhibits a simple makeshift pasang board. The pieces are placed inside squares (just like checkers and chess), a departure from the conventional placement on grid intersections. This is not really unusual; an early non-libre version of Pasang Emas included a theme which departed similarly from the convention. What is really unusual is the set of rules for the game. It is totally different from what Pasang Emas implements. This unusual version of pasang is described by R C Bell in his book "Discovering Old Board Games".

Some people dispute the accuracy of Bell's account. But I do not currently wish to go into that debate. I wouldn't be surprised either way.

Association pour Vivre l'AutoGestion, a social club for family entertainment, has this catalogue of rental games. Page 25 of this catalogue shows an ornamented pasang board. You have got to see it to believe it. The French are adding a dash of their own art to the Brunei game. That's truly multi-cultural.

Geoludie has an online catalogue of world games for sale. It includes what appears to be a modern looking pasang board with small plastic marbles as pieces (unless my discernment has failed me and those are actually computer generated). Geoludie's pasang has 2 sets of rules: the one described by Bell and the one implemented by Pasang Emas. (Geoludie actually contacted me in 2006 regarding the irreconcilable differences between the two versions. So, they are in business of selling pasang for a long time already). The unusual use of marbles (placed presumably inside shallow cups on the board) is based on Bell's description of the game. Having played Chinese checkers using marbles on a holey board, I can attest the practicality of that design.

17 March 2018: Edited to replace broken links with Wayback Machine

November 11, 2010

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 556, which is approximately 1039.

If we use the mean value 7 for the branching factor, the estimated tree size is 756, or approximately 2 x 1047.

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 1042. (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.