Avoiding qsearch explosion

[rvida]

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

Some engines in the first iteration of ID loop perform QSearch on every root move with open window (-INF, +INF) to get accurate 0 ply scores. This is useful for things like "easy move" logic, but in this case is very costly.

Richard

[michiguel]

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

Some engines in the first iteration of ID loop perform QSearch on every root move with open window (-INF, +INF) to get accurate 0 ply scores. This is useful for things like "easy move" logic, but in this case is very costly.

Richard

I do that too in the first ply, -INF +INF.

Miguel

[hgm]

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.

I do not understand exactly what the problem is.

For one, what does 'TT full' mean? After the game is more than a few seconds old, my TT is always full. This is why I have a replacement algorithm.

Secondly, you don't try the hash move in QS if it is a move that would not normally be searched in QS, do you? Often the hash move is a non-capture.

Finally, don't you run into repetitions quite quickly? Or are you assuming that these are all different checks and evasions, and that they are all TT hits?

[mcostalba]

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)

Hi Uri,

could you please apply following patch to movepick.cpp file and retest ?

Code: Select all

--- a/src/movepick.cpp
+++ b/src/movepick.cpp
@@ -95,8 +95,16 @@ MovePicker::MovePicker(const Position& p, Move ttm, Depth d,
   else if (d == Depth(0))
       phasePtr = QsearchWithChecksPhaseTable;
   else
+  {
       phasePtr = QsearchWithoutChecksPhaseTable;
 
+      // Skip TT move if is not a capture or a promotion, this avoids
+      // qsearch tree explosion due to a possible perpetual check or
+      // similar rare cases when TT table is full.
+      if (ttm != MOVE_NONE && !pos.move_is_capture_or_promotion(ttm))
+          searchTT = ttMoves[0].move = MOVE_NONE;
+  }
+
   phasePtr += !searchTT - 1;
   go_next_phase();
 }

Thanks
Marco

[mcostalba]

Secondly, you don't try the hash move in QS if it is a move that would not normally be searched in QS, do you?

Yes, we do

Perhaps not a good idea though....

[hgm]

Well, this then explains why other engines do not have similar problems. I once did this accidentally, and it was very destructive. I would also not expect it to be a good idea. For one, it is illogical to make the searching of a move dependent on if you happen to have a hash hit or not. If the bound type makes the score valid, you would have a hash cut-off, as any draft satisfies QS. If it is an upper-bound, you will have no move. That only leaves the case of a bad lower bound (below beta).

All the hash tells you in that case is that there exists a move that you normally would not search (no surprise in QS), and that this move can either fail low or high when you search it with the new window. There is little reason to suspect that it would be better than its bound, and if it is not, it will fail low, and you would have wasted your time on it.

[John Major]

For one, what does 'TT full' mean? After the game is more than a few seconds old, my TT is always full. This is why I have a replacement algorithm.

Actually this is interesting. It takes remarkably long for a normally sized hash table to completely fill up.
It's some sort of logarithmic function because the probability of filling the last empty slot is very low.

UCI has the optional output parameter 'hashfull', which you can calculate exactly with counters or you can simulate with some formula to save time.

Stockfish has this:

Code: Select all

/// TranspositionTable::full() returns the permill of all transposition table
/// entries which have received at least one write during the current search.
/// It is used to display the "info hashfull ..." information in UCI.

int TranspositionTable::full() const {

  double N = double(size) * ClusterSize;
  return int(1000 * (1 - exp(writes * log(1.0 - 1.0/N))));
}

In my testing this is not very accurate though.

[jwes]

Here is another position that stockfish seems to have trouble with.
[d]r1r1qbnn/1P1P1PP1/8/1k6/6K1/8/1pp1p1p1/BBRN1N1R w - - 0 1

[Eelco de Groot]

Well, this then explains why other engines do not have similar problems. I once did this accidentally, and it was very destructive. I would also not expect it to be a good idea. For one, it is illogical to make the searching of a move dependent on if you happen to have a hash hit or not. If the bound type makes the score valid, you would have a hash cut-off, as any draft satisfies QS. If it is an upper-bound, you will have no move. That only leaves the case of a bad lower bound (below beta).

All the hash tells you in that case is that there exists a move that you normally would not search (no surprise in QS), and that this move can either fail low or high when you search it with the new window. There is little reason to suspect that it would be better than its bound, and if it is not, it will fail low, and you would have wasted your time on it.

I've given up on trying to repair Uri's position or similar ones with all those pawns on the seventh rank. It is not worth it, I amputed half the qsearch, do only two promotions in every qsearch position (I know that really makes not much difference), applied Marco's patch and tried to limit extensions a bit and I still only get the first one ply output

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

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

1.00 0:00 +8.08 1.h8Q (9.209) 65

best move: h7-h8Q time: 3:08.156 min n/s: 878.602 nodes: 165.301.239

This is good enough for a testsuite, it will at least produce output.

Part of the problem is there is an extension in Rainbow Serpent for every queenswap and I assume there that usually you only have one pair of queens. I can test if there are still more queens left on the bord after one exchange but really it does not seem worth it.

a) The qsearch may still explode, if you try all Queen promotions there and all the possible exchanges after them.
b) These are such fabricated positions you will never see them in a game.

Marco's patch did not seem to help in Uri's position, not for Rainbow Serpent. When I tried it in another position I think it may actually not be such a good idea (to apply the patch), I kind of fancy this hash moves in qsearch as an idea! I must admit I do not really understand the counterarguments I can't wrap my head around it, I gave up there

This was the opening position with Marco's patch and several other qsearch limitations inserted:

[D]rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -

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

1.00 0:00 +0.72 1.Nf3 (20) 0

2.00 0:00 +0.12 1.Nf3 Nf6 (51) 0

3.00 0:00 +0.68 1.Nf3 Nf6 2.Nc3 (179) 1

4.00 0:00 +0.12 1.Nf3 Nf6 2.Nc3 Nc6 (388) 3

5.00 0:00 +0.28 1.Nf3 Nf6 2.Nc3 Nc6 3.d4 (743) 6

6.00 0:00 +0.12 1.Nf3 Nf6 2.Nc3 Nc6 3.d4 d5 (1.255) 11

7.00 0:00 +0.32 1.Nf3 Nf6 2.Nc3 Nc6 3.d4 d5 4.Bf4 (2.453) 22

8.00 0:00 +0.32 1.Nf3 Nf6 2.e3 Nc6 3.Bd3 e6 4.O-O d5 (5.436) 43

9.00 0:00 +0.12-- 1.Nf3 Nf6 2.e3 Nc6 3.Bd3 d5 4.O-O e5 (8.491) 67

9.00 0:00 +0.28 1.e4 Nc6 2.Nc3 Nf6 3.Nf3 d5 4.exd5 Nxd5
5.d4 Nxc3 6.bxc3 (18.295) 117

10.00 0:00 +0.28 1.e4 Nc6 2.Nc3 Nf6 3.d4 d5 4.exd5 Nxd5
5.Nf3 Bf5 6.Bc4 Nxc3 7.bxc3 e6 (45.818) 225

11.00 0:00 +0.28 1.e4 Nc6 2.Nc3 e6 3.d4 d5 4.exd5 exd5
5.Nf3 Nf6 6.Bd3 Bd6 (77.293) 291

12.00 0:00 +0.16 1.e4 Nc6 2.Nc3 e6 3.d4 d5 4.e5 f6
5.Nf3 fxe5 6.Nxe5 Nxe5 7.dxe5 (150.636) 386

13.00 0:00 +0.40++ 1.e4 Nf6 2.Nc3 Nc6 3.d4 e6 4.e5 Nd5
5.Nxd5 exd5 6.Nf3 Be7 7.Bd3 O-O
8.O-O (319.084) 453

14.00 0:01 +0.36 1.e4 Nf6 2.Nc3 Nc6 3.d4 d5 4.exd5 Nxd5
5.Nf3 e6 6.Bb5 Bb4 7.Bd2 O-O 8.O-O Bd7
9.Bg5 (922.863) 492

15.01 0:12 +0.48 1.e4 e5 2.Nf3 Nf6 3.Nxe5 Qe7 4.d4 d6
5.Nf3 Qxe4+ 6.Be2 Bf5 7.Na3 Nc6
8.O-O O-O-O 9.Bd3 Qg4 10.h3 (6.056.936) 496

16.01 0:24 +0.48 1.e4 e5 2.Nf3 Nf6 3.Nxe5 d6 4.Nf3 Nxe4
5.Nc3 Nxc3 6.dxc3 d5 7.Be3 Be7
8.Bb5+ c6 9.Bd3 Nd7 10.O-O O-O
11.Re1 Nc5 (11.931.430) 496

17.01 0:32 +0.28-- 1.e4 e5 2.Nf3 Nf6 3.Nxe5 Qe7 4.d4 Nc6
5.Nc3 Nxe5 6.dxe5 Qxe5 7.f4 Qe6
8.Qd4 b6 9.Bc4 Bc5 (16.370.314) 497

18.01 0:58 +0.44 1.e4 e5 2.Nf3 Nf6 3.Nxe5 Qe7 4.d4 Nc6
5.Nc3 Nxe5 6.dxe5 Qxe5 7.f4 Qe6
8.Qd4 b6 9.Bc4 Bc5 10.Qxc5 bxc5
11.Bxe6 fxe6 12.e5 Nd5 13.Nxd5 exd5
14.Kf2 (28.816.941) 496

19.01 2:05 +0.44 1.e4 e5 2.Nf3 Nf6 3.Nxe5 Qe7 4.d4 Nc6
5.Bf4 Nxe5 6.Bxe5 Nxe4 7.Qe2 d5 8.f3 Nd6
9.Nc3 Be6 10.O-O-O O-O-O 11.Nb5 Kb8
12.Nxd6 cxd6 (62.782.302) 500

20.01 8:40 +0.48 1.e4 e5 2.Nf3 Nf6 3.Nxe5 Qe7 4.Nf3 Nxe4
5.Be2 Nc6 6.Nc3 Nxc3 7.dxc3 d6 8.Be3 Bd7
9.O-O O-O-O 10.Re1 a6 11.b4 d5 12.c4 dxc4
13.c3 (264.838.312) 509

best move: e2-e4 time: 8:44.984 min n/s: 509.101 nodes: 267.270.158

This is okay but 3... Qe7 is a bit antipositional opening. Without the patch Rainbow Serpent eventually plays the French in some absurd quick exchange variation, well okay that was not really Grandmaster quality either...

I like the Stockfish idea of being able to insert some quiet moves in qsearch tactics, if these seem proven in the transposed positions and provided you can play a sequence of TT moves that make sense. Maybe if you would limit it to moves of a certain positive depth that would be more along this idea, but then it would not really find a lot of TT moves anymore.

Eelco

[hgm]

I agree that positions like this are not worth it.

That being said, a few factors that would make it more difficult to reach any depth or even get a move in such a position are:

* Promotion extension in full-width search
* Not taking into account promotion bonus in SEE
* Considering under-promotions

For instance, after 1.b8=Q b1=Q an MVV/LVA QS would be inclined to try 2.Qxb1. But this is bad tactics, as the recapture 2... cxb1=Q is also a promotion, so that 2.Qxb1 actually is a bad capture with SEE = -8.