Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: mate threat extension/null move

Author: Stuart Cracraft

Date: 07:23:20 09/29/04

Go up one level in this thread


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




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