## AI: Solution Set 2

### Problem 1

The game tree, as pruned by alpha-beta, is shown below. The number inside
each circle is the state; the value above or to the left of the circle
is the evaluation function. The best starting move for X is B; the
value of the game for X is 86.

### Problem 2

A.
1. ~p V ~q V r.
2. p V q V r.
3. ~q V w
4. ~r V ~w
5. ~p V w V r.
6. p V x
7. q V x.

B.
Step 1. x is a pure literal, so set x=TRUE. Propagating eliminates clauses
6 and 7.

State S1:

Clauses:
1. ~p V ~q V r.
2. p V q V r.
3. ~q V w
4. ~r V ~w
5. ~p V w V r.
Valuation: x=TRUE.

There are no pure literals and no singleton clauses, so try p=TRUE.
Propagation removes ~p from 1 and 5 and deletes clause 2.
State S1.1:

Clauses:
1. ~q V r.
3. ~q V w
4. ~r V ~w
5. w V r.
Valuation: x=TRUE, p=TRUE.

~q is a pure literal, so set q=FALSE. Delete 1 and 3.
State S1.2:

Clauses:
4. ~r V ~w
5. w V r.
Valuation: x=TRUE, p=TRUE, q=FALSE.

No pure literals, no singleton clauses. Try setting r=TRUE. Propagation
deletes ~r from 4 and eliminates 5.
State S1.2.1:

Clauses:
4. ~w
Valuation: x=TRUE, p=TRUE, q=FALSE, r=TRUE

~w is a pure literal (and 4 is a singleton clause). Set w=FALSE.
Answer: x=TRUE, p=TRUE, q=FALSE, r=TRUE, w=FALSE.