Benjamin Jordan wrote:

RPM1 wrote:

Remember alpha-beta *backs up* the tree it does

not "forward prune".

Vincent Diepeveen wrote:

alphabeta is a pruning method.

I think this is why I am confused :-) I'm sure you are both right,

but I cannot yet put my finger on the resolution of this paradox.

Noah Roberts wrote:
Noah is correct. Alpha/beta is a _backward_ pruning algorithm. You can

prove that the result returned by alpha/beta is _exactly_ the same as the

result returned by minmax. With _forward_ pruning, this is not true.

Most engines utilize a quiescence search. This search will continue

alpha beta to infinity or until a quiet position is reached. The search

always reaches a quiet position so infinity is only a theoretical bound.

Simple quiescence searches only look at captures. Slightly more

complicated ones look at checks. Really thorough quiescence searches

might look for "forced" moves that are not one of the other types -

moves where there is no other practical option (actually this falls into

singular extensions also). This type of search would probably find the

mate. If the quiescence search is thurough and it still doesn't see a

mate at the end of a sacrifice then there must be a good reply, and so

it is not a true sacrifice. However, practically I think there will

always be holes where mate combinations could get lost in.

I understand quiescence search and how it helps reduce the horizon

effect. But consider this classic puzzle by Morphy (try to solve it

before reading on, it is a nice puzzle):

FEN: 5Kbk/6pp/6P1/8/8/8/8/7R w - - 0 1

White to play and mate in 2 moves

+---+---+---+---+---+---+---+---+

8 | | | | | | K | *B| *K|

+---+---+---+---+---+---+---+---+

7 | | | | | | | *P| *P|

+---+---+---+---+---+---+---+---+

6 | | | | | | | P | |

+---+---+---+---+---+---+---+---+

5 | | | | | | | | |

+---+---+---+---+---+---+---+---+

4 | | | | | | | | |

+---+---+---+---+---+---+---+---+

3 | | | | | | | | |

+---+---+---+---+---+---+---+---+

2 | | | | | | | | |

+---+---+---+---+---+---+---+---+

1 | | | | | | | | R |

+---+---+---+---+---+---+---+---+

a b c d e f g h

Here, a *simple* quiescence extension wouldn't seem to help, because

the solution is two non-capturing moves. After 1. Rh6 gxh6 white has

dramatically lost material and it would prune - missing 2. g7# on the

next ply. But that would be forward pruning, and RPM1 clearly stated

that alpha-beta doesn't do that! 1. ... gxh6 would trigger

quiescence, but it would only see 2. gxh7 Bxh7 and find that white is

lost.

What I am beginning to believe is that alpha-beta is only used to

prune *leaf* nodes, thereby getting an early return on ply n, but the

entire ply still needs to be generated before starting on n+1. Am I

getting warmer?
Alpha/beta prunes _useless_ branches only.

For example, you search the first root move and find you can win a pawn (score

is +1.0). When you start working on the second root move, the first move for

the opponent you try wins a pawn for him. Is there any need to see if he has

an even better more that wins even more? No. His winning at least a pawn

is enough for you to figure out that this second move (-1.0 and maybe worse)

is worse than the first move (+1.0). That is an alpha/beta/pruning cutoff

point that saves effort without changing the score at all...

--

Robert M. Hyatt, Ph.D. Computer and Information Sciences

University of Alabama at Birmingham

(205) 934-2213 136A Campbell Hall

(205) 934-5473 FAX Birmingham, AL 35294-1170