Re: FYI & my annoyment

[Mousheng Xu <xu@xxxxxxxxxx>]

At 05:24 PM 4/21/99 +0300, Antti Huima wrote:
>
>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]

	For simplicity, you could include P[0,0] & P[5,5], and will make the sum
(1 + 1)^n = 2^n, the number I mentioned in the last email.
>
>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.

	But for 4 x 4, 16!/2^16 = 3.2 * 10^8, much > 9! (3.1 * 10^5).

	How do you guys handle the pruning?
	
	Thanks.

-- Mousheng Xu