Re: FYI & my annoyment

[Antti Huima <huima@xxxxxx>]

On Tue, 20 Apr 1999, Mousheng Xu wrote:

> Ladies & Gentlemen,
> 
> 	Just give you some impression how powerless a computer is at computing. 
> 	I did an exhausted tree build/search on a 2 x 2 board, it takes several
> seconds. Well, that's not bad. While I tried a 3 x 3 board, it didn't
> finish in 2 hours and I killed it. :) Man, 3 x 3 ! I had planned for a 9 x
> 9 ! :)
> 	From 2 x 2 to 3 x 3, it's from 4! to 9!. 9!/4! = 15120. It grows VERY
> FAST. I know I could reduce the calculation by 2^n, but even a 4 x 4
> calculation is still ambitious. 

It seems that the claim 4!->9! is based on a model where every
intersection is filled exactly once and no captures are made.

With this model, 9! = 362880.

However, a more careful calculation under the same model yields a
different result:

Let `P[b,w]' denote the number of distinct positions with `b' black and
`w' white stones.

We have
           
  P[b,w] = C(9, b) * C(9-b, w)

where C(n,k) denotes the binomial coefficient, i.e. the number of
k-subsets from a set of size n. The total number of positions to examine
(in the model given) is

  P[1,0] + P[1,1] + P[2,1] + P[2,2] + P[3,2] + P[3,3]
         + P[4,3] + P[4,4] + P[5,4]

which has the numerical value of

  6045

Comparing this with 9! = 362880 shows that, under this model, using a
transposition table would immediately save 98.33% of the work on the 3 x 
3 board.

-- 
Antti Huima
SSH Communications Security Oy