Alpha-beta safe on incomplete tree?

Question

I'm writing a simple chess program from scratch on a hobbyist basis. I think there is something fundamental I'm overlooking or don't understand.

I read the following http://chessprogramming.wikispaces.com/Alpha-Beta, as well as other articles, e.g. the Wikipedia one. I've also implemented alpha-beta blindly before just by following pseudo-code. I believe I understand how alpha-beta can guarantee no unsafe pruning takes place on a complete search tree, i.e. if you have the whole search tree, and there are no unexplored nodes beyond the horizon.

What I don't understand is how alpha-beta can guarantee no unsafe pruning takes place on an incomplete search tree which does contain such unexplored nodes beyond the horizon, which chess always results in, unless evaluating endgames with a small enough tree.

Consider the following explanation from: http://chessprogramming.wikispaces.com/Alpha-Beta

Say it is White's turn to move, and we are searching to a depth of 2 (that is, we are consider all of White's moves, and all of Black's responses to each of those moves.) First we pick one of White's possible moves - let's call this Possible Move #1. We consider this move and every possible response to this move by black. After this analysis, we determine that the result of making Possible Move #1 is an even position. Then, we move on and consider another of White's possible moves (Possible Move #2.) When we consider the first possible counter-move by black, we discover that playing this results in black winning a Rook! In this situation, we can safely ignore all of Black's other possible responses to Possible Move #2 because we already know that Possible Move #1 is better.

This seems to be false to me, exploring further nodes on the branch of "Possible Move" #2, e.g. a couple more ply, could result in black being guaranteed checkmate?

Hence pruning away this as a possible move is not safe.

What am I missing?

I know this ties in with the horizon effect and quiescence search, however I don't understand how alpha-beta alone, when used in this way on an incomplete search tree can be considered "safe". But I'm sure there is something I'm overlooking and it would be great with some pointers.

Answer 1

As far as I can tell, you are crystal clear conceptually, and you aren't actually missing anything. I think the source of any apparent conflict between your understanding and the quoted passage is that you may be reading the passage to be claiming more than it really is. Here it is again, with some added emphasis:

Say it is White's turn to move, and we are searching to a depth of 2 (that is, we are consider all of White's moves, and all of Black's responses to each of those moves.) First we pick one of White's possible moves - let's call this Possible Move #1. We consider this move and every possible response to this move by black. After this analysis, we determine that the result of making Possible Move #1 is an even position. Then, we move on and consider another of White's possible moves (Possible Move #2.) When we consider the first possible counter-move by black, we discover that playing this results in black winning a Rook! In this situation, we can safely ignore all of Black's other possible responses to Possible Move #2 because we already know that Possible Move #1 is better.

I think that the only point being made here is that in this particular situation, "we already know that Possible Move #1 is better" as far as our limited depth search is concerned. That is, we have fixed this depth of 2 ply for our search in advance, that is as far as our knowledge is going to go, and the information discovered in the scenario does conclusively show that within the scope of the next 2 plies Possible Move #1 is better than Possible Move #2.

Your worry that something crucial might be being missed beyond that limit is absolutely correct, of course, and is why ideally such an algorithm would search all the way to the end of the entire chess game tree. That would be the only way to know that we have no "unsafe pruning," or in other words that we are playing optimally. But going that far isn't feasible (except for e.g. certain endgame positions, as you note, or say positions that are close to a forced conclusion of a game), so in whatever reasonable, finite amount of time an engine will have to search, it will only make it to some particular depth N that is insufficient for complete certainty. The point being made in the above passage isn't that we know Possible Move #1 is truly better than Possible Move #2 (i.e. with respect to the entire game tree), but only that we know it is definitely better with respect to the fixed depth N we actually get to search. But that's OK, as that's all we could possibly be sure of, which is exactly your point.