Mathematical proof that AB with B-cutoff does not miss a variation

[ydebilloez]

At ply 2 in this situation, the best score white can think off is queen down... there is no mate in any of the moves

Which is also why Minimax wouldn't find a mate at 2 plies.

The issue is that AB search is set at e.g. 6 plies, but the cut-off cuts away the complete branch with the winning sacrifice as the combination leading to the win is refuted. In pure minimax, the mate is found.

With enough depth. Sure, you can also have a cut-off right after the queen sacrifice if you search until depth 4, but that isn't AB, that's futility pruning - which does overlook things, unlike AB.

So beta-cutoff here is futility pruning?

In the last commit, I cleaned up the AB search a bit so that housekeeping code gets out of the way and the algorithm stands out more clear.
From search_ab.cpp (but simplified for the question here)

Code: Select all

  for (movenum_t moveid = 0; moveid < n_moves; moveid++) {
    bBoard chldbrd(b, moveid, true);
    bScore chldscore = -CalcBestMove(chldbrd, nDepth + 1, -beta, -alpha);
    b.setMoveScore(moveid, chldscore);
    if (belofte::realScore(chldscore) - nBetaCutOffMargin >= belofte::realScore(beta)) {
        return chldscore; // (fail soft) 
    }
    if (belofte::realScore(chldscore) > belofte::realScore(alpha)) {
      // 𝛼 & ↑ update
      b.setBestScore(chldscore);
      alpha = chldscore;
    }
  }

Please note that I do not do makeMove/unMakeMove on the same position but generate a child-board with the playing move applied.
Please also note I use score for two purposes, set flags on theoretic draw/undefined/etc... and normal score. This is why the call to realscore is required.

In my chess engine, one can disable beta-cutoff in AB search and in AB QS search by setting nBetaCutoffMargin to a high value. One can set the algorithm to AB or ABFS with the alg command.

[ydebilloez]

"one refutation is enough to disqualify a move".

Thanks, indeed. I am working on an algorithm that is more human like and searches for the one refutation and which is not AB that seems too mathematical for me. The idea to go to full depth on the first variation seems wrong and although AB is node-wise an improvement over minimax, I am not convinced that AB is the right solution.

Thanks for your clues on Veto chess. Will have a look.

[Henk]

Original/non standard/creative algorithms are appreciated. We are no accountants.

[Ras]

The issue is that AB search is set at e.g. 6 plies, but the cut-off cuts away the complete branch with the winning sacrifice

AB just doesn't do this. If your search does it, it is not AB, as simple as that.

So beta-cutoff here is futility pruning?

If it doesn't explore the branch and just sees "oh I'm down a queen, that won't change, so I don't need to explore this branch at all in more depth", then it's futility pruning and not AB.

and the algorithm stands out more clear.

I have no idea what this might be doing, but "nBetaCutOffMargin" looks suspiciously like pruning and not AB because AB doesn't need a margin.

[Sven]

"one refutation is enough to disqualify a move".

Thanks, indeed. I am working on an algorithm that is more human like and searches for the one refutation and which is not AB that seems too mathematical for me. The idea to go to full depth on the first variation seems wrong and although AB is node-wise an improvement over minimax, I am not convinced that AB is the right solution.

Thanks for your clues on Veto chess. Will have a look.

You asked for the mathematical proof, so I googled for you ... Here is
one of several matches.

[hgm]

Thanks, indeed. I am working on an algorithm that is more human like and searches for the one refutation and which is not AB that seems too mathematical for me. The idea to go to full depth on the first variation seems wrong and although AB is node-wise an improvement over minimax, I am not convinced that AB is the right solution.

Well, alpha-beta is very human-like, so probably you will eventually re-invent it.

I never considered alpha-beta 'very clever'. More 'pretty obvious'. If Shannon did not know it, he cannot have been even a mediocre chess player. Note that alpha-beta was not introduced through any mathematical proof, and originally thought to be just a heuristic. The proof came later.

And the proves referred to here seems needlessly complex. It is really a trivial thing: in a max node a score lower than that of a move in that same node that has already been searched cannot propagate to the root, because it is not the maximum. And thus might as well not have existed, and can be pruned without consequences. Thus, to propagate to the root, a score for the maxing player must be better than the score of all moves of that player in all nodes along the path to the current node. As something similar holds for the minimizing player, only scores between the limits set by the side branches (which are conventionally called alpha and beta) can propagate to the root. As soon as alpha gets greater or equal to beta nothing can ly in between, so here is no need to actually calculate the score to know that it cannot propagare to the root, and you can just prune all remaining moves unsearched.

[Michel]

Thanks, indeed. I am working on an algorithm that is more human like and searches for the one refutation and which is not AB that seems too mathematical for me. The idea to go to full depth on the first variation seems wrong and although AB is node-wise an improvement over minimax, I am not convinced that AB is the right solution.

Well, alpha-beta is very human-like, so probably you will eventually re-invent it.

I never considered alpha-beta 'very clever'. More 'pretty obvious'. If Shannon did not know it, he cannot have been even a mediocre chess player. Note that alpha-beta was not introduced through any mathematical proof, and originally thought to be just a heuristic. The proof came later.

And the proves referred to here seems needlessly complex. It is really a trivial thing: in a max node a score lower than that of a move in that same node that has already been searched cannot propagate to the root, because it is not the maximum. And thus might as well not have existed, and can be pruned without consequences. Thus, to propagate to the root, a score for the maxing player must be better than the score of all moves of that player in all nodes along the path to the current node. As something similar holds for the minimizing player, only scores between the limits set by the side branches (which are conventionally called alpha and beta) can propagate to the root. As soon as alpha gets greater or equal to beta nothing can ly in between, so here is no need to actually calculate the score to know that it cannot propagare to the root, and you can just prune all remaining moves unsearched.

Well the proof I gave was more transparent I think....

With hindsight(!) many brilliant ideas are trivial. Knuth and Moore give an account of the history of the discovery alpha-beta search. http://www-public.tem-tsp.eu/~gibson/Te ... oore75.pdf . Alex Bernstein, who definitely was a chess player, was also not aware of it, when he wrote his first chess program.

[Desperado]

I have trouble understanding why AB would find the best variation and does not have a cut-off too soon.
Assume a position where white does sacrifice a queen, then a rook to give a forced mate afterwards.
ply 0 - equal - staring position - white to move
ply 1 - equal - queen en prise (last move from list) - black to move
ply 2 - queen down - white to move
ply 3 - queen down - rook en prise (last move from list) - black to move
ply 4 - queen and rook down - white to move
...
ply n - mate

At ply 2 in this situation, the best score white can think off is queen down... there is no mate in any of the moves, and the move ordering does not put the mate leading variation in the first place. (as there is a queen/rook sacrifice, most likely, that move will even be considered last in the move-list)

Why would AB not generate a cut-off rejecting the queen and/or rook sacrifice?
If we remove the cut-off from the algorithm, we get a regular minimax which will find the combination at the expense of a lot of time.

I have the impression that given the performance of mate-net searches in chess programs, the above issue gets masked but is still present.
How to solve this with AB?

Maybe it will help to visualize how minimax and alpha beta works Minimax + AlphaBeta