Author: Ricardo Gibert
Date: 13:24:36 05/31/00
Go up one level in this thread
On May 31, 2000 at 16:12:23, blass uri wrote: >On May 31, 2000 at 15:25:12, Ricardo Gibert wrote: > >>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. > >If the program searches 10 plies after Rxb6 it needs more time than in the case >that it search 10 plies after Ra1. > >The only case when searching Ra1 first is not better is when the program >does a very shallow search and it is logical to have a different order of moves >in the cases that the program needs to do a very shallow search. > >>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. > >I agree and I do not say that the best order of moves is to have the best move >first but to have the move that generates a cut off in the smallest number of >nodes. > > > 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? > >In the example that I posted it is a better idea to search Ra1+ first. > >It may be a good idea to search for short mates not in every node but only in >some nodes close to the root in order to have a better order of moves. You seem to place too much "weight" on finding mates outside of the PV when it is actually irrelevant. I would prefer for the program to be led to the correct move 1 Ra2 as soon as possible. The reply 1...Rxb6 to 1 Nxb6 does this. > >You waste time by searching for mate when there is no mate but you may save more >time when you discover a mate. > >Uri
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.