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?
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.
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.
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.
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.
