Thread: alphabeta?
View Single Post
  #6   Report Post  
Old March 10th 04, 05:07 PM
Benjamin Jordan
 
Posts: n/a
Default alphabeta?

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:

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?