Author: Vincent Diepeveen
Date: 09:25:29 10/28/05
Go up one level in this thread
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. > Additional history moves >>regurarly get put back to a default value. So Fruit is not very consequent in >>trying moves. >> >>When i test games diep versus fruit, at slow time controls i saw Fruit not >>deteriorate when turning off history pruning. > >Note that I suggested reducing default history threshold in fruit2.2 from 70 to >50(I found that fruit could solve faster some tactical positons with that change >because it find them one or 2 ply earlier and the difference between history=50 >and history=70 is less than 1 ply) and fruit2.2 Uri that has only that change >did not perform better in CEGT rating list. > >http://www.husvankempen.de/nunn/ranglisteall.html > >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.