Author: Tony Werten
Date: 01:27:39 10/30/05
Go up one level in this thread
On October 29, 2005 at 16:53:48, Uri Blass wrote: >On October 29, 2005 at 16:06:50, Tony Werten wrote: > >>On October 28, 2005 at 12:52:30, Uri Blass wrote: >> >>>On October 28, 2005 at 12:25:29, Vincent Diepeveen wrote: >>> >>>>On October 28, 2005 at 11:54:37, Uri Blass wrote: >>>> >>>>>On October 28, 2005 at 10:49:21, Vincent Diepeveen wrote: >>>>> >>>>>>On October 26, 2005 at 12:11:27, Bas Hamstra wrote: >>>>>> >>>>>>>On October 26, 2005 at 06:58:41, Tord Romstad wrote: >>>>>>> >>>>>>>>On October 26, 2005 at 05:59:30, Svein Bjørnar Myrvang wrote: >>>>>>>> >>>>>>>>>Can anyone guide me to some good articles on the subject? I can't seem to find >>>>>>>>>anything. Thanks in advance, >>>>>>>>>Svein >>>>>>>> >>>>>>>>In a program with decent move ordering, you would expect a beta cutoff at >>>>>>>>non-PV nodes to occur in one of the first moves played, or not at all. Beta >>>>>>>>cutoffs late in the move list are very rare. This simple observation can be >>>>>>>>used as a basis for reduction techniques. >>>>>>>> >>>>>>>>The basic idea is this: Search the first few moves at each node with full >>>>>>>>depth. If no beta cutoff is found, search the remaining moves with reduced >>>>>>>>depth. If one of the reduced moves returns a score >= beta, re-search this >>>>>>>>move with full depth. >>>>>>>> >>>>>>>>You will probably find that this simple approach reduces your tree size >>>>>>>>dramatically, but the risks are far too big. Blindly reducing all moves >>>>>>>>late in the move list is too dangerous, and you need some extra conditions. >>>>>>>>Most people never reduce captures, promotions, checks, or moves which are >>>>>>>>extended for some reason. If you evaluate internal nodes, you can also >>>>>>>>see how each move changes the components of the evaluation function, and >>>>>>>>make exceptions for moves which dramatically increases your passed pawn >>>>>>>>score, the pressure against the opponent king, and so on. There is lots >>>>>>>>of scope for experiment here, and I suspect that the implementations in >>>>>>>>current programs are very far from optimal. >>>>>>>> >>>>>>>>Another very popular condition is to collect statistics about how often >>>>>>>>every move has failed high or low in the past, and to avoid reducing moves >>>>>>>>which have a high (fail high)/(fail low) ratio. This condition is the >>>>>>>>reason for the name "history pruning", which in my opinion is very >>>>>>>>unfortunate. History is just one of several conditions which can be >>>>>>>>used, and we are not talking about pruning, but reductions. I prefer >>>>>>>>the term "late move reductions", but it seems I am quite alone. >>>>>>>> >>>>>>>>I have found the technique to work even better (especially in tactical >>>>>>>>positions) with the following enhancement: If, at the node directly >>>>>>>>following a reduction, the null move fails low, and the moving piece >>>>>>>>in the move that refuted the null move is the same as the moving piece >>>>>>>>in the reduced move, immediately cancel the reduced-depth search and >>>>>>>>re-search the move with full depth. The point is that in cases like >>>>>>>>this, the reduced depth move often contain some serious tactical >>>>>>>>threat, and deserves a deeper search. >>>>>>>> >>>>>>>>Tord >>>>>>> >>>>>>>Do you any luck with those reductions? I mean provable benefit? >>>>>>> >>>>>>> >>>>>>>Bas. >>>>>> >>>>>>At blitz there is no doubt, searching 2 ply deeper helps usual as it eliminates >>>>>>a worst case. >>>>>> >>>>>>However at serious slow time controls, history pruning is positionally crippling >>>>>>a program. >>>>>> >>>>>>There is 2 circumstances when history pruning might not hurt: >>>>>> a) your evaluation function is extremely simple >>>>>> b) you are doing so many dubious pruning things (multicut, last plies pruning >>>>>>and so on) already that another dubious thing is not really a problem >>>>>> >>>>>>As in diep my evaluation function is not extremely well tuned, despite a >>>>>>pathetic search depth of diep, history pruning is giving 2 ply search depth. >>>>>> >>>>>>However, just consider the problem for diep of history pruning. Even with +2 ply >>>>>>i won't outsearch strong opponents. If i'm getting suddenly 15 ply instead of 13 >>>>>>ply at dutch champs, then that's still less than the 17 ply or so from Zappa and >>>>>>still less than the 16 ply from Fruit. >>>>>> >>>>>>In short you will realize that diep has to win games based upon positional >>>>>>grounds anyway. It needs to get that fail high to a positional better move. The >>>>>>bad thing from history pruning is that better positional moves, suddenly take +6 >>>>>>or +7 ply more now to get found. >>>>>> >>>>>>Do you want to run a +6 or +7 ply extra depth risk just to search 2 ply deeper? >>>>>> >>>>>>When in a few years we search 20 ply search depth, the risk is not 6 nor 7 ply, >>>>>>but the risk is 10-12 ply. >>>>>> >>>>>>In world champs 2005 i presented 1 improvement for history pruning. Which >>>>>>limited the positional risks to less plies. Usually 5 ply positional loss it is >>>>>>in that case. However, all those tiny improvements won't hide the fact that it >>>>>>just positionally cripples a chessprogram and you will need to answer yourself >>>>>>then whether getting down 300 rating points positional is worth 2 ply. >>>>>> >>>>>>In general this 300 points is true for forward pruning. The only forward pruning >>>>>>i'm look at now is last plies pruning. >>>>>> >>>>>>Please note that the implementation as in Fruit 2.1 and Fruit WCCC 2005 is just >>>>>>bringing 1.5 ply extra depth to Fruit initially and a 10 ply positional depth >>>>>>risk. It doesn't bring as much as the implementation i did in Diep. Fruit is not >>>>>>pruning any capture nor check. I did prune also captures. >>>>>> >>>>>>If i'm not pruning captures, then for diep i just win 1 ply search depth with >>>>>>history pruning. Lucky my move ordering is pretty ok, meaning that i'll try good >>>>>>captures as first anyway. >>>>>> >>>>>>In Diep what happens is that trying bad captures is a good idea to try at the >>>>>>end of the move list. In a dumb beancounter experiment i saw that trying bad >>>>>>captures *before* the remainder of the normal moves was a very clever idea and >>>>>>simply gave extra search depth. >>>>>> >>>>>>In move ordering from Fruit 2.1 the score assigned to bad captures is far higher >>>>>>than the score that can get assigned to history moves. >>>>> >>>>>Note that based on the author losing captures are searched last. >>>>>see http://www.talkchess.com/forums/1/message.html?457839 >>>>> >>>>>There are 4 possibilities: >>>>>1)You understand fruit better than Fabien >>>>>2)Fabien made an error in the explanation >>>>>3)You did not understand fruit's code correctly. >>>>>4)I did not understand Fabien's post. >>>>> >>>>>I give the readers to decide which explanation they believe. >>>> >>>>I was waiting for you to bite in the bait. >>>> >>>>Because both explanations are true. >>>> >>>>What i find very simplistic minded from you is that the most important comments >>>>i made, namely that history pruning in the long run isn't going to work, >>>>provided you plan to work on your evaluation function, you completely ignore. >>>> >>> >>>history pruning works for fabien and Fruit has a good evaluation >>>function(otherwise it had no chance to get second place in WCCC inspite of using >>>one processor). >> >>Flawed reasoning. Maybe without the history pruning he would have become first ? >>Or maybe 10th. Point is that not every single thing in Fruit is perfect because >>he became second. >>All things together gave it that 2nd place. >> >>Tony > >I will make my post clearer Hmm, hardly > >I meant that the following claims are correct >1)history pruning works for fabien >2)Fruit has a good evaluation function(otherwise it had no chance to get second >place in WCCC inspite of using one processor). > >Note that 1 is correct based on testing and it is clear that fruit without >history pruning is stronger. Which would prove 1 incorrect ? > >I did not mean that the second place of fruit is a proof that history pruning >works for it but only that it proves that it has good evaluation function. No it doesn't. Maybe it was because he had a good book. Maybe because of hardly any bugs, maybe luck, maybe ... Fruits 2nd place only proves that all these things together, work well. You seem to have the impression that Fruits code contain a few magic lines of code that give it its strength. That's wrong, it's a few 100 or 1000 decent lines that do this. Tony > >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.