Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Measure of moveorder quality

Author: Robert Hyatt

Date: 19:15:16 09/04/99

Go up one level in this thread


On September 04, 1999 at 19:44:22, Ralf Elvsén wrote:

>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


The measurement I do inside crafty is to count the number of positions where I
get a fail-high, and then count the number of positions where I get a fail high
on the _first_ move I search.  I am generally seeing this average about 94%,
which means 94% of the times when I fail high, I fail high on the first move,
which is pretty good.

if you want to compare, count the same things I count, and look at the fh:94%
output in the statistics...




This page took 0.03 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.