Re: On game space size

[Mousheng Xu <xu@xxxxxxxxxx>]

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
you show us how you derive your data?
	Given your numbers, for a 9x9 board, one may save half an order of
calculation if legalty (?) is taken into account. The closer to the root
you trim off a branch, the more you save. But the illegal positions are
more likely to occur when they are more stones on the board.
	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) *
(2^39.2/2^39.6) (W = B+-4))
		= 4.4 * 10^38 / (2.3 * 10^23) * 0.234 * 0.75
		= 3.4 * 10^14
	Given 1 hour = 10^5, we need
		3.4 * 10^14 / 10^5 = 3.4 * 10^9 hours = 390000 years.

	Take a wild jump to sqrt it (no particular reason, but just for
encouragement), 620 years only!
	Cheers. :)
	
-- Mousheng