Quiescence Search Explosions

[xsadar]

Here is a useful position for testing quiescent explosion:
[D]1B1Q2K1/q1p4P/4P3/3Pk1p1/1r1NrR1b/4pn1P/1pRp2n1/1B2N2b w - - c0 "415"; c1 "0"; bm Rxc7; ce 32764; dm 2; pv Rxc7 g4 Rxe4#;

Interesting. Here's the result (as sent to an xboard/winboard gui) with a version of my engine with the old bad move ordering:

Code: Select all

1 357 5 13050 h7h8q
2 427 10 30528 f4f5 e5d4
3 427 11 34868 f4f5 e5d4 b8a7
4 32765 21 70543 c2c7 d2e1q f4e4

and with my newest version with new and improved move ordering:

Code: Select all

1 452 0 498 h7-h8=Q (nps=infM)
2 352 0 2943 h7-h8=Q Ke5xf4 (nps=1.472M)
3 652 0 6292 h7-h8=Q Ke5xf4 Bb8xa7 (nps=1.573M)
4 32765 2 32073 Rc2xc7 d2xe1=Q Rf4xe4 (nps=1.234M)

70,543 nodes compared to 32,073. Note that there are a few other changes as well, which is not so good for comparison purposes. I'm not sure what exactly accounts for the huge difference in NPS (about 1.2M for new and 0.33M for old). Perhaps it's (at least partly) because my new version searches the hash move before generating captures and my old one generated captures before searching ANY moves.

Compared to other positions I've found, this one is surprisingly easy for my engine's old move ordering.

This one is MUCH worse:

[D]r1bqkb1r/ppp5/2n4p/3p1pp1/Q2PnP2/2PB4/PP1NN1PP/R1B2RK1 b kq - 1 10

Old version(to depth 5):

Code: Select all

1 18 14 45342 c8e6
2 15 31 112052 c8e6 d2b3
3 16 277 1099640 c8e6 e2g3 g5g4
4 12 1068 4270555 c8e6 d2f3 f8d6 f4g5
5 13 4982 20052422 c8e6 d2f3 f8e7 f3e5 d8d6

New version:

Code: Select all

1 1 0 118 Ne4xd2 (nps=infM)
2 -10 0 570 Bc8-e6 Nd2xe4 (nps=infM)
3 18 0 2533 Bc8-e6 Nd2xe4 f5xe4 (nps=1.266M)
4 -7 1 16994 Bc8-e6 f4xg5 h6xg5 Nd2xe4 (nps=1.133M)
5 7 6 85270 Bc8-e6 c3-c4 g5xf4 Ne2xf4 Ne4xd2 (nps=1.332M)

That's 20,052,422 nodes for my old version compared to only 85,270 for my new version.

[Zach Wegner]

I am not sure I understand this:

If below 8 ply Rxc7 is refuted by a null move, the node following that null-move must be a low-failing all-node. At d=3 that null move jumps into QS. But as you do checks in the first ply of QS, it should play Rxe4#, as a checkmate is also a check. So how can you fail low on a checkmate (that is faster than any checkmate you have seen so far)?

I don't understand what under-promotion has to do with it.

I'm going to have to get back to you on this. There's only so much my brain can handle tracing through the code by hand. It does appear that the null move should fail low though...

[Tord Romstad]

My initial move ordering is done with a call to QS for each move, so I have 4100000 nodes before starting the search .

I also do this; I call the qsearch with an infinite window for all root moves in order to do the initial sorting. I don't know why, but in this particular position, my search doesn't explode quite as badly as yours:

Code: Select all

 2        #4   00:00   145936 Bxc7+ Qxc7 Nexf3+ Kxf4 Qxc7+ Re5 Qxe5# 
 2        #3   00:00   156026 Rxc7 Qxd4 Rd7+ Rxb8 Qxb8# 
 3        #2   00:00   171552 Rxc7 Qxd4 Rb7# 
 4        #2   00:00   180731 Rxc7 Qxd4 Rb7# 
 5        #2   00:00   188250 Rxc7 Qxd4 Rb7# 

I always hear about people using this technique (Bob uses it too, IIRC). Why?

Probably because Phalanx did it, the rest of us copied it, and it worked well enough that it didn't seem worth the trouble to look for more sophisticated techniques.

What's the difference between that and a 1-ply search?

The infinite window, which makes it possible to compare all root moves.

Is the move ordering for the first couple plies even that important anyway?

Probably not. However, I think there may be a lot to gain by improving root move ordering at later plies, and at internal PV nodes.

Tord

[F. Bluemers]

Another thing that could help is mate-distance pruning:

Most certainly.

Hi Pradu,
lets compare with what you posted earlier
(http://64.68.157.89/forum/viewtopic.php ... 80&t=20727)

Code: Select all

Buzz with mate distance pruning without checks in qsearch with nullmove 
1 656 0 975 Bxa7 
1 988 0 1650 Nexf3+ Kxf4 Bxa7 
1 31993 1 5597 Bxc7+ Qxc7 
1 31995 1 6577 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6# 
1 31995 1 6721 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6# 
2 31995 1 6722 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6# 
2 31995 3 8071 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6# 
3 31995 3 8158 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6# 
3 31997 3 8967 Rxc7 Rxf4 Nc6# 
3 31997 3 9047 Rxc7 Rxf4 Nc6#



Nullmove R = 2 + (&#40;depth&#41; > &#40;6 + (&#40;piecesCurrentSide<3&#41;?2&#58;0&#41;)); 

Buzz with Checks in Qsearch with Nullmove &#40;10529 nodes&#41;
snip..............
..............snap

Buzz without Checks in Qsearch with Nullmove &#40;8967 nodes&#41; 
1 656 0 975 Bxa7 
1 988 1 1650 Nexf3+ Kxf4 Bxa7 
1 31993 1 5597 Bxc7+ Qxc7 
1 31995 1 6577 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6# 
1 31995 1 6721 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6# 
2 31995 3 6722 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6# 
2 31995 3 8071 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6# 
3 31995 3 8158 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6# 
3 31997 3 8967 Rxc7 Rxf4 Nc6# 
3 31997 4 9047 Rxc7 Rxf4 Nc6#

don't see the mate-threat stuff doing much at all...
do I overlook something?
Best
Fonzy

[Pradu]

I don't understand how Buzz can see the mate at such a low depth if you switch checks in QS off. Why isn't Rxc7 refuted by null move ad d=3?

Simply because the qsearch with no checks will play Rxe4# after the nullmove. Here's a longer explanation:

The entire search trace for Buzz on this position without checks in qsearch and with mate distance pruning can be found here (850k html page).
Rxc7 in depth=3 search is first played at node 8488 and subsequently researched after its fail high at node 8914. (do Ctrl-F and search for the node numbers to find the relevant excerpts)

Let us take an excerpt of the Rxc7 search at node 8488.

Code: Select all

Rxc7 (-31996, -31995) 8488
 Null (31995, 31996) 8489
q Bxa7 (-31996, -31995) 8490
q Rxa7 (-31996, -31995) 8491
q  Kxd4 (31995, 31996) 8492
q h8=Q (-31996, -31995) 8493
q  Kxf4 (31995, 31996) 8494
q Bxe4 (-31996, -31995) 8495
q Rxe4 (-31996, -31995) 8496

It can be seen that the search at the root node already has a mate bound (31995,32000) before the search of Rxc7 has started. After Rxc7 has been played the bounds on the child node for a search with a zero-window applied to the root node to test if it's better is (-31996, -31995). A Null move is immediately played after this and you end up with this position
[D]1B1Q2K1/q1R4P/4P3/3Pk1p1/1r1NrR1b/4pn1P/1p1p2n1/1B2N2b w - - 0 1
With bounds (31995, 31996). To create a fail low on the root node for Rxc7 (to throw away Rxc7), the search on this position after the null move search must fail low. However, Rxe4# will create a mate score of 31997 ( MATE_SCORE-depth_to_mate = 32000-3) at the node after the nullmove and this will cause a fail high at this node. This means that the nullmove search at node after Rxc7 will must fail low and therefore Rxc7 is not refuted by nullmove. For similar reasons, the Rxc7 re-search will also not be refuted by nullmove.

[Pradu]

don't see the mate-threat stuff doing much at all...
do I overlook something?
Best
Fonzy

Both searches are identical. Mate-distance pruning is on by default in Buzz (and mate-threat off by default ).

[Allard Siemelink]

~5000 nodes for bright:

Code: Select all

  [1/27]    0.000    2275      885  Bb8xa7 Ke5xf4 Ne1d3+ Kf4g3 h7h8=Q d2d1=Q Nd3xb4 Qd1xb1 Qd8xc7+ Nf3e
  [1/27]    0.015    2292      886  ++2/47 Qh7h8=Q+
  [1/27]    0.015    3515       +3# h7h8=Q+ Ke5xf4 Nd4e2+ Kf4f5 Qh8f6+
  [1/27]    0.015    3758       +3# ok/3758.0
  [2/27]    0.015    3931       +3# h7h8=Q+ Ke5xf4 Nd4e2+ Kf4f5 Qh8f6+
  [2/27]    0.015    5016       +2# ++17/47 Rc2xc7
  [2/27]    0.015    5088       +2# Rc2xc7 d2xe1=Q Rf4xe4+
  [2/27]    0.015    5118       +2# (optimal)

[F. Bluemers]

don't see the mate-threat stuff doing much at all...
do I overlook something?
Best
Fonzy

Both searches are identical. Mate-distance pruning is on by default in Buzz (and mate-threat off by default ).

thanks,see you in chat

(lousy me mixing up mate-distance & mate-threat.)

Fonzy

[hgm]

OK, I see. stupid of me. The mating move is a capture.

So I guess what really prevents Joker from seeing the mate at d=3 is that it stands pat in QS after Rxe4#.

[Dann Corbit]

Here is a useful position for testing quiescent explosion:
[D]1B1Q2K1/q1p4P/4P3/3Pk1p1/1r1NrR1b/4pn1P/1pRp2n1/1B2N2b w - - c0 "415"; c1 "0"; bm Rxc7; ce 32764; dm 2; pv Rxc7 g4 Rxe4#;

Interesting. Here's the result (as sent to an xboard/winboard gui) with a version of my engine with the old bad move ordering:

Code: Select all

1 357 5 13050 h7h8q
2 427 10 30528 f4f5 e5d4
3 427 11 34868 f4f5 e5d4 b8a7
4 32765 21 70543 c2c7 d2e1q f4e4

and with my newest version with new and improved move ordering:

Code: Select all

1 452 0 498 h7-h8=Q (nps=infM)
2 352 0 2943 h7-h8=Q Ke5xf4 (nps=1.472M)
3 652 0 6292 h7-h8=Q Ke5xf4 Bb8xa7 (nps=1.573M)
4 32765 2 32073 Rc2xc7 d2xe1=Q Rf4xe4 (nps=1.234M)

70,543 nodes compared to 32,073. Note that there are a few other changes as well, which is not so good for comparison purposes. I'm not sure what exactly accounts for the huge difference in NPS (about 1.2M for new and 0.33M for old). Perhaps it's (at least partly) because my new version searches the hash move before generating captures and my old one generated captures before searching ANY moves.

Compared to other positions I've found, this one is surprisingly easy for my engine's old move ordering.

This one is MUCH worse:

[D]r1bqkb1r/ppp5/2n4p/3p1pp1/Q2PnP2/2PB4/PP1NN1PP/R1B2RK1 b kq - 1 10

Old version(to depth 5):

Code: Select all

1 18 14 45342 c8e6
2 15 31 112052 c8e6 d2b3
3 16 277 1099640 c8e6 e2g3 g5g4
4 12 1068 4270555 c8e6 d2f3 f8d6 f4g5
5 13 4982 20052422 c8e6 d2f3 f8e7 f3e5 d8d6

New version:

Code: Select all

1 1 0 118 Ne4xd2 (nps=infM)
2 -10 0 570 Bc8-e6 Nd2xe4 (nps=infM)
3 18 0 2533 Bc8-e6 Nd2xe4 f5xe4 (nps=1.266M)
4 -7 1 16994 Bc8-e6 f4xg5 h6xg5 Nd2xe4 (nps=1.133M)
5 7 6 85270 Bc8-e6 c3-c4 g5xf4 Ne2xf4 Ne4xd2 (nps=1.332M)

That's 20,052,422 nodes for my old version compared to only 85,270 for my new version.

Here is 10 minute Rybka analysis of your position:

Code: Select all

Analysis from C:\tmp\quiescent.epd   
5/23/2008 7:42:22 PM Level: 600 Seconds
Analyzing engine: Rybkav2.3.2a.w32

1)                      
    Avoid move: 
    Best move (Rybkav2.3.2a.w32): Qd8-d6
    Not found in: 10:00
      5	00:00	       8.276	67.258	-0.50	Bf8e7 b2b4
      6	00:00	      11.643	68.915	-0.51	Bf8e7 b2b4 00
      7	00:01	      25.044	60.626	-0.54	Bf8e7 b2b4 00 b4b5
      8	00:01	      63.002	59.790	-0.53	Bf8e7 b2b4 00 b4b5 Nc6b8
      8	00:02	     107.209	63.238	-0.39	Qd8e7 Nd2xe4 f5xe4 Bd3a6 Qe7d6 Ba6b5
      9	00:03	     150.172	63.860	-0.37	Qd8e7 Nd2xe4 f5xe4 Bd3a6 Qe7d6 Ba6b5 Bf8e7
     10	00:03	     193.564	64.374	-0.37	Qd8e7 Nd2xe4 f5xe4 Bd3a6 Qe7d6 Ba6b5 Bf8e7 Bc1e3
     11	00:12	     706.684	63.349	-0.28	Qd8e7 Nd2xe4 f5xe4 Bd3a6 Qe7d6 Ba6b5 Bf8e7 Bc1e3 Bc8d7
     12	00:26	   1.632.503	64.369	-0.21	Qd8e7 Nd2xe4 f5xe4 Bd3a6 Qe7d6 Ba6b5 Bc8d7 Bc1e3 Bf8e7 f4f5
     13	00:50	   3.019.680	61.629	-0.38	Qd8e7 Qa4b3 Ne4c5 d4xc5 Qe7e3+ Kg1h1 Qe3xd3 Ne2d4 Bf8xc5 Rf1e1+ Ke8f8 f4xg5 Bc5xd4 c3xd4
     14	01:14	   4.388.321	60.557	-0.38	Qd8e7 Qa4b3 Ne4c5 d4xc5 Qe7e3+ Kg1h1 Qe3xd3 Ne2d4 Bf8xc5 Rf1e1+ Ke8f8 f4xg5 Bc5xd4 c3xd4
     14	02:44	   9.897.182	61.790	-0.29	Qd8d6 b2b4 Bf8g7 Nd2f3 g5g4 Nf3e5 00 b4b5 Nc6xe5 f4xe5 Qd6b6 Qa4b3
     15	03:10	  11.562.631	62.377	-0.35	Qd8d6 b2b4 Bf8g7 Nd2f3 g5g4 Nf3e5 00 b4b5 Nc6xe5 f4xe5 Qd6b6 Qa4b3 c7c6
     16	04:25	  15.848.792	61.324	-0.42	Qd8d6 b2b4 Bf8g7 Nd2f3 g5g4 Nf3e5 00 b4b5 Nc6xe5 f4xe5 Qd6b6 Qa4b3 c7c6 b5xc6
   5/23/2008 7:52:26 PM, Time for this analysis: 00:10:00, Rated time: 10:00

0 of 1 matching moves
5/23/2008 7:52:26 PM, Total time: 12:10:03 AM
Rated time: 10:00 = 600 Seconds