Quiescence perft

[zd3nik]

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

[hgm]

In many positions an all-capture search would cause a tremendous search explosion, if it were not for alpha-beta pruning and good move ordering. In perft you would not have the protection of those, however. So I wonder if a QS perft would be generally usable, or that on most positions the count would suddenly jump from one depth to the next to so many billions that it would never finish in practice.

It might be more useful to just allow a fixed number of capture-only levels on top of a normal search. Perhaps just one level with checks, and one without checks.

[zd3nik]

It might be more useful to just allow a fixed number of capture-only levels on top of a normal search. Perhaps just one level with checks, and one without checks.

What you suggest is what I already described. Normal perft plus one level of checks+caps+promos (at depth=0) and one more level of just caps+promos (at depth=-1).

Perhaps I didn't make it clear that it stops at depth=-1 instead of continuing on like a normal qsearch until the position becomes "quiet".

[hgm]

Ah, OK. Sorry I missed that. Then there is little danger.

It could also be useful to have perft numbers for pseudo-legal moves, with a sufficiently unambiguous definition of the latter.

[stegemma]

If the scope is to debug quiescence search, maybe it could be done just starting with quiescence at the root of the position. This could be done in similar time than standard perft (less time, in fact), even without alpha-beta (as perft does).

If we agree on the conditions to use, then the quiescence of two different engines could be compared.

For sample:

qperft 6 FEN CP+ -> nodes

could means: qperft 6 at FEN position counting only Captures, Promotions and checks gives nodes count.

qperft 6 FEN CP+3 -> nodes

is the same but limiting checks to 3 plies.

[Sven]

I suggest to call the new command "qsperft" since there is already a program named "qperft".

[hgm]

Cperft or ccperft would be more apt, because it is not really looking for quiescence, but more a captures-only or checks+captures only perft.

Starting at the root with captures only seems a bad idea; one of the reasons perft is so suitable for detecting bugs is that exhaustive search of the initial plies sets up all kind of exceptional cases irrespective of the initial position on which your move generator might err. With captures only there are many positions you could not reach. (E.g. there would never be any e.p. capture other than in the root, so the e.p. section of your capture generator would never be tested if you did not think of starting in a position that has e.p. rights!)

[stegemma]

Cperft or ccperft would be more apt, because it is not really looking for quiescence, but more a captures-only or checks+captures only perft.

Starting at the root with captures only seems a bad idea; one of the reasons perft is so suitable for detecting bugs is that exhaustive search of the initial plies sets up all kind of exceptional cases irrespective of the initial position on which your move generator might err. With captures only there are many positions you could not reach. (E.g. there would never be any e.p. capture other than in the root, so the e.p. section of your capture generator would never be tested if you did not think of starting in a position that has e.p. rights!)

Right, so we need an extra parameters to say "compute queiescence perft after N standard plies".

The name is not so important but maybe it could be called "Reducted perft" -> rperft or reperft?

[hgm]

You could indeed introduce separate parameters for the depth of the various move selections. But I think doing one level of each of the reduced move sets would be enough. The important thing is that you get several plies of unrestricted search, to set up all possible exceptional cases. One levelof restricted moving then should already be able to find any errors in the move generation for that, as there would already be nodes that where reached by (a sequence of) captures.

[Sven]

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> &#91; <nCapturePlies> &#91; <nCheckPlies> &#93; &#93;
cdivide <nRegularPlies> &#91; <nCapturePlies> &#91; <nCheckPlies> &#93; &#93;

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.