Jump to content
  • Advertisement
Sign in to follow this  
delivery_guy

Understanding of alpha-beta pruning

This topic is 3035 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

as you can see I am kind of new to this forum. So please correct me if I place my post in the wrong category. Thank you.

I have a small question about alpha-beta pruning. I looked at the pseudo-code at wikipedia (http://en.wikipedia.org/wiki/Alpha-beta_pruning) and tried to run it manually but I can't seem to get any alpha-beta cut offs from the following tree.

I have some questions, can somebody manually run step by step the algorithm or explain to me why I can't seem to get an alpha-beta cutoff? And how can I arrange the tree optimally so I can get maximal amount of cutoffs? (Can someone also tell me what the fastest method is to producing such optimal tree?)

Thanks!

Here is the image: http://img291.imageshack.us/img291/9353/alphabetapruning.png

Share this post


Link to post
Share on other sites
Advertisement
You should probably use constant-depth trees to develop an intuition for alpha-beta. Also, I would try to have at least three successors per node.

The arrangement of the tree that will get you the best rate of beta cut-offs is to always examine the best successor first. Of course, if you had some way of knowing which move is the best at each position, you wouldn't need to search at all. So in practice you try to sort the moves using some heuristics. Common ones are the killer-move heuristic and history heuristic. If you have transposition tables, you would store the move that seemed best last time you visited this node. So even if the parameters of the current search and the one stored in the transposition tables are such that you have to continue searching, you get a hint as to how to best explore the tree.

In the case of your tree, explore C before B and you'll see that E will never be explored by an alpha-beta search.

Share this post


Link to post
Share on other sites
Quote:
Original post by delivery_guy
Thanks! But can you tell me, is it true that in the standard tree no nodes are being cut?


I don't know what you mean by "standard". The left-to-right search of your tree diagram results in no beta cut-offs. Notice that, except for some leaves, the second move is better than the first every time.

Share this post


Link to post
Share on other sites
I refer to the tree at http://img291.imageshack.us/img291/9353/alphabetapruning.png as the standard tree and if I apply alpha-beta pruning to it, there will be no cut off's at all right?

Notice that, except for some leaves, the second move is better than the first every time.

What do you mean by second move? And are leaves being cut in the "standard" tree?

Thanks for your help!

Share this post


Link to post
Share on other sites
Quote:
Original post by delivery_guy
I refer to the tree at http://img291.imageshack.us/img291/9353/alphabetapruning.png as the standard tree and if I apply alpha-beta pruning to it, there will be no cut off's at all right?

Please, re-read my previous post. I am objecting to your question because it is poorly formulated. The answer you are looking for is probably "yes", but the amount of pruning that alpha-beta search gives you depends on the order in which the tree is explored, which your diagram does not specify. My previous answer specifies the order.

Quote:
Quote:
Notice that, except for some leaves, the second move is better than the first every time.


What do you mean by second move?


Alpha-beta is a sequential algorithm: The successors to a node are considered one by one, in some order. By "second" I mean the one that comes after "first".

Quote:
And are leaves being cut in the "standard" tree?

Again, not a meaningful question, but the answer to what you are really trying to ask is "no".

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!