Quiescence Search Performance

[theturk1234]

Ok,
When I profile my engine I find that Quiescence search is taking about 60-70% of the processing time. Obviously I'm doing something wrong....
Are there any Quiescence pruning techniques that I should know about? I'm using a "stand pat" score to get beta cutoffs, but that's about it. I think I'm very lacking in quiescence performance here.

Thank you,
David Cimbalista

[hgm]

Sounds normal to me. I am not sure what exactly you count as timespent in QS. Does that include evaluation?

[theturk1234]

Yes, eval is included in the time in quiescence. I thought I read somewhere that quiescence search should take like 10-30% of the time of the whole search. Is this correct?

[brtzsnr]

SEE pruning in QS would decrease the number of searched nodes quite a bit. Until then, expect that the majority of nodes searched are in QS because it happens at the bottom of the search tree. 60-70% is normal when the engine is new.

[theturk1234]

Yes, as far as I know, I'm using SEE. Basically I have a function that takes the value of the captured piece and subtracts this from the value of the moving piece and if it's greater than 0, search it.
Do you notice and optimizations that can be done with that?

Thanks,
David

[hgm]

Basically I have a function that takes the value of the captured piece and subtracts this from the value of the moving piece and if it's greater than 0, search it.

That seems broken, as you would prune many good captures.

If you include evaluation time, it depends a lot on how heavy your evaluation is. Evaluation alone can easily be 80% of your execution time, even in a program without QS.

[brtzsnr]

SEE in general is not limited to one capture and can continue for several moves. See the excellent documentation at https://chessprogramming.wikispaces.com ... Evaluation .

The way I apply it is

Code: Select all

		eng.DoMove(move)
		if eng.Position.IsChecked(us) || !inCheck && seeSign(pos, move) {
			eng.UndoMove()
			continue
		}
		score := -eng.searchQuiescence(-β, -localα)
		eng.UndoMove()

SEE and stand-pat are my main ways to prune QS. I also have somekind of futility pruning, but it's only to avoid doing needless evals.

[cdani]

Quiescence steps in Andscacs:

* Possible return by hash value.
* Standpat.
* Try hash move even with moves that are no captures.
* Captures and promotions. Possibly futility/SEE pruning.
* Generate checks at first level of quiescence.

[hgm]

* Try hash move even with moves that are no captures.

In some of my engines that did this (as a bug) it caused crashing in some positions, because of infinite recursion. (Especially in combination with check extension.)

[Sven]

Yes, eval is included in the time in quiescence. I thought I read somewhere that quiescence search should take like 10-30% of the time of the whole search. Is this correct?

There is no such globally valid number in my opinion. It depends heavily on the effort you spend in evaluation. If you only do material + PST, for instance, and you even calculate this incrementally in make/unmake then the effort for evaluation is zero so QS will be quite cheap. Strong engines have much more than that, though. So I think it is not uncommon that strong engines spend 30-40% or more of all computation time in their evaluation function (which is not the same as "in quiescence search" since the latter also includes everything the search itself does).

If you have implemented QS correctly and with a decent move ordering then you can expect that 80-90% of all nodes are QS nodes, including the full-width leaves which are QS root nodes (depth=0). How that translates into a percentage of time is hard to say.