CS510-Introduction to Artificial Intelligence

1. Short questions

a) Problem Solving: describe, in one sentence, the following terms, when applied to AI domains.

1. Fully observable:

2. Deterministic:

3. Stochastic:

b) Heuristics: what is a heuristic in the context of problem solving.

c) Heuristics: what is an admissible heuristic?

d) Adversarial search 1: Can we use A∗ for playing games like Chess or Othello? If you answered yes, would it work better than Minimax? If you answered no, why not?

2.Water Jugs

You have two jugs (A and B), measuring 3 gallons and 4 gallons respectively, and a water faucet. You can fill the jugs up or empty them out from one to another or onto the ground. You need to measure out exactly 2 gallons. When doing search, actions are expanded in the following order: 1) fill jug A form the faucet, 2) fill jug B from the faucet, 3) empty jug A, 4) empty jug B, 5) fill jug A from jug B, 6) fill jug B from jug A.

1.Find a solution starting from the state (0, 0) using breadth-first search, not repeating any state. Draw the resulting search tree (clue, the resulting tree has less than 10 nodes).

2. Find a solution starting from the state (0, 0) using depth-first search, not repeating any state. Draw the resulting search tree (clue, the resulting tree has less than 10 nodes).

3.Let the cost of every action be 1. If we represent a state as a pair (a, b), where a is the amount of water in jug A, and b is the amount of water in jug B, is the function h(a, b) = |a − b| an admissible heuristic? Justify your answer

3.Adversarial Search

Consider the following game tree, where it is the maximizer’s turn to play, and the game does not involve randomness. The values in the leaf nodes represent the values computed by the evaluation function (higher scores are better for the maximizer)

1.Write the values of the intermediate nodes inside their circles, and indicate the proper move of the maximizer by circling one of the root’s outgoing arcs

2.Is there any node in the tree above that would be pruned using α − β pruning? which ones?

3.If you are allowed to reorder the nodes in the tree above. Can you reorder them in a way that α − β will prune even more nodes? Show the best order you can find for the tree above.

4 First-Order Logic

Let us assume that:

• onTop(x1, x2) means that object x1 is on top of another object x2 (e.g. we could write onTop(Box1, Box2)).

• shape(x,s) means that object x is of shape s (e.g. shape(Box1, Cube))

• color(x,c) means that object x is of color c (e.g. color(Box1, Green))

• Cube and Pyramid are two types of shapes objects can have, and Red, Green are two colors objects can have.

1.Do the following pairs of terms in this language unify, and what are the corresponding variable substitutions (Assume that xi and yi are variables, and the rest are constants):

• onTop(x1, Box2) and onTop(Box1, y1)

• onTop(x1, P yramid) and onTop(y1, y1)

• onTop(x1, f(x2)) and onTop(f(y1), f(Box1))

• onTop(x1, f(x1)) and onTop(f(y1), f(Box1))

2.Using this vocabulary, write down (in FOL) the fact that all Pyramids are Green.

3.Using this vocabulary, write down (in FOL) the fact that every object on top of a Cube is a Pyramid.

5.Search, constraint satisfaction

A domino is made by sticking together two squares along an edge. An n-omino is made by sticking together n squares along edges, any way you please. Thus, there is only one possible domino shape, but there are two distinct 3-ominoes (3-in-a-row and L-shaped)

1.Suppose we have to construct an n-omino that is beautiful, for fixed n. Give a complete formulation of the search problem that corresponds to this task, assuming that a beauty detector is available.

2.Identify a suitable search algorithm for this task and explain your choice

3.Now consider the problem of tiling a given n-omino with dominoes, that is covering it exactly without overlapping any dominoes. Formulate this problem precisely as a constraint satisfaction problem.