Quiescence Search Performance

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
theturk1234
Posts: 52
Joined: Tue Jul 12, 2016 3:28 am

Quiescence Search Performance

Post by theturk1234 » Thu Jul 28, 2016 3:35 pm

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

User avatar
hgm
Posts: 25076
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Quiescence Search Performance

Post by hgm » Thu Jul 28, 2016 4:12 pm

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

theturk1234
Posts: 52
Joined: Tue Jul 12, 2016 3:28 am

Re: Quiescence Search Performance

Post by theturk1234 » Thu Jul 28, 2016 5:21 pm

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
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

Re: Quiescence Search Performance

Post by brtzsnr » Thu Jul 28, 2016 5:26 pm

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
Posts: 52
Joined: Tue Jul 12, 2016 3:28 am

Re: Quiescence Search Performance

Post by theturk1234 » Thu Jul 28, 2016 5:44 pm

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

User avatar
hgm
Posts: 25076
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Quiescence Search Performance

Post by hgm » Thu Jul 28, 2016 6:00 pm

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.

brtzsnr
Posts: 433
Joined: Fri Jan 16, 2015 3:02 pm
Contact:

Re: Quiescence Search Performance

Post by brtzsnr » Thu Jul 28, 2016 6:00 pm

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.

User avatar
cdani
Posts: 2175
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Quiescence Search Performance

Post by cdani » Thu Jul 28, 2016 6:41 pm

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.

User avatar
hgm
Posts: 25076
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Quiescence Search Performance

Post by hgm » Thu Jul 28, 2016 7:17 pm

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.)

Sven
Posts: 3883
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Quiescence Search Performance

Post by Sven » Thu Jul 28, 2016 10:33 pm

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.

Post Reply