Quiescence perft

[bob]

The usual perft search is very handy for validating your standard move generator (and also handy for performance tuning).

But most engines spend roughly half of their time (or more) in quiescence search. So it would be just as handy to have a way of validating check/promo/capture/check-evasion move generation.

In my last two engines I added a qperft command which is similar to perft, except it does 2 additional plies of search: one with quiescence move generation at depth 0 and one at depth -1.

I know this won't work across the board because not all engines perform the same kind of move generation in quiescence search. I typically make my engines generate all captures, ALL promotions, and all checks (including discovered checks) at depth 0 and only generate captures and queen promotions at depth < 0. And at any depth ALL moves are generated when the side to move is in check (which is typically done by a separate GetCheckEvasions function). The qperft command as I've implemented it also returns total number of nodes, not just leaf nodes.

So here's what I'm asking:

1. Is there already some form of quiescence move generation validation that people are using?

2. I know this one is a long shot, but if anyone out there has an engine that does quiescence move generation identical to what I described above, would you be interested in implementing a qperft function and comparing node counts? I've already done parity checks using the 2 engines I've written which have qperft commands. But more implementations would mean more confidence in the accuracy of the results - it's quite possible my 2 different implementations both suffer from similar bugs and therefore return the same incorrect results.

For an example, here's the output of qperft depth 5 from startpos:

Code: Select all

qperft depth 5
info string a2a3 581905
info string a2a4 591155
info string b1a3 545544
info string b1c3 547598
info string b2b3 552189
info string b2b4 635496
info string c2c3 545209
info string c2c4 725709
info string d2d3 1267879
info string d2d4 1702483
info string e2e3 1156100
info string e2e4 1403687
info string f2f3 572572
info string f2f4 681977
info string g1f3 602979
info string g1h3 558843
info string g2g3 554457
info string g2g4 682667
info string h2h3 564391
info string h2h4 654755
info string Total 15127595
info string Snodes 5072212, Qnodes 10055383 (66.4705%)

This does 5 plies of regular move generation plus qsearch(depth=0) movegen [ply 6] and qsearch(depth=-1) movegen [ply 7].

Snodes = total number of normal search nodes. Qnodes = total nodes in quiescence search (depth 0 and -1 combined).

STC

I don't see how this can work. For example, do you include checks in the q-search or not? Some do, some do not. How many plies of checks? What about escaping check? All moves or is just one good enough? What about alpha/beta? Do you examine all captures, or do you toss out losing captures? Do you toss out even exchanges after some depth limit?

Perft has no options like those.

[zd3nik]

I would leave the decision about the required depth to the user, i.e. the engine developer. What about this proposal for a somewhat generic command line interface:

Code: Select all

cperft  <nRegularPlies> [ <nCapturePlies> [ <nCheckPlies> ] ]
cdivide <nRegularPlies> [ <nCapturePlies> [ <nCheckPlies> ] ]

with 0 as default values for <nCapturePlies> and <nCheckPlies>.

"cperft 3 2" would do 3 plies full-width and 2 plies captures only.
"cperft 3 2 1" would additionally include checks at the first level of capture-only search.

"cperft 3" would do the same as "perft 3".

"cdivide ..." would do the same as "cperft ..." but additionally print subtotals for each root move, same as "divide".

One more note: due to the inherently smaller number of leaf nodes in a capture-only search tree the speed advantage of the typical bulk-counting method will be smaller than in the standard "perft" case.

+1

[zd3nik]

I don't see how this can work. For example, do you include checks in the q-search or not? Some do, some do not. How many plies of checks? What about escaping check? All moves or is just one good enough? What about alpha/beta? Do you examine all captures, or do you toss out losing captures? Do you toss out even exchanges after some depth limit?

Perft has no options like those.

It's not that complicated. Here's a more generalized description.

1. Mode A: Applied at ALL nodes. When in check generate ALL legal moves.

2. Mode B: Applied at shallow quiescence plies (depth 0 through N). Generate ALL legal checks+caps+promos. Checks include discovered checks. promotions include all promotions, including under-promotions.

3. Mode C: Applied at deep quiescence plies (depth N+1 through Z). Generate legal caps+promos. Generate all captures but only Queen promotions (no under promotions). If any of those moves happen to also generate check so be it.

Going with Sven's proposal, all of the tweaky bits could be user definable. Like whether or not under-promotions should be generated. But for cases when the side to move is in check I think it's best to stick with generating all moves, since that's what the vast majority of engines do in quiescence search AFAIK (it also keeps the proposal and therefore the implementations simpler).

[zd3nik]

I don't see how this can work. For example, do you include checks in the q-search or not? Some do, some do not. How many plies of checks? What about escaping check? All moves or is just one good enough? What about alpha/beta? Do you examine all captures, or do you toss out losing captures? Do you toss out even exchanges after some depth limit?

Perft has no options like those.

It's not that complicated. Here's a more generalized description.

1. Mode A: Applied at ALL nodes. When in check generate ALL legal moves.

2. Mode B: Applied at shallow quiescence plies (depth 0 through N). Generate ALL legal checks+caps+promos. Checks include discovered checks. promotions include all promotions, including under-promotions.

3. Mode C: Applied at deep quiescence plies (depth N+1 through Z). Generate legal caps+promos. Generate all captures but only Queen promotions (no under promotions). If any of those moves happen to also generate check so be it.

Going with Sven's proposal, all of the tweaky bits could be user definable. Like whether or not under-promotions should be generated. But for cases when the side to move is in check I think it's best to stick with generating all moves, since that's what the vast majority of engines do in quiescence search AFAIK (it also keeps the proposal and therefore the implementations simpler).

Oops. I forgot a mode:

Mode A: Generate all legal moves.

Mode B: Generate all legal moves when in check regardless of where you are in the search tree (Mode A in prior post)

Mode C: Generate legal checks+caps+all_promos (Mode B in prior post)

Mode D: Generate legal caps+queen_promos (Mode C in prior post)