Author: Robert Hyatt
Date: 14:47:13 05/31/00
Go up one level in this thread
On May 31, 2000 at 15:46:15, blass uri wrote: >On May 31, 2000 at 15:23:28, Robert Hyatt 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: >> >>That particular idea isn't open to debate. Alpha/beta is all about minimizing >>the number of nodes searched. It is easy to prove mathematically that if I >>get the best move first every time, and you don't, I am going to search fewer >>total nodes than you are to get the exact same score. >> >> >> >> >> >>> >>>[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 >> >> >>No... that is the wrong way to think about alpha/beta. In any given position, >>the 'best' move is the one which produces the best score _in that position_. It >>doesn't matter a dime what has happened in similar positions, or at shallower >>search depths. Ie it doesn't matter if a move looks "best" to a human, in the >>context of alpha/beta, or anything else. > > >If a program rejects Nxb6 or Nc5 because of Ra1+ Re1 Rxe1# it is using less time >about Nxb6 and Nc5. > >If a program is using less time to get to the same depth the order of moves is >better. > >The point is not to search first the best move but to search first the move that >you need the minimal number of nodes to create a cutoff. That is an _impossible_ question to answer without searching all the moves. Then you can find the move that (a) causes a cutoff and (b) searches the smallest number of nodes to do so. What you are asking for is impossible to provide. To discover which of two moves will produce the smallest search tree while providing a score >= X requires that I search _both_ and then choose. But I don't need to search both. It is an unrealistic goal to add "with the least amount of work" to the requirement that "In an optimally ordered tree, we require that any move that causes a cutoff be the first move searched." (not "the first move searched which also is the easiest one to search.") > > > > It is all about the move that produces >>a move that causes a cutoff. It is _not_ necessary that alpha search the "best" >>move first, ever. It is only necessary that alpha/beta searches a move good >>enough to cause a cutoff... > >If you search first the move that you need less time to get the cutoff then the >order of moves is better. > Sure, but tell me how to discover which move needs the least amount of time to get a cutoff without searching them all and comparing. And why would I do that when _any_ cutoff is good enough to stop the search at this point? Yes I would _like_ to search the one that takes the least effort. Identifying it seems impossible to me. > >> >>My original statement is still on target: If, at every move where you get a >>cutoff, you get it on the _first_ move, you are searching the "minimal tree" >>which is the goal of alpha/beta. > >No >You are not searching the minimal tree because after Nxb6 because you search >more nodes in the line Rxb6 then in the line Ra1+ with the only exception of a >very shallow search. > >Uri That is an unreasonable limitation to the term "minimal game tree". I (and everyone else that has published anything using this term) have always considered this to be "the miminum number of nodes an algorithm would require to search the tree." So long as the first move I search causes a cutoff, I am happy. Because going beyond this is impossible, IMO.
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.