852 views

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.

### 1 comment

some one explain it more clearly the question itself is quite confusing

Here, the game is started by giving the first move to a player.

Let's assume Player $1$ takes the first move. At initial step, his payoff will be the maximum payoff achieved by Player $2$ for all possible child boards as shown by the following statement:

 value:=max (value, search (C, MIN))

Similarly, Player $2$ will get the minimum payoff achieved by Player $1$ for all the possible child boards.

The problem with the above algorithm is that the same path in the tree will be evaluated repeatedly for different parent node (here node is the board). The amount of search can be significantly reduced if the output of each recursive call is saved and possibly reused if required again, instead of doing a recursive call for each child board.

by

### 1 comment

same path in the tree will be evaluated repeatedly for different parent node (here node is the board)

This is not really true though, very rarely it can happen that after a sequence of two different moves we end up in same board position. I think what they were going for in the question as a optimization method was alpha-beta pruning.

https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning

1
2,444 views