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

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.

Thanks! But can you tell me, is it true that in the standard tree no nodes are being cut?

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.

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!

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".