These are An Introduction to Artificial Intelligence Answers Week 5
Q1. Select the CORRECT statements – With perfect ordering, alpha-beta pruning reduces the time complexity from O(b^m) to O(bm/2) With perfect ordering, alpha-beta pruning increases the depth that can be searched in same time T from d to d^2. Without alpha-beta pruning, the time complexity of search for depth m follows T(m) = b.T(m-1) + c With perfect ordering in alpha-beta pruning, the time complexity of search for depth m follows T(m) = T(m-1) + (b-2)T(m-2) + c
Answer: A, C
Q2. Consider the following game tree. A is the maximizer node and D is the minimizer node. Chance node B chooses left action with probability p = 0.4 and right action with p = 0.6. Chance node C chooses left action with p = 0.7 and right action with p = 0.3. What will be the value at node A if we use expectiminimax to make decisions?
These are An Introduction to Artificial Intelligence Answers Week 5
Q3. Consider the same game tree. Now we have the prior information that all internal nodes have utility values in the range 1-10. Is it possible to perform any pruning? Answer the number of nodes of type D that can be pruned. (Answer 0 if you think no pruning can be done)
Answer: 1
Q4. Consider the given adversarial search tree. Assume that the search always chooses children from left to right. The search tree uses alpha-beta pruning. Which of the following nodes are pruned during the search? J K L M N O
These are An Introduction to Artificial Intelligence Answers Week 5
Q5. What is the final value at node A?(from the above figure)
Answer: 23
Q6. Define score of white as s(p, “white”) = 1 * n(white pawn) + 2 * n(white knight) + 3 * n(white bishop) + 4 * n(white rook) + 5 * n(white queen), where n(x) is number of pieces of type x on the board. Similarly, define the score of black. The utility of white f(p) is defined as score(p, “white”) – score(p, “black”). Calculate f(p) for white.
These are An Introduction to Artificial Intelligence Answers Week 5
Q7. Which of the following is/are true regarding the basic mini-max adversarial search algorithm? It is complete if the search tree is finite It is optimal for all kinds of adversaries The worst-case time complexity and space complexity is similar to that of Depth First Search By itself, it cannot play games like Chess and Go due to huge search depths.
Q8. Which of the following is/are false regarding the alpha-beta pruning for the mini-max search algorithm? It can potentially lead to suboptimal solutions compared to mini-max search without any pruning It is guaranteed to improve the running time in-comparison to the mini-max search without any pruning The order in which nodes are visited affects the amount of pruning If the successors of a node are chosen randomly, the time complexity (on average) is O(b3m/4)
These are An Introduction to Artificial Intelligence Answers Week 5
Q9. Which of the following techniques were used by Deep Blue for beating Garry Kasparov in the game of chess ? Opening and Endgame stage databases A version of mini-max search algorithm Neural Networks for computing Heuristic Functions Monte Carlo Tree Search algorithm
Answer: A, B
Q10. Which of the following is/are true for heuristic functions in the context of adversarial search ? They can be learnt from data/experience for eg. by playing games with another agent They help deal with the problem of extremely large search depths in practice They help reduce the worst-case time complexity of minimax search without comprising optimality against optimal adversaries They can be hand-engineered by humans/experts
Answer: A, B, D
Q11. What will be the value of the node labelled ‘a’ after the run of the min-max search algorithm on the following search tree. Here upwards facing triangles are max nodes, downward facing triangles are min nodes and circles denote game-ends.
These are An Introduction to Artificial Intelligence Answers Week 5
Q1. Which of the following statements are true in the context of alpha-beta pruning? a. The effectiveness of alpha-beta pruning depends on the order of moves encountered during the search b. A node is pruned if beta >= alpha at one of it’s parents c. A node is pruned if alpha >= beta at one of it’s parents d. Alpha-beta pruning can result in a different root value from full minimax search
These are An Introduction to Artificial Intelligence Answers Week 5
Q2. The next three questions will involve the following search tree. The value of the leaf nodes are annotated below the node in the diagram.
What is the backed-up value at the root node after minimax search?
Answer: 20
These are An Introduction to Artificial Intelligence Answers Week 5
Q3. Assume that the successors are expanded from left to right. What is the number of nodes (including leaf nodes) pruned by alpha-beta pruning?
Answer: 12
These are An Introduction to Artificial Intelligence Answers Week 5
Q4. Assume that the successors are expanded from right to left. What is the number of nodes (including leaf nodes) pruned by alpha-beta pruning?
Answer: 3
These are An Introduction to Artificial Intelligence Answers Week 5
Q5. Which of the following is true regarding fixed depth search and the horizon effect? a. Continuing the search at non-quiescent positions can mitigate the horizon effect b. Stopping the search at non-quiescent positions can mitigate the horizon effect c. It can lead to choosing moves with short-term benefits, but catastrophe in the long term d. It can result in ignoring moves that do not have immediate benefits, but can lead to victory in the long term
Answer: a, c, d
These are An Introduction to Artificial Intelligence Answers Week 5
Q6. Which of the following games are deterministic? a. Backgammon b. Go c. Bridge d. Othello
Answer: b, d
These are An Introduction to Artificial Intelligence Answers Week 5
For Questions 7 to 10 –
Aman and Bharat are two friends. Aman is planning an ice-cream treat. They are not able to decide the location, brand and the flavour to be purchased. Therefore, they come up with the following idea: First, Aman gets to choose the location between Hauz Khas and Connaught Place, then Bharat chooses the brand between Giani’s and Nirula’s and then the flavour is chosen uniformly randomly between chocolate and vanilla. The table below lists the cost of each ice-cream in rupees for a particular location, brand and flavour.
Additionally, Aman wants to get by with spending as less money as possible, while Bharat wants to get the most expensive treat he can get out of Aman, both in expectation. Let’s model this as a minimax tree with chance nodes and run expecti-minimax search.
These are An Introduction to Artificial Intelligence Answers Week 5
Q7. If both Aman and Bharat choose optimally and selfishly, which of the following statements are correct? a. They go to the location Connaught Place. b. They buy from the brand Nirula’s. c. They go to the location Hauz Khas. d. They buy from the brand Giani’s
Answer: a, d
These are An Introduction to Artificial Intelligence Answers Week 5
Q8. If both the players play optimally, determine the expected expenditure in rupees.
Answer: 40
These are An Introduction to Artificial Intelligence Answers Week 5
Q9. Which of the following statements are true for the expecti-minimax tree and alpha beta pruning for the problem? a. There are 4 chance nodes in the expecti-minimax tree. b. Some nodes get pruned even if alpha beta pruning is employed with the worst possible node ordering c. Some nodes get pruned if alpha beta pruning is employed with the best possible node ordering. d. The choice of location and brand depends upon the order of nodes explored.
Answer: a, c
These are An Introduction to Artificial Intelligence Answers Week 5
Q10. Suppose the order of decisions is changed as follows: First Bharat chooses the brand between Giani’s and Nirula’s, then Aman gets to choose the location between Hauz Khas and Connaught Place, and then the flavour is chosen uniformly randomly between chocolate and vanilla. If both decide optimally, which of the following statement is correct about the new expected expenditure(E’) compared to the expected expenditure in the original case(E)? a. E’ = E b. E’ > E c. E’ < E d. Cannot be determined
Answer: c. E’ < E
These are An Introduction to Artificial Intelligence Answers Week 5
More Solutions of An Introduction to Artificial Intelligence: Click Here
