Homework 2 – Search + CSP’s

EECS 592: Introduction to Artificial Intelligence
Homework 2 – Search + CSP’s

There is no programming for this assignment. Fill in your written answers into this
document and submit a .pdf to Canvas ( https://umich.instructure.com ). In the page for
this course there is a tab for Assignments, under Homework 2 there will be a place to upload
your answer file. Please use <your-umich-unique-name.pdf as the file name.
1. Comparing Search Strategies (6 points)
A* search is guaranteed to find an optimal solution where it applies, but hill climbing is not.
Give three reasons why in some situations you might want to use hill climbing rather than A*
1.
2.
3.
2. Algorithmic Choice (5 points)
For the following problems, pick the most appropriate search algorithm family. Justify your
answer.
Options:
Uninformed Search
Informed Search
Local Search
Adversarial Search
Constraint Satisfaction
A. Choosing a best move in Connect 4, where 2 players take turns playing pieces until
someone gets 4 in a row. https://en.wikipedia.org/wiki/Connect_Four
EECS 592, Fall 2017 Homework 2 Page 1/9
B. Given a large group of people, divide them into groups of 3 where no one knows
anyone else in their group, but everyone in the group shares a common interest.
C. Finding the best layout for the assembly lines in a factory, where you have an
evaluation function that includes the cost, manufacturing time, and space required for
a given layout.
D. Determining the shortest route from San Francisco to New York by car.
E. Planning where to plant crops in a farmer's fields to try and optimize the extent that
crops with similar needs + harvest times are near each other.
3. Local Search (3 points)
Suppose you had the following search space that has many small local minima but has a
single overall minimum.
You need to choose a local search algorithm to find the state at the global minimum. Which
will work better, Hill Climbing with Random Restart, or Simulated Annealing? Justify your
response.
EECS 592, Fall 2017 Homework 2 Page 2/9
4. Genetic Algorithms (10 points)
Consider the following maze:
Imagine using a genetic algorithm to solve this maze. The 'S' marks the starting tile, and the
'G' marks the goal tile. Each state is a series of 9 moves that can be north, south, east, or
west (NSEW). If a move tries to go into a wall the unit stays where it is.
For example, the state [ N, W, W, N, N, N, S, W, N ] ends at tile A. The fitness function is the
Manhattan distance from the end tile to the Goal. So the value for the above state that ends
in tile A is 4.
At one step, the population is the following 4 states:
[ N, E, S, W, N, S, E, W, S ]
[ W, N, N, N, S, N, E, E, S ]
[ E, N, S, N, E, N, N, N, S ]
[ W, W, E, W, N, N, E, N, E ]
A) Compute the fitness function for each of these states.
B) Circle the two fittest states (note that you are minimizing the fitness function).
C) Assuming that these two fittest states will produce descendants via crossover, and that a
single random mutation is possible, which of the following are possible descendants? Circle
all that are possible.
[ N, W, E, N, E, N, N, E, S ]
[ W, W, E, N, E, N, N, E, S ]
[ W, N, S, S, E, S, E, N, S ]
[ W, W, S, N, N, N, S, N, S ]
EECS 592, Fall 2017 Homework 2 Page 3/9
[ E, W, E, W, N, N, N, N, S ]
[ E, N, S, S, E, N, E, N, E ]
5. Min-Max (8 points)
A. Above is a 2 player game tree with values at the leaf nodes. After performing regular
min-max on it, what are the computed values for each non-leaf node (A-J)?
A B C D E F G H I J
B. If min-max with alpha-beta pruning is run on the tree, which nodes will be pruned?
Assume that child nodes are examined from left to right. List the nodes that will be
pruned (never evaluated).
EECS 592, Fall 2017 Homework 2 Page 4/9
6. Min Max with Chance (4 points)
Imagine a simple game where you buy a lottery ticket. First, you declare the type of ticket (A
or B), then the game master gives you one of two possible tickets for that type. The ticket will
have a distribution over payout amounts. The tree is shown below:
A) Assuming the utility for money is simply U(m) = m, what is the expected utility for each
ticket?
U(TA1):
U(TA2):
U(TB1):
U(TB2):
B) Assume the game master (square) is trying to minimize your utility and you are trying to
maximize it. If both players are playing optimally, which ticket will you receive?
C) Now imagine your utility for money is U(m) = m2
. What is the expected utility for each
ticket?
U(TA1):
U(TA2):
U(TB1):
U(TB2):
D) Suppose the game master is trying to minimize your utility but mistakenly believes your
utility is U(m) = m (Your actual utility is U(m) = m2
) . If you know this and plan accordingly,
which ticket will you receive if you make the best choice?
EECS 592, Fall 2017 Homework 2 Page 5/9
7. Constraint Satisfaction (4 points)
The graph below is a constraint graph for a CSP that has only binary constraints. Initially no
variables have been assigned and no constraints have been enforced.
A) A value is assigned to A. The domains of which variables may change as a result of
running forward checking for A?
B) A value is assigned to A, then forward checking is run for A. Then a value is assigned to B.
The domains of which variables may change as a result of running forward checking for B?
C) A value is assigned to A. The domains of which variables might change as a result of
enforcing arc consistency?
D) A value is assigned to A, then arc consistency is enforced. Then a value is assigned to B.
The domains of which variables may change as a result of maintaining arc consistency after
assigning B?
EECS 592, Fall 2017 Homework 2 Page 6/9
EECS 592, Fall 2017 Homework 2 Page 7/9
8. KenKen Puzzle Constraint Satisfaction (10 points)
The puzzle called KenKen involves filling in numbers on a board to fit a certain set of
constraints. This figure shows the particular problem you will solve:
The constraints that must be satisfied are as follows:
a. Each square will have one of the numbers 1, 2, or 3.
b. Each pair of squares within the same row or column cannot have the same value
assigned to them.
c. The numbers in each “cage”, each area surrounded by heavy lines, must add up to the
number given in that cage.
Refer to the squares by row and column as shown in the figure: The upper-left square is (1,
1), the square below that is (2, 1), …
In the process of solving this problem, answer the following questions:
1. Describe a CSP for this puzzle by defining all the variables you will use and their
domains.
2. Draw a constraint graph of all the nodes (one for each variable) and all the edges (one for
each constraint) that represent constraints between pairs of nodes. Note that some
constraints come from the fact this is a KenKen problem, and some constraints come
from this specific problem. Include in every node their original domain.
EECS 592, Fall 2017 Homework 2 Page 8/9
3. Use node consistency to prune the values of the one node that has a unary constraint.
4. Now use all the X+ (summation) constraints to prune the values of the other nodes.
5. Use the remaining constraints from b. above to prune the values of the nodes, one at a
time until you reach a solution. Show each step and the final solution.
Score summary:
1. Compare search strategies ____/6
2. Algorithmic choice ____/5
3. Local search ____/3
4. Genetic algorithms ____/10
5. Min-max ____/8
6. Min-max with chance ____/4
7. Constraint satisfaction ____/4
8. KenKen puzzle ____/10
Total ____/50
EECS 592, Fall 2017 Homework 2 Page 9/9