COSC 387: Artificial Intelligence

Project 1
Fall 2000

Due: Sep 27 @ 5 P.M.
4 points

1. Encode the following tree as a list assigned to a globally declared variable. Write two Lisp functions, preorder and postorder, that print the pre-order and post-order traversals of the tree passed in as the argument, respectively.

   

2. Encode the following graph using property lists. Write a Lisp function that, when given a start and an end node, uses depth-first search to return a path between them.

   

   For example,

   >(dfs 'a 'g)
   (A C F E G)
   
   >(dfs 'f 'g)
   (F E G)
   
   >(dfs 'e 'c)
   NIL
   

3. Develop a representation for a tic-tac-toe board. Write a function that, when given a board configuration as its argument, returns a list containing all of the next possible moves.

4. Tanimoto defined a heuristic evaluation function for tic-tac-toe boards as

   f = 100A + 10B + C - (100D + 10E + F),

   where

   • A is the number of lines with 3 X's,
   • B is the number of unblocked lines w/ 2 X's,
   • C is the number of unblocked lines with 1 X,
   • D is the number of lines with 3 O's,
   • E is the number of unblocked lines w/ 2 O's, and
   • F is the number of unblocked lines w/ 1 O.

   Implement Tanimoto's heuristic evaluation function. That is, when given a tic-tac-toe board configuration, the function returns f.

Instructions for Submission: Although you can use any Common Lisp environment, all programs must run under GNU gcl. When you are ready to submit your program for grading, e-mail it as one file to the TA using the last four digits of your student ID and the suffix ``.lisp'' as the subject line.

For example, if the last four digits of your student ID is 1234, the name of your source file is proj1.lisp, and your TA's e-mail address is ``imagoodtamaloof@cs'', then you would type at the UNIX prompt:

gusun% mailx -s "1234.lisp" imagoodtamaloof@cs < proj1.lisp

Once you submit your project, it is important to keep an electronic copy that preserves the modification date and time. If we lose your project or the e-mail system breaks, then we will need to look at the modification date and time of your project to ensure that you submitted it before it was due.

Finally, when storing source code on university machines, it is important to set file permissions so others cannot read the file. To turn off such read/write permissions, type at the UNIX prompt chmod og-rw <file>, where <file> is the name of your source file.