Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: New(?) search idea.

Author: Bruce Moreland

Date: 11:21:14 01/22/98

Go up one level in this thread



On January 22, 1998 at 13:33:42, Don Dailey wrote:

>Hi Andrew,
>
>The only reason the first move takes longest to search is because it
>is carrying all of the burden.  You can shift the responsibility to
>other moves but you cannot get something for nothing.  At some point
>you will have to come back and resolve the first move or ignore it
>in which case you are prunning the tree. (this is not something for
>nothing.)

Assume the following:

There are three legal moves in a position.

Your alpha beta bounds are initially -50, 50.

The value of the first move is 0, the value of the second move is -10,
and the value of the third move is also -10.

If you search the first move with your -50, 50 window,  you'll get back
your 0, so if you are using PVS you'll search the next two with 0,1, and
if you aren't you'll search them with 0,50, I guess.

Ok, that's the normal way to do it.

Another way would be to make a very lucky guess about the value of the
first move.  Let's say we guess that it is zero.  We then search the
next two moves with 0,1 or 0,50 depending upon our tastes in search
routines, and both of these fail low.

Did this take any longer than searching the last two moves in the other
example?  I think not.

But we are not done.  We now search the first move with the bounds
-50,50.  Did this take longer?  I don't think so.  So the whole thing
didn't take longer than the original search, either.

Now, if the value of the third move was really +30, you would have found
it sooner this way.

I think this was the whole point of the original post, although some of
the specifics have been changed in order to simplify things.  There are
ways to make this screw up badly, for instance if the value of the first
move is really +35, and the value of the third move is +30, you've just
totally killed yourself.  Of course you get killed in "our" way if the
value of the first one is +30 and the value of the third one is +35.

There was more to his post, he'd tried to compensate for some of this.

I don't think it would work well, but let's at least understand what
he's saying.

bruce



This page took 0.03 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.