I am coding up a chess engine and using the alpha-beta algorithm for tree scanning. I ended up doing what they posted here:
int alphabeta(int depth, int alpha, int beta)
{
move bestmove;
if (game over or depth <= 0) return winning score or eval();
for (each possible move m) {
make move m;
score = -alphabeta(depth - 1, -beta, -alpha)
if (score >= alpha) { alpha = score; bestmove = m; }
unmake move m;
if (alpha >= beta) break;
}
return alpha;
}
It is stated that "The code above always returns alpha, beta, or a number between alpha and beta." In my calcs this is not true and I need it in order to implement aspiration search. I have seen many variants of the algorithm and tried a few but sometimes the return value falls outside the desired interval [alpha, beta].
Can anyone post C++ or pseudo-code of alpha-beta with that property?
Is it possible to prove that ?
Finally, it seems intuitive that the return value is an increasing function of alpha keeping beta fixed and similarly for beta. Is it true and is it provable? In my calcs this is not the case.
How big must be the window of aspiration search in order to ensure we have not pruned out the principal variation? If the return value falls between alpha and beta will that suffice?