Re: On game space size

[John.Tromp@xxxxxx]

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