Avoiding qsearch explosion

[mcostalba]

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]

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]

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]

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

[Eelco de Groot]

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;

[rvida]

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]

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 ?

[rvida]

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.

[Eelco de Groot]

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

[michiguel]

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