[CS logo]

CMSC 25000 - Artificial Intelligence
Winter 2004
Homework #3:  (informal) Solutions

Problem 1 : CrossWords  Puzzle


Part A


The variables in the cross-word puzzle are  the  "down" vertical columns  and  "across"  horizontal rows.

Part B


These variables takes their values from the set of words. In the example, the domains are common to all variables: {the,university, of,chicago}

Part C

Define   len(X)  to be the length  of  a variable (number of boxes in the column or row); and |en(W) be the length of a word.
(1) Unary length constraint:  X can only be assigned W if  len(X)=len(W)
(2) Uniqueness constraint:  A word can be assigned to only one variable:  X != Y  for all pairs of variables X,Y
(3)  Consistency constraint:  If two variables intersect, the intersection character must be the same.  X[i]==Y[j] if  X and Y intersect and box number i for X, and box number j for Y.

Part D

Consider one valid solution of the  puzzle below:

     A A A           <-------X1
         B
     B A B       <------  X2
         :
        X3

where the variables X1,X2,X3  have the domain: {AAA,ABA,BAB}

Then the constraint graph is   X1---X3---X2.

It can be seen that the graph is 2-consistent but not 3-consistent. Thus,  the  assignment  X1=BAB, X3=ABA is not consistent, but undetetected by AC-3.

Part E

Backtracking search is a DFS based technique, which is complete if the search tree is bounded.

Part F

(1)  Assign words to values randomly.
(2) Pick  variables to modify: Swap its value with the value of another variable, so that the word formation on the cross-word puzzle violate minimum number of constraints. Goto 2 until no violations (or maximum number of steps allowed is exceeded)

Part G

[coming soon...meanwhile read section Sec 5.3]

Problem 2

Part A


See sec 5.2 in the book

Part B

See sec 5.2 in the book.

Problem 3: Adversial Search

Note: This is problem 6.1 in the text.

This problem exercises the basic concepts of game playing, using tic-tac-toe as an example. 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)=3*X2(s)+X1(s)-(3*O2(s)+O1(s)).

Part A


Number of Tic-Tac toe games: 9! is a trivial upper bound.  One can consider symmtery to make better estimates - there are minimum 5 moves, and maximum 9;
there are actually only 3 starting moves (center,diagonal, off-center and diagonal) ; to the center move, there are  2 responses,..and so on. Any argument better than 9! gets full points. Some people ran a DFS to come up with a number; others came up with better bounds with combinatorial arguments.

Part C


The tree evaluates to: 2,1  (leftmost subtree);  -1, 0,1,1,0  (central subtree);  -2,0,-1,0,-1 (rightmost subtree) from leftmost to rightmost leaves.

Part D

Marking the center is Max's best first move.

Part E

The leaves on the leftmost tree at maximum depth  are all evaluated. Only one leaf in the middle and righmost tree are evaluated witrh alpha-beta pruning  since this establishes that min will play better than -2 or -1, as against 1 with the leftmost tree. So Max would mark the center and force play on the leftmost side.