Author: Ricardo Gibert
Date: 12:25:12 05/31/00
Go up one level in this thread
On May 31, 2000 at 13:22:34, blass uri 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'. > > >I do not agree that failing high on the first move is optimal move ordering. > >Here is an example: > >[D]8/6k1/rp3ppp/8/N7/8/4RPPP/6K1 w - - 0 1 > >My understanding of optimal move ordering is that after the moves Nxb6 or Nc5 >the first move to search will be Ra1+(at least in cases that you are going to >search more than few plies after these moves because Ra1+ Re1 Rxe1# is the >faster way to prove that Nxb6 or Nc5 is wrong) > >If you start with taking the knight than your first move may fail high but you >waste more time to prove that Nxb6 or Nc5 are wrong. > >Uri I don't understand. It makes no difference in your example whether the program rejects Nxb6 due to Rxb6 or Ra1. In fact, since Ra1 is not mate, the program must still look an additional 2 ply to determine that Ra1+ is really better. Whether it is better is irrelevant. The issue is "optimal move ordering" and not what the optimal move is. That's something different. It is possible that a program could search a larger tree by always examining the best move first, since it is possible for "good enough" moves to get a quicker cut-off. Here black is led into finding the best move Ra2 for white as quickly by Rxb6 in reply to Nxb6 as anything else. Your example is a good example of why it is good idea to examine captures first. They are the most succinct way of generating a fail high. Yes?
This page took 0.01 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.