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?
Mathematical proof that AB with B-cutoff does not miss a variation
Moderators: hgm, Rebel, chrisw
-
- Posts: 163
- Joined: Tue Jun 27, 2017 11:01 pm
- Location: Lubumbashi
- Full name: Yves De Billoëz
Mathematical proof that AB with B-cutoff does not miss a variation
Yves De Billoëz @ macchess belofte chess
Once owner of a Mephisto I, II, challenger, ... chess computer.
Once owner of a Mephisto I, II, challenger, ... chess computer.
-
- Posts: 243
- Joined: Sat Mar 11, 2006 8:31 am
- Location: Malmö, Sweden
- Full name: Bo Persson
Re: Mathematical proof that AB with B-cutoff does not miss a variation
It would - if you only search 2 plies.ydebilloez wrote: ↑Fri Apr 30, 2021 2:38 pm
Why would AB not generate a cut-off rejecting the queen and/or rook sacrifice?
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.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?
-
- Posts: 2488
- Joined: Tue Aug 30, 2016 8:19 pm
- Full name: Rasmus Althoff
Re: Mathematical proof that AB with B-cutoff does not miss a variation
Which is also why Minimax wouldn't find a mate at 2 plies.ydebilloez wrote: ↑Fri Apr 30, 2021 2:38 pmAt ply 2 in this situation, the best score white can think off is queen down... there is no mate in any of the moves
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.How to solve this with AB?
Rasmus Althoff
https://www.ct800.net
https://www.ct800.net
-
- Posts: 396
- Joined: Sat May 05, 2012 2:48 pm
- Full name: Oliver Roese
Re: Mathematical proof that AB with B-cutoff does not miss a variation
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.
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.
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Mathematical proof that AB with B-cutoff does not miss a variation
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Mathematical proof that AB with B-cutoff does not miss a variation
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".BeyondCritics wrote: ↑Fri Apr 30, 2021 6:21 pmIf 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.
-
- Posts: 491
- Joined: Sat Mar 02, 2013 11:31 pm
Re: Mathematical proof that AB with B-cutoff does not miss a variation
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.
-
- Posts: 2272
- Joined: Mon Sep 29, 2008 1:50 am
Re: Mathematical proof that AB with B-cutoff does not miss a variation
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.
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.
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.
Without ideas there is nothing to simplify.
-
- Posts: 7220
- Joined: Mon May 27, 2013 10:31 am
Re: Mathematical proof that AB with B-cutoff does not miss a variation
If evaluation has a random component than maybe one refutation not enough.hgm wrote: ↑Fri Apr 30, 2021 8:18 pmThat 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".BeyondCritics wrote: ↑Fri Apr 30, 2021 6:21 pmIf 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.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Mathematical proof that AB with B-cutoff does not miss a variation
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'.