Author: martin fierz
Date: 12:00:00 03/29/04
Go up one level in this thread
On March 29, 2004 at 14:11:21, Steve Maughan wrote: >Martin, > >Point taken. Here's my second attempt - not sure it's any better than yours: > >Nodes = N ^ (D / 2) x N ^ (D / 2) / (N ^ (F x D / 2)) > >This simplifies to: > >Nodes = (N ^ D) / (N ^ ( F x D / 2)) > >When F = 0 (i.e. worse than random) Node = N ^ D and when F = 1 (perfect) >Node = N ^ (D /2). This formula shows massive changes in nodes whith different >move ordering. > >Interesting topic! > >Steve hi steve, so your engineering formula goes as nodes = N^D * N^(-(FD/2)) an interesting suggestion was made by dan andersson, namely that you always have chance F to find the best move, i.e. you have chance F of finding it on the first move, and if you don't find it there, you find it again with chance F on the second move etc. which means that if you want to find the average cutoff move number that is 1*F + 2*(1-F)*F + 3*(1-F-(1-F)*F)*F +.... = F * (1 + 2*(1-F) + 3*(1-F)^2 + 4*(1-F)^3 +...) (hope my math doesn't fail me...) keeping in mind that (1-F) is a small quantity, this is a power series development in small quantities, and physicists generally only keep the highest-order term: avg. cutoff move = F*(1+2*(1-F)). plugging this into the formula nodes(depth) = N^D/2 * (avg.cutoff move #)^D/2 we get nodes(depth) = N^D/2 * (3F-2F^2)^D/2 (with the side note that F has to be close to 1 for this to work!) therefore the factor (3F-2F^2)^D/2 governs the tree growth, meaning that for the example with D=10, F=0.9 or 0.91 the difference is now "only" 3% in tree size. interesting... basically this of course says that if your move ordering is already very good, then there is not much to be gained any more. i was a bit afraid that the 12% gain for 1% better move ordering were realistic - i hope that is wrong. in any case, i should probably measure the frequency distribution of the cutoff #, because then i could calculate an average cutoff move # and get a real estimate. still not sure though whether one should use the arithmetic or geometric mean there... cheers martin
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.