Page 1 of 3
Q search explosion
Posted: Thu Mar 30, 2017 1:30 pm
by op12no2
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...
Re: Q search explosion
Posted: Thu Mar 30, 2017 2:38 pm
by hgm
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.
Re: Q search explosion
Posted: Thu Mar 30, 2017 3:07 pm
by Stan Arts
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.
Re: Q search explosion
Posted: Thu Mar 30, 2017 4:02 pm
by op12no2
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.
Re: Q search explosion
Posted: Thu Mar 30, 2017 5:37 pm
by JVMerlino
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
Re: Q search explosion
Posted: Thu Mar 30, 2017 7:43 pm
by Evert
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?
Re: Q search explosion
Posted: Thu Mar 30, 2017 7:52 pm
by mar
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.
Re: Q search explosion
Posted: Thu Mar 30, 2017 8:15 pm
by D Sceviour
Code: Select all
Schooner v1.6.7_64 (1 CPU)
White(1): 1QqQqQq1/r6Q/Q6q/q6Q/B2q4/q6Q/k6K/1qQ1QqRb w - -
White(1): go
Search Iteration = 1
PV [1] 32762 f8-g8 b1-b3 h3-b3 a3-b3#
PV [1] 32764 h7-g8 a2-a1#
PV [1] 32766 b8-b1#
Nodes = 1079
Total Nodes = 1235
I noticed that Houdini 1.5 also crashed.
Re: Q search explosion
Posted: Thu Mar 30, 2017 9:36 pm
by JVMerlino
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
Re: Q search explosion
Posted: Thu Mar 30, 2017 10:07 pm
by Evert
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
#[Chess] 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
#[Chess] 0w (f)>go
2. 0.00 2 +159.99 1. Qcxb1
move Qcxb1
1-0 {White mates}
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.