Q search explosion

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.
op12no2
Posts: 349
Joined: Tue Feb 04, 2014 11:25 am
Location: Mumbles, Wales, UK.
Full name: Colin Jenkins
Contact:

Q search explosion

Post by op12no2 » Thu Mar 30, 2017 11:30 am

Mate in 1 via Dann Corbit.

[d]1QqQqQq1/r6Q/Q6q/q6Q/B2q4/q6Q/k6K/1qQ1QqRb w - -

My q search is primitive, no gives/in check tests etc.

A one ply analysis of the above position 'never ends' because as far as I can see, my engine is just lost in an exhaustive q search. It's Javascript and what in fact happens, is it slows to a crawl.

I added a hack to only search -depths to twice the current top level ID depth, but that seems like a cop out? There again, does q search really need to be exhaustive always...?

Does anybody else have problems with this position, or take steps to limit q search ?

For me, it's the only position out of 9560 mate-in-ones that it happens with. But I guess it depends which first move is tried as well...

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

Re: Q search explosion

Post by hgm » Thu Mar 30, 2017 12:38 pm

I have a similar problem in Tenjiku Shogi. Except that there the problem already occurs in the standard opening position. Because the jumping sliders already behave like the Queens in the position above. And like the non-capture check is much more relevant for the game than any capture in the position above (because it is mate), there usually are much more profitable non-captures for manoeuvring the Fire Demon in Tenjiku.

If you would restrict QS to
1) L x H captures
2) capture of unprotected pieces
3) recapture on the same square
the position above might not be so hard.

Another approach would be to replace QS by a search that at d <= 8 only considers captures + stand pat or check evasion, and at d > 4 also safe checks.

Stan Arts
Posts: 179
Joined: Fri Feb 14, 2014 9:53 pm
Location: the Netherlands

Re: Q search explosion

Post by Stan Arts » Thu Mar 30, 2017 1:07 pm

Do you do "delta pruning" where you don't consider captures if the captured piece + margin does not get you close to alpha?

A hard stop on Qsearch depth seems rough indeed but instead you could consider only doing recaptures on the same square after some depth. For example after 4+ ply. Will have you miss some deep tactics where after a delaying forced exchange you can capture something elsewhere but in general returns stable scores and is effective at limiting Qsearch explosions.

op12no2
Posts: 349
Joined: Tue Feb 04, 2014 11:25 am
Location: Mumbles, Wales, UK.
Full name: Colin Jenkins
Contact:

Re: Q search explosion

Post by op12no2 » Thu Mar 30, 2017 2:02 pm

Thanks Hans and Stan - I'll try some experiments. While the above position is not likely, it does kinda imply I'm possibly be wasting time in Q in general.

The hard cutoff version (-depth*2 > current_ID_Start_Depth) is doing pretty good so far in my standard soak test, though coincidently Nemeton in particular is doing very well against it :)

Yes I do delta pruning of (standPat + pieceValue + 200 < alpha) if not endgame phase or promotion.

User avatar
JVMerlino
Posts: 1044
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Q search explosion

Post by JVMerlino » Thu Mar 30, 2017 3:37 pm

I initially had this problem and attempted to reduce its effect in two ways:

1) Put a limit on the number of check extensions in any given branch. I arbitrarily chose 10. That code is still in today, but I don't really know how effective it is in actual games.

2) Once the qsearch has gone 4 plies deep (again, an arbitrary number) I only allow the qsearch to do recaptures on the previous capture's square. This code was eventually commented out.

So, using the latest Myrddin as described above with one core on a fairly slow machine, the position is solved in about 3.5 seconds and 2.4M nodes.

However, if I re-enable #2 above, the position is solved instantly with only 3362 nodes searched. You may look into this for your engine to see if it actually gives you an elo boost.

jm

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Q search explosion

Post by Evert » Thu Mar 30, 2017 5:43 pm

JVMerlino wrote: 2) Once the qsearch has gone 4 plies deep (again, an arbitrary number) I only allow the qsearch to do recaptures on the previous capture's square. This code was eventually commented out.
It seems to me that if you prune SEE<0 captures this would already do most of what a recapture-only search gives you, and do it more cheaply. Am I missing something?

mar
Posts: 2195
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Q search explosion

Post by mar » Thu Mar 30, 2017 5:52 pm

op12no2 wrote:I added a hack to only search -depths to twice the current top level ID depth, but that seems like a cop out?
Exactly what I do in Cheng, except I do this: minqsdepth = -3*rootdepth; no elo regression.

It can still explode at bigger depths but I don't really care much about such insane artificial positions; I only care about finishing depth 1 in no time in those cases.

D Sceviour
Posts: 554
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Q search explosion

Post by D Sceviour » Thu Mar 30, 2017 6:15 pm

Code: Select all

Schooner v1.6.7_64 &#40;1 CPU&#41;
White&#40;1&#41;&#58; 1QqQqQq1/r6Q/Q6q/q6Q/B2q4/q6Q/k6K/1qQ1QqRb w - -
White&#40;1&#41;&#58; go

Search Iteration =  1
PV &#91;1&#93; 32762  f8-g8 b1-b3 h3-b3 a3-b3#
PV &#91;1&#93; 32764  h7-g8 a2-a1#
PV &#91;1&#93; 32766  b8-b1#

Nodes =  1079
Total Nodes =  1235
I noticed that Houdini 1.5 also crashed.

User avatar
JVMerlino
Posts: 1044
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Q search explosion

Post by JVMerlino » Thu Mar 30, 2017 7:36 pm

Evert wrote:
JVMerlino wrote: 2) Once the qsearch has gone 4 plies deep (again, an arbitrary number) I only allow the qsearch to do recaptures on the previous capture's square. This code was eventually commented out.
It seems to me that if you prune SEE<0 captures this would already do most of what a recapture-only search gives you, and do it more cheaply. Am I missing something?
It's certainly possible that I"m missing something. But if I disable SEE and do the same two tests:
All captures in qs -- needs 3.05M nodes, so about 27% more nodes searched.
Recaptures only after qs depth 4 -- needs 3796 nodes, about 13% more.

jm

User avatar
Evert
Posts: 2929
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Q search explosion

Post by Evert » Thu Mar 30, 2017 8:07 pm

op12no2 wrote:Mate in 1 via Dann Corbit.

[d]1QqQqQq1/r6Q/Q6q/q6Q/B2q4/q6Q/k6K/1qQ1QqRb w - -

My q search is primitive, no gives/in check tests etc.

A one ply analysis of the above position 'never ends' because as far as I can see, my engine is just lost in an exhaustive q search. It's Javascript and what in fact happens, is it slows to a crawl.

I added a hack to only search -depths to twice the current top level ID depth, but that seems like a cop out? There again, does q search really need to be exhaustive always...?

Does anybody else have problems with this position, or take steps to limit q search ?

For me, it's the only position out of 9560 mate-in-ones that it happens with. But I guess it depends which first move is tried as well...
Interesting. Very interesting.
Jazz just hangs (I didn't have the patience to wait for it to finish), but SjaakII really surprised me:

Code: Select all

#&#91;Chess&#93; 0w>setboard 1QqQqQq1/r6Q/Q6q/q6Q/B2q4/q6Q/k6K/1qQ1QqRb w - -
 8  Q q Q q Q q   
 7r             Q 
 6Q             q 
 5q             Q 
 4B     q         
 3q             Q 
 2k             K 
 1  q Q   Q q R b *
  a b c d e f g h 
#&#91;Chess&#93; 0w &#40;f&#41;>go
  2.    0.00           2  +159.99   1. Qcxb1 
move Qcxb1
1-0 &#123;White mates&#125;
This may just be serendipity in that it generates the capture of Qb1 first (by scanning the board for victims starting at a1) but even so it is unexpectedly quick.

EDIT: No, it finds the reverse position
[d]1qQ1QqRb/k6K/q6Q/B2q4/q6Q/Q6q/r6Q/1QqQqQq1 w - -
also immediately.

Post Reply