CPSC 420-500 Read-Only Bulletin Board

Last modified: 8/24/06, 08:40AM (Thu)

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: 11/14/07 Title: Homework 3
Date: 10/02/07 Title: Program 2 clarification
Date: 9/28/06 Title: Program 2 tips
Date: 9/18/06 Title: Program 1 typo and clarification
Date: 9/13/06 Title: Tip for deriv-eval
Date: 8/29/06 Title: Announcement
Date: 3/01/06 Title: Resolution solution (customs official)
Date: 2/23/06 Title: Lisp tips — clearing dupe-check list
Date: 2/23/06 Title: Lisp tips — careful with append and cons
Date: 2/23/06 Title: Lisp tips — sorting
Date: 2/23/06 Title: Lisp tips — misc. tips
Date: 2/23/06 Title: Program #2 — getting started
Date: 2/23/06 Title: Heuristic functions
Date: 2/23/06 Title: Compiling Lisp code


Date: 11/14/07 Title: Homework 3
Homework 3:

For homework 3, you will redo problems you did not get right
the first time in the midterm and the final exam.

Re-solve all problems you did not get a full mark. You may omit those questions
where you got partial credit at least 1/2 worth of the full mark.

Write down the solution on a separate sheet. You do not need to write down the 
questions themselves. Just indicate the question # and whether it was for the 
midterm or the final.

	Midterm q1 ...

		your answer

	Final q7 ...

		your answer


	1. The re-solved answers.
	2. Your graded midterm and final exam.

Due: 12/5/07, 3pm, HRBB 322B

Date: 10/02/07 Title: Program 2 clarification


> While doing assignment - II, I got a basic doubt. Is iterative deepening
> search Optimal when we eliminate duplicate nodes? It uses DLS and DLS
> uses DFS for node traversal. Is it possible that by avoiding the visits
> of duplicate nodes, we will miss the optimal solution? Suppose the
> solution was at depth 30. So, when we went on the first path till depth
> 30, we might have marked some nodes as visited and didn't find solution
> in this path (till depth 30). but, when we take different paths, we
> might have got the solution at depth 30 by visiting some of the already
> marked nodes.


	Yes, that is possible, unfortunately.

        Suppose (n)-->(G), and (n) occurs at depth 5 to the far right
        and at depth 6 at the far left. Suppose (G) is the only goal.

        At depth limit 5, DLS will return NIL.

        At depth limit 6, DLS will reach the (n) on left (at depth 6)
        first, and put it in the visited node list, and backtrack.
        Once it reaches (n) on the right at depth (5), it will
        backtrack without going further.

	So, what do you do about this? If you get a suboptimal solution
	because of this reason, just state that fact and explain
	why that happend even when IDS and IDA* are supposed to be 
	optimal. Put this in your README file. You won't get points
	taken off because of this.

Date: 9/28/06 Title: Program 2 tips
>I am having a little trouble understanding
> what is exactly needed from the assignment. Which file is suppost to be
> our main? Also, are we suppost to implement our searches inside the
> interface file? Also, is the dfs file that is available to us the complete
> code?

        You need only one file: eight.lsp

        In it, you copy and paste the contents of eight-util.lsp and
        dfs.lsp, and start modifying.

        The dfs.lsp is complete and working, for that particular
        problem (search within a given tree represented as a list). 
	You need to rewrite the expand function.

Date: 9/18/06 Title: Program 1 typo and clarification
There were some typos in the program 1 slides.

Program 1 typo: In page 1, item 1, page 43 should be page 44. In page 1, item 2, page 46 should be page 47, and page 44 should be page 45.

As for the check for division by zero, you don't need to do that check for deriv-eval.

Date: 9/13/06 Title: Tip for deriv-eval
Suppose you did

   (setq var 'x)			
   (setq num 10)

and then did

   (setq var num) 

What would be contained in x? You can check this by simply typing


Actually, that's a trick question. If you followed the steps above,
you will find that it results in an error.

The reason is that (setq var num) simply assigns 10 to the variable "var".

Let's look at what's contained in what at various time points.

   (setq var 'x)			

   -> "var" contains symbol "x"

   (setq num 10)

   -> "num" contains number 10

   (setq var num) 

   -> "var" contains number 10

   At this point, "x" hasn't been assigned any value.

Somewhere above, you need (list ...) and (eval ...).

Date: 8/29/06 Title: Announcement
The articles below are from Spring 2006, but they are quite relevant still, so I will keep them here. You may also look at various versions of the read-only board from previous semesters.

Date: 3/01/06 Title: Resolution solution (customs official)
(1a) ~E(x) \/ V(x) \/ S(x,f(x))
(1b) ~E(x) \/ V(x) \/ C(f(x))
(2a) E(a)
(2b) D(a)
(2c) ~S(a,y) \/ D(y)
 (3) ~D(x) \/ ~V(x)
 (4) ~D(x) \/ ~C(x)
 (5) ~V(a)                       2b & 3
 (6) V(a) \/ S(a,f(a))           1a * 2a
 (7) S(a,f(a))                   5 & 6
 (8) D(f(a))                     2c & 7
 (9) ~C(f(a))                    4 & 8
(10) ~E(a) \/ V(a)               1b & 9
(11) V(a)                        2a & 10
(12) False                       5 & 11
Date: 2/23/06 Title: Lisp tips — clearing dupe-check list
[Q] My search works the first time I call it, but it seems to go on forever the second time I call it. What's wrong?

[A] It must be the case that you are not refreshing your duplicate check node list. Suppose it is *all-nodes-expanded*, then for each search insert this line before you call the search core:

	(setq *all-nodes-expanded* nil)

Note that for Iterative Deepening Search, you have to reset the list to NIL before each iteration!
Date: 2/23/06 Title: Lisp tips — careful with append and cons
[Q] My (expand ...) function always returns NIL!?

[A] You are probably just doing (cons (apply-op ...) return-node-list) or (append (list (apply-op ...)) return-node-list). What you should do is to assign the result of that cons or append back into the temporary variable that holds the list of expanded nodes (i.e., the return-node-list variable).

	(setq return-node-list (cons (apply-op ...) return-node-list))
Also, at the end of the expand function, you must put return-node-list so that it will be returned as the function value.
(defun expand (...)

  (let (return-node-list) 		; <--- declare local variable

		(setq return-node-list (cons (apply-op ...) return-node-list))


	return-node-list		; <-- (let ...) will return this
					;     This must be the last line
					;     in the (let ....) form.

  )					; <-- and that will be again returned
					;     by your expand function.
Date: 2/23/06 Title: Lisp tips — sorting
Here are some lisp idioms that may help you folks:
  1. Sorting: sort using the heuristic function value only:
    * (setq node-list '(     ((1 2 3 4 5 6 7 8 0) 10 2 (up down))
                            ((1 3 2 6 5 4 8 7 0) 15 1 (left))
                            ((3 4 2 5 6 1 0 7 8) 2  3 (left right down)) ))
    (((1 2 3 4 5 6 7 8 0) 10 2 (UP DOWN)) ((1 3 2 6 5 4 8 7 0) 15 1 (LEFT))
     ((3 4 2 5 6 1 0 7 8) 2 3 (LEFT RIGHT DOWN)))
    * (sort node-list #'(lambda (x y) (< (second x) (second y))) )
    (((3 4 2 5 6 1 0 7 8) 2 3 (LEFT RIGHT DOWN))
     ((1 2 3 4 5 6 7 8 0) 10 2 (UP DOWN))
     ((1 3 2 6 5 4 8 7 0) 15 1 (LEFT)))

    By changing

    #'(lambda (x y) (< (second x) (second y)))
    #'(lambda (x y) (< (+ (second x) (third x))
    		      (+ (second y) (third y))
    you can make the nodes sort according to f(n) = g(n)+h(n).

  2. Reversing a list: simply use reverse.
    * (reverse '(left right up down right down))
  3. While loops: you can define a macro like this:
    * (defvar x 0)
    * (defmacro while (test &rest forms) `(loop (unless ,test (return)) ,@forms))
    * (setq x 0)
    * (while (< x 10)			
          (setq x (+ x 1))
          (print (format nil "~d~%" x))
Date: 2/23/06 Title: Lisp tips — misc. tips
These are some scattered Lisp tips:
  1. To add a single item to a list, use (cons ...):
    	(let (node-list)
    	  (setq node-list '( a b c ))
    	  ; WRONG way: cons alone does NOT update node-list
    	  ; After the following operation, node-list will remain '(a b c)
    	  (cons 'x node-list)
    	  ; RIGHT way: you have to use setq 
    	  ; so that node-list now contains '(x a b c)
    	  (setq node-list (cons 'x node-list))
    The same thing applies for sorting. When you sort, the list you give as an argument does not get updated. You have to make sure that you recover the result by using (setq ...).

  2. Checking for duplicates:
    Just keep a global variable *all-expanded-nodes*, and keep cons-ing to it when you bump into a state that you haven't seen so far. See the (dupe ...) function in the skeleton code for a clue. You first check if a given node is a dupelicate, and if not, add that to the *all-expanded-nodes* list.
    	(defvar *all-expanded-nodes* nil)
    	; if not dupe, add it to the *all-expanded-nodes* list
    	(setq *all-expanded-nodes* (cons given-node *all-expanded-nodes*))

  3. [Q] I am confused about the (expand ....) function in the skeleton code!
    [A] It is just a wrapper. Because there can be different expand functions depending on whether you have to check for a depth limit or an f-limit, you may end up writing redundant code. Instead of doing that, you can take in the expand function name as an argument and use a generic expand as in the provided code.
    	(defvar *expand-func* 'vanilla-expand)
    	(defun general-search (state expand-func)
    		; note that we're setting the expand function to 
    		; the one supplied as an argument to general-search
    		(setq *expand-func* expand-func)
    		; call (expand ...) somewhere and it will use the
    		; desired (depth-check-expand ...) function.
    	(defun ids (state)
    		(general-search state 'depth-check-expand)
    	(defun dfs (state)
    		(general-search state 'vanilla-expand)
Date: 2/23/06 Title: Program #2 — getting 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
           ); 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
           ); 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/23/06 Title: Heuristic functions
[Q1] What is Manhattan distance?

[A1] Here's an approximate algorithm.

1. Pick a tile, say n.

2. Find it's current location in the given state: use the (location ...)

3. Calculate its desired location (from the goal state).

4. Get the x and y location for the current and desired location. Let's
   call them x_c, y_c, and x_d, y_d.

5. The manhattan distance for this tile n is

        manhattan(n) = abs(x_c-x_d) + abs(y_c-y_d).

6. Get the sum for all tiles

        sum_manhattan = Sum manhattan(n)

[Q2] How do I select different heuristics for a* and heuristic search?

[A2] It'e easier to have a global variable that holds the heuristic function name, let's say *heuristic-func*.

Your heuristic search function should take in the function to use as an argument:

	(defun heuristic (state h-func)

		(setq *heuristic-func* h-func)


which can be called as:
	(heuristic '( 1 2 3 ... ) 'h1)
supposing that you defined your heuristic functions as
	(defun h1 (state) 		; tiles out of place

	(defun h2 (state)		; sum of Manhattan distance

In (expand ...) or in (apply-op ...), you should call a heuristic wrapper (h state)

	(defun apply-op (op node)

		...  (h state) ...


	(defun h (state)
		(funcall *heuristic-func* state)
so that the apply-op function should call the heuristic that you selected in your main search wrapper function.

For example, try this to see what the main idea is:

	* (setq op '+)

	* (funcall op 10 20)

	* (setq op 'list)

	* (funcall op 10 20 30)
	(10 20 30)

Date: 2/23/06 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.


* (load "fibo.sparcf")

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


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.

$Id: board.php,v 1.5 2006/08/22 22:01:11 choe Exp $