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.