[CS logo]

CMSC 25000 - Artificial Intelligence
Winter 2004
Homework #3: Due January 27, 2004

Goals

Through this assignment you will:

Background

In this assignment we examine the problem of finding a consistent set of assignments to a set of variables, X1, X2,...Xn, where each variable Xi takes its values from a domain Di. The assignments are restricted by a set of pairwise constraints between the variables. The constraints can be arbitrary functions, so the problems described can be quite general.

Problem 1

We begin by examining a common problem and reformulating it as a constraint satisfaction problem.

Here we will analyze a simplification of the crossword puzzle problem. In this variant, we assume that we have a set of words W1, W2,...Wn and a crossword puzzle grid. Our goal is to fill the crossword grid with the words such that letters of intersecting words match. An example of an uncompleted puzzle and a completed puzzle appear below.

Provide a constraint satisfaction problem formulation for this variant of the crossword puzzle problem.

Part A

Specify the variables to which values are to be assigned.

Part B

Specify the domains from which the variables take their values.

Part C

Define the constraints that must hold between variables. Please provide pseudo-code defining the constraints explicitly.

Part D

Give a simple example of a "fill-in" (crossword) puzzle of the type above that demonstrates the limitations of arc-consistency type constraint propagation for solving constraint satisfaction problems.

Part E

Explain why constraint satisfaction procedures based on backtracking search are not subject to this problem.

Part F

Briefly describe the use of the iterative refinement, min-conflict strategy to solve the crossword puzzle problem.

Part G

Demonstrate the application of your procedure on a simple 4 word example puzzle.

Background 2

The remaining problems will compare the effectiveness of different strategies for solving constraint satisfaction problems such as the one defined above. We will make use of the java applet from MIT demonstrated in class that solves the map coloring problem. This applet can be found here. It requires the Java 2 plug-in, so all details required to answer the problems are included below.

Problem 2

The applet demonstrated in class uses a basic backtracking procedure as the foundation for finding solutions to the constraint satisfaction problem.

Part A

When we run the map-coloring applet with 4 colors on the map of the continental United States, we observe that when a solution is finally reached no constraints checks have been performed. Explain the mechanism that plain backtracking search needs to use to find valid labelings without constraint checks.

Part B

Conversely, backtracking with forward checking performs 492 constraint checks, and encounters 0 dead ends. Explain briefly how forward checking avoids dead ends.

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

Approximately how many possible games of tic-tac-toe are there?

Use the game tree here to complete the sections below. This corresponds to Part B in the text.

Part C

Mark on your tree the evaluations of all the positions at depth 2.

Part D

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.

Part E

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