NPTEL An Introduction to Artificial Intelligence Week 5 Assignment Answers
Q1. Which of the following is/are true about the minimax algorithm with alpha-beta pruning? Assume a 2-player game where the only outcomes are win, loss or draw. An algorithm is called complete when, if there is a way for the player to win, then the algorithm will find it. The notion of optimality is that it must find the sequence of the least number of moves which guarantees a win.
a. The algorithm is complete for the finite tree
b. The algorithm is optimal for the finite tree
c. Worst case space complexity of the algorithm is O(bm)
d. Worst case time complexity of the algorithm is O(b^m)
Answer: a. The algorithm is complete for the finite tree
b. The algorithm is optimal for the finite tree
c. Worst case space complexity of the algorithm is O(bm)
d. Worst case time complexity of the algorithm is O(b^m)
Q2. The famous AlphaGo program defeated one of the best Go players, Lee Sedol 4-1. What key algorithms did AlphaGo use?
a. Alpha beta pruning
b. Monte Carlo tree search
c. Deep neural networks
d. Breadth first Search
Answer: b. Monte Carlo tree search
c. Deep neural networks
I give you a minimax search tree with root node A which is a MAX node. Now, A has three children A1,A2 and A3. Also each Ai has three children Ai1, Ai2 and Ai3 (1 <= i <= 3). Now, suppose that the minimax tree computes the backed up values of the nodes to be 𝐴ij = 3|𝑖 − 2| + 𝑖3𝑗 where |.| represents the absolute value. Now, I wish to perform an alpha-beta pruning. Answer the following questions in order to achieve maximum possible pruning.
Q3. What is the ideal order for A1, A2 and A3 for maximum possible pruning ? (If you think A1 should come first followed by A2 and then A3, then write A1A2A3 without any spaces) Note: If two solutions are equally good then pick the lexicographically largest one.
Answer: A3A2A1
Q4. Assume the ideal ordering of the previous question. Let the number of children of A2 which were explored be e and the number of children which were pruned out be p. Then what is the value of e3 + p?
Answer: 3
Q5. How many nodes would be pruned out? Assume we explore the nodes in lexicographical order. Pruned out node means that the node was never explored.
Answer: 1
Q6. What is the final minimax value which is backed up to root node A?
Answer: 30
Q7. In what situations would minimax search not be the best algorithm in an adversarial game?
a. There is no opportunity to apply alpha beta pruning
b. The adversary is sub-optimal
c. The search tree depth is not finite
d. The action space is continuous
Answer: b. The adversary is sub-optimal
c. The search tree depth is not finite
Q8. Assume that someone gives me a hint that the value backed up at the root of a minimax tree is between 1 and 5. Can I use this information to my advantage?
a. No
b. Yes, set the value of α=1 and β=5
c. Yes, set the value of α=5 and β=1
Answer: b. Yes, set the value of α=1 and β=5
Q9. Consider a game where it is known that the value of a leaf can only be an integer between 1 and 5 (inclusive). In such a case, consider the following game tree:
Answer: 4.8
Q10. If you think carefully, alpha beta pruning is possible in the previous question. In the best case, what is the least number of min nodes that need to be fully evaluated?
Answer: 4
Disclaimer: These answers are provided only for the purpose to help students to take references. This website does not claim any surety of 100% correct answers. So, this website urges you to complete your assignment yourself.
Also Available:
Artificial Intelligence NPTEL Assignment Answers Week 4
