601.664 Artificial Intelligence

Homework 3: Game Playing and Logic

Game Playing

Question 1. Open the following google colaboratory notebook. Follow all the steps specified in it. Include the link to your solved notebook in your submission.
Optional: implement your own chess-playing agent and we will run a small competition between agents of other students (you can work in teams).

Question 2. Why do we assume that we play against an optimal opponent in the minimax algorithm. What happens otherwise?

Question 3. What kind of node exploration is the minimax algorithm using? Depth-first or breadth-first?

Question 4. What is the time complexity of the naive minimax algorithm? Prove it.

Question 5. Explain why minimax algorithm with α − β pruning is more efficient than naive minimax. What is the complexity and why it depends on the ordering of the elements?

Question 6. Why did we introduce EVAL function instead of UTILITY for some games? Explain what is a good EVAL function for chess and how it affects the minimax algorithm.

Question 7. What is a Horizon effect and Quiescence?

Question 8. Under what kind of transformation the behaviour of minimax algorithm is preserved in case of a game with no chance nodes? In case of a game with chance nodes?

Logic

Question 9. A and B are both true.

Question 10. If A is true, then B must be true as well.

Question 11. If a student studies for a test, they will do well on it. We can also tell that if a student did well on a test, then they must have studied for it.

Question 12. If a student is completely dry and it is raining outside, it is because they have an umbrella or a hoodie and it is not raining heavily.

Question 13. Simplify and translate the following propositional logic sentence into English: A∨(A∧B) ⇐⇒ ¬(A ∧ B ∧ C)

Question 14. Is the following sentence valid? A ∨ B

Question 15. Is the following sentence satisfiable? A =⇒ B

Question 16. Is the following sentence unsatisfiable? (A ∧ (B ∨ C)) ∧ ((A ∧ B) ∨ (A ∧ C))