Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: mate threat extension/null move

Author: Don Beal

Date: 12:02:40 10/01/04

Go up one level in this thread


On October 01, 2004 at 12:43:48, Stuart Cracraft wrote:

>Hi Don -- I remember reading your articles through the years
>especially that one on null move. Thanks for your interest.
>
>I did take your code and put it into my program and removed
>both Ross Boyd's and Uri Blass's ideas to test. Since they had
>already solved the problem of my slow WAC 141 from 95 down to
>5 seconds but Bob now tells me it's no good since it throws
>out the null move by disabling it for depth > 1 which is a
>very bad idea. So I can't name Ross nor Uri as receivers of
>the bet after all.
>
>Since that is the case, the $50 bet is still open. I will
>respect the wishes of donation of anyone winning the bet
>if a "donatee" is named as you did.
>
>Unfortunately, no one's code has yet won the bet but since it did
>not worsen the program performance on my test suite, I have
>kept yours in as permanent homage for the invention of null move!
>
>As the bet is still open, other ideas are entertained. Full code
>for entire program is available to well known people or people
>with strong programs (same thing I guess!)

Thanks for your kind remark about my articles.

I do have another suggestion regarding the code you posted.

Your code uses the null move for two distinct purposes (as
do most programs, quite rightly).  (1) Null move pruning, and
(2) threat extension.  Null move pruning requires a test to
see if the value resulting from a null move is >=beta.  Threat
extension requires a test to see if the value resulting from
a null move is <alpha-margin.  (Detecting mate threats is
equivalent to testing for <-MATE.)  Both tests require making
the null move and then executing a search, but the alpha-beta
bounds for the search for a prune test are different to
those you would give to the search for a mate-threat test.

Your code tries to answer both questions (prune available?, and
mate-threat exists?) with one call to search.  You seem to rely
on the search returning mate values outside the alpha-beta
bounds given to the search, if a mate sequence exists.
It is (with difficulty) possible to achieve that, but I
suspect your program doesn't always achieve it.  (Bob Hyatt
was making esentially the same point in an earlier post.)

I suggest you instead call two separate searches after making
the null moves, so your code would be something like:
    makenullmv();
    reduction = 2;
    // test for mate extension
    value = -search(bd,sdepth-1-reduction,ply,MATEV,MATEV+1,
	NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
    if (value < -MATEV) threat=1;
    // test for null move prune
    value = -search(bd,sdepth-1-reduction,ply,-beta,-beta+1,
	NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
    if (value >= beta) { /* do null move prune stuff */ }
    unmakenullmv();

where MATEV is a value large enough that only mate scores will
exceed it.  (Perhaps your value MATE is the same thing.)

The searches do not duplicate significant work, since the
alpha-beta bounds are different.  I think writing the code
this way is easier to understand.

This will at least ensure you are testing for mate extensions
correctly, which should help with Wac141.

Probably this still isn't enough to boost the CCC donation
fund, but it may help you inch closer to your goal.



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