Frozen
Here is an active version
Trilobite: a Lazy Decision Tree
Program decently plays on a tiny board, it’s time to think about increasing the playing field. Since with a simple increase in the size of the board, memory quickly ends, you have to cheat: create in memory only those pieces of tree of combinations that are really needed. Here it should be noted that, without having the opportunity to analyze the whole tree of combinations, AI will have to think better.
Lazy Lists
But back to the lazy tree of combinations. One remarkable macro and one simple function will make a fairy tale happen.
(defmacro lazy (&body body)
(let ((forcedp (gensym)) ; the Calculated? flag
(value (gensym))) ; Calculated value
`(let ((,forcedp nil) ; on the first call, we do not calculate anything
(,value nil)) ; just variable to capture in the closure
(lambda () ; return closure
(unless ,forcedp ; if not yet calculated, then
(setf ,value (progn ,@body)) ; calculate
(setf ,forcedp t)) ; and mark as calculated
,value)))) ; at this point, in any case, it is computed
(defun force (lazy-value)
(funcall lazy-value))
Let’s see how they work: first we make a variable whose calculation of the value requires considerable expenses, which we can not go right now, and then use this variable when the right moment comes:
* (defparameter *lazy-var* (lazy (progn (princ "Very costly calculation process") 12345)))
*LAZY-VAR*
* (force *lazy-var*)
Very costly calculation process
12345
Now one can make lazy lists that are so important to the lazy combination tree.
(defmacro lazy-cons (a d)
`(lazy (cons ,a ,d)))
(defun lazy-car (x)
(car (force x)))
(defun lazy-cdr (x)
(cdr (force x)))
(defun lazy-cadr (x)
(lazy-car (lazy-cdr x)))
(defun lazy-nil ()
(lazy nil))
(defun lazy-null (x)
(not (force x)))
Check.
* (defparameter *lst* (lazy-cons 12 34))
*LST*
* *lst*
#<CLOSURE (LAMBDA ()) {100340CA3B}>
* (lazy-null *lst*)
NIL
* (lazy-car *lst*)
12
* (lazy-cdr *lst*)
34
Simple functions for converting ordinary lists to lazy ones and back:
(defun make-lazy (lst)
(lazy (when lst
(cons (car lst) (make-lazy (cdr lst))))))
(defun take (n lst)
(unless (or (zerop n) (lazy-null lst))
(cons (lazy-car lst) (take (1- n) (lazy-cdr lst)))))
(defun take-all (lst)
(unless (lazy-null lst)
(cons (lazy-car lst) (take-all (lazy-cdr lst)))))
And how without the functions that operate with lazy functions and lists:
; These functions return lazy lists
(defun lazy-mapcar (fun lst)
(lazy (unless (lazy-null lst)
(cons (funcall fun (lazy-car lst))
(lazy-mapcar fun (lazy-cdr lst))))))
(defun lazy-mapcan (fun lst)
(labels ((f (lst-cur)
(if (lazy-null lst-cur)
(force (lazy-mapcan fun (lazy-cdr lst)))
(cons (lazy-car lst-cur) (lazy (f (lazy-cdr lst-cur)))))))
(lazy (unless (lazy-null lst)
(f (funcall fun (lazy-car lst)))))))
; These functions return normal (non-lazy) values
(defun lazy-find-if (fun lst)
(unless (lazy-null lst)
(let ((x (lazy-car lst)))
(if (funcall fun x)
x
(lazy-find-if fun (lazy-cdr lst))))))
(defun lazy-nth (n lst)
(if (zerop n)
(lazy-car lst)
(lazy-nth (1- n) (lazy-cdr lst))))
Lazy moves
Now one have enough tools to modify the combination tree. So the most costly in terms of memory is the list of possible moves moves, it is in the moves elements that the entire tree is stored. Let’s change the function game-tree as follows:
(defun game-tree (board player move)
(let ((fail (if (eql -1 move)
nil
(test-for-win board move
(change-player player)))))
(make-game-node
:player player
:board board
:failp fail
:moves
(if fail
(lazy-nil) ; // 3
(lazy-mapcar (lambda (move) ; // 2
(list move
(game-tree (board-add-move board move player)
(change-player
player)
move)))
(make-lazy (possible-moves board))))))) ; // 1
- make a list of possible moves lazy;
- lazily build a combination for each turn;
- mark the end of the lazy list.
Check how it works, but first increase the size of the board:
(defparameter *board-width* 8)
(defparameter *board-height* 7)
(defparameter *win-len* 4)
* (defparameter *g* (game-tree (new-board) *ai-player* -1))
*G*
* *g*
(1
#(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
NIL #<CLOSURE (LAMBDA () :IN LAZY-MAPCAR) {1004B029AB}>)
Great! As you can see, the whole tree now consists of a board and a closure of a lazy list of possible moves. Let’s see what combination will be after the move with the number 6:
* (defparameter *sixth* (lazy-nth 6 (game-node-moves *g*)))
*SIXTH*
* *sixth*
(54
(2
#(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0)
NIL #<CLOSURE (LAMBDA () :IN LAZY-MAPCAR) {1004B0C04B}>))
*
Great: we get a tree branch only when it really is needed. There remains one more place where the change will be relatively small - this is the output of possible moves in the interface with the player:
;; handle human
(defun handle-human (tree)
(fresh-line)
(princ "choose your move:")
(let ((moves (game-node-moves tree)))
(labels ((print-moves (lst n)
(unless (lazy-null lst) ; // 1
(let* ((move (lazy-car lst)) ; // 2
(action (code-char (+ 97 (mod (car move) *board-width*)))))
(fresh-line)
(format t "~a. ~a" n action)
(print-moves (lazy-cdr lst) (1+ n)))))) ; // 2
(print-moves moves 1))
(fresh-line)
(cadr (lazy-nth (1- (read)) moves)))) ; // 2
- To check the lazy list one need a special function;
- One must also access the list items using special functions.
Let’s try it:
* (handle-human (game-tree (new-board) *ai-player* -1))
choose your move:
1. a
2. b
3. c
4. d
5. e
6. f
7. g
8. h
5
(2
#(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0)
NIL #<CLOSURE (LAMBDA () :IN LAZY-MAPCAR) {10046CCCFB}>)
*
It works 
.