Author: Vincent Diepeveen
Date: 07:49:21 10/28/05
Go up one level in this thread
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. 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. Basic problem i have against history pruning is that the assumption you make with such reductions is that that searching deeper won't give positional better moves anymore. If that argument is valid for your chessprogram, then use history pruning. Because it checks out your mainline a ply or 1.5 - 2 ply deeper. You will see simple things even faster, but complicated positional things, well if your program can't find them anyway, why care for them? Therefore for most programs history pruning qualifies for blitz. Please note in world champs 2005 diep played with history pruning, but a modification of it, turned on. No i didn't use history tables to determine whether a move can be pruned. Why not simply have a hard limit after 3-4 moves? That's what i did. It shows the positional problems the algorithm has sooner simply. You start comparing a simple line of 15 ply with a pruned line of 8 ply. Guess what happens when in root your score drops? Vincent
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.