Re: On game space size

[Antti Huima <huima@xxxxxx>]

On Thu, 22 Apr 1999 John.Tromp@xxxxxxxxxxxxxxxxx wrote:

> my dumb 2x2 search using suicide and positional superko
> reached depths of 80+ before i decided i needed a best-first search:)
> but even there, 3x3 seems out of reach without go knowledge...
> 
> >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).
> 
> here's a short table
> 
> 1x1: 1 legal, 2 illegal, prob 0.333333
> 2x2: 57 legal, 24 illegal, prob 0.703704
> 3x3: 12675 legal, 7008 illegal, prob 0.643957
> 4x4: 24318165 legal, 18728556 illegal, prob 0.564925
> 5x5: prob ~ 0.489
> 9x9: prob ~ 0.234
> 19 : prob ~ 0.012
> 
> regards,
> 
> %!PS                       %  -John Tromp (http://www.cwi.nl/~tromp/)
> 42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
> setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
> arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
> 9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage
> 

Just a fast note: one must observe that the probability is actually a
function on the number of black and white stones on the board. Therefore
it seems one cannot just blindly multiply the total combinatorial size
(3^(n^2)) with the probability; the different cases with different number
of stones should probably be handled separately and then summed together.
I think. 

-- 
Antti Huima
SSH Communications Security Oy