Avoiding qsearch explosion

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Avoiding qsearch explosion

Post by mcostalba » Fri Jan 29, 2010 10:39 am

We stumbled on a strange case where with TT full qsearch hangs forever.

The problem is that in qsearch is always tried as first the TT move, so it can happen that we end up in a unlimited cycle of check + evasion + check + evasion and so on, we have experienced this with TT full.

Please, just to be clear, I am not saying that we generate check moves in qsearch (we do this only at depth 0), I am saying that _if_ the TT move is a check then we _could_ end up with a TT move + evasion + TT move + evasion and so on yielding to a search tree explosion.


What is the standard way to handle this ?

Thanks

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: Avoiding qsearch explosion

Post by Edmund » Fri Jan 29, 2010 10:51 am

a simple fix would be to put a maximum on the number of recursions and just return to the previous ply once this has been reached

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Avoiding qsearch explosion

Post by mcostalba » Fri Jan 29, 2010 10:55 am

Edmund wrote:a simple fix would be to put a maximum on the number of recursions and just return to the previous ply once this has been reached
Yes, thanks.

But I would expect to see this fix already implemented in other engines, but it seems that fruit and crafty don't have this check, so perhaps there is a better fix.

Uri Blass
Posts: 8752
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Avoiding qsearch explosion

Post by Uri Blass » Fri Jan 29, 2010 11:39 am

mcostalba wrote:We stumbled on a strange case where with TT full qsearch hangs forever.

The problem is that in qsearch is always tried as first the TT move, so it can happen that we end up in a unlimited cycle of check + evasion + check + evasion and so on, we have experienced this with TT full.

Please, just to be clear, I am not saying that we generate check moves in qsearch (we do this only at depth 0), I am saying that _if_ the TT move is a check then we _could_ end up with a TT move + evasion + TT move + evasion and so on yielding to a search tree explosion.


What is the standard way to handle this ?

Thanks
I do not know but I think that it is not a good idea not to limit the number of plies in the qsearch

I think that even without checks the qsearch of stockfish can explode and I think that some rule for the worst case should be used(define some array Q[n] when no more than Q[n] moves are searched in the n'th ply of the qsearch and when Q[n]=0 the program return the SEE score.

You can try something like Q[10]={10,9,7,5,3,2,1,1,1,0}

Here is an example for position when stockfish need a lot of time to get a pv because there is no limit about the qsearch(it is only 7 pawns against 7 pawns and I can imagine that with 8 pawns the situation is going to be worse)

I see no pv after some minutes of search
(edit stockfish finally produced a pv)

New game - Stockfish 1.6 JA
[D]4K3/1PPPPPPP/8/8/8/8/1ppppppp/4k3 w - - 0 1

Analysis by Stockfish 1.6 JA:

1.b7-b8Q
± (0.80) Depth: 1 00:15:20
1.b7-b8Q b2-b1Q 2.d7-d8Q g2-g1Q 3.h7-h8Q h2-h1Q 4.c7-c8Q Qb1xb8 5.Qc8xb8 Qh1-c6+ 6.Ke8-f8 c2-c1Q 7.e7-e8Q f2-f1Q 8.g7-g8Q d2-d1Q 9.Qg8xg1 Qf1xg1
± (0.72) Depth: 2 00:15:39
1.b7-b8Q b2-b1Q 2.d7-d8Q g2-g1Q 3.h7-h8Q h2-h1Q 4.c7-c8Q Qb1xb8 5.Qc8xb8 Qh1-c6+ 6.Ke8-f8 c2-c1Q 7.e7-e8Q Qc6-c5+ 8.Kf8-g8 d2-d1Q 9.f7-f8Q Qd1xd8 10.Qb8xd8 f2-f1Q
± (1.17) Depth: 3 00:15:54
1.b7-b8Q b2-b1Q 2.d7-d8Q g2-g1Q 3.h7-h8Q h2-h1Q 4.c7-c8Q Qb1xb8 5.Qc8xb8 Qh1-c6+ 6.Ke8-f8 c2-c1Q 7.e7-e8Q Qc6-c5+ 8.Kf8-g8 f2-f1Q 9.Qh8-h2
± (0.80) Depth: 4 00:15:58
1.b7-b8Q b2-b1Q 2.c7-c8Q h2-h1Q 3.h7-h8Q Qb1xb8 4.Qc8xb8 c2-c1Q 5.f7-f8Q g2-g1Q 6.Qh8xh1 Qg1xh1 7.g7-g8Q f2-f1Q 8.Qg8-g3+ Ke1-d1 9.Qb8-b3+ Qc1-c2 10.d7-d8Q e2-e1Q 11.Qf8xf1 Qh1xf1
+- (2.50) Depth: 5 00:16:35
1.b7-b8Q b2-b1Q 2.c7-c8Q h2-h1Q 3.h7-h8Q f2-f1Q 4.g7-g8Q Qh1xh8 5.Qg8xh8 Qb1xb8 6.Qc8xb8 g2-g1Q 7.d7-d8Q c2-c1Q 8.Qh8-h6 Qg1-g4 9.Qb8-h2 Qc1-c2
+- (2.06) Depth: 6 00:16:45 691397kN
1.b7-b8Q b2-b1Q 2.c7-c8Q h2-h1Q 3.h7-h8Q g2-g1Q 4.Qh8xh1 Qg1xh1 5.g7-g8Q Qh1-h5 6.d7-d8Q Qb1xb8 7.Qc8xb8 c2-c1Q 8.Qb8-b4 f2-f1Q 9.Ke8-f8 Ke1-d1 10.e7-e8Q e2-e1Q 11.Qe8-a4+ Qc1-c2 12.Qg8-g4+ Qh5xg4 13.Qb4xg4+ Qe1-e2
+- (2.14) Depth: 7 00:17:00 700147kN
1.b7-b8Q b2-b1Q 2.c7-c8Q h2-h1Q 3.h7-h8Q g2-g1Q 4.Qh8xh1 Qg1xh1 5.g7-g8Q Qh1-h5 6.d7-d8Q Qb1xb8 7.Qc8xb8 c2-c1Q 8.Qd8-d4 d2-d1Q 9.Qd4xf2+ Ke1xf2 10.Qb8-g3+ Kf2-f1 11.Qg3-g1#
+- (2.74) Depth: 8 00:17:21 713101kN

(so k, 29.01.2010)

Edit:I can add that I see no way for infinite explosion because you probably return draw for repetition or draw for the fifty move rule and you check after every move if it is a draw by repetition or draw by the fifty move rule(It is not logical not to do it)

Uri

User avatar
Eelco de Groot
Posts: 4236
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Avoiding qsearch explosion

Post by Eelco de Groot » Fri Jan 29, 2010 11:46 am

Marco when you say forever did you mean it literally hangs? Did ply >= PLY_MAX - 1 not end the qsearch calls eventually? In this case I already rather assume that it is a perpetual check in Rainbow Serpent so that at least in this case I would return VALUE_DRAW. See for this the small difference in qsearch() Rainbow Serpent style below. But PLY_MAX-1 in case of isCheck and very negative depth could probably be made a smaller number?

Code: Select all

    if (ply >= PLY_MAX - 1)
        if (!isCheck) return evaluate(pos, ei, threadID);

Code: Select all

    // Loop through the moves until no moves remain or a beta cutoff
    // occurs.
    while (   alpha < beta
              && &#40;move = mp.get_next_move&#40;)) != MOVE_NONE&#41;
    &#123;
        assert&#40;move_is_ok&#40;move&#41;);

        moveCount++;
        ss&#91;ply&#93;.currentMove = move;
		
        if &#40;ply >= PLY_MAX - 1&#41;
	         return VALUE_DRAW; // &#91;EdG&#58; I assume that this is an escape in perpetual check, rather than use quick_evaluate&#93;
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 10:00 am
Location: Slovakia, EU

Re: Avoiding qsearch explosion

Post by rvida » Fri Jan 29, 2010 12:17 pm

mcostalba wrote:We stumbled on a strange case where with TT full qsearch hangs forever.

The problem is that in qsearch is always tried as first the TT move, so it can happen that we end up in a unlimited cycle of check + evasion + check + evasion and so on, we have experienced this with TT full.

Please, just to be clear, I am not saying that we generate check moves in qsearch (we do this only at depth 0), I am saying that _if_ the TT move is a check then we _could_ end up with a TT move + evasion + TT move + evasion and so on yielding to a search tree explosion.


What is the standard way to handle this ?

Thanks
If depth < chek_depth (depth 0 in your case) dont try the TT move unless its a capture or queen promotion.

Richard

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Avoiding qsearch explosion

Post by mcostalba » Fri Jan 29, 2010 3:36 pm

rvida wrote:
If depth < chek_depth (depth 0 in your case) dont try the TT move unless its a capture or queen promotion.
Thanks, it seems a good (and elegant) idea. Do you know if some engine has already implemented this ?

User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 10:00 am
Location: Slovakia, EU

Re: Avoiding qsearch explosion

Post by rvida » Fri Jan 29, 2010 4:07 pm

mcostalba wrote:
rvida wrote:
If depth < chek_depth (depth 0 in your case) dont try the TT move unless its a capture or queen promotion.
Thanks, it seems a good (and elegant) idea. Do you know if some engine has already implemented this ?
Yes, I do it in Critter that way.

User avatar
Eelco de Groot
Posts: 4236
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Avoiding qsearch explosion

Post by Eelco de Groot » Sat Jan 30, 2010 2:38 am

Uri Blass wrote: Here is an example for position when stockfish need a lot of time to get a pv because there is no limit about the qsearch(it is only 7 pawns against 7 pawns and I can imagine that with 8 pawns the situation is going to be worse)

I see no pv after some minutes of search
(edit stockfish finally produced a pv)

New game - Stockfish 1.6 JA
[D]4K3/1PPPPPPP/8/8/8/8/1ppppppp/4k3 w - - 0 1
Wow, this is bad Uri :lol: And for Rainbow Serpent the branching behaviour apparently here is much worse, I only get the one ply output, two ply is taking much longer than for Stockfish, I stopped it now after half an hour, no new output from Rainbow Serpent :( My guess is this is not only because of a qsearch tree explosion but I'm not sure. Also the PV takes a long time but I do not see the engine thinking about the other promotions at the root. I would expect these to also take very long actually. Thanks for posting the position and your other suggestions!

Regards, Eelco

[D]4K3/1PPPPPPP/8/8/8/8/1ppppppp/4k3 w - -

Engine: Rainbow Serpent 1.6.3s(dc) Build 65 (Athlon 2009 MHz, 128 MB)
by Tord Romstad, Marco Costalba, Joona Kiiski Modifications: Dann Corbit

1.00 8:16 +0.72 1.b8Q (284.127.781) 572

best move: b7-b8Q time: 32:18.312 min n/s: 785.787 nodes: 1.523.101.517
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

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

Re: Avoiding qsearch explosion

Post by michiguel » Sat Jan 30, 2010 3:21 am

Eelco de Groot wrote:
Uri Blass wrote: Here is an example for position when stockfish need a lot of time to get a pv because there is no limit about the qsearch(it is only 7 pawns against 7 pawns and I can imagine that with 8 pawns the situation is going to be worse)

I see no pv after some minutes of search
(edit stockfish finally produced a pv)

New game - Stockfish 1.6 JA
[D]4K3/1PPPPPPP/8/8/8/8/1ppppppp/4k3 w - - 0 1
Wow, this is bad Uri :lol: And for Rainbow Serpent the branching behaviour apparently here is much worse, I only get the one ply output, two ply is taking much longer than for Stockfish, I stopped it now after half an hour, no new output from Rainbow Serpent :( My guess is this is not only because of a qsearch tree explosion but I'm not sure. Also the PV takes a long time but I do not see the engine thinking about the other promotions at the root. I would expect these to also take very long actually. Thanks for posting the position and your other suggestions!
How other engines perform here? Gaviota reaches ply 10 in one minute. So, if it is not a problem for Gaviota, I wonder whether there is a more serious problem. I do not do HT in Qsearch... though. Also, I do not limit the amount of plies in qsearch at all. I do checks in the first two plies only.

Miguel


Regards, Eelco

[D]4K3/1PPPPPPP/8/8/8/8/1ppppppp/4k3 w - -

Engine: Rainbow Serpent 1.6.3s(dc) Build 65 (Athlon 2009 MHz, 128 MB)
by Tord Romstad, Marco Costalba, Joona Kiiski Modifications: Dann Corbit

1.00 8:16 +0.72 1.b8Q (284.127.781) 572

best move: b7-b8Q time: 32:18.312 min n/s: 785.787 nodes: 1.523.101.517

Post Reply