Introduction to Artificial Inteligence

Example Quiz 1 - answers (currently being edited!)

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
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!