Threat in null move

[Pedro Castro]

In the null move, when we find a near value to a Mate, we extend because there is a threat.

Code: Select all

         if (value >= beta) {
            if (value > MATE-256)
               value = MATE-256;   // don't return unproven mates
            return value;
         }
         if (value < -MATE + 256) {
            threat = TRUE;
            ext++;
         }


Can somebody indicate me a position where when being analyzed you see this?

I have not been able to him to never see in a position.

I have used a matekiller for the ordination and that I find that it works me.

[bob]

try win at chess #141. Everyone using this mate extension (first recommended by Bruce Moreland so far as I know) reports finding it much faster with than without...

[Pedro Castro]

Thank you Bob,

In my case it doesn't seem to work, I extend a ply but I don't find any difference. If on the other hand it works me the matekiller.

Code: Select all

            if (mejor >= beta) {
               if ((pieza[lista[i].a] == VACIO) && lista[i].tipo < PROMOCION_A_DAMA) {
                  killer2[ply] = killer1[ply];
                  killer1[ply] = lista[i];
               }
               if (abs(puntos) > (MATE - 256))
                  matekiller[ply] = lista[i];
               // TTables
               store_hash(mejor, alpha, beta, depth, mejor_movimiento, threat);
               return beta;            
            }


The matekiller is ordered in third position after the move of the table hash and of the pv.

WAC 141

[diag]4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/1B3P2/PP3PK1/2Q4R w - - 0 1[/diag]

Whitout matekiller Qxf4 in 15 sec and mate in 3:35 sec
With matekiller Qxf4 in 10 sec and mate in 27 sec

[Tord Romstad]

try win at chess #141. Everyone using this mate extension (first recommended by Bruce Moreland so far as I know) reports finding it much faster with than without...

Yes. Here is the search output for Glaurung 060601 (on an Intel Core Duo 2 GHz, using one thread):

Mate threat extensions on:

Code: Select all

 2   -7.78     0:00      63 Kg1 Ne2+ Kg2 Nxc1 Rxc1                           
 2   -1.62     0:00     148 Kf1 Kf8                                           
 3   -1.08     0:00     319 Kf1 Kf8 Qc2                                       
 4   -1.20     0:00    1068 Kf1 Kf8 Rg1 Re2                                   
 5   -1.41     0:00    5499 Kf1 Re2 Qb1 Bb4 Be5                               
 6   -1.53     0:00   12683 Kf1 Re2 Qc3 b4 Qc4 Rxb2                           
 7   -0.89     0:00  103322 Kf1 a5 Rg4 Kf8 Qb1 Nd3 Qxd3 hxg4 fxg4             
 8   -0.61     0:00  201944 Kf1 Rde7 Bxe7 Rxe7 a3 Re8 Rg1 Re2                 
 8    7.61     0:00  329536 Qxf4 Be7 Bxf7+ Kxf7 Be5+ Kg8 Bxc7 Bxh4 Rxh4 Re1   
 9    7.44     0:00  349421 Qxf4 Be7 Bxf7+ Kxf7 Be5+ Kg8 Bxc7 Bxh4 Rxh4 Re2 Qg3
10   10.75     0:01  633361 Qxf4 Qd8 Qg5 Qxf6 Qxf6 Bc7 Qxg6+ Kf8 Qh6+ Ke7 Qxc6
                            Kd8 Rxh5
11      #6     0:01  701292 Qxf4 Bxf4 Rxh5 gxh5 Rxh5 Bh6 Rxh6 Qg3+ Kxg3 Rxd4 
                            Rh8#


Mate threat extensions off:

Code: Select all

 2   -7.78     0:00      63 Kg1 Ne2+ Kg2 Nxc1 Rxc1                           
 2   -1.62     0:00     148 Kf1 Kf8                                           
 3   -1.08     0:00     319 Kf1 Kf8 Qc2                                       
 4   -1.20     0:00    1068 Kf1 Kf8 Rg1 Re2                                   
 5   -1.41     0:00    5499 Kf1 Re2 Qb1 Bb4 Be5                               
 6   -1.53     0:00   12683 Kf1 Re2 Qc3 b4 Qc4 Rxb2                           
 7   -0.89     0:00   77503 Kf1 a5 Rg4 Kf8 Qb1 Nd3 Qxd3 hxg4 fxg4             
 8   -1.12     0:00  122647 Kf1 a5 Rg1 Kf8 Bg5 a4 Bxa4 bxa4 Bxf4 Bxf4 Rxf4   
 9   -0.61     0:00  310889 Kf1 Rde7 Bxe7 Rxe7 a4 bxa4 Bxa4 Qa5 Bxc6         
10   -0.34     0:01  670569 Kf1 Rde7 Bxe7 Rxe7 Rg1 Kf8 Rg3 Re8 Qd2 Re2       
11   -0.70     0:02   1044k Kf1 Rde7 Bxe7 Rxe7 Qb1 Kf8 Kg1 Ne2+ Kf1 Bb4 Kg2 Bd2
11    6.56     0:04   1808k Qxf4 Be7 Bxf7+ Kxf7 Be5+ Kg8 Rxh5 gxh5 Qg3+ Bg5   
                            Bxc7 Rh7 Kf1 Rg7 Rxh5
12      #6     0:05   2070k Qxf4 Be7 Rxh5 Bxf6 Qxf6 gxh5 Rxh5 Qg3+ Kxg3 Kf8   
                            Rh8#


Note that mate threat extensions actually help Glaurung find the right move three full plies earlier. This is highly unusual, though. The number of positions where these extensions help is quite low. Perhaps I should try playing without them for a while ...

Tord

[bob]

Here is crafty. First, with the "mate extension" set to normal .75 ply, running on my 750mhz laptop:

Code: Select all

                8->   1.26  -2.36   1. Kf1 a5 2. Rg1 Re2 3. Rxg6+ Nxg6
                                    4. Kxe2 Nxh4 5. Bxh4
                9     3.46     +1   1. Kf1!!
                9     6.76  -1.00   1. Kf1 Rde7 2. Bxe7 Rxe7 3. Rg1 Kf8
                                    4. Qd2 Ke8 <HT>
                9     7.23     +1   1. Qxf4!!
                9     7.45     +3   1. Qxf4!!
                9     7.79     +M   1. Qxf4!!
                9    54.61  Mat06   1. Qxf4 Bxf4 2. Rxh5 gxh5 3. Rxh5 Bh6
                                    4. Rxh6 Qh2+ 5. Kxh2 Kf8 6. Rh8#


Now with extension/mate=0 option to turn off that extension:

Code: Select all


                9     1.92     +1   1. Kf1!!
                9     3.88  -1.00   1. Kf1 Rde7 2. Bxe7 Rxe7 3. Rg1 Kf8
                                    4. Qd2 Ke8 5. Rg5
                9->   3.94  -1.00   1. Kf1 Rde7 2. Bxe7 Rxe7 3. Rg1 Kf8
                                    4. Qd2 Ke8 5. Rg5
               10     4.48     -1   1. Kf1
               10     5.70  -1.48   1. Kf1 Rde7 2. Bxe7 Rxe7 3. Rg1 Kf8
                                    4. Qd2 Ke8 <HT>
               10->   7.27  -1.48   1. Kf1 Rde7 2. Bxe7 Rxe7 3. Rg1 Kf8
                                    4. Qd2 Ke8 <HT>
               11    12.45  -1.36   1. Kf1 Kf8 2. Rxh5 gxh5 3. Rxh5 Re1+
                                    4. Kxe1 Qa5+ 5. Kf1 Nxh5 6. Qh6+ Ke8
                                    7. Qh8+ Bf8 8. Qxh5 Qd2
               11    13.77     +1   1. Qxf4!!
               11    14.18     +3   1. Qxf4!!
               11    15.00     +M   1. Qxf4!!
               11     1:50  16.31   1. Qxf4 Be5 2. dxe5 Qxe5 3. Bxe5 Rd5
                                    4. Bxd5 cxd5 5. Qd4 Rd8 6. Qxa7
               11->   1:50  16.31   1. Qxf4 Be5 2. dxe5 Qxe5 3. Bxe5 Rd5
                                    4. Bxd5 cxd5 5. Qd4 Rd8 6. Qxa7




Notice it found the right move in about twice as long, but it didn't get anywhere near the right score...

Hope that helps...

[Pedro Castro]

FEN: 4r1k1/p1qr1p2/2pb1Bp1/1p5p/3P1n1R/1B3P2/PP3PK1/2Q4R w - - 0 1

The threat extension doesn't work for my in null move, without her:

Code: Select all

DanaSah v2.25:
   2   00:00          1.385   69.250   -2,47   1.Kf1 Nd5 2.Bxd5 cxd5
   3   00:00          2.552   127.600   -2,47   1.Kf1 Nd5 2.Bxd5 cxd5
   4   00:00         24.812   310.150   -1,76   1.Kf1 a5 2.Rg1 a4 3.Bc2
   5   00:00         40.766   339.716   -2,17   1.Kf1 a5 2.Rg1 a4 3.Bd1 Nd3
   6   00:00         69.944   368.126   -2,22   1.Kf1 a5 2.Rg1 a4 3.Bc2 Nd5 4.Qg5 Nxf6 5.Qxf6
   7   00:00        300.935   395.967   -1,66   1.Kf1 Kf8 2.Be5 Rxe5 3.dxe5 Bxe5 4.Rg1 Nd3
   8   00:01        665.183   421.001   -1,44   1.Kf1 a5 2.Rg1 Kf8 3.Rg3 Re2 4.Kg1 Nd5 5.Qh6+ Ke8
   9   00:05      2.376.311   433.633   -0,50   1.Kf1 Rde7 2.Bxe7 Rxe7 3.Rg1 Kf8 4.Rg3 Re2 5.Kg1 a5
  10   00:09      4.412.174   441.659   +8,52   1.Qxf4 Bxf4 2.Rxh5 gxh5 3.Rxh5 Bh6 4.Rxh6 Qg3+ 5.fxg3 Re2+ 6.Kf1 Rh2 7.Rxh2
  11   00:11      5.145.273   447.804   +M6   1.Qxf4 Bxf4 2.Rxh5 gxh5 3.Rxh5 Bh6 4.Rxh6 Qg3+ 5.Kxg3 Kf8 6.Rh8+


[Tony van Roon-Werten]

Only do the extension in case you fail high. That way you reduce the cost.

No point in doing the extension in case your normal search (without the extension) returns something like -rook

Tony

[bob]

Bad idea. In wac141, Qxf4 loses a queen for a knight, -9 + 3 is -6, which is worse than a rook down. But by extending, you get it back and then some...

[Tord Romstad]

Bad idea. In wac141, Qxf4 loses a queen for a knight, -9 + 3 is -6, which is worse than a rook down. But by extending, you get it back and then some...

I think you are misunderstanding Tony's idea. I could be wrong, but I think he meant the following: When you find out that you are threatened by a mate in one, don't extend immediately. Do a search to normal depth first. If this search fails high, re-search with extended depth.

I haven't tried this myself, but it sounds like an idea worth trying.

Tord

[bob]

OK, didn't read it like that "fail-high" is often used incorrectly and I just ignored it completely. But let's figure this out to be sure I follow:

After Qxf4 black is going to try the recapture and since he won't see the mate, he will fail high being over a rook up, so now he extends and researches the same tree one ply deeper? But what if this is a Qxf4 Qxf4 and now material is equal, and qxf4 does not fail high, but if you look a ply deeper you get mated? Here you would not look a ply deeper.

The simplicity of the null-move mate threat is that if you make a null-move anywhere (and I try null moves at _every_ node, and you get mated, then something is definitely "up" about the position... It would seem that restricting it as above might miss things. I'd rathere extend it always (much simpler, no re-search needed) to keep the code simple and not miss threats that being cuter might miss...

[Steve Maughan]

I think you are misunderstanding Tony's idea. I could be wrong, but I think he meant the following: When you find out that you are threatened by a mate in one, don't extend immediately. Do a search to normal depth first. If this search fails high, re-search with extended depth.

I haven't tried this myself, but it sounds like an idea worth trying.
Tord

I use a similar approach in Monarch for one-reply to check situations. If there is only one move I don't extend immediately but if the return value is > alpha (i.e. relevant) then I research with an extended depth. It seems to work well.

If you only extend for fail highs then you may miss the extension when the position is encountered again as a PV node.

Regards,

Steve

[Tony van Roon-Werten]

OK, didn't read it like that "fail-high" is often used incorrectly and I just ignored it completely. But let's figure this out to be sure I follow:

After Qxf4 black is going to try the recapture and since he won't see the mate, he will fail high being over a rook up, so now he extends and researches the same tree one ply deeper? But what if this is a Qxf4 Qxf4 and now material is equal, and qxf4 does not fail high, but if you look a ply deeper you get mated? Here you would not look a ply deeper.

The simplicity of the null-move mate threat is that if you make a null-move anywhere (and I try null moves at _every_ node, and you get mated, then something is definitely "up" about the position... It would seem that restricting it as above might miss things. I'd rathere extend it always (much simpler, no re-search needed) to keep the code simple and not miss threats that being cuter might miss...

Problem is that you will extend a lot of cases where one side is significantly ahead, opponent nullmoves, you say, oh I can checkmate let's extend, wich will just burn nodes.

To Steve: In pv I will always extend.

In XiniX I use an extra safeguard for burning nodes: If the failhigh move is capturing the checkmating piece, it will not extend. (get that for free in XiniX's eval)

I got the idea from Deep Blue: a singular move can only be singular of it fails high. This goes for nullmove threath extensions, singular replies and more...

Side effects: Your hashtable statistics (first move fail high percentage) will go crazy, reaching 95% easily.

Tony

[bob]

OK, didn't read it like that "fail-high" is often used incorrectly and I just ignored it completely. But let's figure this out to be sure I follow:

After Qxf4 black is going to try the recapture and since he won't see the mate, he will fail high being over a rook up, so now he extends and researches the same tree one ply deeper? But what if this is a Qxf4 Qxf4 and now material is equal, and qxf4 does not fail high, but if you look a ply deeper you get mated? Here you would not look a ply deeper.

The simplicity of the null-move mate threat is that if you make a null-move anywhere (and I try null moves at _every_ node, and you get mated, then something is definitely "up" about the position... It would seem that restricting it as above might miss things. I'd rathere extend it always (much simpler, no re-search needed) to keep the code simple and not miss threats that being cuter might miss...

Problem is that you will extend a lot of cases where one side is significantly ahead, opponent nullmoves, you say, oh I can checkmate let's extend, wich will just burn nodes.

To Steve: In pv I will always extend.

In XiniX I use an extra safeguard for burning nodes: If the failhigh move is capturing the checkmating piece, it will not extend. (get that for free in XiniX's eval)

I got the idea from Deep Blue: a singular move can only be singular of it fails high. This goes for nullmove threath extensions, singular replies and more...

What about PV-singular as opposed to FH-singular? In the last version or two of Cray Blitz, I did both based on Hsu's published description... or are you lumping the PV-singular and FH-singular into one "FH-type group"??

Side effects: Your hashtable statistics (first move fail high percentage) will go crazy, reaching 95% easily.

Tony

[Tony van Roon-Werten]

OK, didn't read it like that "fail-high" is often used incorrectly and I just ignored it completely. But let's figure this out to be sure I follow:

After Qxf4 black is going to try the recapture and since he won't see the mate, he will fail high being over a rook up, so now he extends and researches the same tree one ply deeper? But what if this is a Qxf4 Qxf4 and now material is equal, and qxf4 does not fail high, but if you look a ply deeper you get mated? Here you would not look a ply deeper.

The simplicity of the null-move mate threat is that if you make a null-move anywhere (and I try null moves at _every_ node, and you get mated, then something is definitely "up" about the position... It would seem that restricting it as above might miss things. I'd rathere extend it always (much simpler, no re-search needed) to keep the code simple and not miss threats that being cuter might miss...

Problem is that you will extend a lot of cases where one side is significantly ahead, opponent nullmoves, you say, oh I can checkmate let's extend, wich will just burn nodes.

To Steve: In pv I will always extend.

In XiniX I use an extra safeguard for burning nodes: If the failhigh move is capturing the checkmating piece, it will not extend. (get that for free in XiniX's eval)

I got the idea from Deep Blue: a singular move can only be singular of it fails high. This goes for nullmove threath extensions, singular replies and more...

What about PV-singular as opposed to FH-singular? In the last version or two of Cray Blitz, I did both based on Hsu's published description... or are you lumping the PV-singular and FH-singular into one "FH-type group"??

Yes. By changing the "fail high" criterium into "above alpha" wich means pv nodes are automaticly included. And since I know a pv node will return a score>alpha I might as well extend them before searching.

BTW The extend on fail high doesn't seem to work for certain type of moves (like checks), but that's probably because I haven't figured out myself wether those moves should be singular for the side giving them or the side receiving them.

ie giving a check might be dangerous when it's the move failing high, but moving out of check causing a fail high isn't fun either.

Tony

[Steve Maughan]

Yes. By changing the "fail high" criterium into "above alpha" wich means pv nodes are automaticly included. And since I know a pv node will return a score>alpha I might as well extend them before searching.

It may be a good idea to extend them anyway - of course just because beta != alpha + 1 does not mean than the return value will always be > alpha, especially with a windowing heuristic.

Regards,

Steve

[Tony van Roon-Werten]

Yes. By changing the "fail high" criterium into "above alpha" wich means pv nodes are automaticly included. And since I know a pv node will return a score>alpha I might as well extend them before searching.

It may be a good idea to extend them anyway - of course just because beta != alpha + 1 does not mean than the return value will always be > alpha, especially with a windowing heuristic.

Regards,

Steve

Hmm, I don't think I have a lot of pv nodes with score<=alpha, but then again I don't use aspiration windows.

Anyway, I send a nodeType variable to the search function on which I base these decisions. When a research is done, I change the nodeType to PV_NODE.

If this returns a score<=alpha, it would have to be a false PV node I guess.

ie at each node alpha is either -inf or previousBestScore.

Tony