Author: Vasik Rajlich
Date: 05:36:24 03/10/05
Go up one level in this thread
On March 10, 2005 at 05:01:13, Tord Romstad wrote: >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. This makes a lot more sense, but it really shouldn't be called a history reduction. Maybe "history safeguard on fail-low reduction". I think when someone says that they don't believe in the history table as a sound basis for pruning, they mean that it's too noisy to justify unbalancing the tree, since all things being equal a balanced tree is best. Here you are actually using the history table to keep the tree balanced, with the driving force of the reduction being the earlier fail-low moves. > >>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 is true. More speed is always good, as is a more focused search. The big question is scaling. Expanding each node provides a lower utility than expanding previous nodes (and a greater utility than expanding future nodes). It's the basic nature of search, and has been proven in a number of places. Changes to the evaluation function don't suffer from this. I think a lot of the older programmers are stuck in the framework of speed, speed, speed. Franz Morsch appears to be trying to get out of it - and taking a bit of a hit along the way. Christophe Theron OTOH doesn't appear to believe it - the newest Tiger is even faster than its predecessors. Let's see what the future brings ... Vas
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.