Author: blass uri
Date: 13:12:23 05/31/00
Go up one level in this thread
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 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.