COSC 270 Project 1

COSC 270: Artificial Intelligence

Project 1
Spring 2015

Due: Thu, Jan 29 @ 11:59 P.M.
4 points

Write a function that uses the do form to find the minimum and maximum values in a list of numbers. The function should return these two values in a list. Do not use the min and max functions in your implementation.
Same problem as above, but use recursion.
Same problem as above, but use apply, min, and max.
Encode the following tree as a list assigned to a globally declared variable. Write the Lisp functions preorder and postorder that return as a list the pre-order and post-order traversals of the tree passed in as the argument, respectively.

For example,
```
> (preorder *tree*)
(O R E G O ... )
```
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
```
Develop a representation for a tic-tac-toe board. Write a function named successors that, when given a board configuration as its argument, returns a list containing all of the next possible moves.
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.
Write a function that reads a file containing a layout for a maze and returns a problem consisting of the three properties maze, start-state, and goal-state. The first two elements of the file are integers that specify the x and y dimensions of the maze. The remaining characters specify the maze with #\% representing walls, #\Space representing paths, #\S representing the start state, and #\G representing the goal state.

Consider the following example stored in the file named tinyMaze.lay:
```
7 7
%%%%%%%
%    S%
% %%% %
%  %  %
%%   %%
%G %%%%
%%%%%%%
```
Assuming I have implemented the function print-maze, your implementation should work as follows:
```
> (setf *problem* (load-maze-problem "tinyMaze.lay"))
NIL
> (print-maze (get *problem* 'maze))
%%%%%%%
%    S%
% %%% %
%  %  %
%%   %%
%G %%%%
%%%%%%%
NIL
> (get *problem* 'start-state)
(5 1)
> (get *problem* 'goal-state)
(1 5)
```
(Note that the maze layouts we'll use are adapted from Berkeley's Pac-Man Projects.)

For the above, the only global variables should be those required to store the tree, the graph, and a board. These should be passed in to functions. Functions should not access these global variables directly. The functions should not create extra global variables.

Instructions for Electronic Submission

In the header comments of the primary file, provide the following information:

;;;;
;;;; Name
;;;; E-mail Address
;;;; Platform: Windows, Linux (cs-class), etc.
;;;; Lisp Environment: clisp, sbcl, gcl, cmucl
;;;;
;;;; In accordance with the class policies and Georgetown's Honor Code,
;;;; I certify that, with the exceptions of the course materials and those
;;;; items noted below, I have neither given nor received any assistance
;;;; on this project.
;;;;

You'll be using Blackboard to submit your assignments. Put everything in a zip file and upload it.