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.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.