Yellow Rabbit

Трилобит: ленивое дерево решений

Игра Трилобит на Lisp: ленивые вычисления

Программа прилично играет на крошечной доске, пора задуматься об увеличении игрового поля. Поскольку при простом увеличении размеров доски память быстро заканчивается, то придется жульничать: создавать в памяти только те кусочки дерева комбинаций, которые действительно нужны. Здесь нужно заметить, что, не имея возможности проанализировать всё дерево комбинаций, 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


  1. сделаем список возможных ходов ленивым;
  2. лениво построим комбинацию для каждого хода;
  3. пометим конец ленивого списка.

Проверяем как это работает, но сначала увеличим размеры доски:


(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

  1. проверять ленивый список нужно специальной функцией;
  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}>)
*

Работает :triumph:.