Re: On game space size

[John.Tromp@xxxxxx]

>From computer-go-owner@xxxxxxxxxxxxxxxxx Thu Apr 22 19:24:25 1999
>Delivered-To: computer-go@xxxxxxxxxxxxxxxxx
>X-Sender: xu@xxxxxxxxxxxxxxxxx
>To: John.Tromp@xxxxxxxxxxxxxxxxx, computer-go@xxxxxxxxxxxxxxxxx, huima@xxxxxxxxxxxxxxxxx
>From: Mousheng Xu <xu@xxxxxxxxxxxxxxxxx>
>Subject: Re: On game space size
>Mime-Version: 1.0
>X-Loop: computer-go@xxxxxxxxxxxxxxxxx
>
>At 01:45 PM 4/22/99 +0200, John.Tromp@xxxxxxxxxxxxxxxxx wrote:
>>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
>
>John,
>
>	I assume the prob(legal) should arise when the board gets bigger? Could

a probability should arise? i don't understand. probability is just
fraction of all 3^(n^2) positions that are legal.

>you show us how you derive your data?

with two C programs, one giving exact counts, one sampling (monte carlo).

>	Let's do some adjustment on the calculations for the 9 x 9 board:
>	complexity = 3^81 / (2.3 * 10^23 (depth = 10)) * 0.234 (legalty) *
>
>	Take a wild jump to sqrt it (no particular reason, but just for
>encouragement), 620 years only!

Taking a square root on the number of years makes little sense; if you
chose number of seconds you'd reduce it much more (or imagine an eon being
39000 yrs, and taking a square root on the number of eons:-)

I also don't understand why people take factorials; the difficulty with
small boards lies in playing again on points vacated by capture, and
the need to remember the whole move history for superko.

regards,
-John