## Description

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.