Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: move ordering and node count

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.