Author: Robert Hyatt
Date: 07:06:34 02/28/06
Go up one level in this thread
On February 28, 2006 at 08:55:44, Vasik Rajlich wrote: >On February 27, 2006 at 12:28:46, Robert Hyatt wrote: > >>On February 27, 2006 at 12:02:06, Miguel A. Ballicora wrote: >> >>>On February 27, 2006 at 11:15:50, Vasik Rajlich wrote: >>> >>>>On February 27, 2006 at 09:41:37, Tord Romstad wrote: >>>> >>>>>On February 27, 2006 at 06:48:18, Tord Romstad wrote: >>>>> >>>>>>I'll try to write an explanation on my web page, and refer to that one >>>>>>in the future. I hope to have it ready today or tomorrow. Stay tuned! >>>>> >>>>>My first draft is ready: >>>>> >>>>>http://www.glaurungchess.com/lmr.html >>>>> >>>>>Comments, corrections and suggested additions or improvements >>>>>are welcome. >>>>> >>>>>The only two engines I mention in my "Sample Code" paragraph are >>>>>Fruit and Glaurung. This is because of ignorance, and not because >>>>>of disrespect to other authors. If you are the author of an open source >>>>>engine using history pruning (or whatever you prefer to call it) and >>>>>wants it to be mentioned on my page, please let me know. >>>>> >>>>>Tord >>>> >>>>Tord, >>>> >>>>nice summary. >>>> >>>>A few minor things: >>> >>>First of all, congratulations for CCT8! >>> >>>>1) For me, the terms "pruning" and "reducing" are interchangeable. I'd guess >>>>most CC programmers agree with this - for example, we have null move pruning. >>> >>>This is semantics, but I do not agree. Reducing is decreasing (depth--), pruning >>>is removing (depth=0). You may argue that if I reduce a branch by 1, you are >>>pruning the leaf. Not necessarily, because in the subtree you still have chances >>>to extend and get back that leaf into the tree. When your prune, is gone. >>> >>>Maybe somet definitions chanced in the last 3 years, but before, it was >>>understood that pruning was "I do not search this subtree anymore" and >>>reductions was "I search it with reduced depth". >>> >>>Regards, >>>Miguel >> >> >>I would agree there. >> >>The idea of "pruning" is to say "I will not search this move _period_." As in >>the old days of shannon type-a and type-b searches... >> >>I don't like the usage of "null-move pruning" either, but it does have a point, >>in that if the null-move search fails high, we do not search any other moves at >>this point, effectively pruning them away. But we did do a search to see if >>this position deserved a real search and concluded "no". >> >>I like Tord's wording myself "late-move reductions" which really hits the nail >>on the head exactly, definition-wise. When I started playing with this basic >>idea way back, I was calling it "last phase" something as I would first try N >>history-moves and then give up and go into the "last phase of move selection" >>which just took moves in the order they were generated and stuck in the move >>list... but "phase" was a Crafty-term and "late-move" is more generic and clear >>IMHO. > >"Late move" doesn't 100% capture the concept either. You're not necessarily >reducing a move because it's late (for example bad captures). You're reducing it >because you think it is more likely to fail low, given the information that >sibling searches have already failed low. So my favorite is "fail low pruning". >:) In that case, I think I like "fail low reductions". :) That also captures the essence of the idea. "late move" is also ok since that is a key ingredient in the idea (first few moves are not reduced ever, moves later in the move list are if they don't trip some exception case.) Still have a lot to play with and test before I'd consider this "done" however... > >Re "pruning" vs "reductions", if you look at the gardening definition: > >http://en.wikipedia.org/wiki/Pruning > >" >Shearing to form hedges or topiary is also a form of pruning, in which most of >the growing points are tipped back, to produce artificially dense growth That still misses the point IMHO. There you are cutting away tips without letting them grow further and discover what they turn into. Rather than applying some chemical that simply slows the growth of some branches and lets other branches grow longer... >" > >I agree though that it's good to have a special term for throwing a move away >completely. > >Vas > >> >>> >>>>2) Prob-cut is not a fail-high-node selectivity algorithm. You might add SE >>>>there instead. Yes, I know that SE extends rather than reduces - but it's the >>>>same idea as multi-cut. The idea of categorizing selectivity into fail-high-node >>>>and fail-low-node is good. >>>> >>>>Vas
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.