CS 480 – WRITTEN ASSIGNMENT 2
There are five questions. Please submit your solutions through blackboard.
1. Hand trace the mini-max algorithm on the following game tree. What is the maximum utility that MAX
can achieve, assuming MIN plays optimally?
2. This is the same game tree of question 1. Hand trace the alpha-beta search. Show the updated bounds
on the nodes. Clearly mark which branches are pruned, if any.
3. Hand trace the alpha-beta search on the following game tree. Show the updated bounds on the nodes.
Clearly mark which branches are pruned, if any.
4. This is the same game tree of question 3. Assume we modify the alpha-beta search so that the initial
bounds at the root of the tree are NOT (−∞, +∞). Instead, assume the initial bounds at the root of the
tree is [−1, +1]. Hand trace the alpha-beta search. Show the updated bounds on the nodes. Clearly
mark which branches are pruned, if any.
5. We are given the following CSP problem.
The variables and domains are as follows.
A: {4, 5, 6, 7, 8}
B: {10, 20, 30, 40}
C: {2, 3, 4}
D: {28, 43, 56, 77, 94, 114}
The constraints are:
A + C is odd.
A + D is a square of an integer.
B + D < 60.
Solve this problem using the following heuristics and algorithms.
• Use backtracking search.
• For variable ordering, use MRV. If there are ties, use degree to break them. If there are still ties,
break them in alphabetical order.
• For value ordering, order values from smallest to largest.
• For inference, use forward checking.
Please show the search tree and the stack of the domains (see the lectures for examples). When the
search backtracks due to an empty domain, show it clearly on your search tree. Write down the final
solution, if there is any.
