Author: Robert Hyatt
Date: 21:21:08 01/27/99
Go up one level in this thread
On January 27, 1999 at 16:08:10, Ernst A. Heinz wrote: >On January 27, 1999 at 15:48:16, Robert Hyatt wrote: > >>On January 27, 1999 at 15:16:44, Ernst A. Heinz wrote: >> >>>On January 27, 1999 at 13:54:07, Peter McKenzie wrote: >>>> >>>>Bob, what you describe as razoring (which is also what I thought was razoring >>>>and I haven't even read the crafty sources :) matches the definition of Futility >>>>Pruning as given by Ernst Heinz in his recent ICCA article (also on the >>>>excellent web page http://wwwipd.ira.uka.de/Tichy/DarkThought/). >>>> >>>>I guess they call it 'pruning' because, by jumping to the q-srch one ply >>>>earlier, you are tossing out moves that you would have searched had you not >>>>jumped to the q-srch. >>>> >>>>I'm still unsure of exactly what Ernst's (and others who share his definition of >>>> Futility Pruning) definition of razoring is. Maybe its when you just return >>>>alpha instead of jumping to the q-srch? >>> >>>No. >>> >>>I have meanwhile reread the whole thread and think to know where the >>>general confusion stems from (see explanation below). >>> >>>1. Your and Bob's definition of razoring implies a depth reduction of 1 ply >>> at the frontier (remaining depth = 1 ply) with a direct jump into the >>> quiescence search. However, you do *not* cut any moves at frontier nodes. >>> >>>2. The original definition of razoring as given by Birmingham and Kent in >>> 1977 (as correctly quoted by Peter Fendrich) *cuts* *all* moves at >>> frontier nodes with static evaluations <= alpha. Birmingham and Kent >>> proposed even more risky stuff called "deep razoring" and "enhanced >>> razoring" which performed the cuts anywhere in the search tree which >>> featured maximal depths of 5 plies in their times. Marginal forward >>> pruning as suggested by Slagle is similar and at least equally risky. >>> >>>3. Normal futility pruning *cuts* all futile moves at frontier nodes and >>> searches the remaining non-futile captures and checks to their full >>> depth (1 ply). This holds accordingly for my extended futility pruning >>> which applies at pre-frontier nodes (remaining depth = 2 plies). On top >>> of these two types of futility pruning, my limited razoring adds a depth >>> reduction of 1 ply for very bad positions at pre-pre-frontier nodes >>> (remaining depth = 3 plies) and subsequently subjects them to extended >>> futility pruning. Thus, limited razoring *cuts* extremely futile moves >>> at pre-pre-frontier nodes and searches the remaining non-futile captures >>> and checks to a reduced depth of 2 plies. >>> >>>=Ernst= >> >> >>Then I don't like the terms... at all... what I do is _not_ pruning in any >>sense of the word, any more than null-move is direct pruning. I reduce the >>depth, but I don't throw anything away in the 'razoring' code. >> >>OTOH, in my q-search I _do_ prune, and I have called this 'futility pruning' >>because if my current material score is say -9.00, and I am about to try a >>move that captures a pawn, I call that 'futile' and don't even search it, since >>one pawn gain, plus the positional score, is _not_ going to pop the score back >>over alpha so that it can be useful. >> >>I have _always_ called 'pruning' the decision to toss out a move apriori with >>no searching of any kind, even to reduced depth. And the term 'futility >>pruning' as I described it above has been used since the middle 70's in >>discussions I have had with others. If it was used differently in a paper >>somewhere, that's ok by me. But I'm not going to call the 'razoring' Idea I >>use 'futility pruning' when I don't prune anything. And I'm not going to call >>my quiescence pruning 'razoring' when I do prune something. :) >> >>Perhaps just a gross terminology issue, but the definition of 'pruning' ought >>to be pretty standard. Pruning means "in the world of trees, such as my >>crepe myrtles, "cutting away a branch in its entirety", not "cutting a chunk >>out of a branch and sticking the pieces back together with a chunk in the middle >>missing. >> >>Somewhere along the line, that 'pruning' term got misused, and maybe it stuck >>in some cases. But the 'meaning' seems clear to me... and this is nothing more >>than _really_ confusing... :) > >Where and why did the term "pruning" get misused in your opinion? > >1. Normal futility pruning (as coined by Jonathan in his Ph.D.thesis), >2. extended futility pruning (as coined by me in the ICCA Journal), and >3. futility pruning in the quiescence search (as done by almost anybody) > >all *cut* (or prune if you like) moves at the nodes where they are applied >according to my above explanation. > >=Ernst= It was misused, IMHO, when talking about what I call 'razoring' in my search. I absolutely do _not_ do any pruning at that point, where pruning has always been defined as not searching a branch from a specific node. IE classic alpha/ beta pruning does just that. Some branches from a node are searched, some are not. No reference to depth reductions or anything here. I absolutely _do_ discard some branches in my quiescence search, in what has been called 'futility pruning' for 20 years or so. The idea of discarding (not searching) a branch because it is considered futile to do so. No searching it in _any_ way at all (as in with a reduced depth, for example). That's where I get confused... when the discussion said what I am doing as 'razoring' is really 'futility pruning'. Because my 'razoring' block of code is _not_ pruning _anything_.... it is just cheating on the depth a little bit to speed things up..
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.