Author: martin fierz
Date: 11:26:33 03/29/04
Go up one level in this thread
On March 29, 2004 at 14:09:50, Gerd Isenberg wrote: >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, gerd! you and mathematical ignorance?? gerd, the master of the bitwise operator universe want to claim 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)? i never said i knew anything about this, instead i was looking for people who do know about it to answer my questions! let me try to answer, but i'm not so sure about this... i would think that the second part of your question is easy to answer: there you get the same worst case as usual. ordering all-nodes is useless (which is why some engines don't order moves any further after the first few, assuming they are all-nodes). ordering the cut-nodes worst will obviously give you no cutoffs either. and the "still pv-nodes" thing doesn't matter either, because pv-nodes are also "all-nodes" in the sense that you have to search every move there (i assume with all-nodes you talked about those which fail low for all moves, else pv-nodes are simply a part of the all-node-set). as for your first question, i think that as you will always be looking at the best move for white, therefore you will, as white, always be either in a pv node, or in a cut-node (if black plays bad moves, as he can under your assumption). you cannot go into a fail-low-node (except if you use aspiration search and fail low there, but let's forget about that for now...). which means that black will always be in either pv nodes or fail-low-nodes, and therefore it doesn't matter - in this case, you have the same as perfect move ordering for both sides. perhaps i get this wrong, you correct me. on second thought, it seems to me that you want to discredit my formula because that of course is useless for such cases. of course there i am assuming some sensible move ordering where both sides are ordering with equal efficiency. cheers martin > >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.