| Date: 2/09 | Title: Alpha beta pruning example |
Here's how to print out the alpha beta pruning results.
This is the example from slide03
> (defvar *ab-slide* '(((-1 -4) (1 3) (2 6)) ((30 -1) (-4 -10) (1 6)) ((1 10) (-1 9) (3 4))))
(((-1 -4) (1 3) (2 6)) ((30 -1) (-4 -10) (1 6)) ((1 10) (-1 9) (3 4)))
Run the pruning function
>(alpha-beta *ab-slide*)
"MAX CUT (1 3): alpha = 1, beta=-1, after 1
"
"------> (1 MAXCUT)
"
"MAX CUT (2 6): alpha = 2, beta=-1, after 2
"
"------> (2 MAXCUT)
"
"MIN CUT ((30 -1) (-4 -10) (1 6)): alpha = -1, beta =-4, after (-4 -10)
"
"------> ((30 -1) (-4 -10) MINCUT)
"
The result shows the game tree with "MAXCUT" and "MINCUT" where the cut happens.
(((-1 -4) (1 MAXCUT) (2 MAXCUT)) ((30 -1) (-4 -10) MINCUT)
((1 10) (-1 9) (3 4)))
|
| Date: 2/06 | Title: Homework 1 tips |
Homework 1 tips
Worked out example for DFS, using the node-list
Step0 : Init node-list with initial state
node-list = [ (1) ]
Step1 : node-list = [ (1) ]
- Take out (1) : after this, node-list = [ ]
- Goal check (1) = not a goal
-> this counts as a VISIT!
- Expand (1) -> (2) (3)
- Push into node-list : node-list = [ (2) (3) ]
Step2 : node-list = [ (2) (3) ]
- Take out (2) : after this, node-list = [ (3) ]
- Goal check (2) : not a goal
-> this counts as a VISIT!
- Expand (2) -> (4) (5)
- Push into node-list : node-list = [ (4) (5) (3) ]
Step3 : node-list = [ (4) (5) (3) ]
- Take out (4) ...
[Summary]
- After step 2, before entering step 3, nodes remaining: [ (4) (5) (3) ]
- Node visit order: (1) -> (2) -> (4)
- Note: If (3) was the goal node, the solution path will be (1) -> (3),
different from the visit order!
How to compute h*(n)
h*(n) is the minimum cost from (n) to the goal. It is easier to start computing this from near the end.
Examples:
h*(e) = 10.
h*(c) = 10+10 = 20. (c->e->g: other paths that are more expensive)
|
| Date: 2/05 | Title: LISP: compiling |
You can compile the lisp file for faster execution.
For most of the different variants of LISP, the following works.
- "*" is assumed to be the prompt.
- ";" is the system generated message.
- "XXXX" is the extension of the object file, which can vary depending on
your LISP interpreter. See below
Steps to follow
1. Compile
2. Load the object file
3. Execute your function as usual
* (compile-file "eight.lsp")
; ....
; ....
; ....
; ....
; some message that indicates the object file name ..../eight.XXXX
* (load "eight.XXXX")
* (dfs-iter ...)
[Object file extensions]
- CMUCL: *.sse2f (CSE Linux)
- CLISP: *.fas (Ubuntu Linux)
- GCL: *.o (Ubuntu Linux)
- SBCL: *.fasl (Windows 10, Ubuntu Linux)
|
| Date: 1/21 | Title: LISP: resources |
Aside from CMU Common Lisp, the following also works
for most purposes in case you want to install on your
local computer.
- CLISP
- Steel Bank Common Lisp
Binary distributions are available for most of the
typical platforms.
On Ubuntu
sudo apt install clisp
sudo apt install sbcl
On MacOS X
brew install sbcl
or
port install sbcl
Here's a good tutorial page for beginners
https://lisp-lang.org/learn/getting-started/
|