Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Evaluation-based Reductions and/or Extensions

Author: Vasik Rajlich

Date: 00:47:11 12/29/03

Go up one level in this thread


On December 28, 2003 at 21:07:34, Tom Likens wrote:

>On December 28, 2003 at 16:55:49, Tord Romstad wrote:
>
>>Hi Tom!
>>
>>That's precisely what I am doing in Gothmog, as you probably know.  I'm glad
>>to hear that you try similar ideas, and that your first results are promising.
>>I've found that it takes lots of tuning and testing before it works well,
>>but I think such techniques have great potential in the long run.  If it's
>>done right, most of the improvements you do in your evaluation function will
>>automatically improve the accuracy of your search.
>
>When I first started experimenting with this idea I was *very* aggressive.
>Interesting it didn't really hurt the programs tactics and it seemed to
>reach much deeper depths while searching, so I was very excited.
>Unfortunately, when I played the new version against the older non-pruning
>version it lost rather badly.  So, now I'm starting out in a more
>conservative fashion and tuning the reductions based on actual games.
>
>>>My (obvious) question, how do other programmers deal with this phenomenon?
>>>I suppose ignoring it is one option, but I'm hoping there is a better
>>>solution.
>>
>>I agree that this problem is extremely annoying, and I have spent lots of
>>time and effort trying to find a solution.  Unfortunately, I still haven't
>>found any good ideas. I asked a question about exactly this problem here in
>>CCC just a couple of days ago, but the only person who replied was Dieter
>>Bürssner, who also hadn't found a better solution than just ignoring the
>>problem and hoping it wasn't too important.
>>
>>Tord
>
>The fact that neither yourself nor Dieter have found a satisfactory solution
>illustrates the difficulty of the problem.  It may be possible to tag these
>nodes when they are saved into the hash table and simply use them for move
>ordering, as Uri suggested.  I need to gather some data before I can make
>any kind of intelligent decision.  I do agree though that the concept has
>*massive* potential.  I wouldn't be surprised if this wasn't part of the
>"secret" of the commercial programs, (especially that Tiger fella) ;-)
>
>--tom

Hello,

It seems to me that there is a way to deal with this.

Let's say you're at node A going to node B. You can statically evaluate node A,
statically evaluate the move (A->B) in the context of node A, apply the
appropriate reduction/extension, and enter node B with the already
extended/reduced search depth. In this case, node B will go into the hash table
with that new remaining search depth.

If I understand the issue correctly, you'd also like to statically evaluate node
B before deciding on the reduction/extension for move (A->B). However, I am not
sure that that is necessary.

Let's consider the typical node which is a candidate for reduction. It should
have one of two qualities: A) it is extremely static B) it looks unpromising, ie
score somewhat below alpha.

In the case of very static nodes, it's pretty clear that you shouldn't need to
also look at the next move/node. In the case of an unpromising node, I was
thinking that you could do something like identify the few factors which could
change the evaluation. For example, if you're down two pawns but there are some
vague attacking prospects, then king safety would be that factor, and moves that
attack the king would be extended/not reduced, while moves which attack pawns on
the queenside are reduced. If you have an advanced passed pawn, then pushing
that pawn or supporting its advance would be the one way to bring the score
back, and moves which support that would be extended/not reduced. In all of
these cases, it seems to me to be enough to only consider the original node
(node A) and the moves themselves. The static evaluation of the next node can
then be done already knowing the new depth.

Unfortunately I haven't started to implement this, so there might be some issues
here.

At any rate, any reports on your experience in implementing this are welcome.
There appears to be almost nothing in the chess literature about this. The best
I found was Ed Schroeder's description of the pruning in Rebel, but he
concentrates on pruning positions with very bad scores rather than on pruning
irrelevant moves.

It does also seem to me that this is "the key" to a good program, or at least
that it could be "a key".

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.