UGC NET CSE | October 2020 | Part 2 | Question: 63

Question

Which of the following statements are true?

1. Minimax search is breadth-first; it processes all the nodes at a level before moving to a node in next level.
2. The effectiveness of the alpha-beta pruning is highly dependent on the order in which the states are examined
3. The alpha-beta search algorithms computes the same optimal moves as minimax algorithm
4. Optimal play in games of imperfect information does not require reasoning about the current and future belief states of each player

Choose the correct answer from the options given below:

• A. $(i)$ and $(iii)$ only
• B. $(i)$ and $(iv)$ only
• C. $(ii)$ and $(iii)$ only
• D. $(iii)$ and $(iv)$ only

Answer 1

a    Minimax  search is breadth-first; it processes all the nodes at a level before moving to a node in next level.

       False it is DFS

 

b   The effectiveness of the alpha-beta pruning is highly dependent on the order in which the states are examined

               True It depends on the order in which children are visited. If children of a node are visited in the

               worst   possible order, it may be that no pruning occurs. For max nodes, we want to visit the

               best child first so that time is not wasted in the rest of the children exploring worse scenarios.

               For min nodes, we want to visit the worst child first (from our perspective, not the opponent's.)

https://www.cs.cornell.edu/courses/cs312/2002sp/lectures/rec21.htm

c  The alpha-beta search algorithms computes the same optimal moves as minimax algorithm

       True   it prunes those nodes who dont have any effect on final result

 

d       Optimal play in games of imperfect information does not require reasoning about the current and future belief                  states of each player

           False it requires 

https://www.cs.umd.edu/~nau/papers/parker2006role.pdf

HENCE OPTION C)(B) AND (C) ONLY IS RIGHT ANS