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

a. The value of nl is given by

Find a similar expression for n2 and hence an expression for nl 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 r.i be the minimum (or maximum)
value of the unexplored nodes to the right of ni at depth i. Rewrite your expression for nl in terms of the li and ri values.

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

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

Transcribed Image Text:

n1 min(n2, n21,...,n2b).