Assignment 3 Game Playing

Homework Assignment 3
601.464/664 Artificial Intelligence 

Game Playing
In the past weeks, we discussed intelligent agents and how they can use tree searching techniques to solve
abstracted problems. In this assignment, you will implement chess-playing agent and answer some theoretical
questions.
Question 1. Open the following google colaboratory notebook. Follow all the steps specified in it. Include
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
Translate the following English sentences into propositional 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.
1
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))
2