Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: mate threat extension/null move

Author: Stuart Cracraft

Date: 16:13:55 10/01/04

Go up one level in this thread


On October 01, 2004 at 15:02:40, Don Beal wrote:

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

I see your point and have put it under a "NULLBEAL" conditional
compilation. Initial testing gave a 5% worse result and I think
all the settings are correct. The extra search does seem to have
some bad effects:

Before double-search

+ 7.23/22.74 82% 247/300 ha=33 302.85 69122512 230408/1/228240
0/414899/376597/0/16986524/259220

After double-search

+ 5.63/20.38 77% 232/300 ha=26 303.42 75126144 250420/1/247600
0/419336/230182/0/26909694/210430

So about 1.6 fewer plies searched on average in main search and
2 plies less deep for maximum ply researched. Although speed was
up from 228k to 247k nps the total nodes search jumped from 69M
to 75M.

Here is the code:
  if (null move okay to do) {
#ifndef NULLBEAL
    value = -search(bd,sdepth-1-reduction,ply,-beta,-beta+1,
        NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
    if (value == -MATE+ply+2) threat=1;
#endif
#ifdef NULLBEAL
    // test for mate extension
    value = -search(bd,sdepth-1-reduction,ply,MATE-1,MATE,
        NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
    if (value < -MATE) { threat=1; printf("threat\n"); pbd(bd); getchar(); }
    // test for null move prune
    value = -search(bd,sdepth-1-reduction,ply,-beta,-beta+1,
        NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
#endif
    if (value >= beta) {
       :


Stuart



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