Author: Uri Blass
Date: 01:34:49 10/30/05
Go up one level in this thread
On October 30, 2005 at 03:27:39, Tony Werten wrote: >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 know tests that show better result when history pruning parameter is reduced. The results that I saw in tests suggest better result for the default history pruning and not for reducing it to 50. If I reduce it to 0 almost always fruit is slower than the default in finding the right move even if fruit can find the right move at smaller depth. > >> >>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. I think that it is impossible to get good results without good evaluation. I do not claim that good evaluation is enough for good results but it is a necessary condition. Uri
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.