Author: Robert Hyatt
Date: 12:28:47 05/31/00
Go up one level in this thread
On May 31, 2000 at 12:09:02, Ed Schröder wrote:
>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 term first came from (I believe) Tony Marsland and Murray Campbell, in
a paper with "strongly ordered game trees" in the title. They defined strongly
ordered as I have given. That means you are doing reasonably well, although
the difference between a tree with 92% optimal ordering and 100% optimal
ordering is _very_ significant. I have stuck with that definition, simply
because it was one established in the literature.
Yes, it is interesting to watch it drop at times (fail lows are good examples)
when the program suddenly discovers that everything is wrong and all the killers
and old good moves are now lousy moves to play.
I think this piece of data might offer more information to a running engine. IE
if it is way high (I have seen way over 96%) that might be a signal that extra
time is not needed here, while lower values might suggest "take more time, the
tree is somewhat unstable".
>
>>>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.