Author: Ed Schröder
Date: 09:09:02 05/31/00
Go up one level in this thread
On May 30, 2000 at 18:11:51, Robert Hyatt wrote:
>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.)
In our example I got the "fh++" before and the "right++" after the alpha-beta
check which is also a nice piece of information. Now that I have changed this
into your way I typically get 92-94%. Since this percentage is updated on the
screen every second I can follow its behavior. You indeed see the percentage
dropping when for instance a move fails low on the root and the engine has to
search for a new move it did not had as best move sofar before.
The question remains "who has decided" or "how do you know" that 90% is good
and below is bad (as you say).
Ed
>>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 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.