Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Pseudo-code for verification search.

Author: Jeremiah Penery

Date: 04:23:03 11/07/99

Go up one level in this thread


On November 06, 1999 at 07:19:19, Dan Homan wrote:

>Ok,  your standard null-move code looks something like this....
>
>  search(position current, int alpha, int beta, int depth) {
>
>    .....
>    position next;
>    int score;
>
>    /* null move */
>    if( /* conditions to decide if null-move is appropriate */ ) {
>      next = makeNull(current);
>      if(depth >= R+1) {
>        score = -search(next, -beta, -beta+1, depth-R-1);
>      } else {
>        score = -Qsearch(next, -beta, -beta+1);
>      }
>      if(score >= beta) return(beta);
>    }
>
>    .....
>
>  }
>
>I simply modified the null move code to look like
>
>    /* null move */
>    if( /* conditions to decide if null-move is appropriate */ ) {
>      next = makeNull(current);
>      if(depth >= R+1) {
>        score = -search(next, -beta, -beta+1, depth-R-1);
>      } else {
>        score = -Qsearch(next, -beta, -beta+1);
>      }
>      /* verification search */
>      if(score >= beta && depth >= R+1) {
>        next = current;
>        set flag for no null move on next search;
>        score = search(next, beta-1, beta, depth-R-1);
>      }
>      if(score >= beta) return(beta);
>    }
>
>You can see that the verification search is just 3 or 4 lines of code.
>All it does is search the current position to a reduced depth with
>no null move.... this only happens when the null move is going to force
>a fail high, and it should confirm that we are not in zug.  The time spent
>doing these verification searches is very small, so I think this might
>be a good addition.  I still have to do tests on those positions you
>posted.

Trying to get this to work in Crafty, I tried several things.  Unfortunately,
none of them worked.

First, I tried what you did above.  I think it was performing some verification
searches, because it was slower than normal, but I never got a different
move/score from normal.  With this scheme I was also getting "bad move from hash
table" errors. :(

Then I tried to do two separate searches - The normal null-move search, and then
a reduced-depth non-null move search, when the depth is low enough already (so
it wouldn't take too much time), then use the non-null score if it differs from
the other one.  This also didn't work.  Results about the same as above, but no
errors.

I tried to implement double null-move, but I couldn't figure out how to make
this work properly, either.  I may work on this some more, since I only tried a
couple different things.

The only thing I've found that works so far is to simply turn off null-move
below a certain depth.  Of course, this slows down the search a bunch, though.
Any other ideas on what I can try?  I really would like to make this idea, or a
similar one, work, because it's a good one. :)

Jeremiah



This page took 0.04 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.