Re: FYI & my annoyment

[Mousheng Xu <xu@xxxxxxxxxx>]

At 06:33 PM 4/21/99 EDT, Compgo123@xxxxxxxxxxxxxxxxx wrote:
>It's an interesting problem to study 3x3, etc ... board. Too bad my program 
>is not convenient to change to 3x3 board. Anyway I think the reason why it 

Dan, 
	First, I would say I did the wrong calculation on the complexity in my
last email. Instead of n!/2^n, it should be 3^n.
	Second, as depth is concerned, you save (n - d) levels of the tree from
the bottom, which is a save  of 3^n/(C(n,d)*2^d) times. Given 
	n = 9, d = 10, save = 1 (no save), complexity = 2.0 * 10^4 
	n = 16, d = 10, save = 5,	complexity = 8.6 * 10^6
	n = 25, d = 10, save = 253, complexity = 3.3 * 10^9
	n = 81, d = 10, save = 2.3 * 10^23, complexity = 1.9 * 10^15
 
	If we want to finish a calculation in a reasonable time, say 1 hour for a
step, the complexity should be in the order of 10^5 (remember my algorithm
for a 3 x 3 board takes 9! = 10^5 computation and it can't finish in two
hours. What eats up time includes node creation, rule checking, flow
control, etc.). Which means, for a 4 x 4 board, depth should be <= 6. If
you agree, I would say this is still a useless tree. I thought a 100 MHz
machine could finish 10^8 complexity in seconds, but it actually takes
hours for 10^5, a 10^4 difference. My ambition for a 5 x 5 board was on
paper only. Even with limited depth as calculated above, 9 x 9 takes 10^10
hours > 1000 years. :) Don't blindly try it out on your machine and hoping
that you could tolerate months of calculation.
	Sigh for the speed of lightning fast computers, sigh for the speed of
evolution.
	God help me to trim off useless branches! :)

	Thanks.

-- Mousheng Xu