How to test quiescence search quality?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
SMIRF
Posts: 91
Joined: Wed Mar 26, 2014 3:29 pm
Location: Buettelborn/Hessen/Germany
Contact:

How to test quiescence search quality?

Post by SMIRF » Thu Feb 26, 2015 12:30 pm

Having only a very weak evaluation yet, I am about to verify / optimize my quiescence search, move sorting, and killer heuristic. I have some test positions, to which I evaluate all possible moves by unshrinked quiescence and count every call of the quiescence routine.

Are there any comparable node counts e.g. to following position:

Code: Select all

XFEN  0: 3q2R1/2P5/1k1B4/4np2/1NPK1Pr1/1R6/PP1N1Q2/3q2b1 w - - 0 123
   +-a--b--c--d--e--f--g--h-+
 8 |   &#58;&#58;&#58;   &#91;q&#93;   &#58;&#58;&#58;<R>&#58;&#58;&#58;|  Compiled on Feb 26 2015
 7 |&#58;&#58;&#58;   <P>   &#58;&#58;&#58;   &#58;&#58;&#58;   |  MS Vis.Studio C/C++ 32-Bit Vers. 18.0
 6 |   &#91;k&#93;   <B>   &#58;&#58;&#58;   &#58;&#58;&#58;|
 5 |&#58;&#58;&#58;   &#58;&#58;&#58;   &#91;n&#93;&#91;p&#93;&#58;&#58;&#58;   |  Move &#40;preevaluated and sorted&#41; count&#58; 37
 4 |   <N><P><K>   <P>&#91;r&#93;&#58;&#58;&#58;|
 3 |&#58;&#58;&#58;<R>&#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   |
 2 |<P><P>   <N>   <Q>   &#58;&#58;&#58;|
 1 |&#58;&#58;&#58;   &#58;&#58;&#58;&#91;q&#93;&#58;&#58;&#58;   &#91;b&#93;   |
&#40;w&#41;+-a--b--c--d--e--f--g--h-+

 c7xd8Q+  Kd4xe5+  Kd4-d5+  c7xd8B+  Kd4-c3+  Nb4-d3+  Nb4-d5++
 Nb4-c2+  c4-c5+   Nb4-c6+  Nb4-a6+  c7xd8R   Rg8xd8   c7xd8N
 c7-c8N+  c7-c8Q   Rg8xg4   c7-c8R   Rb3-e3   Rg8-g5   Rg8-g7
 Rg8-g6   Rg8-f8   Qf2xg1   Qf2-e3   Rb3-f3   c7-c8B   Kd4-e3
 Rb3-h3   Rb3-g3   Rb3-a3   Rb3-c3   a2-a4    a2-a3    Rb3-d3
 Rg8-h8   Rg8-e8

 50.000   19.234   15.585   14.956   14.804   12.995   11.790
 11.758   11.638   11.460    8.363    7.549    6.220    3.408
  2.154    2.154    1.959    0.066   -2.400   -3.377   -3.381
 -3.381   -3.396   -4.892   -4.952   -5.098   -5.888   -8.165
 -8.328   -8.330   -8.352   -8.387   -8.406   -8.418   -8.427
 -8.901   -8.905

Counter&#58; 2302

jdart
Posts: 3842
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: How to test quiescence search quality?

Post by jdart » Thu Feb 26, 2015 2:27 pm

How many times you call quiescence depends on your scoring routine (it will change how much you cutoff), among other things. So counting these nodes is not useful.

For verifying you have reasonable move ordering you can instrument your code so that it measures how often the first move is successful (causes cutoff or is returned as the best move at the end of qsearch), how often it is the 2nd move, etc.

You should be getting a high percentage for the first few moves. The first four moves will probably sum to 90% or higher.

Note though for the quiescence search, the ordering methods are usually different than for the main search and there are usually far fewer moves to search. So you will get different numbers there, but still the first few moves should be successful most of the time.

--Jon

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: How to test quiescence search quality?

Post by kbhearn » Thu Feb 26, 2015 9:01 pm

While i can see it may be interesting to compare with a top engine, it's not really as simple as a node count as the philosophy of a qsearch may vary significantly from engine to engine.

- try bad (SEE < 0) captures?
- try futile captures (capture value expected to be insufficient to avoid next player standing pat and failing high)?
- generate full evasions while king in check instead of standing pat?
- allow safe(SEE >=0) noncapture checks for the first N ply of quiescence?
- allow unsafe noncapture checks for the first N ply of quiescence?

The philosophy of answering no to any of those questions is that you'd rather the quiescence to be as small as possible and you'll deal with the less common issues those moves might provide in a future iteration where the node is being considered more fully. Answering yes to those questions you're trying to catch some remaining outstanding tactics on the current iteration.

Furthermore, pathological cases like the example you tested are not really so important (beyond the fact that they do terminate) as positions that are typical within the search (which while different than positions that are typical within a game are not so different as to match with your example).

User avatar
SMIRF
Posts: 91
Joined: Wed Mar 26, 2014 3:29 pm
Location: Buettelborn/Hessen/Germany
Contact:

Re: How to test quiescence search quality?

Post by SMIRF » Sat Feb 28, 2015 10:10 am

Well I see, that modifying and testing of quiescence search will not make much sense, before a usable evaluation function is implemented. When I have added a simple king savety component, I already got:

Code: Select all

XFEN  0&#58; 3q2R1/2P5/1k1B4/4np2/1NPK1Pr1/1R6/PP1N1Q2/3q2b1 w - - 0 123
   +-a--b--c--d--e--f--g--h-+
 8 |   &#58;&#58;&#58;   &#91;q&#93;   &#58;&#58;&#58;<R>&#58;&#58;&#58;|  Compiled on Feb 28 2015
 7 |&#58;&#58;&#58;   <P>   &#58;&#58;&#58;   &#58;&#58;&#58;   |  MS Vis.Studio C/C++ 64-Bit Vers. 18.0 
 6 |   &#91;k&#93;   <B>   &#58;&#58;&#58;   &#58;&#58;&#58;|
 5 |&#58;&#58;&#58;   &#58;&#58;&#58;   &#91;n&#93;&#91;p&#93;&#58;&#58;&#58;   |  Move &#40;preevaluated and sorted&#41; count&#58; 37
 4 |   <N><P><K>   <P>&#91;r&#93;&#58;&#58;&#58;|
 3 |&#58;&#58;&#58;<R>&#58;&#58;&#58;   &#58;&#58;&#58;   &#58;&#58;&#58;   |
 2 |<P><P>   <N>   <Q>   &#58;&#58;&#58;|
 1 |&#58;&#58;&#58;   &#58;&#58;&#58;&#91;q&#93;&#58;&#58;&#58;   &#91;b&#93;   |
&#40;w&#41;+-a--b--c--d--e--f--g--h-+

 c7xd8Q+  c7xd8B+  Kd4xe5+  Kd4-c3+  Nb4-d3+  Kd4-d5+  Nb4-d5++
 c4-c5+   Nb4-c6+  Nb4-c2+  Nb4-a6+  c7xd8R   Rg8xd8   c7xd8N
 c7-c8N+  c7-c8Q   Rg8xg4   c7-c8R   Rb3-e3   Rg8-g5   Rg8-g7
 Rg8-g6   Rg8-f8   Qf2xg1   Rb3-f3   Qf2-e3   c7-c8B   Rb3-a3
 Rb3-g3   Rb3-h3   Rb3-c3   a2-a4    a2-a3    Rb3-d3   Kd4-e3
 Rg8-e8   Rg8-h8

 Win&#58; 2   15.476   15.450   14.735   13.171   11.990   11.856
 11.810   11.800   11.684    8.289    7.549    6.138    3.908
  2.346    2.154    1.877    0.857   -2.400   -3.459   -3.463
 -3.463   -3.479   -4.892   -5.098   -5.124   -5.575   -7.977
 -8.152   -8.328   -8.387   -8.406   -8.418   -8.427   -8.534
 -8.765   -8.901

Counter&#58; 2174

Post Reply