Justify all answers CONCISELY! 1) a) Number of people on the wrong shore is an admissible heuristic is correct - value is 0 for goal, and we always need to move at least as many people as there are on the wrong shore (note the PATH COST is NUMBER OF PEOPLE moved, not number of trips!) 2) Construct a taxonomic hierarchy for animals, which contains mammals, which contain primates, which in turn contains apes and humans (which are disjoint). Whales are also mammals, which are not primates, and no primate is a whale. All whales can swim. Jesus is a human who can walk on water, but cannot swim. Anything that can swim has a fin. Juju is a whale. a) animals - mammals - primates - humans (-) Jesus \ - apes whales (-) Juju axioms: (forall x) x in mammals => x in animals ; etc. disjoint({whales, primates}, mammals) (forall x) x in whales => swims(x) (forall x) swims(x) => (exists y) fin(y) and part_of(y, x) fin(x) - true if object is a fin part_of(x, y) - true if object x is a part of object y facts: Jesus in humans. can_walk_on_water(Jesus) ; predicate signifying that object can walk on water ~swims(Jesus) ; swims - predicate signifying object can swim Juju in whales b) (outlines only - full proof as in answer to exercises) 1) Jesus has no fin cannot be proved or disproved 2) Jesus is a whale disprove via inheritence and disjointness of whales and primates 3) Some animals can swim proved via example of Juju the whale,, thus a mammal, and thus an animal 4) Some primates cannot swim proved via example of Jesus who's a human, and thus a primate 5) If some primate can walk on water, then there are no primates false - proved by counterexample (Jesus) 3) a) Idea is similar to MINIMAX. In general, for an n-person game (value, best_value are lists of n elements): best(position, #_of_players, player, depth) { if(terminal(position)) return(value(position)); best_value[player] = -infinity; best_move = error; foreach(move in legal_moves(position, player)) { new_position = apply_move(position, move); new_value = best(new_position, #_of_players, (player+1) mod #_of_players, depth + 1); if(new_value[player] >= best_value[player]) { best_value = new_value; best_move = move; } } if(depth == 0) do_move(best_move); else return(best_value); } For b and c, let us name the moves: A's moves are a1 or a2, B's are b1 or b2, and C's c1 or c2. b) If two players, say B and C, could make deals, this could lead to a a different choice of moves and possibly a worse score for A. In addition, A's algorithm would depend on HOW B and C make their deals. For example, in the following, B can agree with C NOT to make move b1 if C agrees NOT to make move c1. In this case BOTH B AND C benefit. This will NOT work without a prior agreement - if each tries direct maximization of individual score, the best they can hope for is 2 each. 0 - a1 - b1 - c1 (5 2 7) \ \ - c2 (5 7 2) \ b2 - c1 (5 0 7) \ - c2 (0 5 5) a2 - b1 - c1 (2 3 3) \ - c2 (2 3 4) b2 - c1 (2 0 0) - c2 (2 0 0) As a result of this, A must choose action a2, rather than a1, which would have been optimal without agreements!