QS investigation

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Rebel
Posts: 5694
Joined: Thu Aug 18, 2011 10:04 am

QS investigation

Post by Rebel » Thu Mar 07, 2013 10:52 pm

What I am always missing in the QS discussions (checks or no checks, TT or no TT) is the percentage of time (nodes, evals) a program is spending in QS in comparison to the main search. I made a little table and if you are interested post or PM me your results and QS description and I will update the page and perhaps we can make some sense out of it.

http://www.top-5000.nl/qs.htm

For sure the default settings (allow 2 checks + full TT use) are best for my thing and with a significant margin. I like to understand why others experience something else, sometimes even the opposite. Comparing percentages could be a start.

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: QS investigation

Post by bob » Fri Mar 08, 2013 5:34 pm

Rebel wrote:What I am always missing in the QS discussions (checks or no checks, TT or no TT) is the percentage of time (nodes, evals) a program is spending in QS in comparison to the main search. I made a little table and if you are interested post or PM me your results and QS description and I will update the page and perhaps we can make some sense out of it.

http://www.top-5000.nl/qs.htm

For sure the default settings (allow 2 checks + full TT use) are best for my thing and with a significant margin. I like to understand why others experience something else, sometimes even the opposite. Comparing percentages could be a start.
First question: "Define q-search node". For example, your last full-width ply will make a move, and then call q-search. Is that a q-search node? Or do you call that something else and only call a q-search node as a node that is produced by making a capture/check inside quiesce? That makes a huge difference in the counters since you ALWAYS get to quiesce at least once at the end of each full-width branch. That will, by definition, be a larger number than the total interior nodes combined.

AlvaroBegue
Posts: 925
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: QS investigation

Post by AlvaroBegue » Fri Mar 08, 2013 6:12 pm

bob wrote:[...] That makes a huge difference in the counters since you ALWAYS get to quiesce at least once at the end of each full-width branch. That will, by definition, be a larger number than the total interior nodes combined.
If the tree consists of a single long branch, there will be more interior nodes than leaves, so it's not quite "by definition" (sorry, mathematician here). The general argument stands, though.

User avatar
JVMerlino
Posts: 1044
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: QS investigation

Post by JVMerlino » Fri Mar 08, 2013 8:58 pm

Not sure if you're interested in the results of a mediocre engine, but here's what my current version of Myrddin reports:

Unlimited checks in QS.
No transposition hash writes, but calls to Evaluate() to get a stand pat value will probe the eval hash.
Minor promotions only.

8/5p1p/1p2pPk1/p1p1P3/P1P1K2b/4B3/1P5P/8 w - - bm b2b4; id BS2830;
8%

r1b1r1k1/ppp2ppp/2nb1q2/8/2B5/1P1Q1N2/P1PP1PPP/R1B2RK1 w - - bm c1b2;
0%! (because this is a book move :) ) But if I turn off book it is 14%

r3r1k1/pp1bp2p/1n2q1P1/6b1/1B2B3/5Q2/5PPP/1R3RK1 w - - bm b4d2;
14%

r3k2r/pp1n1ppp/1qpnp3/3bN1PP/3P2Q1/2B1R3/PPP2P2/2KR1B2 w kq - bm c3e1;
17%

r1bq1rk1/pp4bp/2np4/2p1p1p1/P1N1P3/1P1P1NP1/1BP1QPKP/1R3R2 b - - bm c8h3;
11%

rn2r1k1/pp3ppp/8/1qNp4/3BnQb1/5N2/PPP2PPP/2KR3R b - - bm g4h5;
11%

2rq1rk1/pb3ppp/1p2pn2/4N3/1b1PPB2/4R1P1/P4PBP/R2Q2K1 w - - bm d4d5;
11%

r3k2r/pb3pp1/2p1qnnp/1pp1P3/Q1N4B/2PB1P2/P5PP/R4RK1 w kq - bm e5f6;
11%

8/2p5/7p/pP2k1pP/5pP1/8/1P2PPK1/8 w - - bm f2f3;
7%

7r/2qpkp2/p3p3/6P1/1p2b2r/7P/PPP2QP1/R2N1RK1 b - - bm f7f5;
21%

8/8/4b1p1/2Bp3p/5P1P/1pK1Pk2/8/8 b - - bm g6g5;
7%

8/7p/8/7P/1p6/1p5P/1P2Q1pk/1K6 w - - bm b1a1;
6%

2r2rk1/1bpR1p2/1pq1pQp1/p3P2p/P1PR3P/5N2/2P2PPK/8 w - - bm h2g3;
14%

r3kb1r/1p1b1p2/p1nppp2/7p/4PP2/qNN5/P1PQB1PP/R4R1K w kq - bm c3b1;
13%

8/2kPR3/5q2/5N2/8/1p1P4/1p6/1K6 w - - bm f5d4;
17%

r4r1k/pbnq1ppp/np3b2/3p1N2/5B2/2N3PB/PP3P1P/R2QR1K1 w - - bm c3e4;
7%

r1b1qrk1/ppBnppb1/2n4p/1NN1P1p1/3p4/8/PPP1BPPP/R2Q1R1K w - - bm c5e6;
10%

r1bqr1k1/pp1n1ppp/5b2/4N1B1/3p3P/8/PPPQ1PP1/2K1RB1R w - - bm e5f7;
12%

r1bqk2r/pppp1Npp/8/2bnP3/8/6K1/PB4PP/RN1Q3R b kq - bm e8g8;
9%

rnb1kb1r/1p3ppp/p5q1/4p3/3N4/4BB2/PPPQ1P1P/R3K2R w KQkq - bm e1c1;
17%

1r4k1/1q2pN1p/3pPnp1/8/2pQ4/P5PP/5P2/3R2K1 b - - bm b7d5;
18%

r2qr2k/pbp3pp/1p2Bb2/2p5/2P2P2/3R2P1/PP2Q1NP/5RK1 b - - bm d8d3;
11%

4r1k1/p1pb1ppp/Qbp1r3/8/1P6/2Pq1B2/R2P1PPP/2B2RK1 b - - bm d3f3;
13%

r5k1/p4n1p/6p1/2qPp3/2p1P1Q1/8/1rB3PP/R4R1K b - - bm a8f8;
18%

8/pR4pk/1b6/2p5/N1p5/8/PP1r2PP/6K1 b - - bm d2b2;
19%

2r1r3/p3bk1p/1pnqpppB/3n4/3P2Q1/PB3N2/1P3PPP/3RR1K1 w - - bm e1e6;
15%

5r2/1p4r1/3kp1b1/1Pp1p2p/2PpP3/q2B1PP1/3Q2K1/1R5R b - - bm f8f3;
21%

jm

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: QS investigation

Post by bob » Fri Mar 08, 2013 9:16 pm

AlvaroBegue wrote:
bob wrote:[...] That makes a huge difference in the counters since you ALWAYS get to quiesce at least once at the end of each full-width branch. That will, by definition, be a larger number than the total interior nodes combined.
If the tree consists of a single long branch, there will be more interior nodes than leaves, so it's not quite "by definition" (sorry, mathematician here). The general argument stands, though.
OK, for one exceptional case my statement was wrong. :) BTW my old chess partner (Harry Nelson) spent a lot of time with "straight-jacket positions", which were positions where each side only had one legal move, which was a check, for many consecutive plies. I don't remember specifics now, but 30+ plies was common (sometimes there were no requirements for legal positions so > 9 queens were sometimes allowed).

But this discussion is still relevant. Do we count the FIRST time we get to quiesce() as a q-search node, or not? Makes a huge difference in how we compare nodes. And in this context, comparing node counts is an interesting issue. Commonly one increments "nodes" at the top of search, and "qnodes" at the top of quiesce. That's not exactly correct according to accepted definitions.

Of course there is also another issue. What about true leaf positions? That is you call quiesce(), depth=0, and there are no moves that qualify for searching. As opposed to the usual definition of "frontier nodes" which are nodes interior to the q-search. As opposed to the usual definition of "interior nodes" which are nodes interior to the full-width part of the search.

Most every time I have participated in a discussion that led to making comparisons, we discovered we were not talking about exactly the same thing.

"leaf nodes" are pretty obvious. Static eval and return. But the rest have a boundary between them that influences the totals and different boundaries make comparison problematic unless the differences are explained early on.

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: QS investigation

Post by bob » Fri Mar 08, 2013 9:18 pm

JVMerlino wrote:Not sure if you're interested in the results of a mediocre engine, but here's what my current version of Myrddin reports:

Unlimited checks in QS.
No transposition hash writes, but calls to Evaluate() to get a stand pat value will probe the eval hash.
Minor promotions only.

8/5p1p/1p2pPk1/p1p1P3/P1P1K2b/4B3/1P5P/8 w - - bm b2b4; id BS2830;
8%

r1b1r1k1/ppp2ppp/2nb1q2/8/2B5/1P1Q1N2/P1PP1PPP/R1B2RK1 w - - bm c1b2;
0%! (because this is a book move :) ) But if I turn off book it is 14%

r3r1k1/pp1bp2p/1n2q1P1/6b1/1B2B3/5Q2/5PPP/1R3RK1 w - - bm b4d2;
14%

r3k2r/pp1n1ppp/1qpnp3/3bN1PP/3P2Q1/2B1R3/PPP2P2/2KR1B2 w kq - bm c3e1;
17%

r1bq1rk1/pp4bp/2np4/2p1p1p1/P1N1P3/1P1P1NP1/1BP1QPKP/1R3R2 b - - bm c8h3;
11%

rn2r1k1/pp3ppp/8/1qNp4/3BnQb1/5N2/PPP2PPP/2KR3R b - - bm g4h5;
11%

2rq1rk1/pb3ppp/1p2pn2/4N3/1b1PPB2/4R1P1/P4PBP/R2Q2K1 w - - bm d4d5;
11%

r3k2r/pb3pp1/2p1qnnp/1pp1P3/Q1N4B/2PB1P2/P5PP/R4RK1 w kq - bm e5f6;
11%

8/2p5/7p/pP2k1pP/5pP1/8/1P2PPK1/8 w - - bm f2f3;
7%

7r/2qpkp2/p3p3/6P1/1p2b2r/7P/PPP2QP1/R2N1RK1 b - - bm f7f5;
21%

8/8/4b1p1/2Bp3p/5P1P/1pK1Pk2/8/8 b - - bm g6g5;
7%

8/7p/8/7P/1p6/1p5P/1P2Q1pk/1K6 w - - bm b1a1;
6%

2r2rk1/1bpR1p2/1pq1pQp1/p3P2p/P1PR3P/5N2/2P2PPK/8 w - - bm h2g3;
14%

r3kb1r/1p1b1p2/p1nppp2/7p/4PP2/qNN5/P1PQB1PP/R4R1K w kq - bm c3b1;
13%

8/2kPR3/5q2/5N2/8/1p1P4/1p6/1K6 w - - bm f5d4;
17%

r4r1k/pbnq1ppp/np3b2/3p1N2/5B2/2N3PB/PP3P1P/R2QR1K1 w - - bm c3e4;
7%

r1b1qrk1/ppBnppb1/2n4p/1NN1P1p1/3p4/8/PPP1BPPP/R2Q1R1K w - - bm c5e6;
10%

r1bqr1k1/pp1n1ppp/5b2/4N1B1/3p3P/8/PPPQ1PP1/2K1RB1R w - - bm e5f7;
12%

r1bqk2r/pppp1Npp/8/2bnP3/8/6K1/PB4PP/RN1Q3R b kq - bm e8g8;
9%

rnb1kb1r/1p3ppp/p5q1/4p3/3N4/4BB2/PPPQ1P1P/R3K2R w KQkq - bm e1c1;
17%

1r4k1/1q2pN1p/3pPnp1/8/2pQ4/P5PP/5P2/3R2K1 b - - bm b7d5;
18%

r2qr2k/pbp3pp/1p2Bb2/2p5/2P2P2/3R2P1/PP2Q1NP/5RK1 b - - bm d8d3;
11%

4r1k1/p1pb1ppp/Qbp1r3/8/1P6/2Pq1B2/R2P1PPP/2B2RK1 b - - bm d3f3;
13%

r5k1/p4n1p/6p1/2qPp3/2p1P1Q1/8/1rB3PP/R4R1K b - - bm a8f8;
18%

8/pR4pk/1b6/2p5/N1p5/8/PP1r2PP/6K1 b - - bm d2b2;
19%

2r1r3/p3bk1p/1pnqpppB/3n4/3P2Q1/PB3N2/1P3PPP/3RR1K1 w - - bm e1e6;
15%

5r2/1p4r1/3kp1b1/1Pp1p2p/2PpP3/q2B1PP1/3Q2K1/1R5R b - - bm f8f3;
21%

jm
Same question I asked above. What exactly are you counting / measuring? The numbers seem very low...

User avatar
JVMerlino
Posts: 1044
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: QS investigation

Post by JVMerlino » Fri Mar 08, 2013 9:35 pm

bob wrote:
JVMerlino wrote:Not sure if you're interested in the results of a mediocre engine, but here's what my current version of Myrddin reports:

Unlimited checks in QS.
No transposition hash writes, but calls to Evaluate() to get a stand pat value will probe the eval hash.
Minor promotions only.

8/5p1p/1p2pPk1/p1p1P3/P1P1K2b/4B3/1P5P/8 w - - bm b2b4; id BS2830;
8%

r1b1r1k1/ppp2ppp/2nb1q2/8/2B5/1P1Q1N2/P1PP1PPP/R1B2RK1 w - - bm c1b2;
0%! (because this is a book move :) ) But if I turn off book it is 14%

r3r1k1/pp1bp2p/1n2q1P1/6b1/1B2B3/5Q2/5PPP/1R3RK1 w - - bm b4d2;
14%

r3k2r/pp1n1ppp/1qpnp3/3bN1PP/3P2Q1/2B1R3/PPP2P2/2KR1B2 w kq - bm c3e1;
17%

r1bq1rk1/pp4bp/2np4/2p1p1p1/P1N1P3/1P1P1NP1/1BP1QPKP/1R3R2 b - - bm c8h3;
11%

rn2r1k1/pp3ppp/8/1qNp4/3BnQb1/5N2/PPP2PPP/2KR3R b - - bm g4h5;
11%

2rq1rk1/pb3ppp/1p2pn2/4N3/1b1PPB2/4R1P1/P4PBP/R2Q2K1 w - - bm d4d5;
11%

r3k2r/pb3pp1/2p1qnnp/1pp1P3/Q1N4B/2PB1P2/P5PP/R4RK1 w kq - bm e5f6;
11%

8/2p5/7p/pP2k1pP/5pP1/8/1P2PPK1/8 w - - bm f2f3;
7%

7r/2qpkp2/p3p3/6P1/1p2b2r/7P/PPP2QP1/R2N1RK1 b - - bm f7f5;
21%

8/8/4b1p1/2Bp3p/5P1P/1pK1Pk2/8/8 b - - bm g6g5;
7%

8/7p/8/7P/1p6/1p5P/1P2Q1pk/1K6 w - - bm b1a1;
6%

2r2rk1/1bpR1p2/1pq1pQp1/p3P2p/P1PR3P/5N2/2P2PPK/8 w - - bm h2g3;
14%

r3kb1r/1p1b1p2/p1nppp2/7p/4PP2/qNN5/P1PQB1PP/R4R1K w kq - bm c3b1;
13%

8/2kPR3/5q2/5N2/8/1p1P4/1p6/1K6 w - - bm f5d4;
17%

r4r1k/pbnq1ppp/np3b2/3p1N2/5B2/2N3PB/PP3P1P/R2QR1K1 w - - bm c3e4;
7%

r1b1qrk1/ppBnppb1/2n4p/1NN1P1p1/3p4/8/PPP1BPPP/R2Q1R1K w - - bm c5e6;
10%

r1bqr1k1/pp1n1ppp/5b2/4N1B1/3p3P/8/PPPQ1PP1/2K1RB1R w - - bm e5f7;
12%

r1bqk2r/pppp1Npp/8/2bnP3/8/6K1/PB4PP/RN1Q3R b kq - bm e8g8;
9%

rnb1kb1r/1p3ppp/p5q1/4p3/3N4/4BB2/PPPQ1P1P/R3K2R w KQkq - bm e1c1;
17%

1r4k1/1q2pN1p/3pPnp1/8/2pQ4/P5PP/5P2/3R2K1 b - - bm b7d5;
18%

r2qr2k/pbp3pp/1p2Bb2/2p5/2P2P2/3R2P1/PP2Q1NP/5RK1 b - - bm d8d3;
11%

4r1k1/p1pb1ppp/Qbp1r3/8/1P6/2Pq1B2/R2P1PPP/2B2RK1 b - - bm d3f3;
13%

r5k1/p4n1p/6p1/2qPp3/2p1P1Q1/8/1rB3PP/R4R1K b - - bm a8f8;
18%

8/pR4pk/1b6/2p5/N1p5/8/PP1r2PP/6K1 b - - bm d2b2;
19%

2r1r3/p3bk1p/1pnqpppB/3n4/3P2Q1/PB3N2/1P3PPP/3RR1K1 w - - bm e1e6;
15%

5r2/1p4r1/3kp1b1/1Pp1p2p/2PpP3/q2B1PP1/3Q2K1/1R5R b - - bm f8f3;
21%

jm
Same question I asked above. What exactly are you counting / measuring? The numbers seem very low...
Yes, sorry. Forgot to answer that. I am NOT counting the first call to qsearch from the main search -- only when qsearch recursively calls itself.

jm

User avatar
hgm
Posts: 25075
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: QS investigation

Post by hgm » Fri Mar 08, 2013 10:23 pm

So you are not counting QS nodes...

User avatar
lucasart
Posts: 3141
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: QS investigation

Post by lucasart » Sat Mar 09, 2013 1:54 am

Searching the below positions at depth=12:

Code: Select all

"r1bqkbnr/pp1ppppp/2n5/2p5/4P3/5N2/PPPP1PPP/RNBQKB1R w KQkq -",
"r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq -",
"8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -",
"4rrk1/pp1n3p/3q2pQ/2p1pb2/2PP4/2P3N1/P2B2PP/4RRK1 b - - 7 19",
"rq3rk1/ppp2ppp/1bnpb3/3N2B1/3NP3/7P/PPPQ1PP1/2KR3R w - - 7 14",
"r1bq1r1k/1pp1n1pp/1p1p4/4p2Q/4Pp2/1BNP4/PPP2PPP/3R1RK1 w - - 2 14",
"r3r1k1/2p2ppp/p1p1bn2/8/1q2P3/2NPQN2/PPP3PP/R4RK1 b - - 2 15",
"r1bbk1nr/pp3p1p/2n5/1N4p1/2Np1B2/8/PPP2PPP/2KR1B1R w kq - 0 13",
"r1bq1rk1/ppp1nppp/4n3/3p3Q/3P4/1BP1B3/PP1N2PP/R4RK1 w - - 1 16",
"4r1k1/r1q2ppp/ppp2n2/4P3/5Rb1/1N1BQ3/PPP3PP/R5K1 w - - 1 17",
"2rqkb1r/ppp2p2/2npb1p1/1N1Nn2p/2P1PP2/8/PP2B1PP/R1BQK2R b KQ - 0 11",
"r1bq1r1k/b1p1npp1/p2p3p/1p6/3PP3/1B2NN2/PP3PPP/R2Q1RK1 w - - 1 16",
"3r1rk1/p5pp/bpp1pp2/8/q1PP1P2/b3P3/P2NQRPP/1R2B1K1 b - - 6 22",
"r1q2rk1/2p1bppp/2Pp4/p6b/Q1PNp3/4B3/PP1R1PPP/2K4R w - - 2 18",
"4k2r/1pb2ppp/1p2p3/1R1p4/3P4/2r1PN2/P4PPP/1R4K1 b - - 3 22",
"3q2k1/pb3p1p/4pbp1/2r5/PpN2N2/1P2P2P/5PP1/Q2R2K1 b - - 4 26",
"2r5/8/1n6/1P1p1pkp/p2P4/R1P1PKP1/8/1R6 w - - 0 1",
"r2q1rk1/1b1nbppp/4p3/3pP3/p1pP4/PpP2N1P/1P3PP1/R1BQRNK1 b 0 1",
"1r1r4/3q2k1/3p1p2/p1pNpPp1/PpP1B1Pp/1P5P/2Q5/6K1 b 0 1",
"r4rk1/1pp1q1pp/p2p4/3Pn3/1PP1Pp2/P7/3QB1PP/2R2RK1 b 0 1",
"r2q1rk1/1ppbbpp1/2n2n1p/p3pP2/3pP3/3P3N/PPP1B1PP/RNBQ1RK1 w 0 1",
Here are the numbers I get for DiscoCheck
%age of QS nodes: 68.0%
%age of QS nodes where the static eval does not cause a beta cutoff immediately: 39.5%

So my numbers are very different from ProDeo, it seems. But intuitively they make sense. There should be significantly more QS nodes than search nodes, no ?

PS:
- I have an arbitrary depth limit in my QS, where I return eval+see (unless it's check)
- I use 1 check in the QS, not 2 like ProDeo. In my testing, 2 was a regression, and so was 0. So I settled for 1 check , which seems to be standard (Fruit and Stockfish use 1 check for example).
Last edited by lucasart on Sat Mar 09, 2013 2:00 am, edited 2 times in total.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Uri Blass
Posts: 8796
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: QS investigation

Post by Uri Blass » Sat Mar 09, 2013 1:55 am

hgm wrote:So you are not counting QS nodes...
I disagree.

All the nodes that he is counting are QS nodes
and he is counting the number that is more interesting because it is
the number of the additional nodes that you need to search because of having a qsearch(instead of evaluation that gives the same value with no search in case the last thing was possible).

Post Reply