Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: mate threat extension/null move

Author: Robert Hyatt

Date: 07:37:08 09/29/04

Go up one level in this thread


On September 29, 2004 at 10:23:20, Stuart Cracraft wrote:

>On September 28, 2004 at 10:25:16, Robert Hyatt wrote:
>
>>On September 28, 2004 at 00:01:15, Stuart Cracraft wrote:
>>
>>>On September 27, 2004 at 18:17:19, Robert Hyatt wrote:
>>>
>>>>On September 25, 2004 at 16:35:05, Stuart Cracraft wrote:
>>>>
>>>>>On September 25, 2004 at 16:02:08, Andrew Platt wrote:
>>>>>
>>>>>>On September 25, 2004 at 10:30:52, Rick Bischoff wrote:
>>>>>>
>>>>>>>Hi,
>>>>>>>
>>>>>>>I am confused about the mate threat extension.  I have the following code:
>>>>>>>
>>>>>>>search ( depth, alpha, beta )
>>>>>>>
>>>>>>>->check extension
>>>>>>>->else pawn extension
>>>>>>>
>>>>>>>->if depth <= 0 do the queiscent
>>>>>>>
>>>>>>>->if checkReps return draw
>>>>>>>->if insufficnetMaterial return draw
>>>>>>>
>>>>>>>->Probe the hash table and return if good
>>>>>>>
>>>>>>>->if not in check and depth>3 and last move was not null and material is ok:
>>>>>>>->-> do null move
>>>>>>>->-> x = -search(depth - 3, -beta, -beta +1 )
>>>>>>>->-> undo null move
>>>>>>>->-> if ( x >= beta ) return beta
>>>>>>>->-> if ( x < (-MATE+MAXPLY) ) cout << "found mate"
>>>>>>>
>>>>>>>->normal alpha/beta stuff
>>>>>>>
>>>>>>>end search
>>>>>>>
>>>>>>>"found mate" never gets printed out in WAC141 unless I change the null move to a
>>>>>>>full width search... Why?  Well, I shouldn't say never, but I let it run to ply
>>>>>>>9.
>>>>>>
>>>>>>if (x >= beta) return beta
>>>>>>
>>>>>>means that you don't return the actual scores, just the cutoff. This is fine
>>>>>>until you try to detect threats. Then you need to return the actual scores
>>>>>>because only those will have the mate in them.
>>>>>>
>>>>>>In WAC 141 you should hit a bunch of mate threat extensions on the way to the
>>>>>>lowest ply because each time your Rooks take a pawn, and then the bishop, you
>>>>>>should trigger one. In my search it still isn't enough to counteract the drop
>>>>>>into qsearch where I don't consider checks. I've given up on generating the mate
>>>>>>score in a short time right now (I have plenty of other problems!). It's enough
>>>>>>that the first few plies in the PV are correct so if it actually hit it, it
>>>>>>would find it. Of course that only works here because it turns out that the
>>>>>>Queen sacrifice is good more material as well as mate!
>>>>>>
>>>>>>Andy.
>>>>>
>>>>>So do you solve WAC 141 in a reasonable amount of time?
>>>>>I don't and my code returns all values, does a null move
>>>>>with -beta,-alpha, checks if the returning value is
>>>>>equal to -MATE+ply+2 to extend (but doesn't extend it if
>>>>>already in check), and I return -MATE+ply when in check
>>>>>in the main search. In quiescence, I pass back to the main
>>>>>search if in check, but I don't search checking moves unless
>>>>>they are captures.
>>>>>
>>>>>Anyway, with the above, WAC 141 is out of reach and no one
>>>>>has been able to help it!
>>>>
>>>>
>>>>If you do mate threat right, you should find this quickly.  Here is Crafty on a
>>>>single-CPU 2.8ghz PIV:
>>>>
>>>>                8->   1.58  -1.20   1. Kf1 a5 2. Rxh5 gxh5 3. Rxh5 Re1+
>>>>                                    4. Kxe1 Nxh5 5. Qg5+ Kf8 6. Qh6+ Kg8
>>>>                                    7. Qxh5
>>>>                9     3.91  -1.20   1. Kf1 a5 2. Rxh5 gxh5 3. Rxh5 Re1+
>>>>                                    4. Kxe1 Nxh5 5. Qg5+ Kf8 6. Qh6+ Kg8
>>>>                                    7. Qxh5
>>>>                9     4.38     +1   1. Qxf4!!
>>>>                9     4.63     +3   1. Qxf4!!
>>>>                9     5.11     +M   1. Qxf4!!
>>>>                9    49.31  Mat06   1. Qxf4 Bxf4 2. Rxh5 gxh5 3. Rxh5 Bh6
>>>>                                    4. Rxh6 Qh2+ 5. Kxh2 Kf8 6. Rh8#
>>>>                9->  49.31  Mat06   1. Qxf4 Bxf4 2. Rxh5 gxh5 3. Rxh5 Bh6
>>>>                                    4. Rxh6 Qh2+ 5. Kxh2 Kf8 6. Rh8#
>>>>
>>>>4 secs to find it.  49 secs to produce the mate score.
>>>>
>>>>With mate threat extension disabled (ext/mate=0 command) I see this:
>>>>
>>>>               10->  20.95  -1.31   1. Kf1 Kf8 2. Rxh5 gxh5 3. Rxh5 Re1+
>>>>                                    4. Kxe1 Nxh5 5. Qh6+ Ke8 6. Qxh5 Bf4
>>>>               11    40.48  -1.08   1. Kf1 a5 2. Rxh5 gxh5 3. Rxh5 Re1+
>>>>                                    4. Kxe1 Nxh5 5. Qg5+ Kf8 6. Qxh5 Bb4+
>>>>                                    7. Kd1 Qd6
>>>>               11    43.03     +1   1. Qxf4!!
>>>>               11    43.94     +3   1. Qxf4!!
>>>>               11    52.35     +M   1. Qxf4!!
>>>>               11     5:12  Mat06   1. Qxf4 Bxf4 2. Rxh5 gxh5 3. Rxh5 Bh6
>>>>                                    4. Rxh6 Qh2+ 5. Kxh2 Kf8 6. Rh8#
>>>>               11->   5:12  Mat06   1. Qxf4 Bxf4 2. Rxh5 gxh5 3. Rxh5 Bh6
>>>>                                    4. Rxh6 Qh2+ 5. Kxh2 Kf8 6. Rh8#
>>>>
>>>>
>>>>SO it finds the right move 2 plies quicker, 10X faster, with than without the
>>>>mate threat extension...
>>>>
>>>>This with a simple q-search with no checks, no check evasion or anything else..
>>>
>>>I obviously don't do mate threat right.
>>>
>>>Taking the result of the null move with -beta,-beta+1 or -beta,-alpha, or
>>>MINIMUM_INT,MAXIMUM_INT, and checking that result if < beta for
>>
>>
>>There is the problem.  If you can't return a score outside alpha/beta window,
>>this threat detection will not work.  99.99999% of the time alpha is > MATE.
>>You have to make your null-move search return a score < alpha in this case so
>>that when it fails low, you notice that not only did not moving look bad, it got
>>you mated instantly.  If you can't return a score < alpha from the next ply, the
>>mate threat won't work.
>>
>
>Not happening here unless you see something I don't.
>
>I modified my code so that -MATE is < MINNUM and +MATE is > MAXNUM.
>My search normally goes from evaluation-MARGIN,evaluation+MARGIN
>where MARGIN is 1/3 of a pawn. If I get a faillow, it will research
>with the window MINNUM,MAXNUM.
>
>If a mate is detected within a call to null move, it is returned up
>through the tree in the main search. I don't prevent this. There is
>clearl a line that returns -MATE+ply. This is matched by code below
>for detection of the threat.
>
>  best = alpha;
>  inpv = insidepv(ply);
>  if (hashed && MATESCORE(score)) donull = 0;
>  if (!threat && donull && (material[stm^1]>weights[0][stm^1][rook]) && !checked
>      && !inpv) {
>    makenullmv();
>    reduction = 2;
>    value = -search(bd,sdepth-1-reduction,ply,-beta,-beta+1,
>	NULLNOTOK,mvstr,SAVETOP,verify,REDUCENOTOK,checked);
>    if (value == -MATE+ply+2) threat=1;
>    if (value >= beta) {
>	unmakenullmv();
>        best = value;
>	if (hashed) savemove(&sml[0],hashmv);
>	else if (legalmove2(bd,pv[ply])) savemove(&sml[0],pv[ply]);
>        else savemove(&sml[0],nullmv);
>	flag = NULLM;
>	goto donenull;
>
>    }
>    unmakenullmv();
>    nulled=1;
>  }
>  if (!extended && threat /* && MATESCORE(beta) */) {
>    extend=1.0; extended=1; depth++;
>  }
>
>In the above if, I put a printf and see it showing lots of mates
>on various problems, and lots of extensions. In a worst case problem,
>I might get 8000 mate threat extensions in 1 second.
>
>So anyway, that is working, but something more subtle isn't working
>and I don't know what it is.
>
>This is a strange one for me. I've looked at Crafty's code and GES's
>code in an attempt to ameliorate, to no avail.
>
>For this one, I am *paying* $50 to the first person who can point out
>the solution to make my mate threat work and make the Win at Chess #141
>problem time drop from 95 seconds on a 1ghz p3 to ~30 seconds or less
>on the same box.
>
>Stuart


The above code is not where the problem appears to be for returning mate scores.
 At the _next_ ply you do a normal search, and and you find a move that delivers
mate.  The problem is, the last piece of code for your _normal_ search had
something like this:

     if (value > beta) return(beta).

That will kill it because you return beta, not the mate score you are looking
for...  Note that the above is based on the code you posted for your regular
search a week or so ago...




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.