Старая версия
Здесь находится настоящий сайт
Трилобит: ленивое дерево решений
Программа прилично играет на крошечной доске, пора задуматься об увеличении игрового поля. Поскольку при простом увеличении размеров доски память быстро заканчивается, то придется жульничать: создавать в памяти только те кусочки дерева комбинаций, которые действительно нужны. Здесь нужно заметить, что, не имея возможности проанализировать всё дерево комбинаций, AI придётся немного поднапрячься.
Ленивые списки
Но вернёмся к ленивому дереву комбинаций. Один замечательный макрос и одна простейшая функция сделают сказку былью.
(defmacro lazy (&body body)
(let ((forcedp (gensym)) ; флажок Вычислено?
(value (gensym))) ; вычисленное значение
`(let ((,forcedp nil) ; при первом вызове ничего не вычисляем
(,value nil)) ; просто переменная для захвата в closure
(lambda () ; возвращаем closure
(unless ,forcedp ; если ещё не вычислено, то
(setf ,value (progn ,@body)) ; вычисляем
(setf ,forcedp t)) ; и помечаем как вычиленное
,value)))) ; в этой точке уже в любом случае вычисленно
(defun force (lazy-value)
(funcall lazy-value))
Посмотрим как они работают: сначала сделаем переменную, вычисление значения которой требует значительных затрат, на которые мы не можем пойти прямо сейчас, а затем используем эту переменную когда наступит нужный момент:
* (defparameter *lazy-var* (lazy (progn (princ "Очень жуткий процесс вычисления") 12345)))
*LAZY-VAR*
* (force *lazy-var*)
Очень жуткий процесс вычисления
12345
Теперь можно сделать ленивые списки, которые так важны для ленивого дерева комбинаций.
(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)))
Проверяем.
* (defparameter *lst* (lazy-cons 12 34))
*LST*
* *lst*
#<CLOSURE (LAMBDA ()) {100340CA3B}>
* (lazy-null *lst*)
NIL
* (lazy-car *lst*)
12
* (lazy-cdr *lst*)
34
Простые функции для преобразования обычных списков в ленивые и обратно:
(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)))))
И как же без функций оперирующих с ленивыми функциями и списками:
; Эти функции возвращают ленивые списки
(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)))))))
; Эти функции возвращают обычные (не ленивые) значения
(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))))
Ленивые ходы
Теперь в наличии достаточно инструментов чтобы модифицировать дерево комбинаций. Итак самым затратным в плане памяти является список возможных ходов moves, именно в элементах moves хранится всё дерево. Изменим функцию game-tree следующим образом:
(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
- сделаем список возможных ходов ленивым;
- лениво построим комбинацию для каждого хода;
- пометим конец ленивого списка.
Проверяем как это работает, но сначала увеличим размеры доски:
(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}>)
Замечательно! Как видно всё дерево сейчас состоит из доски и closure ленивого списка возможных ходов. Попробуем посмотреть какая комбинация будет после хода с номером 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}>))
*
Великолепно: мы получаем ветку дерева только тогда, когда она действительно нужна. Осталось ещё одно место, где изменение будет сравнительно небольшим - это вывод возможных ходов в интерфейсе с человеком:
;; 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
- проверять ленивый список нужно специальной функцией;
- обращаться к элементам списка нужно также с помощью специальных функций.
Попробуем:
* (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}>)
*
Работает 
.