Quiescence Search Explosions

[Zach Wegner]

ZCT always does replies to checks and generates checks for the first two plies (or more, it is extended if there is a node with a single reply a la Rebel) of the qsearch. I get this:

Code: Select all

Depth          Time     Score   PV (nodes)
  1/ 4        0.000     -7.32   1. d6 (31)
  1/ 4        0.000     -7.22   1. e7 (70)
  1/10        0.001    +14.99   1. h8=Q Kxf4 2. Bxc7+ Re5 3. Bxe5+ Nxe5 4. Nxg2+ Bxg2 (158)
  1/10        0.001    +15.72   1. Nd3+ Kxd4 2. Bxa7+ Kxd3 3. Rxc7+ Ke2 (192)
  1/10        0.001    +21.30   1. Bxc7+ Qxc7 2. h8=Q Kxf4 3. Qxc7+ Re5 4. Nxg2+ Bxg2 (286)
[ 1/10]       0.002    +21.30   1. Bxc7+ Qxc7 2. h8=Q Kxf4 3. Qxc7+ Re5 4. Nxg2+ Bxg2 (322)
  2/10        0.002    +21.30   1. Bxc7+ Qxc7 2. h8=Q Kxf4 3. Qxc7+ Re5 4. Nxg2+ Bxg2 (455)
[ 2/10]       0.003    +21.30   1. Bxc7+ Qxc7 2. h8=Q Kxf4 3. Qxc7+ Re5 4. Nxg2+ Bxg2 (738)
  3/10        0.005    +21.30   1. Bxc7+ Qxc7 2. h8=Q Kxf4 3. Qxc7+ Re5 4. Nxg2+ Bxg2 (1285)
  3/11        0.006    +28.23   1. Rf5+ Kxd4 2. Bxa7+ Rb6 3. h8=Q Ne5 4. Bxb6+ cxb6 (1565)
[ 3/11]       0.006    +28.23   1. Rf5+ Kxd4 2. Bxa7+ Rb6 3. h8=Q Ne5 4. Bxb6+ cxb6 (1678)
  4/16        0.007    +29.08   1. Rf5+ Kxd4 2. Bxa7+ Rb6 3. h8=Q Ne5 4. Bxb6+ cxb6 5. Nf3+ Kd3 6. Nxe5+ Rxe5 7. Rxb2+ Kc4 (1761)
[ 4/19]       0.055    +29.08   1. Rf5+ Kxd4 2. Bxa7+ Rb6 3. h8=Q Ne5 4. Bxb6+ cxb6 5. Nf3+ Kd3 6. Nxe5+ Rxe5 7. Rxb2+ Kc4 (19082)
  5/19        0.060    +29.08   1. Rf5+ Kxd4 2. Bxa7+ Rb6 3. h8=Q Ne5 4. Bxb6+ cxb6 5. Nf3+ Kd3 6. Nxe5+ Rxe5 7. Rxb2+ Kc4 (21059)
  5/28        0.076       +#5   1. Rxf3 Kxd4 2. Bxa7+ Rb6 3. h8=B Re5 4. Rxc7 dxe1=R 5. Bxb6# (31797)
  5/28        0.078       +#4   1. Bxc7+ Qxc7 2. Qxc7+ Kxd4 3. Nxf3+ Kxd5 4. Qc6# (33768)
  5/28        0.080       +#3   1. h8=Q Kxf4 2. Ne2+ Kf5 3. Qhf6# (36198)
[ 5/28]       0.080       +#3   1. h8=Q Kxf4 2. Ne2+ Kf5 3. Qhf6# (37169)
  6/28        0.081       +#3   1. h8=Q Kxf4 2. Ne2+ Kf5 3. Qhf6# (37258)
[ 6/28]       0.082       +#3   1. h8=Q Kxf4 2. Ne2+ Kf5 3. Qhf6# (38478)
  7/28        0.082       +#3   1. h8=Q Kxf4 2. Ne2+ Kf5 3. Qhf6# (38570)
[ 7/28]       0.085       +#3   1. h8=Q Kxf4 2. Ne2+ Kf5 3. Qhf6# (42493)
  8/28        0.085       +#3   1. h8=Q Kxf4 2. Ne2+ Kf5 3. Qhf6# (42585)
  8/28        0.087       +#2   1. Rxc7 dxe1=N 2. Rxe4# (46781)
[ 8/28]       0.087       +#2   1. Rxc7 dxe1=N 2. Rxe4# (46821)

[hgm]

ZCT always does replies to checks and generates checks for the first two plies ...

How is it possible then, that you find the mate-in-2 only at 8 ply?

For Joker I can imagine that at 4 ply it doesn't see it, because Rxc7 is 'refuted' by a null move, after which no depth is left, and the mating move is not searched. But ZCT should have seen it even at 3 ply, as the QS after null move would still see the checkmate in its first ply.

[michiguel]

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#;

Gaviota AMD64 X2 2.4 Ghz

Code: Select all

+-----------------+
| . B . Q . . K . |
| q . p . . . . P |
| . . . . P . . . |
| . . . P k . p . |    Castling: 
| . r . N r R . b |    ep: -
| . . . . p n . P |
| . p R p . . n . |
| . B . . N . . b | [White]
+-----------------+

analyze
      5197   1:      0.0   +Mat_3  h7-h8=Q  Ke5xf4   Nd4-e2   Kf4-f5   
                                   Qh8-f6   
      5906   2:      0.0   +Mat_3  h7-h8=Q  Ke5xf4   Nd4-e2   <-transp 
      7680   3:      0.1   +Mat_2  Rc2xc7   Ng2xf4   h7-h8=Q  

[Pradu]

Interesting that you need so few nodes, compared to Joker. But I guess this is mainly due to the fact that you also find the mate at much lower depth (3 ply, vs Joker's 5 ply and uMax' 6 ply).

You probably search checks after null move?

Code: Select all

Nullmove R = 2 + ((depth) > (6 + ((piecesCurrentSide<3)?2:0)));

Buzz with Checks in Qsearch with Nullmove (10529 nodes)
1 656 1 975 Bxa7
1 988 1 2089 Nexf3+ Kxf4 Bxa7
1 31993 3 6393 Bxc7+ Qxc7
1 31995 3 7632 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6#
1 31995 3 7786 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6#
2 31995 4 7787 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6#
2 31995 4 9583 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6#
3 31995 6 9670 h8=Q+ Kxf4 Ne2+ Kf5 Qdf6#
3 31997 6 10529 Rxc7 Kxf4 Rf7#
3 31997 6 10609 Rxc7 Kxf4 Rf7#

Buzz without Checks in Qsearch with Nullmove (8967 nodes)
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#

[pijl]

Interesting that you need so few nodes, compared to Joker. But I guess this is mainly due to the fact that you also find the mate at much lower depth (3 ply, vs Joker's 5 ply and uMax' 6 ply).

You probably search checks after null move?

Not specific after nullmove, but I do search a few checks in quiescense (forced lines only, i.e. first ply of quiescense, or in a checking sequence).
The Baron tries quite a few more, and is also less restricted where it tries them.
Another thing that could help is mate-distance pruning:

Code: Select all

	best=-MATEVALUE+ply;
	if (best>=tbeta) return best;
	if (best>talpha) talpha=best;
	x=MATEVALUE-ply-1;
	if (x<=talpha) return x;
	if (x<tbeta) tbeta=x;

This is checked in all (regular search as well as quiescense search) nodes.
Richard.

[xsadar]

Hi Mike!

Welcome to the computer chess world! I joined computer chess as I thought it would be less frustrating than try and improve my own humble rating. Imagine my surprise!

What is your engine called? ...and when do you think the first release will be made available?

Thanks. I started chess programming because it sounded like fun. I've found that it's a lot more fun than I even expected! I don't really get frustrated. I enjoy the challenge.

I'm actually writing my second engine now. When I first started I just jumped right in and wrote something up. The result was my first version of Knightmare. I then felt like exploring a couple of ideas, mainly with opening books, resulting in Knightmare BP, which is (temporarilly) available for download at: http://www.mikeleany.com/knightmare . Be warned that it's extremely buggy and plays very horrid chess (around 1000 Elo maybe?).

My new engine is called Zilch. With it, my intent is to actually write a mature stable engine. Already it's far superior to Knightmare (maybe around 2000 Elo on FICS?) and far less buggy. I'm guessing it will be available for download within a couple months. When it is you'll find it here: http://www.mikeleany.com/zilch . You can currently find a small amount of information about it on that page.

[Zach Wegner]

It's a combination of R=3 infinite nullmove and not searching underpromotions in qsearch (unless we are in check or they give check). Rxc7 is refuted by a null move. This null move is not refuted itself by another null move until the depth is big enough that dxe1=N is searched in the main search. So you get Rxc7 null null dxe1=N Rxe4#, where the first four moves take up 8 plies and the mate is in qsearch.

Or I just have a bug.

[Pradu]

Another thing that could help is mate-distance pruning:

Most certainly.

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#

Buzz without mate distance pruning without checks in qsearch with nullmove
1 656 0 975 Bxa7
1 988 0 1650 Nexf3+ Kxf4 Bxa7
1 31993 1 5669 Bxc7+ Qxc7
stuck...didn't wait for it to finish

[hgm]

It's a combination of R=3 infinite nullmove and not searching underpromotions in qsearch (unless we are in check or they give check). Rxc7 is refuted by a null move. This null move is not refuted itself by another null move until the depth is big enough that dxe1=N is searched in the main search. So you get Rxc7 null null dxe1=N Rxe4#, where the first four moves take up 8 plies and the mate is in qsearch.

Or I just have a bug.

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.

BTW, both my engines do mate-distance pruning. This is an automatic side effect of the delayed-loss bonus, which also takes care of making sure the fastes mate is preferred. You can clearly see that from the uMax node count: once it finds the mate in 2 (at ply 6, as uMax is a King-capture engine), the node count hardly increases anymore. It just walks the same tree on every iteration, truncated at a certain level by the mate-distance pruning, to increase the search depth of every node.

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?

[Harald Johnsen]

I'm now using a window in my qs search for initial move ordering, and I've found a bug in my razoring so the mate can be found earlier now.

Code: Select all

Cyrano 0.5b3:
  1/32	00:00	     137.666	0	+7,56	h8Q+ Kxf4 Nd3+ Kg3 Bxa7 d1Q Nxb4 Qxb1
  1/32	00:00	     155.023	0	+8,52	Bxa7 dxe1Q Nxf3+ Kxf4 Nxe1
  1/32	00:00	     155.241	0	+9,80	Nexf3+ Kxf4 Bxa7
  1/32	00:00	     156.962	0	+21,26	Rxe4+ Kxe4 Rxc7+ Kf4 Rxa7+ Ne5 h8Q
  1/32	00:00	     158.226	0	+M4	Rf5+ Kxd4 Bxa7+ Rb6 Bxb6+ cxb6 Qxb6+
  2/12	00:00	     159.502	1.016.294	+M4	Rf5+ Kxd4 Bxa7+ Rb6 Bxb6+ cxb6 Qxb6+
  3/14	00:00	     165.565	1.016.294	+M4	Rf5+ Kxd4 Bxa7+ Rb6 Bxb6+ cxb6 Qxb6+
  3/23	00:00	     167.782	1.016.294	+M3	h8B+ Kxf4 Ne2+ Kf5 Qf6+
  3/23	00:00	     172.138	1.016.294	+M2	Rxc7 Kxf4 Rf7+
  4/27	00:00	     226.071	1.016.294	+M2	Rxc7 Kxf4 Rf7+
  5/27	00:00	     281.299	1.016.294	+M2	Rxc7 Kxf4 Rf7+
  6/27	00:00	     335.255	1.016.294	+M2	Rxc7 Kxf4 Rf7+

And before you ask, i'm not doing null move in the first 6 iterations.

HJ.