search explosion

[xr_a_y]

In this position

[d] rnbqkbnr/rrrrrrrr/8/8/8/8/RRRRRRRR/RNBQKBNR w KQkq - 0 1

some engines are instantaneously going to depth 10 while other takes ages to go to depth 1 ...

It looks like a qsearch explosion, but Stockfish or Ethereal or demolito have no limited depth qsearch and are very fast on this.
While Minic, Amoeba, asymptote, Fruit or arasan are dying here.

Minic is doing perft on this thing quite fast (perft 5 in 7 sec, 232.475.999 nodes),
while a depth 1 search is 37 sec ! for 64.306.778 nodes

Is there a real bug hidden here ?

[xr_a_y]

Might be that futility/delta pruning is currently off inside Minic... Wait better when activated !

[hgm]

A lot depends on move ordering here. Search explosions are typically caused by plunder raids, and orderings that prefer recapture tend to be much less suceptible to search explosion. In this pathological example you have lots of RxR captures, and their ordering might be arbitrary. SOme engines might simply have more luck at this than others.

In the tiny AI of the Interactive Diagram I needed a very stable QS, as there is no way to know in advance how wild the positions are that people will feed it. The position you give her could very well be the start position of a chess variant they want to play with it. Trying a depth-first all-captures search is thus a recipe for disaster.

What I do instead is only make LxH 'recaptures' (i.e. to the same square) and recapture of unprotected pieces absolutely free. Other new captures (i.e. with the previously moved piece, or the captures that move discovered), as well as equal recaptures on protected pieces count as 0.5 ply, and new HxL captures of protected pieces, or non-new captures count as 1 ply. (I.e. the same as PV moves.) This way the plunder raids still deepen at twice the rate of the quiet lines, but they don't immediately deepen to infinity to cause search explosion.

[xr_a_y]

I indeed give a nice bonus to recapture with positive SEE in move ordering but that won't do the trick here.
Futility pruning in qsearch seems to help a lot in this case, but remains quite slow at depth 1 (4sec !), then speed up to reach depth 10 in 21 sec.
I'll try if delta can help also ...

[hgm]

The point is that recaptures with zero or negative SEE are often also the best move: allowing the intruder to survive can be fatal, because you don't know what valuable pieces it will be attacking in its new position. A Knight capturing into your position might now attack your Queen, and going for a a Rook elsewhere won't bring you much. If you recognize threats, and upgrade the SEE score on the piece that makes the threat with the value of the threat, you won't have that problem.

[xr_a_y]

Ok, I try recapture bonus even for negative SEE and it works quite well on this position, although still slower than qfutility here.
But in Minic, qfutility is a big elo drop, while this recapture bonus seems to be quite ok ... I'm doing some more testing about this ...

[xr_a_y]

Mmmm just found this in SF

Code: Select all

  case QCAPTURE:
      if (select<Best>([&](){ return   depth > DEPTH_QS_RECAPTURES
                                    || to_sq(*cur) == recaptureSquare; }))
          return *(cur - 1);

with DEPTH_QS_RECAPTURES = -5

This may very well be the trick for this kind of position !

[Pio]

The point is that recaptures with zero or negative SEE are often also the best move: allowing the intruder to survive can be fatal, because you don't know what valuable pieces it will be attacking in its new position. A Knight capturing into your position might now attack your Queen, and going for a a Rook elsewhere won't bring you much. If you recognize threats, and upgrade the SEE score on the piece that makes the threat with the value of the threat, you won't have that problem.

That is an interesting observation. Maybe it is also a good idea to place The captures of the discovered Pieces in front of other captures of same priority.

[hgm]

In the tiny AI I make a distinction between moves that are new because of what the opponent did on the previous ply ('recapture' and 'pin enforcement'), and because of what you did yourself two ply earlier ('plunder' and 'discovery'). In general discovered pieces are a bit less dangrous than pieces that moved, as they get at most a single new capture, while a moved piece often gets many. But you are right, in principle discovery and plunder are similar, and if a discovered piece makes an important new threat, it can be beneficial to capture that quickly to. In general, the way to combat search explosion is to first play the lines that allow creation of as few new captures as possible. These lines terminate relatively quickly, and put tighter bounds on the search window that is then used when searching the exploding lines, often to the point of cutting them off completely. With a recapture you can be sure that none of the new captures by the mover survives, and at most some discovered attacks will be added.

You must be a bit pragmatic about it, though; if a Pawn moves it can never have many new attacks, and using a Queen to capture it when it was protected is defeating the purpose. The tiny AI is not aware of protection, and there is no easy way to figure out whether a piece is protected when pieces can have bent or zig-zag trajectories, or hop over other pieces or possibly even capture by hopping over you. So the only sure way is to just generate all moves of the opponent, and see whether any hit a certain square. That poses a bit of a problem, because I want to try recapture of an unprotected piece at any depth. So I speculatively recapture anything at d=0, but if it was a HxL or equal capture, I pass a flag to the daughter to indicate we are working from a 'depth deficit', and if that daughter then finds a recapture, it returns a fail high without actually searching that, to make the HxL (which is now known to be H x protected L) in the parent fail low, as if it was pruned.