Quiescence Search and hanging pieces

[osvitashev]

I am tinkering with a project that will become a chess engine eventually. At this point there several more things i need to implement before i can run the engine end-to-end and start using ELO gain as a way to analyze what is best.

I was writing test cases for my quiescence search and happen to come across this position:
[d]8/8/6k1/5p1N/3p1Pp1/3K2P1/8/8 w - - 0 1

The quiescence routine is based on the pseudocode from chess programming wiki: https://www.chessprogramming.org/Quiescence_Search
At every depth of q-search I am generating all of the possible captures (not checks) and choose between the score of the best capture and the score of the current position. The evaluation function is based on piece-square tables.

In the position above, the q-search favors doing nothing over taking d4. Not seeing that the knight on h5 is lost.
So, a case of "if i don't give my opponent a turn, they cannot do bad things to me".

I can think of two possible ways to handle this better:

1. A more sophisticated evaluation function that is aware of hanging pieces. That would surely be way too expensive in terms of CPU time. Especially, compared to PSTs.

2. Allowing null moves in quiescence search. So, instead of evaluating the position as standing pat, we pass the move to the opponent and let them choose between doing nothing and taking a capture. That would increase the quiescence search tree somewhat. Obviously i'd need to limit the number of allowed null moves (is just one enough?) in order to avoid infinite recursive descent.

Which approach is better? Are there any other ways to handle it?

Alternatively, is this even a real problem to solve? I am assuming it must be - otherwise the engine would be susceptible to horizon-style effects.

[jorose]

Thank you for giving a nice illustrative example! I have a couple thoughts.

In my opinion, I think you should not view QS as being a perfect tactics solver. Instead, it is there to prevent the most common form of horizon effect, which is ending search in the middle of a capture sequence.

Your given case is an edge case which I don't think is too common and it may be challenging to come up with a good generalization of what this edge case actually is. As such, investing resources into solving this edge case may not be worth it, as instead having a more efficient QS may result in the given situation being reached in the main AB search tree, in which case it would get solved due to a lack of standing pat.

My impression is people tend to overemphasize the evaluation portion of a chess engine, perhaps because it is easier for humans to think about than reasoning about search trees which are inherently more dynamic and complex. In this case, however, I actually believe it may be better to leave the problem to the evaluation function for 2 reasons.

Firstly, you don't need to compute the next few moves to see the Nh5 is probably dead. For handcrafted evaluation functions this may not be trivial, but I think modern neural network based evaluation functions excel at this type of pattern recognition (especially larger ones like Leela's transformers and ResNets, but I think also Winter style nets do well). As such, it may not be a real problem for modern engines.

Secondly, if you think about other positions with trapped pieces (eg a trapped white knight on a8 that has captured a rook), the effort of going to capture the knight may not be worth it, meaning the search will continuously encounter the situation where it will consider capturing the knight even though it prioritize something else. Adding mechanisms to overemphasize these sequences in search may be actively counterproductive in this case. The following TCEC game comes to mind. Consider how long the Nh7 was trapped, but Winter prioritized other play, over trying to capture it.

[pgn][Event "TCEC Season 26 - Swiss 6"]
[Site "https://tcec-chess.com"]
[Date "2024.01.24"]
[Round "1.11"]
[White "Cheese 3.2.0"]
[Black "Winter 2.07e"]
[Result "0-1"]
[Annotator "archive"]

1. d4 d5 2. c4 dxc4 3. e4 c5 4. d5 Nf6 5. Nc3 b5 6. Bf4 a6 7. e5 Nfd7 8. Nh3 Nb6 9. e6 fxe6 10. Bxb8 Rxb8 11. Qh5+ g6 12. Qe5 exd5 13. Qxh8 Qd6 14. Ng5 Qf6 15. Qxf6 exf6 16. Nxh7 Be7 17. h4 Bf5 18. g4 Bxg4 19. h5 Bxh5 20. Be2 Bxe2 21. Nxe2 d4 22. Ng3 Nd5 23. O-O-O Rb6 24. Ne4 Kf7 25. Rde1 Nf4 26. Kb1 Re6 27. f3 Kg7 28. Reg1 Re5 29. Rg4 g5 30. Rgg1 d3 31. Rh2 Nd5 32. Kc1 Rf5 33. Rh3 Nf4 34. Ng3 Re5 35. Rh2 b4 36. Kd2 c3+ 37. bxc3 c4 38. Ne4 Ra5 39. a4 bxa3 40. Ra1 Nd5 41. Rah1 Rb5 42. Kc1 Rb3 43. f4 gxf4 44. Rg2+ Kf7 45. Rh5 Nxc3 46. Nxc3 Rxc3+ 47. Kb1 Rb3+ 48. Ka2 Rb5 49. Rh1 Re5 50. Rd2 Re2 51. Rh2 f3 52. Rf2 Bc5 53. Nxf6 Bxf2 54. Ne4 Rxe4 55. Kxa3 Bc5+ 56. Ka2 Re2 57. Rb2 f2 58. Rxe2 dxe2 59. Kb2 f1=Q 60. Ka2 Qf2 61. Kb2 e1=Q#
0-1[/pgn]

[hgm]

In a minority of chess positions searching one ply deeper completely alters the score. QS is not an exception to that. Unless you have some free oracle which will tell you for which positions this is the case, the only solution would be to do that 1-ply-deeper search, and compare the score. But since you already searched to the maximum depth that you could afford timewise, this is an unaffordable solution.

Of course having the oracle would change that. Detecting that the side not to move has a threat by examining all its moves is already as expensive as searching 1 ply for the side to move, and thus halves the engine speed. Since it would only come up with something useful in less than 1% of the cases, the improved accuracy for a given nominal depth would would not be able to overcome the general deterioration by the slowdown. You would need some significantly more efficient method to detect the threat.

But even if you could detect the threat for free, you should then still try to find a defense. As when such a defense exist you would still achieve the stand-pat score. In which case the time spent on finding the defense would have been wasted. You might have a smaller slowdown by only doing these extra searches, but most threats can be easily dealt with by having the move, so the increase of the accuracy would still be very dismal. Again not worth it.

Besides, extending the search, for whatever reason, incurs a high risk for search explosion. Both sides could have naging pieces (when using null move in the full-width search that is quite common, as you would prefer null move over capturing hanging pieces). That could make both sides extending the QS indefinitely.

So you don't just have to recognize threats for free; you would have to detect incurable threats. Neural nets might be able to do that. But of course NN can hardly be called efficient methods for static evaluation. Detection of the threats is only free because even in the absence of them evaluation is a huge calculation. But at least there is no risk for search explosion in that case.

[osvitashev]

The following TCEC game comes to mind. Consider how long the Nh7 was trapped, but Winter prioritized other play, over trying to capture it.

@jorose Thanks for your thoughts! That is a very interesting game.
I would expect the principal variation to include the move capturing h7 at some point.
If that's the case, it would mean the engine regarded capture as won, but never choose to expend a tempo on it over doing other things on the board.

Might be wrong about that.

I spent some more time musing over the nature of q-search. Originally, i was thinking of relying on fast search and simplistic evaluation, but maybe i want too far with that.

The position i posted earlier is extreme in the sense that the knight is trapped and lost.

Consider this:
[d]8/8/4k3/4N3/1p6/1K6/8/8 w - - 0 1
Again, q-search favors doing nothing over capturing the pawn.
This can be interpreted as "if White got to this position, they would have a tempo to resolve whatever threats they are facing."
This assumption can be incorrect if there are multiple hanging pieces.
I understand the point that evaluation function is supposed to gauge 'threat level' among other things.
If i recall correctly, i ,at some point, saw a mention of eval function detecting potentially hanging pieces and increasing the score penalty based on how many there are.

I am actually curious to eventually try null moves in q-search as a way to resolve this.
Will come back to this when my engine has ELO usable for comparison.

[Ras]

Again, q-search favors doing nothing over capturing the pawn.

That's an eval problem. My engine evaluates this position as slightly better for Black because a pawn might promote while the White's knight can never enforce mate. So my engine would take the pawn even in QS.