Answers.Body: <p>If a chess engine isn't aware of the mate, then it will be happy to play the moves as Black. By the time it sees the checkmate, it'd be too late. Game over. 1-0.</p>
  <p>Fortunately, your scenario is quite simple. A good engine should have sufficient depth to see the mate. The iterative deepening depth-first algorithm will allow searches with increasing depth limits: d,d+1,d+2,d+3... I believe any decent chess engine should be able to handle it, it's not a very deep search.</p>
  <p>While your example is simple, pruning does cause problems for tactical positison. Take a look at Chessbase's article:</p>
  <blockquote>
  <p><a href="https://en.chessbase.com/post/houdini5tacticalmode" rel="nofollow noreferrer">https://en.chessbase.com/post/houdini5tacticalmode</a></p>
  <p>...Suppose there is a complicated position in which you just feel there must be a tactic. You could be right, but sometimes even the monster engines can miss it at first...</p>
  </blockquote>
  <p>&quot;Tactical mode&quot; is a fantasy term for applying passive pruning.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-17T00:48:50.397Z
Answers.LastActivityDate: 2018-04-17T00:48:50.397Z
Answers.LastEditDate: 2020-06-17T09:59:59.497Z
Answers.UserDisplayName: SmallChess
Answers.Body: <p>You are confusing several concepts.</p>
  
  <p><strong>Alpha-beta pruning</strong></p>
  
  <p>Alpha-beta pruning is <em>not</em> "where they don't calculate positions that are obviously winning or obviously losing."</p>
  
  <p>It's pruning branches where it doesn't matter what their evaluation is, because another move is already good enough to know that this direction won't work.</p>
  
  <p>For instance, the opening position. Let's say that the engine is trying to figure out the best starting move and first it has researched 1.d4 (using whatever method), and found that it evaluates to +0.15 for white.</p>
  
  <p>Now it starts evaluating 1.e4. There are many different replies. First it tries 1...e6. This evaluates to +0.2. Fine. Then it tries 1...c5. This evaluates to +0.1.</p>
  
  <p>But wait! That means that black can do <em>at least</em> +0.1, and so regardless of the score of all the other possible moves, 1.e4 <em>must</em> end up worse than 1.d4. <em>So the other replies to 1.e4 are never evaluated.</em></p>
  
  <p>That trick also works recursively deeper in the tree. That's alpha beta pruning. For the same move tree it finds the same evaluation as normal minimax search, but faster.</p>
  
  <p><strong>Pruning</strong></p>
  
  <p>There is also more general heuristic based pruning of possible moves. Heuristic means that the engine <em>guesses</em> which moves probably aren't relevant. It's a trade-off between being able to search deeper and guessing wrong now and then. The big difference with alpha-beta pruning is that that only prunes branches that are absolutely certain not to matter, while this guesses.</p>
  
  <p><strong>Other</strong></p>
  
  <p>The rest of your question is about the problem of <em>where to stop</em> -- about quiescence, horizon effects (evaluation bad because the engine wasn't able to look deep enough) and so on, but those are unrelated to alpha-beta search. You have to think about that with any search method.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-23T15:13:01.393Z
Answers.Text: IMO, this doesn't address his point.  In my "answer", the computer would evaluate this position as -6 and prune this branch due to its score.  Without reaching further down the branch, the computer would return the wrong answer, and this is a major problem with pruning.
Answers.UserDisplayName: Fred Knight
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-24T20:09:19.600Z
Answers.Text: Yes but he's talking about alpha-beta pruning, which never results in a different move being chosen, it's purely for speed.
Answers.UserDisplayName: RemcoGerlich
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-25T09:40:35.657Z
Answers.Text: We're not talking about the move being chosen, we're talking about the program cutting off good moves due to lack of depth.  All search functions, except brute force--the pure minimax, try to search more by pruning the tree.  Without searching these branches, the computer will sometimes miss a great move.
Answers.UserDisplayName: Fred Knight
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-25T10:08:53.017Z
Answers.Text: But the question is confusing alpha-beta pruning with pruning in general, and I try to explain that. Alpha-beta pruning cannot cause you to miss a great move because it doesn't matter how good the pruned moves are.
Answers.UserDisplayName: RemcoGerlich
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-23T13:09:44.740Z
Answers.LastActivityDate: 2018-04-23T13:09:44.740Z
Answers.UserDisplayName: RemcoGerlich
Answers.Body: <p>Not an answer but an example of the question:</p>
  
  <pre><code>
  [FEN ""]
  [Event "?"]
  [Site "Bled"]
  [Date "1961"]
  [Round "?"]
  [White "T. Petrosian"]
  [black "L. Pachman"]
  [startply "40"]
  
  1. Nf3 c5 2. g3 Nc6 3. Bg2 g6 4. O-O Bg7 5. d3 e6 6. e4 Nge7 7. Re1 O-O 8. e5 d6 9. exd6 Qxd6 10. Nbd2 Qc7 11. Nb3 Nd4 12. Bf4 Qb6 13. Ne5 Nxb3 14. Nc4! Qb5 15. axb3 a5 16. Bd6! Bf6 17. Qf3! Kg7 18. Re4 Rd8 19. Qxf6+! Kxf6 20. Be5+ Kg5 21. Bg7!
  *
  </code></pre>
  
  <p>Here most computers would only examine forcing moves and not consider the "quiet" winning move. Since white is down material, most computers would eliminate Bg7 as a losing move, and by following the tree,  reject 19. Qxf6+!.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-22T04:29:32.623Z
Answers.Text: Good point... positions like these are probably why engines often take a while to adjust their evaluations. Maybe they re-examine quiet positions later on after finding an initial evaluation.
Answers.UserDisplayName: Inertial Ignorance
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-14T09:46:26.003Z
Answers.Text: I tested the position with Leela Zero, Stockfish, and Rybka. They all found M7 in about 100 ms.
Answers.UserDisplayName: user904963
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-04-21T18:42:58.443Z
Answers.LastActivityDate: 2018-04-21T18:42:58.443Z
Answers.UserDisplayName: Fred Knight
Body: <p>In order to calculate far ahead, minimax chess engines must perform alpha-beta pruning, where they don't calculate positions that are obviously winning or obviously losing. Without doing pruning, engines would have to deal with over a billion positions in the first 4 moves / 8 ply of the game.</p>
  
  <p>My question is how do minimax engines perform alpha-beta pruning without evaluating the final positions? How does an engine know whether a position is completely won / lost without calculating as deep as it can go? For example:</p>
  
  <ol>
  <li>e4 e5 2. Nf3 d6 3. Bc4 Bg4 4. Nc3 Nc6 5. h3 Bh5 6. Nxe5 Bxd1</li>
  </ol>
  
  <p>At this point, White's two moves away from checkmate. Assuming the engine wasn't aware of the Legal's Mate, wouldn't it apply Alpha-Beta pruning and just stop calculating at this point, assuming the position is won for Black?</p>
  
  <p>I'm aware of quiescence search, where the engine won't stop calculating until the position is considered "quiet". In this position, White is able to play Bxf7+ and Black's King is in danger, so this position wouldn't qualify as a quiet position.</p>
  
  <p>But if an engine has to perform quiescence search everytime it needs to decide whether to perform Alpha-Beta pruning and stop calculating further, doesn't this defeat the purpose of pruning in the first place? Since you need to calculate ahead to check to see if you don't need to calculate ahead.</p>
  
  <p>EDIT: There are two answers to this question that I found very useful. Look at SmallChess' answer for info on issues with the depth-limit of engines' calculations. See RemcoGerlich's answer for an excellent description of what Alpha-Beta pruning is. When I wrote this question I didn't truly know what it was.</p>
  
Tags: <engines><programming><calculation><chess-algorithms><minimax>
Title: How can minimax chess engines do alpha-beta pruning without reaching the final positions?
ThreadText: # How can minimax chess engines do alpha-beta pruning without reaching the final positions?
  
  (Asked by: username_0 on 2018-04-16)
  
  In order to calculate far ahead, minimax chess engines must perform alpha-beta pruning, where they don't calculate positions that are obviously winning or obviously losing. Without doing pruning, engines would have to deal with over a billion positions in the first 4 moves / 8 ply of the game.
  
  My question is how do minimax engines perform alpha-beta pruning without evaluating the final positions? How does an engine know whether a position is completely won / lost without calculating as deep as it can go? For example:
  
  1. e4 e5 2. Nf3 d6 3. Bc4 Bg4 4. Nc3 Nc6 5. h3 Bh5 6. Nxe5 Bxd1
  
  At this point, White's two moves away from checkmate. Assuming the engine wasn't aware of the Legal's Mate, wouldn't it apply Alpha-Beta pruning and just stop calculating at this point, assuming the position is won for Black?
  
  I'm aware of quiescence search, where the engine won't stop calculating until the position is considered "quiet". In this position, White is able to play Bxf7+ and Black's King is in danger, so this position wouldn't qualify as a quiet position.
  
  But if an engine has to perform quiescence search everytime it needs to decide whether to perform Alpha-Beta pruning and stop calculating further, doesn't this defeat the purpose of pruning in the first place? Since you need to calculate ahead to check to see if you don't need to calculate ahead.
  
  EDIT: There are two answers to this question that I found very useful. Look at username_1' answer for info on issues with the depth-limit of engines' calculations. See username_2's answer for an excellent description of what Alpha-Beta pruning is. When I wrote this question I didn't truly know what it was.
  
  **Tags:** engines, programming, calculation, chess-algorithms, minimax
  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2018-04-17. Score: 3 | Accepted answer
  
  If a chess engine isn't aware of the mate, then it will be happy to play the moves as Black. By the time it sees the checkmate, it'd be too late. Game over. 1-0.
  
  Fortunately, your scenario is quite simple. A good engine should have sufficient depth to see the mate. The iterative deepening depth-first algorithm will allow searches with increasing depth limits: d,d+1,d+2,d+3... I believe any decent chess engine should be able to handle it, it's not a very deep search.
  
  While your example is simple, pruning does cause problems for tactical positison. Take a look at Chessbase's article:
  
  > <https://en.chessbase.com/post/houdini5tacticalmode>
  >
  > ...Suppose there is a complicated position in which you just feel there must be a tactic. You could be right, but sometimes even the monster engines can miss it at first...
  
  "Tactical mode" is a fantasy term for applying passive pruning.
  
  
  ---
  
  ### Answer by username_2 on 2018-04-23. Score: 6
  
  You are confusing several concepts.
  
  **Alpha-beta pruning**
  
  Alpha-beta pruning is *not* "where they don't calculate positions that are obviously winning or obviously losing."
  
  It's pruning branches where it doesn't matter what their evaluation is, because another move is already good enough to know that this direction won't work.
  
  For instance, the opening position. Let's say that the engine is trying to figure out the best starting move and first it has researched 1.d4 (using whatever method), and found that it evaluates to +0.15 for white.
  
  Now it starts evaluating 1.e4. There are many different replies. First it tries 1...e6. This evaluates to +0.2. Fine. Then it tries 1...c5. This evaluates to +0.1.
  
  But wait! That means that black can do *at least* +0.1, and so regardless of the score of all the other possible moves, 1.e4 *must* end up worse than 1.d4. *So the other replies to 1.e4 are never evaluated.*
  
  That trick also works recursively deeper in the tree. That's alpha beta pruning. For the same move tree it finds the same evaluation as normal minimax search, but faster.
  
  **Pruning**
  
  There is also more general heuristic based pruning of possible moves. Heuristic means that the engine *guesses* which moves probably aren't relevant. It's a trade-off between being able to search deeper and guessing wrong now and then. The big difference with alpha-beta pruning is that that only prunes branches that are absolutely certain not to matter, while this guesses.
  
  **Other**
  
  The rest of your question is about the problem of *where to stop* -- about quiescence, horizon effects (evaluation bad because the engine wasn't able to look deep enough) and so on, but those are unrelated to alpha-beta search. You have to think about that with any search method.
  
  > **Comments:**
  > **username_3**: IMO, this doesn't address his point.  In my "answer", the computer would evaluate this position as -6 and prune this branch due to its score.  Without reaching further down the branch, the computer would return the wrong answer, and this is a major problem with pruning.  
  > **username_2**: Yes but he's talking about alpha-beta pruning, which never results in a different move being chosen, it's purely for speed.  
  > **username_3**: We're not talking about the move being chosen, we're talking about the program cutting off good moves due to lack of depth.  All search functions, except brute force--the pure minimax, try to search more by pruning the tree.  Without searching these branches, the computer will sometimes miss a great move.  
  > **username_2**: But the question is confusing alpha-beta pruning with pruning in general, and I try to explain that. Alpha-beta pruning cannot cause you to miss a great move because it doesn't matter how good the pruned moves are.  
  
  ---
  
  ### Answer by username_3 on 2018-04-21. Score: 1
  
  Not an answer but an example of the question:
  
  ```
  
  [FEN ""]
  [Event "?"]
  [Site "Bled"]
  [Date "1961"]
  [Round "?"]
  [White "T. Petrosian"]
  [black "L. Pachman"]
  [startply "40"]
  
  1. Nf3 c5 2. g3 Nc6 3. Bg2 g6 4. O-O Bg7 5. d3 e6 6. e4 Nge7 7. Re1 O-O 8. e5 d6 9. exd6 Qxd6 10. Nbd2 Qc7 11. Nb3 Nd4 12. Bf4 Qb6 13. Ne5 Nxb3 14. Nc4! Qb5 15. axb3 a5 16. Bd6! Bf6 17. Qf3! Kg7 18. Re4 Rd8 19. Qxf6+! Kxf6 20. Be5+ Kg5 21. Bg7!
  *
  
  ```
  
  Here most computers would only examine forcing moves and not consider the "quiet" winning move. Since white is down material, most computers would eliminate Bg7 as a losing move, and by following the tree, reject 19. Qxf6+!.
  
  > **Comments:**
  > **username_0**: Good point... positions like these are probably why engines often take a while to adjust their evaluations. Maybe they re-examine quiet positions later on after finding an initial evaluation.  
  > **username_4**: I tested the position with Leela Zero, Stockfish, and Rybka. They all found M7 in about 100 ms.  
  
  ---
  
  