On game space size

[Antti Huima <huima@xxxxxx>]

Hi,

I performed some calculations for the 5 x 5 board. First, I used Monte
Carlo esimation to estimate the fraction of legal positions from all
positions with a certain number of black and white stones. Then I used the
combinatorial formula shown recently. In these calculations I included all
positions, not only those were the number of black and white stones is
almost equal.

  (5 * 5)! = 25! =      15.511.210.043.330.985.984.000.000 = 2^83.7

  Combinatorial result: 853.076.946.538                    = 2^39.6

  Combinatorial result + Monte Carlo estimation:
                        414.572.660.630                    = 2^38.6

When considering only those positions where the number of white stones is
between (black - 4, black + 4) we get:

  Combinatorial result: 622.904.488.512                    = 2^39.2

  Combinatorial result + Monte Carlo estimation:
                        305.745.757.051                    = 2^38.2

One should observe the huge difference between the brute approximation n!
and the more exact value: the number of distinct legal positions is less
than a square root of the factorial approximation!

Observe also that 2^83.7 >> (2^38.6 * 2^25) (25 = n^2 = board size).

Furthermore we find that the number of legal positions seems to be about
one half from all the positions (on 5 x 5 board; the result probably does
not generalize).

These considerations do not take ko positions into account.

-- 
Antti Huima
SSH Communications Security Oy