5

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.

4

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.

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

  • 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. – Inertial Ignorance Apr 22 '18 at 4:29
3

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.

  • 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. – Fred Knight Apr 23 '18 at 15:13
  • Yes but he's talking about alpha-beta pruning, which never results in a different move being chosen, it's purely for speed. – RemcoGerlich Apr 24 '18 at 20:09
  • 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. – Fred Knight Apr 25 '18 at 9:40
  • 3
    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. – RemcoGerlich Apr 25 '18 at 10:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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