Only recaptures in qsearch?

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.
Post Reply
User avatar
JVMerlino
Posts: 1044
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Only recaptures in qsearch?

Post by JVMerlino » Sat Nov 21, 2009 10:40 pm

A few months ago, I was working on significantly improving the speed of my engine, and it was suggested by a couple of people that I should have the qsearch only check recaptures after the first capture. In other words, in the first ply of the qsearch, all moves are checked, but in each ply after that, only recaptures on the same target square are checked.

I implemented this and, no surprise, I got a big boost in speed.

Since then I have also added promotions to qsearch, and those can be checked at any ply, regardless of the target square.

But I recently had a thought that this "recapture only" method could be very dangerous. Consider this position, if it is reached at the beginning of qsearch:

[D] 2k5/2r3r1/1P6/8/8/8/1K4Q1/8 w

The recapture method will clearly see that Qxg7 is bad, because Black can recapture with Rxg7, which is on the same square. But it will see that bxc7 is GOOD, because (if only recaptures are checked), then Black will play Rxc7 and White supposedly wins material. But it completely misses that Black can play Rxg2, winning the queen.

So, I have changed my implementation such that the first TWO plies of the qsearch can be on any square, effectively giving the opponent the opportunity to choose the recapture square. I'm pretty sure this will solve the entire problem. But, of course, the qsearch is now noticeably slower.

Is this an effective way of solving the problem? Or was there really no problem at all? Or is the idea too dangerous even with this change and I should go back to checking all captures at all plies in qsearch?

Your thoughts are appreciated,

jm

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

Re: Only recaptures in qsearch?

Post by hgm » Sat Nov 21, 2009 10:44 pm

Initially micro-Max did a recapture-only QS. (I.e. I had a recapture extension, so that I did not need a dedicated QS.) But when I switched to using a full QS it gained about 60 Elo.

User avatar
michiguel
Posts: 6401
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Only recaptures in qsearch?

Post by michiguel » Sat Nov 21, 2009 11:47 pm

JVMerlino wrote:A few months ago, I was working on significantly improving the speed of my engine, and it was suggested by a couple of people that I should have the qsearch only check recaptures after the first capture. In other words, in the first ply of the qsearch, all moves are checked, but in each ply after that, only recaptures on the same target square are checked.

I implemented this and, no surprise, I got a big boost in speed.

Since then I have also added promotions to qsearch, and those can be checked at any ply, regardless of the target square.

But I recently had a thought that this "recapture only" method could be very dangerous. Consider this position, if it is reached at the beginning of qsearch:

[D] 2k5/2r3r1/1P6/8/8/8/1K4Q1/8 w

The recapture method will clearly see that Qxg7 is bad, because Black can recapture with Rxg7, which is on the same square. But it will see that bxc7 is GOOD, because (if only recaptures are checked), then Black will play Rxc7 and White supposedly wins material. But it completely misses that Black can play Rxg2, winning the queen.

So, I have changed my implementation such that the first TWO plies of the qsearch can be on any square, effectively giving the opponent the opportunity to choose the recapture square. I'm pretty sure this will solve the entire problem. But, of course, the qsearch is now noticeably slower.

Is this an effective way of solving the problem? Or was there really no problem at all? Or is the idea too dangerous even with this change and I should go back to checking all captures at all plies in qsearch?

Your thoughts are appreciated,

jm
I do recaptures only after 6 plies of traditional qsearch. I have no idea if this works better or not. I need to test this as well as many other gazillion parameters. My intuition tells me that after 6 plies of q search, recapt only should be relatively safe. It may not reduce the tree too much, but it may avoid explosions in certain positions. I also have the feeling that this number should be even, otherwise, you give a big advantage to the side that capture first.

Miguel

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Only recaptures in qsearch?

Post by bob » Sun Nov 22, 2009 5:38 pm

JVMerlino wrote:A few months ago, I was working on significantly improving the speed of my engine, and it was suggested by a couple of people that I should have the qsearch only check recaptures after the first capture. In other words, in the first ply of the qsearch, all moves are checked, but in each ply after that, only recaptures on the same target square are checked.

I implemented this and, no surprise, I got a big boost in speed.

Since then I have also added promotions to qsearch, and those can be checked at any ply, regardless of the target square.

But I recently had a thought that this "recapture only" method could be very dangerous. Consider this position, if it is reached at the beginning of qsearch:

[D] 2k5/2r3r1/1P6/8/8/8/1K4Q1/8 w

The recapture method will clearly see that Qxg7 is bad, because Black can recapture with Rxg7, which is on the same square. But it will see that bxc7 is GOOD, because (if only recaptures are checked), then Black will play Rxc7 and White supposedly wins material. But it completely misses that Black can play Rxg2, winning the queen.

So, I have changed my implementation such that the first TWO plies of the qsearch can be on any square, effectively giving the opponent the opportunity to choose the recapture square. I'm pretty sure this will solve the entire problem. But, of course, the qsearch is now noticeably slower.

Is this an effective way of solving the problem? Or was there really no problem at all? Or is the idea too dangerous even with this change and I should go back to checking all captures at all plies in qsearch?

Your thoughts are appreciated,

jm
There are a couple of approaches, each of which offers something different.

(1) you could just use SEE() on the target square of the last move you made, to see if that move actually appears to lose material or not. At some point, Junior did something like this. The advantage? An extra ply or two of normal search, since you have no q-search at all. The disadvantage? SEE() is not very accurate with regards to overloaded/pinned pieces or tactical traps.

(2) captures-only, but allow captures on any square. This makes a big q-search and will slow the depth down a bit.

(3) captures-only, but use SEE() to screen apparently losing captures such as QxR PxQ, so that you don't search moves that are almost always hopeless.

(4) captures only on the destination square of the previous move. This is no better than using SEE() and would be more expensive in terms of computation, so I would use (1) rather than this.

(5) captures-only + safe checking moves at the first ply or two or three. I do this in Crafty, and only include moves that give check in the first ply of the q-search. This lets you detect some threats that null-move tends to hide and thus overlook.

BTW when I say "captures only" you could/should include pawn promotions, or at least include pawn promotions to a queen (the under-promotions can be skipped out that far into the tree with reasonable safety). I include promotions to a queen, but only if the promotion doesn't appear to lose materiax (d8=Q is not very good if the opponent can reply Rxd8 safely.)

The goal is to restrict the q-search as much as possible, as it is full of errors (only rarely is the best move in a given position going to be a capture). By reducing the q-search tree, you can search more deeply with a normal search that doesn't throw out all non-captures.

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Only recaptures in qsearch?

Post by bob » Sun Nov 22, 2009 5:41 pm

hgm wrote:Initially micro-Max did a recapture-only QS. (I.e. I had a recapture extension, so that I did not need a dedicated QS.) But when I switched to using a full QS it gained about 60 Elo.
That actually has a ring of sensibility in it and is worth experimenting with. The general theme is that once you start the q-search, you are introducing huge error into the search anyway, so as you get further into it, you may as well limit the effort as well.

User avatar
Daniel Mehrmann
Posts: 857
Joined: Wed Mar 08, 2006 8:24 pm
Location: Germany
Full name: Daniel Mehrmann

Re: Only recaptures in qsearch?

Post by Daniel Mehrmann » Mon Nov 23, 2009 12:17 pm

Hi !

There are serval solutions for your problem as Bob pointed out already. I think the best way would be to work with "Pins" or your search-window bounds if you have no SEE.

Bound based (without SEE): You can take your bounds to drop "bad" captures or recaptures. A capture move in QS is _only_ interesting if it, at least, fit into your current search-window. A pseudo code would looks like this:

Code: Select all

while (moves) {
	if &#40;StandPat + ScoreMove&#40;move&#41; + bonus < alpha&#41; &#123;
		continue;
	&#125;  
	
	makeMove&#40;move&#41;;
	.....
&#125;

ScoreMove returns the score of the captured piece.    
Pin based:

Your pins might be generated through your evaluation function or attacktables. Always if a pin is located in the current position the "only recapture QS" will be disabled only in this position.


Best,
Daniel

Post Reply