ICS 171Spring 2007Homework #4(Due Th. May 10)CSP1) Consider the following binary constraint network: There are 4 variables: X1, X2, X3, X4 with the domains: D1={1,2,3,4}, D2={3,4,5,8,9},D3={2,3,5,6,7,9}, D4={3,5,7,8,9}. The constraints are X1≥X2, X2>X3 or X3-X2=2, X3≠X4.a. Draw the constraint graph.b. Is the network arc-consistent? If not, compute the arc-consistent network. (show the whole process of enforcing arc-consistency and not just the finalnetwork)c. Is the network consistent? If yes, give a solution.2) Consider the 8 squares positioned as follows:The task is to label the boxes above with the numbers 1-8 such that the labels of any pair of adjacent squares (i.e. horizontal, vertical or diagonal) differ by at least 2 (i.e. 2 or more).a. Write all constraints and draw the constraint graph.b. Is the network arc-consistent? If not, compute the arc-consistent network. (show the whole process of enforcing arc-consistency and not just the finalarc-consistent network)ICS 171Spring 2007c. Is the network consistent? If yes, give a solution. Games1) (Based on question 6.1 in Russel and Norvig) Consider a Tic-Tac-Toe game.Let Xn be the number of rows, columns or diagonals containing exactly n X'sand no O's. Similarly, let On be the number of rows, columns or diagonalscontaining exactly n O's and no X's. We propose a utility function whichassigns +1 to any position with X3 = 1 (i.e. winning position) and assigns -1 toany position with O3 = 1 (i.e. loosing position). The linear evaluation functionwe suggest is 3X2 + X1 - (3O2 + O1):a) How many states (i.e. board positions) are there in a Tic-Tac-Toe game(including symmetric board positions)b) What is the depth of the complete game tree? Does the complete game tree contain all the board positions you counted in (a)? c) Show the game tree down to depth 2, namely starting from an empty board to all position in which there is one X and one O on the board.d) Mark on your tree the evaluation of the positions at level 2 (i.e. the value of the utility function at each position). Thereafter, mark on yourtree the min-max values.e) Apply alpha-beta search on your tree, and mark the pruned subtrees when traversing from left to right, from right to left. What is the optimal order?f) What property should the leaf values of a tree have so that pruning willbe maximized (resp. minimized) when the tree below is traversed fromleft to right.2) Consider the following game tree in which the static scores (in parentheses at the tip nodes) are all from the first player’s point of view. Assume that the firstplayer is the maximizing player.ICS 171Spring 2007a) What move should the first player choose?b) What nodes would not need be examined using the alpha-beta algorithm – assuming that the nodes are examined left-to-right
View Full Document
Unlocking...