Author: martin fierz
Date: 10:26:42 03/29/04
Go up one level in this thread
On March 29, 2004 at 12:24:42, Steve Maughan wrote: >After hacking around in Excel for a couple of minutes I came up with this >formula. Of course it's an engineers fomula and not a mathematicials formula >i.e. it looks about right and I'm not really interested in the proof :-)) > >Node = 2 * sqrt(moves ^ depth) * sqrt((1 / MoveOrdering) ^ depth) > >It's based on the thought that when the MoveOrdering stat falls we need to >search more than one move at a theoretical cuttoff node i.e. alternative depths. > Also the effect is going to be multiplicative and as the MoveOrdering >approaches 1 the nodes approaches the theoretical minimum. > >Thoughts? hi steve, i posted the formulas below in the other thread: i like my formula(s) better than yours since there is no real reason for your 1/moveordering term. i mean, let's assume random move ordering meaning you get the 1st move right in about 2% of the cases, and let's assume 50 moves, then your formula reproduces the formula for the worst case. but random move ordering is of course FAR superior to totally wrong move ordering. so you are missing some kind of constant in your formula for this. here's what i suggested - they are also "engineer formulas" but i think a bit better than what you suggest: i can imagine some kind of formula just by doing some assumptions, which may be completely wrong...: the totally wrong-ordered case goes as nodes(depth) ~ (N*N)^D/2 the totally ordered case goes as nodes(depth) ~(1*N)^D/2 this formula stems from the fact that you search exactly 1 move at player A's moves, and all N at player B's moves AFAIK, so for going 2 ply deeper i need 1*N nodes. so let me assume random move ordering for player A, meaning i get the best move right on average at move N/2, which gives me nodes(depth) ~ (N*N/2)^D/2. perhaps that should read (N*sqrt(N))^D/2, because it might be the geometric instead of the arithmetic mean?! in any case, you can now assume that you find the best move 1st in the fraction F (~0.9), and in the remaining case at random, this leads to nodes(depth) ~ (N*(1*F+(N/2*(1-F)))^D/2. plugging in some numbers like N=20 (reduce from 40, trying to account for nullmove?!), D=10, F=0.90 and 0.91 i get nodes(10, F=0.90) = 79 million nodes(10, F=0.91) = 62 million so for 1% better move ordering i get 22% less nodes?! seems rather excessive. let me try again using sqrt(N) instead of N/2 - that still gets a 12% reduction. hmm, either my formulas are crap or i really have to work on my move ordering ;-) cheers martin >Interestingly this means that the difference between a move ordering stat of 0.9 >and 0.95 for a 10 ply search is 31% more nodes. At a 15 ply search this >increases to 50% more nodes. So improving the move ordering has more effect at >slower time controls - I think we knew this anyway. > >Regards, > >Steve
This page took 0.01 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.