Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Toga Clone

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 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.