CS 480 Homework 2

Assigned: 18 March 2022   Due: 28 March 2022

Problems use ideas from the Russell & Norvig textbook. These homework problems are to be done individually, not in pairs or other groups. Upload your solution using the Blackboard course page. Please typeset your solutions as much as possible.

  1. Give a careful, precise formulation of the following problem as a constraint satisfaction problem:

    Class scheduling: There are a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots for classes. Each professor has a set of classes that he or she can teach.

  2. This is continuation of the tic-tac-toe problem from the previous homework assignment. As before, show the whole game tree from an empty board (depth 0) to depth 2 (one X and one O on the board) taking symmetry into account.

    As part of this problem we define Xn as the number of rows, columns, or diagonals with exactly n X's and no O's. Similarly, On is the number of rows, columns, or diagonals with just n O's. The utility function assigns +1 to any position with X3=1 and -1 to any position with O3=1. All other terminal positions have utility 0. For nonterminal positions, we use a linear evaluation function defined as Eval(s)=3X2(s)+X1(s)-(3O2(s)+O1(s)). Given this evaluation function, mark on your tree the evaluations of all the positions at depth 2.

    Using the minimax algorithm, mark on your tree the backed-up values for the positions at depths 1 and 0, and use those values to choose the best starting move. Be clear about what the best starting move is.

    Circle the nodes at depth 2 that would not be evaluated if alpha-beta pruning were applied, assuming the nodes are generated in the optimal order for alpha-beta pruning.