Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Pseudo-code for verification search.

Author: Dan Homan

Date: 06:52:46 11/07/99

Go up one level in this thread


On November 07, 1999 at 07:23:03, Jeremiah Penery wrote:

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

I am not so sure.  So far I only have results on that one position... I think
the idea has promise and will test the other positions that Dann Corbit
posted when I get the time (probably later this week).

I have no idea how to get this to work in crafty.  It should make the search
only marginally slower (a few percent in my tests on the WAC positions), so you
really wouldn't see a very noticable slow down.

In my program this change was trivial (just the 3 extra lines you see above),
but crafty may do some move-tree history stuff that this would completely
screw up.  It may have other things going on which cause other problems.

 - Dan


>Jeremiah



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