Problem 1: The top number at each node is its state; the lower number is the game-tree value of the node, propagated upward. MAX MIN MAX MIN LEAF 100 ---A---> 97 ---C---> 105 ---A---> 107 ---C---> 101 101 | 101 | 101 | 101 | | | | |-D---> 122 | | | | | |-B---> 101 ---C---> 117 | | 53 | | | |-D---> 53 | | | |-D---> 145 ---A---> 141 ---C---> 135 | >=135 135 | | B branch pruned |-D---> 161 | |-B---> 98 ---C---> 108 ---A---> 113 ---C---> 119 <=101 101 | 91 | D branch pruned | |-D---> 91 | |-B---> 107 ---C---> 101 101 | |-D---> 122 The value of the starting node is 101. X will make move A. (In fact move B is just as good --- they both lead to a final state of 101 --- but after doing alpha-beta pruning X does not know that B achieves 101, he just knows it can't be better than 101.) Problem 2 A. Converting these sentence to CNF gives Set S0: A. ~p V ~q V r B. ~p V q V ~r C. ~p V x V w D. ~w V q. E. ~w V ~r F. ~x V ~p V w. G. ~x V p V ~w There are no singleton clauses or pure literals, so try the assignment p=TRUE Set S1: (p=TRUE) A. ~q V r B. q V ~r C. x V w D. ~w V q. E. ~w V ~r F. ~x V w. There are still no singleton clauses or pure literals, so try q=TRUE Set S2: (p=TRUE, q=TRUE) A. r C. x V w E. ~w V ~r F. ~x V w. A is a singleton clause, so set r=TRUE. Set S3: (p=TRUE, q=TRUE, r=TRUE) C. x V w E. ~w F. ~x V w. E is a singleton clause, so set w=FALSE Set S4: (p=TRUE, q=TRUE, r=TRUE, w=FALSE) C. x F. ~x C is a singleton clause, so set x=TRUE Set S5: (p=TRUE, q=TRUE, r=TRUE, w=FALSE, x=TRUE) F. empty F is the empty clause, so fail. Backtrack to the last choice point, which was setting q=TRUE at S1. From S1, set q=FALSE. Set S6: (p=TRUE, q=FALSE) B. ~r C. x V w D. ~w E. ~w V ~r F. ~x V w. B and D are singleton clauses, so set r=FALSE, w=FALSE. Set S7: (p=TRUE, q=FALSE, r=FALSE, w=FALSE) C. x F. ~x C is a singleton clause, so set x=TRUE Set S8: (p=TRUE, q=FALSE, r=FALSE, w=FALSE, x=TRUE) F. empty F is the empty clause, so fail. Backtrack to the last choice point, which was setting p=TRUE at S0. From S0, set p=FALSE. Set S9: (p=FALSE) D. ~w V q. E. ~w V ~r G. ~x V ~w ~w is a pure literal, so set w=FALSE. Set S10: (p=FALSE,w=FALSE) Empty set of clauses. Return the valuation p=FALSE, w=FALSE. The other atoms may be set arbitrarily.