Q6i

Given below is the sketch of a program that represents the path in a two-person game tree by the sequence of active procedure calls at any time. The program assumes that the payoffs are real number in a limited range; that the constant INF is larger than any positive payoff and its negation is smaller than any negative payoff and that there is a function “payoff” and that computes the payoff for any board that is a leaf. The type “boardtype” has been suitably declared to represent board positions. It is player-$1$’s move if mode = MAX and player-$2$’s move if mode=MIN. The type modetype = (MAX, MIN). The functions “min” and “max” find the minimum and maximum of two real numbers. function search(B: boardtype; mode: modetype): real; var C:boardtype; {a child of board B} value:real; begin if B is a leaf then return (payoff(B)) else begin if mode = MAX then value :=-INF else value:INF; for each child C of board B do if mode = MAX then value:=max (value, search (C, MIN)) else value:=min(value, search(C, MAX)) return(value) end end; (search) Comment on the working principle of the above program. Suggest a possible mechanism for reducing the amount of search.