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.