How can minimax chess engines do alpha-beta pruning without reaching the final positions?

Question

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 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.

Answer 1

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 2

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.

Answer 3

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+!.