Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Mixing alpha-beta with PN search

Author: Tord Romstad

Date: 22:31:03 01/19/04

Go up one level in this thread


On January 19, 2004 at 18:03:23, Jay Scott wrote:

>On January 18, 2004 at 06:05:06, Tord Romstad wrote:
>
>>formulate some sort of goal, and call the PN search to determine whether this
>>goal could be achieved or not.
>
>That is an interesting idea, but how are you going to choose the goals? The
>program has to identify the goal ("queen this pawn") and its relation to the
>game outcome ("you win"--there should be no exceptions, or else the exceptions
>should be identified), and the goal should be tractable to proof-number search,
>or the program will waste time on fruitless searches.

Yes, identifying good goals is a very difficult problem, of course.

>That is great if you can do it, but it sounds hard.

Very hard, but perhaps worth a try.  I like to experiment with such
unusual ideas and techniques.  Even when they don't work (which is
usually the case), I can often learn something useful from the
experiments.

>Ideas:
>
>Perhaps a small expert system is called for, to choose the goals.

Yes, I've been considering something like this.

>One way to deal with possible exceptions is to use the main game search: PN
>search says yes, this vital pawn can be captured, and you end up in this
>position if you do it. Is this position really the win that was expected? What
>does the main search say? This could get expensive if there are many ways to win
>the pawn, and some of them turn out to be bad.

In many cases, I think the problem of exceptions can be handled by using
the value of the normal static evaluation function as one condition of
the goal.  For instance, the goal could be "capture this pawn, with a
static eval of at least 1.50 and no hanging pieces in the resulting
position".

But perhaps it is better to use the results of the PN search only for
move ordering, move selection and extension decisions.  This seems
safer, but of course also much more expensive.

>You want to feed as much information as possible over from the PN searches to
>the main search. If the PN search can produce definite scores or bounds for
>positions it reaches, you want to stuff those into the hash table for the main
>search to reuse. That could potentially be a big win.
>
>Multiprocessor would be good: The goals could be farmed out and solved
>independently. With a sufficiently large number of processors, identifying the
>tractability of each goal becomes less important. You can let many of the
>searches time out, as long as some of them pay.

I think I'll have to wait a very long time before I have sufficiently
many processors to use that I can make something like this work, but
it would be cool.

Thanks for the ideas!

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.