| Date: 3/01 | 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 | 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 | 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 | Title: Lisp tips — sorting |
Here are some lisp idioms that may help you folks:
- 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)))
to
#'(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).
- Reversing a list: simply use reverse.
* (reverse '(left right up down right down))
(DOWN RIGHT DOWN UP RIGHT LEFT)
- While loops: you can define a macro like this:
* (defvar x 0)
X
* (defmacro while (test &rest forms) `(loop (unless ,test (return)) ,@forms))
WHILE
* (setq x 0)
0
* (while (< x 10)
(setq x (+ x 1))
(print (format nil "~d~%" x))
)
"1
"
"2
"
"3
"
"4
"
"5
"
"6
"
"7
"
"8
"
"9
"
"10
"
NIL
|
| Date: 2/23 | Title: Lisp tips — misc. tips |
These are some scattered Lisp tips:
- 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 ...).
- 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*))
...
- [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 | 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:
- 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.
- 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 ....).
- 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.
- 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/23 | 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 ...)
function.
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
n=8
sum_manhattan = Sum manhattan(n)
n=0
[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)
30
* (setq op 'list)
LIST
* (funcall op 10 20 30)
(10 20 30)
|
| Date: 2/23 | 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/08 | Title: Make-up dates |
Make-up dates (X indicates unavailablity so far):
Thu 2/9 8:00-9:15am XX
Thu 2/9 9:00-10:15am XX
Thu 2/9 10:00-11:15am XX
Thu 2/9 4:30-5:45pm X
Fri 2/10 8:00-9:15am XX
Fri 2/10 9:00-10:15am X
Fri 2/10 10:00-11:15am XX
Fri 2/10 3:00-4:15pm X
Fri 2/10 4:10-5:25pm X
Tue 2/14 5:00-6:15pm
Tue 2/14 6:00-7:15pm
|