Computer Chess Club Archives




Subject: Measure of moveorder quality

Author: Ralf Elvsén

Date: 16:44:22 09/04/99

I was thinking of the number of positions one has to search
in the alpha-beta algoritm. With perfect moveordering the
number is roughly  n^(d/2)  , where n = number of moves
in a position and  d = search depth. I know this is a
simplification of the actual formula but it catches
the "essence" of it.

With the worst possible
moveordering it goes like n^d (same as mini-max).

We can summarize this qualitatively as

number of positions = n^(s*d) , where s = 1 for the worst case
and s = 0.5 for the best case.

Is there anyone out there who has a feel for the actual
value of s in the programs used today? This would be a measure
of the quality of the moveordering. I realize that most
programs have a more complicated search structure with null moves,
hash tables etc, but it would be interesting to see
some educated guesses.

	Thanks in advance, Ralf

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.