Page 1 of 3
Quiescence Search Performance
Posted: Thu Jul 28, 2016 5:35 pm
by 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
Re: Quiescence Search Performance
Posted: Thu Jul 28, 2016 6:12 pm
by hgm
Sounds normal to me. I am not sure what exactly you count as timespent in QS. Does that include evaluation?
Re: Quiescence Search Performance
Posted: Thu Jul 28, 2016 7:21 pm
by 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?
Re: Quiescence Search Performance
Posted: Thu Jul 28, 2016 7:26 pm
by 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.
Re: Quiescence Search Performance
Posted: Thu Jul 28, 2016 7:44 pm
by 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
Re: Quiescence Search Performance
Posted: Thu Jul 28, 2016 8:00 pm
by hgm
theturk1234 wrote: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.
Re: Quiescence Search Performance
Posted: Thu Jul 28, 2016 8:00 pm
by 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.
Re: Quiescence Search Performance
Posted: Thu Jul 28, 2016 8:41 pm
by 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.
Re: Quiescence Search Performance
Posted: Thu Jul 28, 2016 9:17 pm
by hgm
cdani wrote:* 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.)
Re: Quiescence Search Performance
Posted: Fri Jul 29, 2016 12:33 am
by Sven
theturk1234 wrote: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.