in Algorithms recategorized by
852 views
9 votes
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.

in Algorithms recategorized by
852 views

1 comment

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

1 Answer

8 votes
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.

edited by
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
1

Related questions