Alpha Beta Pruning Search Algorithm

[philmetz]

Im a little confused how this search works. Good someone help explain it to me. I tried on this picture (http://en.wikipedia.org/wiki/File:AB_pruning.svg) but it doesnt make sense. Where am I starting on the tree? is it bottom left? How does alpha beta pruning work then?

[thoughtcoder]

There is pseudocode in the Wikipedia article.

[philmetz]

I still dont quiet understand it. Im not sure when to prune.
The definition is:
"It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move"

But how does it know it found a move that is worse that a previously examined move? is thre previously examined move every move so far or the one just prior?

[thoughtcoder]

When looking at the image, you see how the subtree with the 8 at the root is blocked? Note that the diagram shows the results of a left-to-right traversal of the tree. It's blocked because we've visited the left subtree, with a 5 at the root, and we're going to take the min of the scores of the two subtrees. That means the score we take will be less than or equal to 5. Also, we'll take the max, the next row up, and that'll be 6. No matter what is in the blocked subtree, we'll end up taking a 6, the next row up. So there's no reason to visit the subtree.

[philmetz]

cool, i also found this so incase anyone was as confused as me, check this out: http://www.cs.ucla.edu/~rosen/161/notes/alphabeta.html