CPSC 420-200 Read-Only Bulletin Board

Last modified: 1/17/05, 01:15PM (Mon)

This page will have all relevant email transactions with the students regarding the AI course, so that everyone has equal information regarding the course material.

Newest transactions will be posted on the top. Regularly view this page to see what's going on between other students and the instructor.

All sensitive material such as your name, email address, etc. will be removed, and also any part of code that is not relevant to the discussion will not be uploaded here.


Article List

Date: 3/09 Title: Program #2 tip -- how to get started
Date: 2/13 Title: Compiling Lisp code
Date: 2/09 Title: Program #1 tip
Date: 1/31 Title: Typo in prog1.pdf slides


Articles

Date: 3/09 Title: Program #2 tip -- how to get started
Here's a quick guide to get you started on program#2. Because you can work on so many different aspects of the provided problem, it may not be entirely clear where to begin. Following the steps given below will give you a head-start:
  1. Node vs. state:
    The first matter is to distinguish between a node and a state. A node is a super-structure, containing extra information in addition to the game-board's state. Look carefully the arguments of the function. If you see state, provide a state. If you see node, provide a node.
  2. Implement (expand ....):
    First, implement a simple expand function, where a node is taken as an argument. The result is a list of child nodes.

    For each operator in 'up, 'down, 'left, 'right, you should go through a series of tests before actually expanding:

    • Is the operator applicable?
    • Is the resulting state a duplicate state?
    • Does the child node go over the depth- or the f-limit? (only applies to DLS, IDS, and IDA*; ignore this at first).
    Collect the new nodes by running (apply-op ...) and putting those into a list:
    (setq return-list nil)
    ...
    ... run checks ...
    ; apply operator, and use cons to paste it to the return-list
    (setq return-list (cons (apply-op ....) return-list))
    ...
    Finally, return that list as a result of (expand ....).
  3. Using the expand function, either get dfs or bfs to work.
    BFS is easier to test. Modify dfs-core to use your expand function and to take in initial state as necessary. Provide input that would only take 2 to 3 moves to reach the goal. Start from the goal state, and move the blank 2 to 3 times, and use that resulting state as the initial state.
  4. For example, if (0 2 3 7 1 8 4 5 6) was the initial state,
    • Your initial node would be:
           ( (0 2 3 7 1 8 4 5 6)
             0 ; let's assume we're doing uninformed search
             0 ; depth is 0
             () ; no operator applied yet
           )
      
    • When you run expand on the initial node above, you should get a list of two nodes:
         ( 
           ( (2 0 3 7 1 8 4 5 6)
             0; ignore this for now
             1; one operator has been applied so far
             (RIGHT)
           ); this is your first node, resulting from moving right.
      
           ( (7 2 3 0 1 8 4 5 6)
             0; ignore this for now
             1; one operator has been applied so far
             (DOWN)
           ); this is your second node, resulting from moving down.
      
         ) ; end of expanded node list
      
      This is the list that needs to be returned by your expand function. In your core routine, this list will be appended to your existing node list.

      Note that since I added the comments above, so the actual result would be more like:

         (((2 0 3 7 1 8 4 5 6) 0 1 (RIGHT)) ((7 2 3 0 1 8 4 5 6) 0 1 (DOWN)))
      
Date: 2/13 Title: Compiling Lisp code
To optimize and speed up execution, you should compile your program code. You can do this in CMUCL by running the (compile-file <filename>) function. See below for an example, where I am compiling function(s) in the file fibo.l. The file contained the definition for the (fibo ..) function. Of course you can have multiple function definitions in the file, and all of those will be compiled. Again, * is the lisp prompt, and my inputs to lisp are in bold.
* (compile-file "fibo.l")

; Python version 1.1, VM version UltraSparc/Solaris 7 on 09 SEP 04 10:49:52 am.
; Compiling: /user/choe/web_project/420/fibo.l 09 SEP 04 10:44:02 am

; Converted FIBO.
; Compiling DEFUN FIBO: 
; Byte Compiling Top-Level Form: 

; fibo.sparcf written.
; Compilation finished in 0:00:00.

#p"/user/choe/web_project/420/fibo.sparcf"
NIL
NIL

* (load "fibo.sparcf")

; Loading #p"/user/choe/web_project/420/fibo.sparcf".
T
* (fibo 20)

10946
* 

Note that you need to first compile it, and the note what the resulting compiled file is (the one highlighted in red above), and then finally (load ...) that.
Date: 2/09 Title: Program #1 tip
You can use one of these possibilities for (deriv-eval ...). First, do (deriv ...), in all cases. Then, do either of the following:
  1. Recursively evaluate, terminating when you bump into the given variable or a number. Return the value or the number itself.
  2. Use (subst ...) and then (eval ...).
  3. Use a combination of (setq ...), (list ...), and (eval ...).

Hint:

      (setq y 20)
      (setq x 'y)
      (eval (list '+ x x))
Date: 1/31 Title: Typo in prog1.pdf slides
> I noticed that asking for the derivative of (/ x x)
> returns
> (/ (+ x x) (* x x))

        Naturally, that was a typo:

                The "+" in the middle should be a "-":

        d(f/g)    g * df/dx - f * dg/dx
        ----- =  -----------------------
          dx              g^2

> which follows the derivdiv formula, but is incorrect.  (*side note* Do
> you know how this exception is justified in calculus?)  Also, should we
> account for (/ 1 x)?  Thanks again.

        Yes, you should account for (/ 1 x).

	I updated the prog1.pdf slide.


$Id: board.php,v 1.4 2003/09/04 21:56:27 choe Exp $