Author: Gerd Isenberg
Date: 11:09:50 03/29/04
Go up one level in this thread
On March 29, 2004 at 13:26:42, martin fierz wrote: >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 ;-) Sorry Martin for my mathematical ignorance, but what if you sort white moves (even ply) perfect and black moves (odd ply) worst case? Or all-nodes perfect but cut-nodes worst (there a sill pv-nodes)? Cheers, Gerd > >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 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.