alpha-beta algorithm returns a value between alpha and beta inclusive?

Question

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

1. Can anyone post C++ or pseudo-code of alpha-beta with that property?

2. Is it possible to prove that ?

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

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

Answer 1

My usual reference is https://chessprogramming.wikispaces.com/Alpha-Beta#Implementation-Negamax%20Framework, which I believe is correct.

In your lecture slide, if score > beta ==> alpha = score ==> return alpha which is greater than beta. Thus, the claim looks incorrect to me.

You don't need to prove "increasing function of alpha" because any score less than alpha is a bad move for you, so you would ignore it.

Aspiration window width is a parameter and there is no definitive answer. You don't want it too big, or too small. You'll need to run tests...