Quiescence Search Explosions

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

[bob]

There are a couple of things you can do. First, you are trying captures in an almost random order. You want to try the capture that appears to win the most. RxQ is far better than BxP or BXB.

Second, you can safely exclude captures that appear to be losing (QxP) where pawn is defended. I use SEE to make this determination. Doing this alone will reduce the size of your try by 50% over searching all captures, and in your case, it will reduce much more because of the order you are currently using.

[Harald Johnsen]

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

Shame on me, explosion at the root

Code: Select all

Cyrano 0.5b2:
  1/37	00:03	   4.104.019	0	+M4	Bxc7+ Qxc7 Nexf3+ Kxf4 Qxc7+ Re5 Qxe5+
  2/7	00:03	   4.104.670	0	+M4	Bxc7+ Qxc7 Nexf3+ Kxf4 Qxc7+ Re5 Qxe5+
  3/13	00:03	   4.109.371	0	+M4	Bxc7+ Qxc7 Nexf3+ Kxf4 Qxc7+ Re5 Qxe5+
  4/13	00:04	   4.113.014	1.223.384	+M4	Bxc7+ Qxc7 Nexf3+ Kxf4 Qxc7+ Re5 Qxe5+
  5/13	00:04	   4.117.430	1.223.384	+M4	Bxc7+ Qxc7 Nexf3+ Kxf4 Qxc7+ Re5 Qxe5+
  6/35	00:04	   4.207.846	1.223.384	+M4	Bxc7+ Qxc7 Nexf3+ Kxf4 Qxc7+ Re5 Qxe5+
  6/35	00:04	   4.211.879	1.223.384	+M3	h8Q+ Kxf4 Ne2+ Kf5 Qhf6+
  6/35	00:04	   4.223.417	1.223.384	+M2	Rxc7 Kxf4 Rf7+

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

HJ.

[Zach Wegner]

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

HJ.

I always hear about people using this technique (Bob uses it too, IIRC). Why? What's the difference between that and a 1-ply search? Is the move ordering for the first couple plies even that important anyway?

[Harald Johnsen]

I'm outputing the pv since the first ply and it's not fun to see a lot of pv with negative score at ply 1 With the qs sort the output is clean.

Anyway it depends on how you do your root move ordering. At some point I was doing a mix of the score and the node count, so having a score for all moves was usefull.

HJ.

[Kempelen]

What would be a normal result for this test????
I get this, after 9 seconds:

Code: Select all

ply score     time     nodes  pv
 1    M04      984    637963  1. Rf5+ Kxd4 2. Bxa7+ Rb6 3. Bxb6+ cxb6 4. Qxb6#

Take into account that I have not hast tables implemented, but I have null move, and SEE. Does this sound acceptable?

[sparky]

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?

[hgm]

Code: Select all

Joker:
  5	+100.02	109034	0:00.55	c2c7 d2e1 f4e4
  5	+100.02	77481	0:43.00	c2c7 d2e1 f4e4
  5	+100.03	31948	0:24.00	h7h8 e5f4 d4e2 f4f5 d8f6
  4	+100.03	17360	0:00.17	h7h8 e5f4 d4e2 f4f5 d8f6
  4	+100.03	11331	0:13.00	h7h8 e5f4 d4e2 f4f5 d8f6
  3	+100.03	6150	0:00.10	h7h8 e5f4 d4e2 f4f5 d8f6
  3	+100.03	2642	0:08.00	h7h8 e5f4 d4e2 f4f5 d8f6
  3	+17.06	2044	0:07.00	f4f5 e5d4 b8a7 b4b6 h7h8 f3e5 a7b6 c7b6
  2	+17.06	1493	0:00.06	f4f5 e5d4 h7h8 f3e5 b8a7 b4b6 a7b6 c7b6
  2	+17.06	1421	0:06.00	f4f5 e5d4 h7h8 f3e5 b8a7 b4b6 a7b6 c7b6
  2	+11.62	853	0:05.00	f4e4 e5e4 c2d2 e4f4 b8a7
  2	+5.93	692	0:04.00	h7h8 e5f4 e1d3 f4g3 b8a7 d2d1 d3b4 d1b1 d8c7 f3e5
  1	+4.88	301	0:00.03	h7h8 e5f4 e1g2 h1g2 b8a7 d2d1 c2g2 d1b1 d8c7 f3e5

micro-Max:
 28	+79.98	203746	0:01.08	c2c7
  ....
 10	+79.98	109844	0:00.57	c2c7
  9	+79.98	104424	0:00.55	c2c7
  8	+79.98	102672	0:00.54	c2c7
  7	+79.98	101416	0:00.53	c2c7
  6	+79.98	99106	0:00.52	c2c7
  5	+79.97	37766	0:00.24	d8f6
  4	+79.97	31451	0:00.22	d8f6
  3	+11.67	16225	0:00.13	f4f5
  2	+6.20	6457	0:00.07	e1f3
  1	+3.95	1781	0:00.03	h7h8
  0	+1.94	1581	0:00.01	e1f3

Both uMax and Joker seem to need ~100,000 nodes to find the mate in 2. (This is on a 1GHz machine without DDR memory.) So it seems the uMax QS, which only pulls a single move in front (with the best MVV/LVA score), and tries all other moves in move-generator order, is not doing such a bad job.

[pijl]

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

CTD needs just over 10k nodes to find the mate in 2:

Code: Select all

W[1]> setboard 1B1Q2K1/q1p4P/4P3/3Pk1p1/1r1NrR1b/4pn1P/1pRp2n1/1B2N2b w - -
W[1]> post
W[1]> analyze
ply   score   time           nodes pv
 1.  99.993   0:00.03         5094 b8c7 a7c7 e1f3 e5f4 d8c7 e4e5
 2.  99.995   0:00.04         8184 h7h8q e5f4 d4e2 f4f5
 3.  99.997   0:00.07        10879 c2c7 d2e1q f4e4
 4.  99.997   0:00.07        11063 c2c7 d2e1q f4e4

The Baron 2.22, which also uses a quiescense search with an (almost) open window on all moves does have some problems and requires 324k nodes for its first line of output and finds the mate in 2 in 346k nodes.
When I added the quiescense search to aid rootmove ordering, I saw a small decrease in the number of nodes used and had to implement a few measures to prevent the damage done in these type of positions. With CTD I decided I would go for simplicity again, so I did not implement the initial rootmove ordering in this way.
Richard.

[hgm]

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?