QS in Crazyhouse

[hgm]

What is the consensus on doing QS in Crazyhouse? I am used to detecting checks and extending the evasions in QS. In Shogi this never gave me any obvious problems. But in Crazyhouse this suffers from tremendous search explosion in QS. When an enemy King walks out of its hiding it is often possible to do a plunder raid with checks only. Even if you toss material that way, so that he is on the right side of beta eval-wise, he can never stand pat because he is in check all the time. And in some branches he tosses the material right back by stupid interposition through drops.

An alternative would be to just give a penalty in the eval for being in check, and only allow legal captures, but no non-capture extensions. But I am afraid that would get very inaccurate.

Very often the node-burning lines have early mate-in-one branches, but as MVV/LVA is not really tailored to searching the move with the largest mating probability first, it often first embarks on the search of a checking capture that burns a million nodes. A breadth-first search would catch that. I guess I could emulate a breadth-first search by iteratively deepening QS. DOes anyone do that?

[Ferdy]

What is the consensus on doing QS in Crazyhouse? I am used to detecting checks and extending the evasions in QS. In Shogi this never gave me any obvious problems. But in Crazyhouse this suffers from tremendous search explosion in QS. When an enemy King walks out of its hiding it is often possible to do a plunder raid with checks only. Even if you toss material that way, so that he is on the right side of beta eval-wise, he can never stand pat because he is in check all the time. And in some branches he tosses the material right back by stupid interposition through drops.

An alternative would be to just give a penalty in the eval for being in check, and only allow legal captures, but no non-capture extensions. But I am afraid that would get very inaccurate.

Very often the node-burning lines have early mate-in-one branches, but as MVV/LVA is not really tailored to searching the move with the largest mating probability first, it often first embarks on the search of a checking capture that burns a million nodes. A breadth-first search would catch that. I guess I could emulate a breadth-first search by iteratively deepening QS. DOes anyone do that?

I have not done breadth-first.
I only detect qsearch checks and evasion replies at early plies of qsearch, I want to exit early in qsearch and would like to spend more time in main search.
Dropping non-contact check moves and dropping contact-check moves in QS does not help either. So I only have capture and promote moves searched plus evasion moves when under check.
But my eval has penalties to address this kind of positions. There are still a lot to experiment with this variant.

[Evert]

I don't do anything special when in check in QS for CrazyHouse: I generate all evasions as normal. I sort moves by MVV/LVA. Outside of check, I prune moves that have SEE<0.
I'm not claiming this is optimal, but I don't remember seeing problematic search explosions in CrazyHouse. If you have a test position in mind where this happens, I can check what happens in SjaakII.

[hgm]

The position I traced to figure out what is going on is this one:

[d]1R1bk2r/ppp1Nppp/1bp5/8/2b1N3/3P1KNP/prprNPP1/2Bq4 b k - 3 35
hand: [Qppp]

This actually comes from a Sjaak-CrazyWa game. Both engines agreed that CrazyWa is over +20 here. But in this position it thinks

Code: Select all

1 1460 0 2575 e8e7 e4d2 a2a1q c1b2 a1b2 d2c4 d1d3 R@e3 P@e4 g3e4 d3c4
1 1965 0 9408 d2e2 g3e2 d1d3 f3f4 d3e2 c1b2 a2a1q
1 2096 1 16264 d2d3 f3g4 a2a1q c1b2 a1b2
2 2096 1 16313 d2d3 f3g4 a2a1q c1b2 a1b2
3 2121 21 245469 d2d3 f3f4 a2a1q c1b2 a1b2
3 2144 31 352651 d2e2 b8d8 e8d8 g3e2 d1d3 f3f4 d3e2 c1b2 a2a1q
4 -14997 308 3032171 d2e2 b8d8 e8d8 Q@c8 d8e7 g3f5
4 2185 358 3573472 d2d3 f3f4 b2b1 e7c6 b7c6

but in the game it timed out before the first 4-ply result came in, and hence played d2e2 (Rxe2). Which, as the 4-ply analysis of this move shows, gets it mated in 3.

So I wondered why it could only reach 3 ply here. It turned out that most of the nodes burnt before getting the 4-ply result are still burned at 3 ply (the PV is printed as soon as it is found, not at the end of the iteration), on proving that P@g4+ is worse than d2e2 (which at that point is still thought to be good). This was searched with beta at +INF, because it is in the root, and I don't have implemented PVS yet, and took 2.20M nodes. So white desperately tries to beat the 2144 score while the root eval is at 1614, and nothing is 'good enough'.

It was refuted by Kxg4 {2.20M} h7h5+ {2.19M} Nxh5 {2.19M} Be6+ {2.19M} Kg3 {2.19M} Bxf2+ {2.19M} Kxf2 {2.19M} Rxe2+ {2.13M} Kg3 {2.13M} Qxd3+ {1.90M} Be3 {1.89M} Qxe3+ {1.12M; Rxe3+ took the other 650K nodes} Kh2 {1.04M} Rxg2+ {1.04M} Kxg2 {1.04M} c1=Q+ {1.03M}, after which it strongly branches. (Size of the sub-tree mentioned in braces.) After Be6+ this is all QS. There is a Qxh3+ alternative for Rxg2+ that is a mate in 2 and took only 264 nodes, but it was searched after Rxg2+.

I guess PVS and aspiration could help here, but they do not seem to address the fundamental problem. Which is that MVV/LVA is not good enough a method to quickly run out of moves in Crazyhouse, in combination with a check extension.

[Evert]

Multi-PV analysis by SjaakII:

Code: Select all

  2.    0.09       19344  +22.45   35. ... Rxd3   36. Kg4     a1Q  
  2.    0.13       29172  +12.20   35. ... Rxe2   36.  dxc4   a1Q   37. Nxe2   Kxe7   38. Rxb7  
  2.    0.13       30745  +10.78   35. ... Bxd3   36. Rxd8   Kxd8   37. Nxd2    a1Q   38. Bxb2   Qxb2  
  3.    0.30       89527  +19.50   35. ... Rxd3   36. Kg4     a1Q   37. Nc3   
  3.    1.19      429395  +15.09   35. ... Rxe2   36. Rxd8   Kxd8   37.  dxc4   a1Q   38. Nxe2   Kxe7   39. Bxb2   Qxb2  
  3.    1.22      436188  +11.63   35. ...  a1Q   36. Rxd8   Kxd8   37. Nxd2  
  4.    1.35      471250  +21.06   35. ... Rxd3   36. Kf4     a1Q   37. Rxd8   Rxd8   38. Bxb2   Qxb2  
  4.    1.92      656661  +10.91   35. ... P@g4   36. Kxg4   Rxe2   37. Bxb2    a1Q   38. Bxa1    c1Q   39. Bxg7   Bxd3  
  4.    1.99      678197  +8.69   35. ... Rb3    36. Nxd2   Rxd3   37. Kf4     a1Q   38. Nxc4   Kxe7   39. Nxb6    cxb6  40. Rxb7   Kf8   
  5.    2.58      854804  +21.06   35. ... Rxd3   36. Kf4     a1Q   37. Rxd8   Rxd8   38. Bxb2   Qxb2  
  5.    3.07     1015792  +12.93   35. ... P@g4   36. Kxg4   Rxe2   37. Rxd8   Kxd8   38. Bxb2    c1Q   39. Bxc1    a1Q   40.  dxc4  Kxe7   41. Nxe2   Qxe2   42. B@f3   Qxc4  
  5.    4.49     1449639  +8.53   35. ... Be6    36. Bxd2    a1Q   37. R@g8   Rxg8   38. Nxg8  
  6.    5.02     1591000  +21.06   35. ... Rxd3   36. Kf4     a1Q   37. Bxb2   Qxb2   38. Rxd8   Rxd8  
  6.   18.96     6243044  +11.85   35. ... P@g4   36. Kxg4   Be6    37. Kh4    P@g5   38. Kxg5   Rb5    39. P@c5   Kxe7   40. Bxd2    a1Q  
  6.   20.51     6709150  +8.40   35. ... Be6    36. Bxd2    a1Q   37. Rxd8   Kxd8   38. Q@b8   Kxe7   39. Qxh8  
  7.   23.52     7502664  +22.99   35. ... Rxd3   36. Kg4     a1Q   37. Bxb2   Qxb2   38. R@g1    h5    39. Kh4    Kxe7   40. Rxb7  
  7.   59.23    19596284  +12.26   35. ... P@g4   36. Kf4    P@e5   37. Kxg4   Be6    38. Kh4    Rxe2   39. Rxd8   Kxd8   40. Bxb2    a1Q   41. Bxa1    c1Q   42. Nxe2   Qxe2  
  7.   68.20    22646282  +8.21   35. ... Be6    36. Bxd2    a1Q   37. Q@g5    c1Q   38. Bxc1   Qxd3   39. P@e3  

Looking at the output, I wonder if it's not just lucky that the line it picks after Rxe2 takes fewer nodes to refute than CrazyWa's first choice. It takes a lot more effort to evaluate P@g4. I guess PVS+aspiration help, as you say, but I don't think SjaakII is immune to a catastrophic search explosion in general.
The depth isn't large enough here for the mate-search to kick in near the leaves, but it should run a loss-seeking mate-search verification for the root moves. That may help as well.

[hgm]

Indeed when CrazyWa's depth is strongly decreasing, this usually also is the case for Sjaak's depth.

I am thinking now about the following QS strategy to make the search more robust:

Code: Select all

int QSearch(Frame *ff, alpha, beta, depth)
{
  Frame f; // local variables accessible to daughters, e.g. for returning info beyond score
  int lower = -INF, upper = -INF;
  HashProbe();

  // narrow search window pre-sciently with limits from all daughters
  if(hash.score > alpha) alpha = hash.score;

  // hash cutoff for irrelevant or already resolved nodes
  if(alpha >= beta || hash.score == hash.lim) { ff->lim = -hash.score, return hash.lim; }

  // stand pat
  if&#40;depth <= 0&#41; lower = upper = Evaluate&#40;);
  if&#40;lower >= beta || depth < -depthLimit&#41; &#123; ff->lim = -lower; return INF; &#125;
  if&#40;lower > alpha&#41; alpha = lower;

  for&#40;ALL_MOVES&#40;depth&#41;) &#123;
    int score; Frame f;
    MakeMove&#40;);
    score = -QSearch&#40;&f, -beta, -alpha, depth-1&#41;; // returns upper, puts lower in f
    UnMake&#40;);
    upper = max&#40;f.lim, upper&#41;; // both components
    if&#40;score > alpha&#41; &#123;
      alpha = score;
      if&#40;score >= beta&#41; &#123; upper = INF; break; &#125;
    &#125;
  &#125;
  hash.score = lower;
  hash.lim   = upper;
  ff->lim = -lower;
  return upper;
&#125;

The idea is that it works with score intervals rather than scores. The interval {L,H} of the node is {max(L_i), max(H_i)} of its moves i (where stand pat is move 0); as soon as moves are not considered the interval of the node becomse {L, INF}, as the unconsidered move could be arbitrarily good. The interval {L, H} of a node appears as {-H, -L} of the move leading to the node in the parent, so moves refuted by cutoff in the daughter will have interval {-INF, -L}, -L < alpha, and are irrelevant (i.e. do not affect the interval of the current node, or the search window). Alpha is increased with the lower bound of the node's interval.

'Open' intervals (i.e. L != H) are generated only in two places: after cutoff (but then they do not propagate), or when the artificial depth limit is reached, and we return {eval, INF} without searching any moves. These do propagate. The idea is to repeat QS from a horizon node of the full-width search with increasing depth limit until the returned interval collapses to a single value. (Or falls entirely outside the search window.)

Of course instead of cutting off at a fixed depth, you could also prune non-capture evasions after a certain number of checks in the branch, which you then increase iteratively.

[hgm]

Interesting. I never realized this, but if a QS node fails low, and all of the captures have upper bounds below the stand-pat score, it is still an exact score. Because the stand-pat score also is a lower bound. Even if some of the upper bounds of the captures are above the stand-pat score, the result is a range {eval, max_upper_bound}, and could still be used to cause beta cutoffs if later probed with a lower beta (below eval).

[hgm]

Actually this can also happen in full-width nodes:

one of the moves can hit upon a position that is in the TT with an exact score (and sufficient depth), which due to a change of the window is now below alpha. So the move would fail low. Normally you would now assume that it can be arbitrarily poor, and that the score is just an upper bound. If all other moves in the node also fail low, you would assume the score of the node is not bound from below.

But in fact it is. The move with the exact hit provides a lower bound, you can always play that. If all other moves had an upper bound lower than the node that got the exact hit, the low-failing node in fact has an exact score!