Quiesce Search Move Ordering

[Charles Roberson]

We've had a several posts on quiesce of late.

Here are some of my learnings from NoonianChess and Telepath.

1) Don't replace Quiesce with SEE -- it doesn't work well

2) there are two ways one might implement MVV/LVA for move ordering

2a) value of captured piece - value of capuring piece

2b) value of captured piece - small percentage of capturing piece
This puts all captures of the queen (inclucing qxq) ahead
of captures of rooks .....

Version 2b produces a 1.5x speedup over 2a.

I was clued into this in a converation with Gian-Carlo, Andrew
Williams and Peter McKenzie.
Just a casual converation at WCCC led to a 2x speedup overnight.
This is one of the major advantages of attending face-to-face
events.

3) You can not blindly prune inferior captures.

I tried it and have some counter examples to prove its bad.
I am defining an inferior capture as big piece takes smaller piece
and no search or SEE is done.
You get a nice speed up but the engine performs worse.

4) Using SEE for all move ordering produces better
ordering but doesn't speed things up due to overhead of SEE.

5) The best use of SEE in Quiesce seems to be only for inferior
captures. You can use it for move ordering or for pruning the
inferior captures.

6) I've not recently tried transposition tables in quiesce and don't
remember what my results were. They are logged in a journal.

7) I've not recently tried tracking the PV in Quiesce and putting the
PV first. Seems this would work well as it is quite efficient to track
even without hashtables.

8) Early versions of a program may produce all moves for quiesce and
search only captures and promos ...
This is quite inefficient as you waste time generating the moves and
ordering the noncaptures to the tail of the list. Better to generate
only what you need.

9) I had an early version of NoonianChess generating moves
completely on demand. It generated one move, searched it,
generated the next, searched it ......
This didn't not work well as I didn't get the ordering well.

I am coding an experiement to tell me the average branchfactor in
a full quiesce search. Full meaning search all captures and promos.
Knowing the average branchfactor in Quiesce might shed some light
on how much cost in move ordering is worth the effort.

[Pradu]

Don't replace Quiesce with SEE -- it doesn't work well

How can you replace a quiesce search with an SEE? They work on different parameters. Quiesce rates a position and SEE rates a move.

[Charles Roberson]

You can replace quiesce with SEE in this manner.

On the final ply of the interior search a capture is made.
Don't just call the position evaluator,
heuristically continue that node. Do so by looking only at captures
on that square and then call the position evaluator. A capture only
search focused on a given square could be replaced by SEE.

[Charles Roberson]

Just tried using MVV/LVA in Quiesce with the PV move tried first.
This increased the number of interior nodes and the number of
quiesce nodes searched.

[Daniel Shawul]

I use SEE for all of the moves generated in quiescence.
that includes check evasion and checking moves. Some people use MVV/LVA for ordering this moves and then SEE to cut off.
Do you find a significat speed up by doing this?
daniel

[Reinhard Scharnagl]

Hi all,

because of being simple I only use a kind of MVV/LVA in Smirf related to version b) mentioned some postings before. That will be overlayed by a bonus when being a check threat. Then there is additionally an overlayed bonus/malus for a trivial positional preestimation of the move. Any found killer move will be placed first. Any found known optimal move would be placed on second position. All recapture moves will have added the same value as the optimal move distributing recaptures around that second placed move. I am satisfied with the resulting presort of generated moves in Smirf.

Reinhard.

[Charles Roberson]

Curious as to others Qnode/leafInode ratio.

Here are my definitions:

Code: Select all

       Search ()
       {
             if (ply>0)
             {
                    Inode++
                     .....
              }
              else
              {
                   leafInodes++
                   Quiesce()
               }
         }

        Quiesce()
        {
               Qnode++
               ......
        }


Here are two positions I've tried and results. What are yours?
I find it interesting how small the ratio is. My Quiesce searches
captures and promos only. My Quiesce runs until it finds a
quiet position; no depth limiting.

They are from the BK test suite.
r1bqk2r/pp2bppp/2p5/3pP3/P2Q1P2/2N1B3/1PP3PP/R4RK1 b kq - 0 0 2r2rk1/1bqnbpp1/1p1ppn1p/pP6/N1P1P3/P2B1N1P/1B2QPP1/R2R2K1 b - - 0 0

Code: Select all

    Depth     INodes       LeafInodes       Qnodes    TotalNodes
     7       3341284          2902307          7730392      11071676
     8       9745383          8637400        19553551      29298934
     9      26063257         22768487       46816414      72879671


It is interesting that the Qnodes/LeafInodes ~= 2
If that is typically the case then adding a complicated move ordering
mechanism may not improve over MVV/LVA (concerning runtime).

[Reinhard Scharnagl]

Hi Charles,

I am sorry, except of special test routines for expanding special positions (also incl. move ordering) or some Perft variants etc. I have not yet placed statistic creating parts into my Smirf engine. I am actually putting my efforts into finishing a first (Shareware?) version (about estimated 2575 Elo) until end of next month. It will be a rare creation consisting of a GUI for 8x8 and 10x8 chess variants communicating with a single all purpose engine.

Reinhard.

[Robert Allgeuer]

Charles,
so you count leaf nodes twice? once as leaf node and once as part of the qnodes.

Robert

[Charles Roberson]

Normally, I look at inodes and qnodes only where there is no
double counting. For this issue, I am estimating branchfactor in
the qsearch. Part of that estimation is knowing the number of
nodes that spawn a qsearch (leaf inodes).