13 Develop a formal proof of correctness for alpha–beta pruning. To do this, consider the situation shown in Figure 18. The question is whether to prune node n , which is a max node and a descendant of node n1. The basic idea is to prune it if and only if the minimax value of n1 can be shown to be independent of the value of nj .

a. Mode n1 takes on theminimum value among its children: n1 = min(n2, n21, . . . , n2b2

).

Find a similar expression for n2 and hence an expression for n1 in terms of nj .

b. Let li be the minimum (or maximum) value of the nodes to the left of node ni at depth i, whose minimax value is already known. Similarly, let ri be the minimum (or maximum)

value of the unexplored nodes to the right of ni at depth i. Rewrite your expression for n1 in terms of the li and ri values.

c. Now reformulate the expression to show that in order to affect n1, nj must not exceed a certain bound derived from the li values.

d. Repeat the process for the case where nj is a min-node.