4

Example puzzle (I'm sure there are numerous that fit this bill):

[FEN "rnbq3r/pppp4/3b1pkp/5p2/2BP4/4P3/PPP2PPP/RN1QK2R w KQ - 0 1"]
[Site "Earth"]
[White ""]

1. Qh5+ Kxh5 2. Bf7+ Kh4 3. Nd2 Bb4 4. c3 f4 5. Nf3+ Kg4 6. e4 Bxc3+ 7. bxc3 f5 8. h3#

I've found a 8 move checkmate that takes Stockfish a depth of 36 ply to solve. Since the checkmate is only 16 ply deep in the game search tree, what specific mechanisms cause the engine to take 20 ply longer to find the solution?

I understand that the high level answer is engine selectivity. However, my understanding is that Stockfish's forward pruning tended to be pretty safe (such as null move pruning). Plus, if the solution were being forward pruned, wouldn't it keep being pruned even at later depths?

I also thought that reductions such as late move reductions only really reduce the search depth by a one or a few ply, not 20!

(The winning move is a check, so it shouldn't be reduced by something like late move reduction anyways.)

What gives?

(Crossposted...will be sure to update if anything comes of it)

1
  • Enumerating the exact set of techniques in action here might be too difficult, but I'd really appreciate if anyone could give me a general idea of where my thought process might be going wrong.
    – iRove
    Aug 17 at 23:25
2

For anyone who stumbles across this wondering the same thing, I received an answer to my question here. This post is thus a courtesy of u/__Durandal__ and IMJorose. Though I can't do justice to their write-ups and highly recommend them, in case it somehow goes down, I'll summarize the gist here.

The reduction techniques in Stockfish are not limited to just one or two ply—late move reductions, for example, are calculated based on the number of moves already searched and the current depth. In the current implementation:

If a position has 40 moves in it and is searched at depth 16, the reduction applied is five plies.

Furthermore, any potentially-unsafe pruning techniques (i.e. avoiding entire part of the tree) have a depth cap at which they stop operating. These two phenomena explain what I was seeing.

Notably, given infinite time, Stockfish will still converge to the minimax solution: reduction techniques become inconsequential at infinite depth and depth caps mean that nothing will be overlooked via pruning.

1

I am not an expert on this, but I think one can get some insight into this by examining how Leela's Monte Carlo Tree Search works. Leela's neural network gives 1) a win percentage for that position, and 2) a list of candidate moves to consider, each with a probability. Leela then uses that probability in its searches. For example, if the neural network is 99% confident that a particular move is correct, then Leela will spend 99% (?) of its time looking at that move.

However, it will also eventually look at the remaining 1%. It will de-emphasize the other moves, and it will spend less time looking at those moves, but it will do so eventually.

I think that's what you're seeing here. The key first move gives away a Queen for no apparent compensation, so Stockfish de-emphasizes it. However, after it has searched the mainlines to very high depth (d=36), it goes back and looks at the moves it earlier de-emphasized. It finds that 1.Qh5+ is better, and this line becomes promoted to the new principal variation.

I do not know the technical details, however.

1
  • Thanks for taking a stab! From what I understand, you're absolutely correct. This explains how Leela might respond to the puzzle. I guess I'm looking for the alpha/beta search equivalent of this monte carlo tree search characteristic. It's almost like we get there with late move reductions, but I didn't think they could go as far as 20 ply.
    – iRove
    Aug 18 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.