Author: Tord Romstad
Date: 02:01:13 03/10/05
Go up one level in this thread
On March 09, 2005 at 23:13:30, Anthony Cozzie wrote: >1. History pruning does NOT seem like a good idea. The history table is >completely unrelated to the current position, and yet you want to prune based on >it? Given that Glaurung does use history reductions, this may seem strange, but in fact I agree with the above sentence. But you miss the point, probably because "history reductions" is an unfortunate name. The history table is not really a very important (nor even necessary) part of the pruning mechanism. History reductions, the way I use them, can be described as follows: In non-PV nodes, if the first N moves return scores below alpha, I do a pre-search with reduced depth for the remaining moves, except for moves which appear particularly promising, forcing, or otherwise interesting. Moves for which this reduced-depth search fails low case are pruned without doing a full-width search. An important question is, of course, which criterions to use when deciding which of the moves late in the move list deserve a full-depth search. Of course, tactical moves like captures, promotions, checks and all moves which are extended for some reason should always be searched with full depth. Other moves which may deserve a full-depth search are passed pawn pushes, moves which threaten enemy pieces or move hanging pieces to safe squares, and moves which increase the pressure against the enemy king. The history counters only enter the picture as a last safety measure: If a move is still a candidate for reduction after testing all other criterions, look at the history counter for the move. If the move has often failed high in the past, the move may still be worthy of a full-depth search. In Glaurung, I do not yet use many other criterions except history data. Even this gives me about 100 Elo points (or at least it did the last time I tested, which is admittedly a very long time ago). No doubt, the explanation for this is that (as Vincent likes to point out) in a sufficiently weak engine, all pruning tricks appear to work. But I still think the underlying observation used in history reductions (that the search usually fails low at non-PV nodes where the first N moves return scores below alpha) can be used to implement sound and effective pruning systems in stronger engines. >IMO you aren't going to get 100 elo (or even 40) with search tricks. You would >have to improve the evaluation, which is the primary area where it fails in >comparison to the commercials. I think Crafty (and all other amateur engines) are at least as far behind the commercials in search as in evaluation. At least this appears to be the case with Hiarcs and Chess Tiger, the only commercial programs which I have played with recently (Hiarcs on Mac OS X and PalmOS, Chess Tiger on PalmOS). When watching Glaurung play against Hiarcs, it looks like Hiarcs is running on a 10 times faster computer. Glaurung is so badly outsearched that it is painful to watch. Hiarcs constantly sees tactics several full moves before Glaurung realizes that it is in trouble. This never happens against Crafty or Fruit. It is also amazing to see how well Chess Tiger, a 68k program, performs while searching only about 300 nodes/second on my Tungsten T. When I slow down Glaurung to the same speed, it is pathetically weak (only about 100 points stronger than TSCP). Whatever Hiarcs and Chess Tiger are doing in their search, it is vastly superior to what Crafty (and all other amateurs) does. Tord
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.