Thread: alphabeta?
View Single Post
  #8   Report Post  
Old March 10th 04, 06:47 PM
Robert Hyatt
 
Posts: n/a
Default alphabeta?

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