Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old March 9th 04, 11:40 PM
Benjamin Jordan
 
Posts: n/a
Default alphabeta?

I'm a beginner having trouble understanding alphabeta search. A mating
sequence might start with a queen sacrifice, but since the search
hasn't gotten deep enough to see the mate, won't the sacrifice get cut
off? And since that line is cut off, how does the search ever find
it? Thanks.
  #2   Report Post  
Old March 10th 04, 12:42 AM
RPM1
 
Posts: n/a
Default alphabeta?


"Benjamin Jordan" wrote in message
om...
I'm a beginner having trouble understanding alphabeta search. A mating
sequence might start with a queen sacrifice, but since the search
hasn't gotten deep enough to see the mate, won't the sacrifice get cut
off? And since that line is cut off, how does the search ever find
it? Thanks.


The sacrifice won't get cut off unless the mate is beyond the
'horizon'. Remember alpha-beta *backs up* the tree it does
not "forward prune". Also many alpha-beta programs will
extend the search beyond the horizon if the king is in check
or a piece was just captured.

Here's a web site that might be of interest:
http://www.seanet.com/~brucemo/topics/alphabeta.htm

There are lots of web sites that discuss alpha-beta search,
try a Google search.

Hope this helps,
Patrick



  #3   Report Post  
Old March 10th 04, 02:27 AM
Vincent Diepeveen
 
Posts: n/a
Default alphabeta?

alphabeta is a pruning method.

It is independant from the search depth in that sense.

Your question has to do with the depth limited nature of the search. The
answer is that when the remaining search depth is very small a deep trick
will keep hidden behind the horizon.

All alphabeta does is trigger decision after a move has been searched,
whether you still need to search the remaining moves.

Best example is that you search 1.e4,h5 2.Qxh5,Rxh5 ...

For Rxh5 you get back +9.0 black up.

So using negamax which is using the side to move score, that's +9000 side to
move up in the position where you try Rxh5.

Assuming alfa and beta were set already to 1.e4,e5 being the best line, that
means simply that

alfa = -0.001 beta = 0.000

Seen from black side.

From black side you capture a queen now which after searching that move
gives back score = 9.000

9.0 = 0.0 so you get a cutoff.

For a human that's logical. Giving away a queen doesn't make sense so it is
pruned.


"Benjamin Jordan" wrote in message
om...
I'm a beginner having trouble understanding alphabeta search. A mating
sequence might start with a queen sacrifice, but since the search
hasn't gotten deep enough to see the mate, won't the sacrifice get cut
off? And since that line is cut off, how does the search ever find
it? Thanks.



  #4   Report Post  
Old March 10th 04, 05:33 AM
Noah Roberts
 
Posts: n/a
Default alphabeta?

Benjamin Jordan wrote:
I'm a beginner having trouble understanding alphabeta search. A mating
sequence might start with a queen sacrifice, but since the search
hasn't gotten deep enough to see the mate, won't the sacrifice get cut
off? And since that line is cut off, how does the search ever find
it? Thanks.


Pure alpha beta will not see a mate combination that involves any kind
of sacrifice (even pawn) if a gain in material or a win is not within
the search horizon. But engines do not use alpha beta by itself.

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.

The horizon is one of alpha beta's most prominant weaknesses. There is
no way to fix it. We use quiescence and extensions to make it less of a
problem, but the fundamental weakness is not solvable. This is why the
evaluation function is so important. The more analysis in the
evaluation, the less of an impact the horizon will have. But the more
you evaluate, the closer the horizon gets. It is a balancing act.

As a beginner I found citeseer to be very useful. Google for it.

--
"I'm a war president. I make decisions here in the Oval Office
in foreign policy matters with war on my mind." - Bush

  #5   Report Post  
Old March 10th 04, 12:15 PM
Mikko Nummelin
 
Posts: n/a
Default qsearch (was alphabeta?)

On Tue, 9 Mar 2004, 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).


Too complicated quiescence search is disadvantageous as it may cause a
"quiescence search explosion", meaning that there will be so much extra
hassle with it that the actual full-width search does not get deep enough.
That means that best programs limit severely the qsearch width in order to
get about next full width search sooner. The ways to do this a

- ordering qsearch moves so that captures with least valuable attacker and
most valuable victim are executed first, if attack boards are in use, then
captures to squares not in opponents attack boards would be also good
tries to do first.

- perhaps taking a risk and not running qsearch to infinity, but stopping
it to, say 6 plies, or not trying captures with more valuable attacker
than victim if victim stands on opponents attack board.


Mikko Nummelin


  #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?
  #7   Report Post  
Old March 10th 04, 06:04 PM
Mikko Nummelin
 
Posts: n/a
Default alphabeta?

On Wed, 10 Mar 2004, Benjamin Jordan wrote:

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?


Yes, the alpha and beta are not updated unless the new scores have
actually come from leaf nodes all the way down.


Mikko Nummelin
  #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
  #9   Report Post  
Old March 10th 04, 10:23 PM
David Richerby
 
Posts: n/a
Default alphabeta?

Robert Hyatt wrote:
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...


And, just to be explicit about it, the conclusion that playing the second
move leads to Black having an advantage of at least one pawn is made by
fully analyzing the results of one of Black's replies to that move, not
just by saying `Oh, he can take a pawn with his queen' without looking to
see if that queen can then be taken. Of course, by `fully analyzed', I
mean that it's analyzed with a recursive call to the alpha-beta routine
but, as Dr Hyatt says, that has just the same result as doing an
exhaustive search but does it much faster. (I keep wanting to say,
`hence, by induction...' and cutting myself short (-: ).


Dave.

--
David Richerby Miniature Ghost (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ haunting spirit but you can hold in
it your hand!
Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On



All times are GMT +1. The time now is 03:36 AM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright 2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017