Computer Chess Club Archives


Search

Terms

Messages

Subject: move ordering and node count

Author: martin fierz

Date: 07:17:18 03/29/04


aloha!

i was discussing this somewhere in a thread, but thought i'd like to make this
question more visible in the hope of getting a good answer:

everybody knows that with plain alpha-beta, a fixed number of moves N per node,
and perfect move ordering a search to depth D needs

nodes(depth) = sqrt(N)^(D/2) nodes.

with absolutely imperfect move ordering it needs

nodes(depth) = N^(D) nodes.

a typical chess program gets something like 90% move ordering in the sense that
if a cutoff move exists, it will search it as first move in 90% of all cases.
here's my question:

can anybody give an estimate for nodes(depth) as function of this move ordering
parameter? obviously, this would also depend on when you find the best move in
those cases where you don't find it first. any kind of model is acceptable, e.g.
you always find it on 2nd, always on sqrt(N)th, always last, at a random number,
whatever. i'm just interested in the general behavior of nodes(depth) as a
function of the cutoff-%age.

i'd be extremely surprised if nobody ever estimated this, so: has any of you
ever seen or calculated such numbers, and if yes, what do they look like?

and is there any theory how this would apply to a modern chess program with
nullmove and extensions instead of the plain A/B framework above?

basically this question of course means: do you really gain anything tangible
when improving your MO from say 90% to 92%?

cheers
  martin




This page took 0.07 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.