Does depth (number of ply) still matter once it is high enough?

Question

This isn't real, just imagine this happening.

Computer A is supercomputer. It can calculate 30 ply deep within 20 seconds.

Computer B is supercomputer. It can calculate 15 ply deep within 20 seconds.

They play against each other chess.

Does these 15 depths really matter? I guess that within these 15 depths there may be trillions way to escape a checkmate or capture of important piece. Sure, Computer A knows more. But Computer B is able to predict future quite far too, in my opinion, far enough to defend himself really well.

Answer 1

Yes, those 15 depths very much matter.

Consider this position that occurred in Kasparov's Immortal Game vs Topalov.

  [White "Kasparov"]
  [Black "Topalov"]
  [FEN "b2r3r/k4p1p/p2q1np1/NppP4/3R1Q2/P4PPB/1PP4P/1K2R3 b - - 0 24"]

I tested this position with several engines. Some engines, at depth 15, failed to detect that 24...cxd4 is a losing move and thought it was winning. Those same engines, at a greater depth, played the correct move 24...Kb6!

For example, even an engine as powerful as Stockfish 4 initially at depth 21 thinks the losing move 24...cxd4 is correct.

Stockfish DD 64 SSE4.2: 24...cxd4 25. Re7+ Kb6 26. Qxd4+ Kxa5 27. Qc3+ Kb6 
28. Qd4+ Qc5 29. Qxf6+ Bc6 30.Qxc6+ Qxc6 31. dxc6 Rd1+ 32. Ka2 f5 33. c7 Rc8 
34. Rxh7 Rxc7 35. Rh6 Rc6 36. g4 f4 37. g5 Rd2 38. c3 Rxc3 39. Rxg6+ Kc5 
40. Bg4 Rcc2 41. Rxa6 Rxb2+ 42. Ka1 Rbc2 43. Kb1 
(-1.45/21)

The same engine, when kept on for a little more depth, shows 24...Kb6 to the correct move.

Stockfish DD 64 SSE4.2: 24...Kb6 25. b4 Qxf4 26. Rxf4 Nxd5 27. Rxf7 cxb4 
28. axb4 Rhe8 29. Rxe8 Rxe8 30. Nb3 Re1+ 31. Kb2 Re2 32. Rxh7 Nxb4 
33. Kc3 Nd5+ 34. Kd3 Rxh2 35. Rh4 Ne7 36. Nd4 Nc6 37. Nxc6 Bxc6 38. f4 Kc5 
39. Be6 Rxh4 40. gxh4 Bd5 41. f5 gxf5 42. Bxf5 a5
(-0.78/26)

Fritz 11 SE, at depth 15, also failed. But it found the correct move at depth 16!

Fritz 11 SE: 24... cxd4 25. Qxd4+ Qb6 26. Re7+ Nd7 27. Qe5 f6 28. Qc3 Qg1+ 
29. Ka2 Bxd5+ 30. Nb3 f5 31. Qc7+ Ka8 32. Rxd7 Rxd7 33. Qxd7 Bxf3 34. Qd6 Qa7  
(-1.44/15) 

Fritz 11 SE: 24... Kb6 25. b4 Qxf4 26. Rxf4 Nxd5 27. Rxf7 cxb4 28. axb4 Nxb4 
29. Nb3 Bd5 30. Rf6+ Nc6 31. Nd4 Rdf8 32. Rd6 Kc5 33. Rxc6+ Bxc6 34. Ne6+ Kd6 
35. Nxf8 
(-0.59/16)

Also consider this incredible problem like position that I found here.

Stockfish was not able to find the winning line 1. Be2+! until depth 31 and up until then it thought it was a bad move. I demonstrate the win here. The point is that Black is in zugswang because of mate threats and has to either give up the queen or move the a pawn which would allow White to create a passed pawn and win.

   [FEN "8/2p1q3/p3P3/2P4p/1PBP2kP/2N3P1/7K/8 w - - 0 1"]

   1. Be2+ $1 Kf5 2. Nd5 $1 Qxe6 3. Bd3+ Kg4 4. Be4 $3 Qh6 (4... Qxe4 5. Nf6+) 
   5. Nf4 Qg7 6. Nd3 $1 Qxd4 7. c6 $1 a5 (7... Qxe4 8. Nf2+ Kf3 9. Nxe4 Kxe4 
   10. Kg2 Kd4 11. g4 hxg4 12. h5 Ke5 13. h6 Kf6 14. Kg3 Kg6 15. Kxg4 Kxh6 
   16. Kf5 Kg7 17. Ke6 Kf8 18. Kd7 Kf7 19. Kxc7) 8. b5 $1 a4 9. b6 cxb6 
   10. c7 Qxe4 (10... Qc3 11. Nf2#) 11. Nf2+ Kf3 12. Nxe4 1-0

Here's the engine log from Stockfish 4. As you can see, it detects that 1. Be2+ is winning, only on depth 31!

Stockfish DD 64 SSE4.2: 1. Be2+ Kf5 2.Bc4 c6 3. Ne2 Qf6 4. Kg2 Kg4 5. Nf4 Qxd4 
6. Bd3 Qe3 7. Be2+ Kf5 8. Bf3 Qd2+ 9. Kh3 Qxb4 10. e7 Qe1 11. Ne2 Qf1+ 12. Kh2 Qf2+
13. Kh3 Qe3 (-1.05/22) 

Stockfish DD 64 SSE4.2: 1. Be2+ Kf5 2. Bc4 Qf6 3. Ne2 c6 4. Bxa6 Qxe6 5. Bd3+ Kf6 
6. Nf4 Qe1 7. d5 Qxb4 8. dxc6 Qxc5 9. Be4 Ke7 10. c7 Kd7 11. Nd5 Kd6 12. Kh3 Qc4 
13. Bg2 Qg4+ 14. Kh2 Qc8 15. Be4 (-1.15/26) 

Stockfish DD 64 SSE4.2: 1. Be2+ Kf5 2. Bc4 Qf6 3. Ne2 c6 4. d5 cxd5 5. Bxd5 Qb2 
6. Bc4 Kf6 (-1.01/28) 

Stockfish DD 64 SSE4.2:  1. Be2+ Kf5 2. Nd5 Qxe6 3. Bd3+ Kg4 4. Be4 Qh6 5. Nf4 Qf6 
6. Nd3 Qxd4 7. c6 Qxe4 8. Nf2+ Kf3 9. Nxe4 Kxe4 10. Kg2 Ke5 11. Kf3 Kf5 12. g4+ Kf6
13. gxh5 Kg7 14. Kf4 Kf6 15. h6 Kg6 16. h5+ Kh7 17. Kg5 Kg8 18. h7+ Kxh7 19. Kf5 Kg7
20. Ke6 Kh6 21. Kd7 Kxh5 22. Kxc7 Kg5 23. Kd7 (6.06/31) 

Answer 2

The relationship between performance gains and search depth has actually been an active area of research for quite a long time in the computer chess programming communities. There was a theory that increases in search depth resulted in diminishing returns in strength... this seemed to be verified in experimental results.

From my perspective, there is an intuitive foundation for this. Imagine your hypothetical match up between two supercomputers, starting from endgame tablebase positions. Most forced wins in tablebases happen at a horizon less than (for instance) 50 ply. The majority of the remaining positions are drawn, only a small fraction resolve to wins at a higher depth. A computer searching at 100 ply would have limited advantage over a 50 ply computer, because (as you mention) the weaker program is able to navigate through nearly all the losing lines, all occurring at more limited depth. A 50 ply program would actually have a much bigger advantage over a 25-ply program... as would a 4 ply program have an even bigger advantage over a 2 ply program.

I first came across this concept about 15 years ago, in the series of papers on Dark Thought, experimenting in deep searches. These are a great read if you are interested in computer chess.

Although I couldn't find an online reference, there is a paper from last year on this topic...

Diogo R. Ferreira (2013). The Impact of the Search Depth on Chess Playing Strength. ICGA Journal, Vol. 36, No. 2

Answer 3

The question is: Do you mean 15/30 ply of exhaustive search, or a nominal depth/iteration of 15/30 of a modern chess engine like Stockfish?

If you meant the latter, 15 ply does not necessarily mean much. Modern chess engines heavily prune and reduce moves that are supposedly bad, so it might be that a sacrifice that seems to be bad at first sight, at a nominal depth/iteration of 15 is actually only searched to a depth of e.g. 5-10. At depth/iteration 30, the move probably is still searched only to a reduced depth, but then it might be an effective depth of 15-20, which could be sufficient to find that the sacrifice is actually good, and as soon as the engine discovers that the move is promising, it will decrease the reduction, so that the move is searched to a depth closer to 30 ply (or even deeper due to extensions and quiescence search). So yes, I think it can make a difference, even if the combination is within the nominal horizon of 15 ply.

If you were referring to an exhaustive search, then I think an engine with a depth of 15 would be very strong provided that it has a good evaluation function and some kind of quiescence search (after the leave nodes at depth 15). Due to diminishing returns, I think the gain by doubling the depth would be much less than what you would get for a match between two modern engines with depth 15 vs. depth 30. But that is of course only theoretical, since an exhaustive search to depth 15 would take several orders of magnitude longer than what engines usually take to reach depth/iteration 15, so such an experiment would only be feasible at lower depths.

Answer 4

FWIW When the ARM was new, I wrote an optimised ARM exhaustive search program with a material only position evaluation after ply 1.

I used tricks with optimised machine code, iterative deepening, alpha-beta windowing on sorted moves (almost all positions had value 0, so got near-optimal alpha-beta pruning) - and hash tables which reduced the branch factor to much less than the theoretical square root for alpha-beta, typically around 4 at the worst part of the game.

In a competition against the standard programs at the time, my E6P program got into terrible positions, but with an extra ply or two exhaustive search compared to pro software at the time (ie typically 6 ply exhaustive + quiescent search in the worst stage, with up to 12 ply as the game simplified), it kept wriggling out of actually losing, despite the confidence of its opponents. Almost all the games went to adjudication after many hours because the opposing programs couldn't actually win.

Later I optimised it for StrongARM, where it moved to 10 ply. This version could easily beat all the non-chess players, though obviously it lacked any strategy awareness, so the famous comment applied: yes, they are chess moves - but it isn't chess!

This was quite a few years ago, but I am tempted to try exhaustive again with a more strategic position evaluation at ply 1 - and with an Intel XEON theoretically 10,000-100,000x faster (and with 30k times more hash table memory) than a 4MIPS ARM2 Acorn Archimedes.

Admittedly not mainstream, but fun to play.

Answer 5

+1 ply is estimated +55..70 ELO gain (a lot of researches on this topic)

I guess that within these 15 depths there may be trillions way to escape a checkmate or capture of important piece.

The thing is that all this "trillions" were calculated by A @ D=30, and if A choose move with winning eval, it mean that it calculated all this "trillions" and no matter which of "trillions" moves opponent reply - move is still winning