Question

please answer (b)

Consider the zero-sum game tree shown below. Trapezoids that point up, such as at the root, represent choices for the player seeking to maximize; trapezoids that point down represent choices for the minimizer (a) Assuming both opponents act optimally, carry out the minimax search algorithm. Write the value of each node inside the corresponding trapezoid and highlight the action the maximizer would take in the tree. (b) Now reconsider the same game tree, but use alpha-beta pruning. Expand successors from left to right. Record the alpha- beta pair that is passed down that edge (through a call to MIN VALUE or MAX-VALUE). Circle all leaf nodes that are visited Put an X' through edges that are pruned off.

Answer 1

In alpha-beta pruning, we assume alpha = -infinity and beta= infinity initially. Values of alpha and beta are always passed downwards only and not upwards.

On the leftmost node, we compare: alpha(-infinity,5). Since we are talking about maximizing, value of alpha will be 5.

Now alpha=5

Now we check alpha(5,7). 7>5 so alpha =7. We write 7 in the node.

The minimizer will pick least value and only 7 is present so it will select 7.

Now the next node will have alpha = -infinity and beta = 7 (as I said earlier values are passed down)

Similarly, we will take largest value of alpha which is -3.

Minimizer will select -3 now as -3<7 and pass it down wards.

On the next node, maximizer will pick 8. Now it will see that alpha >= beta is satisfied as 8 > -3. So the next edge will be pruned.

Similarly other nodes will be calculated on the second subtree.

On the third subtree, after checking the first node we will get value of beta = -5. We had value of alpha = -1. Since -1 > -5, the other two edges will be pruned and the minimizer will have final value of -5.

Finally the maximizer will pick maximum of -3, -1, -5 which is -1.

So, aplha = -1 and beta = infinity on the root node.

-1 -3 -1 -5 -3 3 -5 2 3 9 4