General Instructions: Put your answers to the following problems into a PDF document and submit as an attachment under Content à Homework 4 for the course CptS 440 Pullman (all sections of CptS 440 and 540 are merged under the CptS 440 Pullman section) on the Blackboard Learn system by the above deadline. Note that you may submit multiple times, but we will only grade the most recent entry submitted before the above deadline.
1. Consider the following game tree. Upward-pointing triangles are MAX nodes, downward- pointing triangles are MIN nodes, and squares are terminal nodes.
a. Perform Minimax-Decision search on the above tree. Put the final value next to each node in the tree. Finally, indicate which action MAX should take: a1, a2 or a3.
MAX should take a2.
b. Perform Alpha-Beta-Search on the above tree (don’t reuse your tree from part (a)). Put an “X” over all nodes (internal and terminal, and all nodes in a subtree) that are pruned, i.e., not evaluated. Put the final value next to all non-pruned nodes. Finally, indicate which action MAX should take: a1, a2 or a3.
MAX should take a2.
c. 540 students only. Consider reordering the children of the MIN nodes in the above tree in
order to maximize the number of nodes pruned by the Alpha-Beta-Search. You cannot reorder the children of any other nodes above or below the MIN nodes. Show this tree and perform Alpha-Beta-Search on this tree in the same way as described in part (b).
2. Consider the following logic problem:
If you like checkers, then you like chess. If like computers, then you like coding.
If you like chess and you like coding, then you will learn AI. If you learn AI, you will be rich and famous.
You like checkers.
You like computers.
Prove that you will be rich.
a. We will solve this problem using propositional logic. First, show one propositional logic sentence for each of the first six sentences in the above problem. You may only draw from the following atomic sentences.
• Like(Checkers)
• Like(Chess)
• Like(Computers)
• Like(Coding)
• Learn(AI)
• Rich
• Famous
b. Convert each of the six sentences from part (a) into Conjunctive Normal Form (CNF). You may just show the final result for each sentence; no need to show the intermediate steps. Number your clauses.
c. Perform a resolution proof by refutation to prove you will be Rich, using the knowledge base from part (b). For each resolution step, show the numbers of the clauses used, the resulting clause, and then number the resulting clause.
d. 540 students only: What one literal (other than ¬Famous) could you add to the knowledge base in part (b) in order to prove ¬Famous using resolution proof by refutation?
