CSCIUA 0472 Programming Assignment 2

Assigned: Feb. 13 Due: Mar. 20

Overview

In this assignment, you are to implement the Davis-Putnam algorithm and use it to solve a simple form of an adventure game.

The puzzle is as follows: You are given (1) a maze with treasures at particular nodes; (2) a maximum number of steps. If a player goes to a node, then they get all the treasures at that node. The object is to find a path through the maze starting at START in at most the given number of steps that collects all the different types of treasure.

Example: Suppose that the maze is as follows:

Then the path "START, C, G, H" succeeds in collecting all three types of treasure in 3 steps. The path "START, A, D, C, F" succeeds in 4 steps. You may assume that START has no treasure.

The player is only required to get one of each type of treasure.

You will write three programs.

1. An implementation of the Davis-Putnam procedure, which takes as input a set of clauses and outputs either a satisfying valuation, or a statement that the clauses cannot be satisfied.
2. A front end, which takes as input a maze problem and outputs a set of clauses that can be input to (1).
3. A back end, which takes as input the output of (2) and translates it into a solution to the original problem.

Compiling the maze puzzle to propositional logic

The MAZE puzzle can be expressed propositionally as follows: There are two kinds of atoms:

1. At(N,I) means that the player is on node N at time I. For instance At(C,2) means that the player is on node C at time 2. (Note: in propositional logic, a construction like "At(C,2)" is considered a single symbol of 7 characters. The parentheses and comma are not punctuation, they are just characters in the symbol, to make it easier for the human reader.)
2. Has(T,I) means that the player is in possession of treasure T at time I. For example, Has(Gold,3) means that the player has the gold at time 3.

If there is a maximum of K steps, then for each time I=0 ... K, there should be an atom At(N,I) for each node N, and an atom Has(T,I) for each treasure T. There are 7 categories of propositions.

1. The player is only at one place at a time. For any time I, for any two distinct nodes M and N, ¬(At(M,I) ∧ At(N,I)). In CNF this becomes ¬At(M,I) ∨ ¬At(N,I). For example, ¬At(C,2) ∨ ¬At(F,2).

2. The player must move on edges. Suppose that node N is connected to M1 ... Mq. For any time I, if the player is at node N at time I, then the player moves to M1 or to M2 ... or to Mq at time I+1. Thus At(N,I) → At(M1,I+1) ∨ ... ∨ At(Mq,I+1). In CNF, ¬At(N,I) ∨ At(M1,I+1) ∨... ∨ At(Mk,I+1). For example, ¬At(C,2) ∨ At(START,3) ∨ At(D,3) ∨ At(F,3) ∨ At(G,3)

3. Suppose that treasure T is located at node N. Then if the player is at N at time I, then at time I the player has T. At(N,I) → Has(T,I). In CNF, ¬At(N,I) ∨ Has(T,I). For example ¬At(C,2) ∨ Has(Ruby,2)

4. If the player has treasure T at time I-1, then the player has T at time I. (I=1..K) Has(T,I-1) → Has(T,I) In CNF, ¬Has(T,I-1) ∨ Has(T,I) For example ¬Has(GOLD,2) ∨ Has(GOLD,3).

5. Let M1 ... Mq be the nodes that supply treasure T. If the player does not have treasure T at time I-1 and has T at time I, then at time I they must be at one of the nodes M1 ... Mq. [¬Has(T,I-1) ∧Has(T,I)] → At(M1,I) ∨ At(M2,I) ∨ ... ∨At(Mq,I). In CNF Has(T,I-1) ∨ ¬Has(T,I) ∨ At(M1,I) ∨ At(M2,I) ∨ ... ∨At(Mq,I). For example Has(GOLD,1) ∨ ¬Has(GOLD,2) ∨ At(A,2) ∨ At(H,2).

6. The player is at START at time 0. At(START,0).

7. At time 0, the player has none of the treasures. For each treasure T, ¬Has(T,0). For instance: ¬Has(GOLD,0).

8. At time K, the player has all the treasures. For each treasure T, Has(T,K). For instance: Has(GOLD,4).

...