Artificial Intelligence

Setting up the environment
1. Lisp in a Box on Windows or Linux
OR
2. Install Emacs, SLiME, and CLisp

February 26th Reading Assignment
1. Beating the Averages by Paul Graham
2. The first 6 chapters of Practical Common Lisp by Peter Seibel.

March 09th In-Class Assignment
1. Figure out what these functions do:

    (defun enigma (x)
      (and (not (null x))
           (or (null (car x))
               (enigma (cdr x)))))
    
    (defun mystery (x y)
      (if (null y)
          nil
          (if (eql (car y) x)
              0
              (let ((z (mystery x (cdr y))))
                (and z (+ z 1))))))
    

   Use this debugging reference to aid you
2. The following functions are incorrect implementations of "sum up all non-nil elements in a list". Explain what's wrong with each, give a correct version.

    (defun summit (lst)
    	(remove nil lst)
    	(apply #'+ lst))
    
    (defun summit (lst)
    	(let ((x (car lst)))
    		(if (null x)
    			(summit (cdr lst))
    			(+ x (summit (cdr lst))))))
    

March 12th In-Class assignment
1. Familiarize yourself with and customize the Emacs/Slime/Clisp environment on your account on homer
2. Download the source code for the book into your home directory, load it up, read it

March 26th Lecture
1. March 12th entry is crossed out because there are a number of issues with the source code as provided by the author of the textbook. A general overview of compatibility issues is provided here. The actual instructions for getting the source code to work and a detailed explanation of the issues with the code are here.
2. Do not be impressed with the name "General Problem Solver". At the time of its invention or discovery, which happened in the late 1950's, it seemed really impressive. It is really nothing more than an abstracted state-space search: imagine doing a DFS or BFS on a tree or a graph. Hopping from one node to another is allowed if there exists an edge between the two, and we usually represent that as a line. Now, let's abstract the concept of an "edge", and replace it with "operator" - a generic mechanism that allows you to transform one state into another state . That's all GPS is: a start state, a goal state (where a "state" is a set of "conditions" - e.g. "have-money" is a condition, "son-at-school" is as well), and a set of operators that it recursively searches through when trying to transform the start state into an end state.
3. Make sure that you have gps1 (the first version of GPS in the textbook) correctly loading and executing as described in chapter 4:

    (load "auxfns.lisp")
    (load "gps1.lisp")
    (gps '(son-at-home car-needs-battery have-money have-phone-book)
         '(son-at-school)
         *school-ops*)
    

   You should get the following output:

    (EXECUTING LOOK-UP-NUMBER)
    (EXECUTING TELEPHONE-SHOP)
    (EXECUTING TELL-SHOP-PROBLEM)
    (EXECUTING GIVE-SHOP-MONEY)
    (EXECUTING SHOP-INSTALLS-BATTERY)
    (EXECUTING DRIVE-SON-TO-SCHOOL)
    SOLVED
    

4. Illustrate that you understand how the functions "some" and "every" are used in Common Lisp by creating your own examples (different from the textbook, 2 per function: 1 that will return a nil value and 1 that will return a non-nil value) of their invocations and their callback functions.
5. Read through the code of the following functions (defined in gps1.lisp in the source code) and make sure you understand how they work:
   • GPS
   • achieve
   • appropriate-p
   • apply-op
6. In-class (and homework) assignment: create a problem description for GPS to solve. The requirements are: the start state must have at least 2 preconditions. The end state must have at least 2 preconditions. There must be at least 5 operators applied to get from the start state to the end state. The problem can be on any topic. Possible topic suggestions:
   • Beating an army of alien buggers a-la Ender's Game (for the sci-fi minded)
   • Getting into Stanford (for the academically serious)
   • Dating hot supermodels (for the superficially inclined)
   E-mail me the problem specification as well as the output produced when it is run.

March 30th Lecture
Continue (or start) the March 26th entry