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

a. The value of n1 is given by n1 = (n2, n21, . . . n21r2) 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 mini max 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 ni 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 amm-node.

Transcribed Image Text:

112 n,