AI Midterm Review Questions

The following questions are provided as an aid to preparing for the mid term exam. The scope of the midterm exam will vary from year to year, so this list may include some questions on material that we did not cover. If you are in doubt about whether or not you should know something the safest and best strategy to use is to go ahead and learn it. Just think of how much you will end up knowing. You can also check with the TA or instructor.

Prolog

Buggy Prolog Code

One of your teammates on a group project has written the following code to compute the absolute value of an integer. You detect a bug in her code. Demonstrate the bug by finding a an example which does not work. 
  
  % abs(+N,?M) is true iff the absolute value of N is M.
  abs(N,M) :- number(N), N < 0, !, M is -N.
  abs(N,N) :- number(N).

Buggy code

Your friend complains that his Prolog project is going into an infinite loop somewhere. You look at his code and zero in on this predicate. 
  % sumTo(+N,?Sum) is true if the sum of the integers from 1 to N
  % (inclusive) is Sum.
  sumTo(1,1).
  sumTo(N,Sum) :- 
    integer(N),
    N2 is N-1, 
    sumTo(N2,M),
    Sum is N+M.
(a) Describe the bug, (b) give an example of a call to this predicate which will not terminate, and (c) give two ways to fix the bug, one using cut and one not suing cut.

Buggy code

You are asked to implement the following database: 
  Bert only likes cookies.
  Elmo likes cake.
  Elmo likes cookies.
  Ernie likes pudding.
  Ernie likes candy.
  Cookie Monster eats everything.
Your friend proposed to encode this as follows: 
  likes(elmo,cake).
  likes(elmo,cookies).
  likes(bert,cookies) :- !.
  likes(ernie,pudding).
  likes(ernie,candy).
  likes(cookiemonster,X).
(a) Show a Prolog query that corresponds to the question "Who eats cookies". (b) What is returned by this query? (c) Is this the right answer? (d) If not, how would you change the code to work properly?

between/3

Write the prolog predicate between(+From,+To,?X) which is true if X is an integer between the integers From and To. For example: 
  ?- between(1,10,3).
  yes
  ?- between(1,3,X),
  X=1;
  X=2;
  X=3;
  no

sumInterval

One of the ways that Prolog is not a pure logic programming language is that mathematical computations are done as calls to subroutines rather than done at "the logic level". This means that some programs can not be run "backwards". For example, consider the sumInterval/3 predicate which 
  % sumInterval(From,To,Sum) true iff the sum of the integers from From
  % to To is Sum (inclusive)
  sumInterval(N,N,N).
  sumInterval(N,M,Sum) :- 
   N < M, 
   N2 is N+1,
   sumInterval(N2,M,Partialsum),
   Sum is N+Partialsum.
This works for calls like sum(1,100,N) and sum(5,7,18) but not for sum(1,X,6). Write a version of sumInterval that works when called with at least two (any two) of its arguments are instantiated.

Prolog notation conventions

If I ask you to write a predicate foo/3, what does that tell you about the predicate? If I dewxcribe a predicate using the convention bar(+X,?Z,-Y) what can you tell me about the predicate?

Mysterious predicate I

Describe in a few sentences what the following mystery predicate does. 
mystery([]). 
mystery([H|T]) :- mystery(T).

Mysterious predicate II

What does the following mystery predicate do? Why? 

  mystery([],0).
  mystery([_|T],N) :- mystery(T,M), N is M+1.

Mysterious predicate III

Describe in a few sentences what the following mystery predicate does. 
  foo([],1).
  foo([H|T],N) :- foo(T,M), N is M*H.

Simulating Prolog

Given the following Prolog facts and rules 
  parent ( a, b ).
  parent ( a, c ).
  parent ( b, d ).
  parent ( b, e ).
  parent ( c, f ).
  parent ( f, g ).
  parent ( f, h ).
  parent ( f, i ).
  ancestor ( X, Y ) :- parent ( X, Y ).
  ancestor ( X, Y ) :- parent ( Z, Y ), ancestor ( X, Z ).
show the output which will be printed in response to the query assuming the user prompts for all possible responses. 
  ?- ancestor ( U, h ).

Assume the user prompts for all possible responses.

Unique/2

Write a Prolog program that counts the number of unique atoms in a list of atoms. The entry point to the program must be the clause unique/2. For example: 
        ?-unique([cat,hat,cat,rat,mat,cat,hat],N).
        yes
        N = 4

Reverse/2

Write the Prolog predicate reverse(?List1,?List2) which is true when List1 is a list and when it's top level elements are reversed it is equal to List2.

Permutation/2

Write a Prolog predicate permutation(?list1,?List2) which is true when List1 is a list and it has the same top-level elements as List2 but in a different permutation.

Delete/3

write a Prolog predicate delete1(?Term,?List1,?List2) which is true if List one is equal to List2 with the first occurrence of Term removed. Write deleteall(?Term,?List1,?List2) which is true if List one is equal to List2 with the fall occurrences of Term removed.

Unification in Prolog

Unification is an essential operation in Prolog. For each of the following, tell (1) whether the two expressions can be unified, and (2) if so, what is the value of each variable after unification.
  • Able = Baker
  • mother(Bill) = mother(Sally)
  • loves(john, mary) = loves(Mary, john)
  • husband(John, Mary) = wife(Mary, John)
  • spouse(John, Mary) = spouse(father(Bill), mother(Bill))
  • father(mother(bill)) = father(Jane)
  • child(Mary, mother(Bill)) = child(child(Bill), Mary)
  • child(child(Sally), mother(Bill)) = child(child(John), Sally)
  • Mary = mother(child(Mary))
  • loves(john, _) = loves(_, Mary)

More Prolog

Convert the following C program to Prolog. Your prolog program should have the same I/O behavior as the C program, but need not follow the same algorithm in implementing it.

  main(v,c)char**c;{for(v[c++]="Hello, world!\n)";
  (!!c)[*c]&&(v--||--c&&execlp(*c,*c,c[!!c]+!!c,!c));
  **c=!c)write(!!*c,*c,!!**c);}

Kinship relations

Assume you have a Prolog database consisting of a large number of clauses of the following two predicates:

  son(Son, Mother, Father).            /* Example: son(bill, Mary, john). */
  daughter(Daughter, Mother, Father).  /* Example: daughter(sally, Mary, john). */
Write the following predicates. Each predicate should require not more than three clauses.
female(X)
mate(X, Y) /* X and Y are parents of some child */
childless(X) /* X has no children */
different(X, Y) /* X and Y are not the same */
siblings(X, Y) /* X and Y are different people with at least one parent in common */

Search

Heuristic functions

Invent a heuristic function for the 8-puzzle that sometimes over-estimates and illustrate how it can lead to a suboptimal solution.

Search algorithms

What is the time complexity of the following algorithms:
  1. Breadth-first search.
  2. Depth-first search.
  3. Uniform-cost search.
  4. A* search.

Search algorithms

  1. Describe uniform-cost search.
  2. Describe A* search.
  3. What is the relation between the two?

Search Strategies

  • Compare and contrast Breadth-first and Depth-first search strategies.
  • Compare and contrast Breadth-first and Branch-and-Bound.
  • Compare and contrast Best-first and Branch-and-Bound.
  • Compare and contrast A*, Best-first and Branch-and-Bound.

Games

Tic Tac Toe

Explain the follow traditional AI koan:

In the days when Sussman was a novice, Minsky once came to him as he sat hacking at the PDP-6.

"What are you doing?", asked Minsky.

"I am training a randomly wired neural net to play Tic-Tac-Toe", Sussman replied.

"Why is the net wired randomly?", asked Minsky.

"I do not want it to have any preconceptions of how to play", Sussman said.

Minsky then shut his eyes.

"Why do you close your eyes?", Sussman asked his teacher.

"So that the room will be empty."

At that moment, Sussman was enlightened.

Nim (again)

Consider a version of the simple game Nim in which play begins with 23 tokens. Players alternate and each player removes 1, 2, or 3 tokens. The goal is to force the other player to take the last one. Assume an evaluation function as follows, where N is the number of objects remaining:
  • N mod 4 = 0 is a position worth 4 points.
  • N mod 4 = 1 is a position worth 3 points.
  • N mod 4 = 2 is a position worth 2 points.
  • N mod 4 = 3 is a position worth 1 point.
For example, a position with 20 tokens is worth 4 points because 20 mod 4 is 0. So, removing three tokens would be a good first move, under this evaluation function.
  1. Assume you go first. On the next page draw the search tree for the first 3 moves of the game (e.g., your initial move, your opponents response, and your response to that). Use the evaluation function and the minimal algorithm to fill in the evaluation value of each node in the tree.
  2. After you have filled in the evaluation values, circle any nodes (both leaf nodes and non-leaf nodes) that would not need to be evaluated if Alpha-Beta pruning was used.

minimax vs alphabet

If a game playing program is constrained to search to a certain number of ply before moving, then alpha-beta is clearly faster than mini-max search. But does it produce the same quality of play? Why or why not?

 

designing a static evaluation function

alpha-beta pruning

Describe alpha-beta pruning in game search. How does it differ from the minimax algorithm without pruning?

Peg jumping

This solitaire game consists of a triangular board 
        x
       x x
      x o x
     x x x x
    x x x x x
where x denotes a peg and o an empty hole. A peg may jump over an adjacent peg if the hole behind it is empty. The peg that was jumped over is then removed. For example, in the initial configuration above there are two possible symmetric moves. The game is won if there is only one peg left on the board and lost if there is more than one but no further possible moves. A solution is strong if the final peg ends up in the initial hole.
  1. Write a Prolog program without using assert or retract to solve this puzzle and display a sequence of winning moves.
  2. Write a second version that uses assert and retract and compare running times.
  3. Determine if there is a strong solution.
  4. Generalize one of your programs so that the initially empty hole may be anywhere on the board. Which initial configurations have a solution? Which initial configurations have a strong solution?
  5. Modify your program so you can calculate (or at least estimate) the solution density for this puzzle: What is the probability that a sequence of random legal moves leads to a solution?

Towers of Hanoi

Consider a version of the familiar Towers of Hanoi puzzle with three towers and three disks. Initially the three disks (with sizes 1, 2 and 3) are all on tower one and the goal is to move them to tower three. The constraint is that a disk can never be on top of a smaller one one and that only one disk at a time can be moved.
  1. Define the state space, including the states and arcs. You don't need to list every state and arc, just define them. You may define the arcs in terms of actions.
  2. Draw the complete search tree for this problem to a depth of three.
  3. What is the maximum branching factor of the search tree?
  4. What is the minimum branching factor of the search tree?
  5. What is the length of the longest possible branch in the search tree?
  6. What is the length of the shortest possible branch?

Heuristic Search

Invent a heuristic function for the eight puzzle that sometimes overestimates and illustrate how it can lead to a suboptimal solution.

Search Problem

Suppose that you need to find a path between S and G in the following graph. The number attached to each edge in the graph represents the COST of traversing the edge.

 

 

Assume also that the ESTIMATED distances to the goal are given by the following table:

Node: S B C D E F G
Estimated Distance to G: 6 1 3 2 5 4 0

For EACH of the following search methods list the nodes in the order in which they are EXPANDED by the search method while looking for a solution. As an illustration, the solution for Depth 1st search is provided below.

  1. Depth 1st Search
  2. (5 points) Breadth 1st Search
  3. (5 points) Depth-limited Search (depth-limit = 2)
  4. (5 points) Iterative Deepening Search

Bi-directional Search

Bi-directional search can be more effective than a unidirectional search from the start state to a goal state. However, it can not be used for all problems. Give two characteristics of a problem that must hold in order for bi-directional search to be applicable.

Search terms

Define the following terms as they are used to describe search algorithms.

  1. Admissibility
  2. Optimality
  3. Completeness

Heuristic search

Suppose we have two heuristic functions, h1 and h2, both of which are known to be admissible (e.g. underestimates of the optimal heuristic function h*). (a) What constraint has to hold for h1 to be considered as a stronger heuristic than h2? (b) which of the following heuristic is also admissible. (c) which are guarantee to be no weaker than either h1 or h2?

   h3(n) = (h1(n) + h2(n)) / 2 
   h4(n) = min(h1(n),h2(n))
   h5(n) = max(h1(n), h2(n))
   h6(n) = w1*h1(n) + w2*h2(n) where 0 =< w1,w2 =<1 and w1+w2=1.0