1
$\begingroup$

I have an AI class this semester. For our exam, we also cover alpha-beta pruning.

I found an old example, where I think we can stop already earlier. Here is a picture of it.

enter image description here

I think, because $X$ wants to maximize his win, and finds 10, he knows that he cannot get better. Therefore he cuts and puts 10.

I marked my "improvement" with red.

$\endgroup$
0

3 Answers 3

2
$\begingroup$

The vanilla Alpha-Beta Pruning algorithm as it has been taught to you in class does not assume any domain knowledge / knowledge about the game / knowledge about the tree it is searching. Therefore, if it immediately finds a score of 10 directly to the left of the root node, it can not prune yet, because... maybe there's a score of 20 somewhere else in the tree?

In your description, you seem to assume prior knowledge that the maximum score that can possibly be obtained in the entire game is 10. This is not typically assumed to be available knowledge ahead of time, at least not in the original formulation of Alpha-Beta. That is why in pseudocode of the algorithm (for example on wikipedia), they initialize alpha and beta at minus and plus infinity.

You are right though. If you have better estimates of the upper and lower bounds on scores that can every be achieved throughout the entire game, you can use better initializations of alpha and beta than minus and plus infinity. alpha and beta would have to be -11 and 11 if the true bounds are -10 and 10. I suspect you'd also have to make some additional changes to the typical pseudocode to actually make use of this though.

In more complex games than Tic Tac Toe, you're often not going to have very useful knowledge of better bounds though. Typically you can't afford to search all the way to terminal game states, you'll have to stop the search earlier and use heuristic evaluation functions to estimate scores. If you do that, you'll often want to assign really high constants (like +/- 1Million) to actual terminal nodes (wins and losses), so that all your heuristic scores for non-terminal nodes can be somewhere in between. If you have such a large range of possible scores, your idea stops having much value.

$\endgroup$
1
$\begingroup$

http://inst.eecs.berkeley.edu/~cs61b/fa14/ta-materials/apps/ab_tree_practice/

you can make practice for better understanding the topic.

And i also recommend this lecture from MIT

https://www.youtube.com/watch?v=STjW3eH0Cik&index=6&list=PLUl4u3cNGP63gFHB6xb-kVBiQHYe_4hSi

$\endgroup$
0
$\begingroup$

So I assumed that we know that the maximum value overall is 10. But we do not know that, therefore we need to continue and cannot cut off the way I was thinking.

Although we would know that the max. value overall is 10, then we can cut off there.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .