Dark Mode

852 views

9 votes

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.

8 votes

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.

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.

1