Quiescence Search Explosions

Zach Wegner · Post by **Zach Wegner** » Sat May 24, 2008 9:59 am

hgm wrote:If below 8 ply Rxc7 is refuted by a null move, the node following that null-move must be a low-failing all-node. At d=3 that null move jumps into QS. But as you do checks in the first ply of QS, it should play Rxe4#, as a checkmate is also a check. So how can you fail low on a checkmate (that is faster than any checkmate you have seen so far)?

I don't understand what under-promotion has to do with it.

I'm back! I found it. The issue is that after the null move, Rxe4# _isn't_ searched. The reason is that only non-capture checks are generated, and that is only after all of the captures failed low. But because alpha is 20 pawns, Rxe4 is delta pruned!

I'm not sure of a good general solution to this. Maybe not to delta prune checks? I tried this and came up with this result:

Code: Select all

Depth          Time     Score   PV &#40;nodes&#41;
  1/ 4        0.001     -8.16   1. d6 &#40;31&#41;
  1/12        0.001    +12.80   1. h8=Q Kxf4 2. Bxc7+ Ne5 3. Nxg2+ Bxg2 &#40;259&#41;
  1/12        0.002    +15.11   1. Nd3+ Kxd4 2. Bxa7+ Kxd3 3. Rxc7+ Ke2 &#40;416&#41;
  1/12        0.002    +16.74   1. Nexf3+ Kxf4 2. Qxc7+ Qxc7 3. Bxc7+ Re5 4. Bxe5+ Ke4 &#40;511&#41;
  1/12        0.003       +#4   1. Bxc7+ Qxc7 2. Nexf3+ Kxf4 3. Qxc7+ Re5 4. Qxe5# &#40;689&#41;
&#91; 1/12&#93;       0.003       +#4   1. Bxc7+ Qxc7 2. Nexf3+ Kxf4 3. Qxc7+ Re5 4. Qxe5# &#40;884&#41;
  2/12        0.003       +#4   1. Bxc7+ Qxc7 2. Nexf3+ Kxf4 3. Qxc7+ Re5 4. Qxe5# &#40;986&#41;
&#91; 2/12&#93;       0.014       +#4   1. Bxc7+ Qxc7 2. Nexf3+ Kxf4 3. Qxc7+ Re5 4. Qxe5# &#40;7861&#41;
  3/12        0.014       +#4   1. Bxc7+ Qxc7 2. Nexf3+ Kxf4 3. Qxc7+ Re5 4. Qxe5# &#40;8238&#41;
&#91; 3/12&#93;       0.018       +#4   1. Bxc7+ Qxc7 2. Nexf3+ Kxf4 3. Qxc7+ Re5 4. Qxe5# &#40;10659&#41;
  4/12        0.018       +#4   1. Bxc7+ Qxc7 2. Nexf3+ Kxf4 3. Qxc7+ Re5 4. Qxe5# &#40;10802&#41;
&#91; 4/12&#93;       0.047       +#4   1. Bxc7+ Qxc7 2. Nexf3+ Kxf4 3. Qxc7+ Re5 4. Qxe5# &#40;32642&#41;
  5/12        0.049       +#4   1. Bxc7+ Qxc7 2. Nexf3+ Kxf4 3. Qxc7+ Re5 4. Qxe5# &#40;34334&#41;
  5/12        0.058       +#2   1. Rxc7 Rexd4 2. Rf5# &#40;46271&#41;
&#91; 5/12&#93;       0.058       +#2   1. Rxc7 Rexd4 2. Rf5# &#40;46333&#41;

It finds a mate in 689 nodes (a record?), but the real mate eludes discovery for 5 plies. So now I'm on another wild goose chase...

hgm · Post by **hgm** » Sat May 24, 2008 10:28 am

Indeed it is not logical to prune capture checks, if you think all non-capture checks are worth searching.

So now the question is: what refutes Rxc7 at d=3? After null you should search Rxe4# in QS, and the reply should be extended enough to see it is checkmated. So it cannot be the null move.

Could you have a similar delta-pruning problem at d=1, when some insignificant real move is used to 'refute' Rxc7?

In Joker I understand why it needs d=5: at d=4 Rxc7 runs into null move, after which the R=2 reduction leaves d=0, which in Joker (currently) is the same as QS. Rxe4# then runs into a stand-pat (or, more likely, is justly futilty-pruned in anticipation of that stand-pat). Joker does not search checks in QS, and thus feels no need to test if it is in-check after an accidental check by a capture. There seemed to be little benifit in recognizing beyond-the-horizon mates through captures only, as most such mates would probably be through non-captures anyway.

pedrojdm2021 · Post by **pedrojdm2021** » Wed Feb 23, 2022 9:31 pm

I found another one that might be useful
I did not got explosion with your position, but i did with this:

[fen]8/8/7p/4k3/P7/2K5/3N1r2/6q1 w - - 0 12[/fen]

btw anyone has an idea of how to improve that? a pure "alpha-beta" Quiescense search can cause explosions?

Ras · Post by **Ras** » Wed Feb 23, 2022 10:18 pm

pedrojdm2021 wrote: ↑Wed Feb 23, 2022 9:31 pmbtw anyone has an idea of how to improve that?

Don't do underpromotions in QS, and try mate distance pruning (see CPW) in main search.

pedrojdm2021 · Post by **pedrojdm2021** » Wed Feb 23, 2022 10:54 pm

Ras wrote: ↑Wed Feb 23, 2022 10:18 pm
pedrojdm2021 wrote: ↑Wed Feb 23, 2022 9:31 pmbtw anyone has an idea of how to improve that?
Don't do underpromotions in QS, and try mate distance pruning (see CPW) in main search.

I do Mate Distance Pruning inside Negamax, but i didn't knew that i could apply that in QS too, thanks, i will try and see if it improves

Ras · Post by **Ras** » Wed Feb 23, 2022 11:10 pm

pedrojdm2021 wrote: ↑Wed Feb 23, 2022 10:54 pmI do Mate Distance Pruning inside Negamax

That would already cope with most. I don't do mate distance pruning in QS, but I skip underpromotions.

pedrojdm2021 · Post by **pedrojdm2021** » Thu Feb 24, 2022 1:09 am

Ras wrote: ↑Wed Feb 23, 2022 11:10 pm
pedrojdm2021 wrote: ↑Wed Feb 23, 2022 10:54 pmI do Mate Distance Pruning inside Negamax
That would already cope with most. I don't do mate distance pruning in QS, but I skip underpromotions.

I understand, well, i solved it with a "hack" that i've found in the "Demolito" source code:
https://github.com/lucasart/Demolito/bl ... rch.c#L139

Code: Select all

        // Recursion (plain alpha/beta)
        if (depth <= MIN_DEPTH && !pos->checkers) {
            score = worker->eval[ply] + see; // guard against QSearch explosion
        } else
            score = -qsearch(worker, &nextPos, ply + 1, nextDepth, -beta, -alpha, pvNode, childPv);

it basically says if your qsearch depth more negative than your minimun depth ( a negative depth, let's say -8 ) and your position is not in check, one can guess the possible outcome with the evaluation + SEE score of the current move, avoiding the recursion again

I did the mate distance pruning in the QS, and i added more pruning in QS too, like Delta Pruning and i don't try Negative SEE captures ( SEE < 0 )

Mike Sherwin · Post by **Mike Sherwin** » Fri Mar 04, 2022 4:29 am

Talk about reviving a thread after 14 years - wow!

This thread is confusing because of the huge disparity in results.

[fen]1B1Q2K1/q1p4P/4P3/3Pk1p1/1r1NrR1b/4pn1P/1pRp2n1/1B2N2b w - - 0 1 [/fen]

SF14 finds the mate in 2 at depth 9. RomiChess also finds the mate in 2 at depth 9. And Romi gets to depth n very fast but of course nowhere near as fast as SF14. Nothing special is done in Qsearch at all to limit explosion. No delta. No mate distance. No see exclusion. Nothing. Maybe I should try moving null move. idk. Also I have no clue what is done right and what is done wrong. Maybe AddCapts(x) has something of value?

Code: Select all

#define AddCapts(x) while(capts)\
                    {\
                      t->ts = FirstBit(capts);\
                      capts &= clrBit[t->ts];\
                      t->fs = fs;\
                      t->typ = (x);\
                      t->score = piece[board[t->ts]].val;\
                      if((h-1)->attacked & setBit[t->ts] && (h-1)->ts != t->ts)\
                        t->score -= piece[id].val;\
                      t++;\
                    }


s32 CaptSearch(s32 alpha, s32 beta) {
  s32 score;
  s32 Ply;
  trees *node;

  qnodes++;
  Ply = ply - base;
  score = Eval();
  if(score + 20 >= beta) return beta;
  if(CaptGen()) return MATE - Ply;
  if(t == h->t) return score;
  if(score > alpha) alpha = score;
  for(node = h->t; node < (h+1)->t; node++) {
    Sort(node, (h+1)->t);
    MakeMove((moves *)&node->m);
    node->score = -CaptSearch(-beta, -alpha);
    TakeBack();
    if(node->score > alpha) {
      if(node->score >= beta) return beta;
      alpha = node->score;
    }
  }
  return alpha;
}

FEN: 1B1Q2K1/q1p4P/4P3/3Pk1p1/1r1NrR1b/4pn1P/1pRp2n1/1B2N2b w - - 0 1

RomiChess64P3n:
1 00:00 21k 21k +4.70 h7h8q
2 00:00 28k 28k +5.75 e1f3 e5f4
3 00:00 38k 38k +13.70 f4f5 e5d4 h7h8q f3e5
4 00:00 39k 39k +13.70 f4f5 e5d4 h7h8q f3e5
5 00:00 51k 51k +M3 h7h8q e5f4 d4e2 f4f5 h8f6 d2d1q
6 00:00 80k 8,004k +M3 h7h8q e5f4 d4e2 f4f5 h8f6 d2d1q
7 00:00 132k 13,162k +M3 h7h8q e5f4 d4e2 f4f5 h8f6 d2d1q
8 00:00 188k 9,385k +M3 h7h8q e5f4 d4e2 f4f5 h8f6 d2d1q
9 00:00 2,019k 9,175k +M2 c2c7 d2d1q f4e4 e5e4
10 00:00 2,116k 9,198k +M2 c2c7 d2d1q f4e4 e5e4
11 00:00 2,492k 9,231k +M2 c2c7 d2d1q f4e4 e5e4
12 00:00 2,710k 9,345k +M2 c2c7 d2d1q f4e4 e5e4
13 00:00 3,748k 9,611k +M2 c2c7 d2d1q f4e4 e5e4
14 00:00 4,381k 9,736k +M2 c2c7 d2d1q f4e4 e5e4
15 00:00 6,770k 9,956k +M2 c2c7 d2d1q f4e4 e5e4
16 00:00 7,964k 10,080k +M2 c2c7 d2d1q f4e4 e5e4
17 00:01 12,287k 10,155k +M2 c2c7 d2d1q f4e4 e5e4
18 00:01 14,789k 10,270k +M2 c2c7 d2d1q f4e4 e5e4
19 00:02 22,867k 10,301k +M2 c2c7 d2d1q f4e4 e5e4
20 00:02 27,231k 10,393k +M2 c2c7 d2d1q f4e4 e5e4
21 00:04 45,648k 10,374k +M2 c2c7 d2d1q f4e4 e5e4
22 00:05 54,826k 10,463k +M2 c2c7 d2d1q f4e4 e5e4
23 00:08 91,369k 10,418k +M2 c2c7 d2d1q f4e4 e5e4
24 00:10 107,018k 10,461k +M2 c2c7 d2d1q f4e4 e5e4
25 00:17 185,326k 10,412k +M2 c2c7 d2d1q f4e4 e5e4
26 00:21 227,911k 10,445k +M2 c2c7 d2d1q f4e4 e5e4
27 00:35 367,342k 10,403k +M2 c2c7 d2d1q f4e4 e5e4
28 00:40 426,689k 10,415k +M2 c2c7 d2d1q f4e4 e5e4
29 01:07 696,660k 10,361k +M2 c2c7 d2d1q f4e4 e5e4
30 01:21 843,296k 10,378k +M2 c2c7 d2d1q f4e4 e5e4
31 02:14 1,393,059k 10,339k +M2 c2c7 d2d1q f4e4 e5e4
32 02:35 1,607,039k 10,340k +M2 c2c7 d2d1q f4e4 e5e4
33 04:04 2,525,526k 10,322k +M2 c2c7 d2d1q f4e4 e5e4

I just do not know what to make of this thread in relation to RomiChess.

Mike Sherwin · Post by **Mike Sherwin** » Fri Mar 04, 2022 8:19 pm

Mike Sherwin wrote: ↑Fri Mar 04, 2022 4:29 am Talk about reviving a thread after 14 years - wow!

This thread is confusing because of the huge disparity in results.

[fen]1B1Q2K1/q1p4P/4P3/3Pk1p1/1r1NrR1b/4pn1P/1pRp2n1/1B2N2b w - - 0 1 [/fen]

SF14 finds the mate in 2 at depth 9. RomiChess also finds the mate in 2 at depth 9. And Romi gets to depth n very fast but of course nowhere near as fast as SF14. Nothing special is done in Qsearch at all to limit explosion. No delta. No mate distance. No see exclusion. Nothing. Maybe I should try moving null move. idk. Also I have no clue what is done right and what is done wrong. Maybe AddCapts(x) has something of value?
Code: Select all
#define AddCapts(x) while(capts)\
                    {\
                      t->ts = FirstBit(capts);\
                      capts &= clrBit[t->ts];\
                      t->fs = fs;\
                      t->typ = (x);\
                      t->score = piece[board[t->ts]].val;\
                      if((h-1)->attacked & setBit[t->ts] && (h-1)->ts != t->ts)\
                        t->score -= piece[id].val;\
                      t++;\
                    }


s32 CaptSearch(s32 alpha, s32 beta) {
  s32 score;
  s32 Ply;
  trees *node;

  qnodes++;
  Ply = ply - base;
  score = Eval();
  if(score + 20 >= beta) return beta;
  if(CaptGen()) return MATE - Ply;
  if(t == h->t) return score;
  if(score > alpha) alpha = score;
  for(node = h->t; node < (h+1)->t; node++) {
    Sort(node, (h+1)->t);
    MakeMove((moves *)&node->m);
    node->score = -CaptSearch(-beta, -alpha);
    TakeBack();
    if(node->score > alpha) {
      if(node->score >= beta) return beta;
      alpha = node->score;
    }
  }
  return alpha;
}
FEN: 1B1Q2K1/q1p4P/4P3/3Pk1p1/1r1NrR1b/4pn1P/1pRp2n1/1B2N2b w - - 0 1

RomiChess64P3n:
1 00:00 21k 21k +4.70 h7h8q
2 00:00 28k 28k +5.75 e1f3 e5f4
3 00:00 38k 38k +13.70 f4f5 e5d4 h7h8q f3e5
4 00:00 39k 39k +13.70 f4f5 e5d4 h7h8q f3e5
5 00:00 51k 51k +M3 h7h8q e5f4 d4e2 f4f5 h8f6 d2d1q
6 00:00 80k 8,004k +M3 h7h8q e5f4 d4e2 f4f5 h8f6 d2d1q
7 00:00 132k 13,162k +M3 h7h8q e5f4 d4e2 f4f5 h8f6 d2d1q
8 00:00 188k 9,385k +M3 h7h8q e5f4 d4e2 f4f5 h8f6 d2d1q
9 00:00 2,019k 9,175k +M2 c2c7 d2d1q f4e4 e5e4
10 00:00 2,116k 9,198k +M2 c2c7 d2d1q f4e4 e5e4
11 00:00 2,492k 9,231k +M2 c2c7 d2d1q f4e4 e5e4
12 00:00 2,710k 9,345k +M2 c2c7 d2d1q f4e4 e5e4
13 00:00 3,748k 9,611k +M2 c2c7 d2d1q f4e4 e5e4
14 00:00 4,381k 9,736k +M2 c2c7 d2d1q f4e4 e5e4
15 00:00 6,770k 9,956k +M2 c2c7 d2d1q f4e4 e5e4
16 00:00 7,964k 10,080k +M2 c2c7 d2d1q f4e4 e5e4
17 00:01 12,287k 10,155k +M2 c2c7 d2d1q f4e4 e5e4
18 00:01 14,789k 10,270k +M2 c2c7 d2d1q f4e4 e5e4
19 00:02 22,867k 10,301k +M2 c2c7 d2d1q f4e4 e5e4
20 00:02 27,231k 10,393k +M2 c2c7 d2d1q f4e4 e5e4
21 00:04 45,648k 10,374k +M2 c2c7 d2d1q f4e4 e5e4
22 00:05 54,826k 10,463k +M2 c2c7 d2d1q f4e4 e5e4
23 00:08 91,369k 10,418k +M2 c2c7 d2d1q f4e4 e5e4
24 00:10 107,018k 10,461k +M2 c2c7 d2d1q f4e4 e5e4
25 00:17 185,326k 10,412k +M2 c2c7 d2d1q f4e4 e5e4
26 00:21 227,911k 10,445k +M2 c2c7 d2d1q f4e4 e5e4
27 00:35 367,342k 10,403k +M2 c2c7 d2d1q f4e4 e5e4
28 00:40 426,689k 10,415k +M2 c2c7 d2d1q f4e4 e5e4
29 01:07 696,660k 10,361k +M2 c2c7 d2d1q f4e4 e5e4
30 01:21 843,296k 10,378k +M2 c2c7 d2d1q f4e4 e5e4
31 02:14 1,393,059k 10,339k +M2 c2c7 d2d1q f4e4 e5e4
32 02:35 1,607,039k 10,340k +M2 c2c7 d2d1q f4e4 e5e4
33 04:04 2,525,526k 10,322k +M2 c2c7 d2d1q f4e4 e5e4

I just do not know what to make of this thread in relation to RomiChess.

It took me a while to understand my ancient code. The macro AddCapts(x) gives a score to each capture just based on the value of the captured piece. But then it modifies that score by the value of the piece moved if the ts was attacked in the previous ply and the previous ply's move did not move to the ts. So it is kind of stupid compared to a full SEE but it is much much faster and right more often than it is wrong.

Quiescence Search Explosions

Re: Quiescence Search Explosions

Re: Quiescence Search Explosions

Re: Quiescence Search Explosions

Re: Quiescence Search Explosions

Re: Quiescence Search Explosions

Re: Quiescence Search Explosions

Re: Quiescence Search Explosions

Re: Quiescence Search Explosions

Re: Quiescence Search Explosions