1) For each of the following domains, which type of agent is appropriate (table lookup, reflex, goal based, or utility based): a) An agent that solves the cannibals and missionaries problem. b) An agent that plays chess. c) An agent that can pass the Turing test. d) An autonomous robot for exploring Mars EXPLAIN each choice in about 2 sentences. 2) We are given a search problem that has a path cost equal to the number of operators applied on the path to reach the goal (i.e. the path length, as in, e.g. the 8 puzzle). The branching factor is bounded by b (i.e. is never more than b). We are given an admissible heuristic h, that is never wrong by more than 2. There is exactly ONE optimal solution. How many expansion steps are needed in A* to find an optimal solution of length d, in the worst case, if there is NO other solution of length less than d+3. You need to PROVE your answer! 3) Invent a heuristic function for the travelling sales-person problem (TSP) and show a case where it can lead to a sub-optimal solution where the path cost is the total tour length (or argue that such a case does NOT exist DESPITE the over-estimate)! (Recall that TSP is the problem of finding a minimal-weight complete (i.e. visit every node once) tour in a weighted graph). 4) Give an example of a 3-person game tree where the best choice of move made by player A will be DIFFERENT for all of the following assumptions: a) Paranoid assumption: all that players B and C want is to make it bad for player A. b) Each player out to help itself, with no communication. c) Same as b, but player B and C can make deals. d) Same as c, but A can also make deals. 5) Which of the following are valid, satisfiable, or neither: a) Good => Good b) Good => Bad c) (Bad => ~Good) => (Good => ~Bad) d) (Good => ~Good) e) Big v Dumb v (Big => Dumb) f) Good v Bad v Ugly g) (P <=> Q) <=> ((~P v Q) ^ (P v ~Q))Deadline: December 24, 2001.