recategorized by
1,132 views
11 votes
11 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.

recategorized by

1 Answer

9 votes
9 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

Related questions

13 votes
13 votes
5 answers
1
go_editor asked Dec 20, 2016
3,237 views
Solve the recurrence equations:$T(n)= T( \frac{n}{2})+1$$T(1)=1$
8 votes
8 votes
3 answers
2
go_editor asked Dec 20, 2016
3,280 views
Assume that the matrix $A$ given below, has factorization of the form $LU=PA$, where $L$ is lower-triangular with all diagonal elements equal to $1, U$ is upper-triangula...
7 votes
7 votes
3 answers
3
go_editor asked Dec 20, 2016
1,211 views
Are the two digraphs shown in the above figure isomorphic? Justify your answer.
1 votes
1 votes
1 answer
4
go_editor asked Dec 20, 2016
537 views
Verify whether the following mapping is a homomorphism. If so, determine its kernel.$f(x)=x^3$, for all $x$ belonging to $G$.