Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: move_generation + hash

Author: Robert Hyatt

Date: 15:11:51 05/30/00

Go up one level in this thread


On May 30, 2000 at 15:24:36, Ed Schröder wrote:

>On May 30, 2000 at 00:28:47, Robert Hyatt wrote:
>
>>On May 28, 2000 at 16:37:32, Gian-Carlo Pascutto wrote:
>>
>>>On May 28, 2000 at 10:02:05, Georg v. Zimmermann wrote:
>>>
>>>>From my tests it shows that it sticks with the hash-move about 50% of the time.
>>>>Should this number be higher ?
>>>
>>>Hmm...if this number is also effectively your 'move ordering percentage',
>>>which I assume it is, it is quite low. I'd expect it to be at least about 75%.
>>>
>>>>
>>
>>
>>
>>The classic definition of a "strongly-ordered tree" is this:  If, for every
>>node where you fail high, you fail high on the first move at least 90% of the
>>time, then your move ordering is good."  If you are much below 90% and already
>>have a serious problem that is not hard to fix.  The traditional ordering ideas
>>holds Crafty at 92% and better for most of the game.
>
>I can't understand the 92%. A perfect mini-max search requires many many
>nodes an alpha-beta cutoff will not work and you are forced to search all
>the nodes of the ply in question. And this number is certainly much higher
>than 8%.

You have to re-read the definition again, _very carefully_ to avoid the semantic
trap you just fell into.

For every position where you fail high, if you fail high on the first move you
try, you increment a counter "right++".  You always increment a counter "fh++".
When you finish the search,  you compute percent=right/fh.  That number needs to
be over 90% to consider your tree strongly ordered.  Notice that this 92% number
(in crafty) simply says this:

    "if we look at _all_ the positions in the tree where the search fails high,
     then 92% of those fail highs happen on the first move searched in that
     position, which is known as 'optimal move ordering'.  In 8% of those fail-
     high positions, we failed high on a move other than the first one (a killer
     move, a capture, a history move, etc.)



>
>The way I count is to calculate the percentage around the alpha-beta check.
>I get 65 to 70% and this number is pretty stable for each position I tested.
>So the question is how you count, and your interpretation of a fail-high.
>When I read fail-high I interprete this as a normal alpha-beta cutoff check.
>
>Ed



Yes...  I call fail high this:

    value=-Search(xxxx);
    if (value > alpha) {
      if (value > beta) {
         stuff done here is done after a fail high condition was detected.
         return value;
      }
    }



>
>
>
>>>>I was very dissapointed when I didn't notice any speedup after my changes. What
>>>>speedup should I expect ? Something like 0.5-1% or more like 1ply ?
>>>>
>>>>Am I doing something wrong or does this simply not matter as much as I thought ?
>>>
>>>It's strange. I did the same thing in the past and arrived at the same result.
>>>My eval is pretty small, my movegen is very expensive yet my speed was hardly
>>>any better. I didn't get it. I still don't.
>>>
>>>I still don't get how some programs run 10x as fast as mine either.(Little
>>>Goliath). What the hell do they do to make those things so darned fast?
>>>
>>>--
>>>GCP
>>
>>
>>Easy:  Never do now, that which you can defer doing until later.  Because if you
>>defer doing it, a cutoff will mean you don't do it at all.



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