Description

Homework 3 – Conceptual
1. Adversarial Search
Select all that are true about adversarial search. No need to justify.
[ ] In zero-sum games with two players, one agent maximizes one single value, while the other minimizes it.
[ ] Both Alpha and Beta are sent down the tree
[ ] Min updates Alpha and Max updates Beta
[ ] Alpha is the current lower bound on MAX’s outcome and Beta is the current upper bound on MIN’s outcome
2. Adversarial search
Consider the following game tree.

(a) What is the value of Max at the root?
(b) Using alpha beta pruning, what branches are cut? Justify your answer. Give all branches even if you gave their parents.
3. Knowledge-based agents
Consider the two sentences:
“If it is Heads then I win”
“If it is Tails then you lose”
1. Use the atomic propositions HEADS, TAILS, IWIN, YOULOSE to write the sentence in propositional logic (PL) as implications. Add these two propositions to your knowledge base KB.
2. Add to KB the general knowledge that:
1
(a) The outcome of a coin toss is either HEADS or TAILS (“or” here is the disjunction ∨, not the exclusive or).
(b) if YOULOSE then IWIN, (c) if IWIN then YOULOSE.
This general knowledge should be expressed in PL before you add it to KB. Your KB should now have 5 PL sentences.
3. Replace every PL sentence in KB by its equivalent disjunctive clause.
4. Using resolution, prove the goal sentence IWIN.
4. KNN
Consider the following grid that represents examples A through Y. Let the coordinates x1 and x2 represent the features of the examples. Suppose A…L are positive examples and N…Y are negative examples.

(a) What are the 5 nearest neighbors of example M? Use the Euclidean distance and the alphabetical ordering for breaking any tie.
(b) Using these neighbors, what is the class of M.
(c) In addition to x1 and x2 coordinates, we include the “mass” in grams of each example as an additional feature. The standard deviation of mass is stdevm = 100. Explain the consequences of using the mass feature along with the x1 and x2 coordinates on the Euclidean distance between examples. How would you address any problem that might arise.
Page 2