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

[ydebilloez]

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?

[Bo Persson]

Why would AB not generate a cut-off rejecting the queen and/or rook sacrifice?

It would - if you only search 2 plies.

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?

To get the mate score, you have to search deep enough to actually see the mate. And alpha-beta cuts down on the search tree, enabling you to search deeper.

[Ras]

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.

How to solve this with AB?

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.

[BeyondCritics]

Nope, you are mingling up Iterative deepening (https://www.chessprogramming.org/Iterative_Deepening), alpha beta (https://en.wikipedia.org/wiki/Alpha%E2% ... ta_pruning) and unsafe pruning (https://www.chessprogramming.org/Pruning) somehow and then you get totally confused of course. Best to forget all that and start afresh. If you really want to understand it mathematically, then you must become more precise:
What is a graph? What is a tree? What is a directed graph? What is a game tree? What is the minimax value of a game tree?
Can you write a short program, that calculates the minimax value of a game tree directly from the definition?
If so, then you are ready for the alpha beta algorithm, which is just a refinement of that algorithm.

[Dann Corbit]

https://www.google.com/search?q=alpha+b ... e&ie=UTF-8

[hgm]

If you really want to understand it mathematically, then you must become more precise:
What is a graph? What is a tree? What is a directed graph? What is a game tree? What is the minimax value of a game tree?
Can you write a short program, that calculates the minimax value of a game tree directly from the definition?
If so, then you are ready for the alpha beta algorithm, which is just a refinement of that algorithm.

That is really overdoing things. Even the most non-mathematically inclined chess player is intuitively aware of alpha-beta pruning, which in layman's terms is completely covered by the principle "one refutation is enough to disqualify a move".

[JohnWoe]

If beta (minimizer) has already found move values B one ply before. Then alpha (maximizer) has found move valued A. If A >= B. Then searching beyond is a waste of time as minimizer won't pick this variation anyway. If not then keep searching. Terminal nodes are of course returned immediately (Checkmates/draws). Vice versa for black of course.

[Michel]

The OP was asking for a mathematical proof. The proof is a simple induction on the depth of the tree using the induction hypothesis that the value returned by AB search is either an upper bound for, a lower bound for or equal to the exact minimax value, depending on its position with regard to the AB interval.

AB is very clever (e.g. I read somewhere that Shannon was not aware of it) but the proof that it works is very short.

[Henk]

If you really want to understand it mathematically, then you must become more precise:
What is a graph? What is a tree? What is a directed graph? What is a game tree? What is the minimax value of a game tree?
Can you write a short program, that calculates the minimax value of a game tree directly from the definition?
If so, then you are ready for the alpha beta algorithm, which is just a refinement of that algorithm.

That is really overdoing things. Even the most non-mathematically inclined chess player is intuitively aware of alpha-beta pruning, which in layman's terms is completely covered by the principle "one refutation is enough to disqualify a move".

If evaluation has a random component than maybe one refutation not enough.

[hgm]

Sure. But then minimax doesn't apply either. A determinisic example is Veto Chess; there you always need two refutations, as the best of those will be vetoed. So you have to propaate scores through the nearlymininearlymax algorithm. With non-deterministic games (such as Einstein Wuerfelt Nicht) one uses 'expectimax'.