problem 1: Show the search tree generated by Hill-Climbing search for each of the two heuristics (a) and (b) applied to the following 8-puzzle problem. Search tree must show all states generated all along with their heuristic value. If two neighbor states have the same value, then consider them in order of the actions (movement of blank): up, down, left, right. Also point out the final state returned by the Hill-Climbing function.

a) Value = 1 / (number of tiles out of place, including the blank tile). For illustration, the value of the initial state = 1/4.
b) Value = 1 / (number of tiles out of place, not including the blank tile). For illustration, the value of the initial state = 1/3.

problem 2: Perform alpha-beta pruning on the following tree. Put an “X” over each node that is pruned. Put the final value next to all other nodes. Point out which action MAX should take: to B, to C or to D.

problem 3: Suppose a logic-based agent in the wumpus world has found that locations (1,1) and (2,1) do not contain a stench, but that locations (3,1) and (2,2) do contain a stench. Can the agent deduce the location of the wumpus? Let’s use propositional logic to find out.

a) Using propositional symbols Sx,y  for stench in  (x,y) and Wx,y  for wumpus in (x,y), where x and y are integers greater than zero, prepare down a knowledge base containing relevant propositional statements about the wumpus world and containing what the agent knows about this wumpus world. Number each statement.

b) Show a propositional proof of the location of the wumpus. For each step of your proof, clearly indicate the newly inferred statement, the previous statements used to infer this new statement, and the inference rule used.
 
problem 4: Consider the following statements about the types of fruit people like.
 
If people like apples, then they do not like oranges. If people do not like apples, then they like oranges and grapes. If people do not like oranges or they like grapes, then they like pears. If people like pears, then they like bananas.
 
a) Express the above statements in propositional logic. Clearly define the meaning of your propositional symbols.

b) Convert your statements from (a) into conjunctive normal form (CNF). Number the clauses in your knowledge base (KB) starting with number 1.

c) Using proof by refutation and resolution, try to prove that people like bananas using your KB from (b). For each new clause  in your proof, clearly indicate the previous clauses  used. If “people like bananas” cannot be proven, then clearly describe or
demonstrate why.

d) Using proof by refutation and resolution, try to prove that people like apples using your KB from (b). For each new clause  in your proof, clearly indicate the previous clauses  used. If “people like apples” cannot be proven, then clearly describe or demonstrate why.