Dice of Doom v2

Published on 6月 29, 2012

Dice of Doom v2

我已经不怎么看得懂在讲什么了,所以胡言乱语请见谅,有几个问题:

记不起之前的游戏树什么样了,我又懒得回头去看。是不是某种决策树?

不停的函数接着函数扩展看起来很方便,但又要求你时刻记得之前实现的细节,以实现正确的改进

作者的编程风格,以后还是按htdp里说的玩去吧,起码不会像现在这样晕。

英语还是障碍啊,有时候看完一大段文字后不知道在讲什么,囧了。

Dice of Doom v2

首先加载之前我们完成的 Dice of Doom 源码和为惰性求值所实现的一系列库文件。没有的话就从land of lisp网站上下载吧,话说这本书真贵要40刀左右,豆瓣上竟然380元人民币……

    (load "dice_of_doom_v1.lisp")
    (load "lazy.lisp")

然后先把游戏board扩大到4x4。

    (defparameter *board-size* 4)
    (defparameter *board-hexnum* (* *board-size* *board-size*))

下面把Dice of Doom游戏全面lazy化吧

    (defun add-passing-move (board player spare-dice first-move moves)
      (if first-move
        moves
        (lazy-cons (list nil
                         (game-tree (add-new-dice board player
                                                  (1- spare-dice))
                                    (mod (1+ player) *num-players*)
                                    0
                                    t))
                   moves)))
    (defun attacking-moves (board cur-player spare-dice)
      (labels ((player (pos)
                 (car (aref board pos)))
               (dice (pos)
                 (cadr (aref board pos))))
        (lazy-mapcan
          (lambda (src)
            (if (eq (player src) cur-player)
              (lazy-mapcan
                (lambda (dst)
                  (if (and (not (eq (player dst)
                                    cur-player))
                           (> (dice src) (dice dst)))
                    (make-lazy
                      (list (list (list src dst)
                                  (game-tree (board-attack board
                                                           cur-player
                                                           src
                                                           dst
                                                           (dice src))
                                             cur-player
                                             (+ spare-dice (dice dst))
                                             nil))))
                    (lazy-nil)))
                (make-lazy (neighbors src)))
              (lazy-nil)))
          (make-lazy (loop for n below *board-hexnum*
                           collect n)))))

注意lazy-mapcan要求被创建的列表是惰性的,现在你知道htdp标明每个函数输入输出的习惯多好了吧……

lazy化handle-human函数和play-vs-human函数

    (defun handle-human (tree)
      (fresh-line)
      (princ "choose your move:")
      (let ((moves (caddr tree)))
        (labels ((print-moves (moves n)
                   (unless (lazy-null moves)
                     (let* ((move (lazy-car moves))
                            (action (car move)))
                       (fresh-line)
                       (format t "~a. " n)
                       (if action
                         (format t "~a -> ~a" (car action) (cadr action))
                         (princ "end turn")))
                     (print-moves (lazy-cdr moves) (1+ n)))))
          (print-moves moves 1))
        (fresh-line)
        (cadr (lazy-nth (1- (read)) moves))))
    (defun play-vs-human (tree)
      (print-info tree)
      (if (not (lazy-null (caddr tree)))
        (play-vs-human (handle-human tree))
        (announce-winner (cadr tree))))

现在你可以试试人人对战了,速度不错。

让AI运行在更大的游戏区域

对AI的惰性化之前,我们先做一些修剪的工作,这是对AI决策树/游戏树算法的优化[1]。

我们现在的AI很尽职尽责的搜索计算所有的可能的结果。但在大的游戏面板中这样很累,为了在效率上取得平衡,限制AI的考虑决策树深度

    (defun limit-tree-depth (tree depth)
      (list (car tree)
            (cadr tree)
            (if (zerop depth)
              (lazy-nil)
              (lazy-mapcar (lambda (move)
                             (list (car move)
                                   (limit-tree-depth (cadr move) (1- depth))))
                           (caddr tree)))))
    (defparameter *ai-level* 4)
    (defun handle-computer (tree)
      (let ((ratings (get-ratings (limit-tree-depth tree *ai-level*)
                                  (car tree))))
        (cadr (lazy-nth (position (apply #'max ratings) ratings)
                        (caddr tree)))))
    (defun play-vs-computer (tree)
      (print-info tree)
      (cond ((lazy-null (caddr tree)) (announce-winner (cadr tree)))
            ((zerop (car tree)) (play-vs-computer (handle-human tree)))
            (t (play-vs-computer (handle-computer tree)))))

我没看懂……已经深深迷失在car cadr caddr的海洋之中,总之它限制了AI的思考深度,让它把评分限制在4步之内。[2]

启发算法[3]

让AI只思考较少的深度来实现投入和产出的统一。

让我们用更复杂的启发算法来重新对游戏面板评分:对一个自己的地盘,如果附近有比自己强大的敌人则评分1,否则则评分2。若该地盘属于对手则评分为-1

    (defun score-board (board player)
      (loop for hex across board
            for pos from 0
            sum (if (eq (car hex) player)
                  (if (threatened pos board)
                    1
                    2)
                  -1)))
    ;附近有更多骰子的位置有威胁
    (defun threatened (pos board)
      (let* ((hex (aref board pos))
             (player (car hex))
             (dice (cadr hex)))
        (loop for n in (neighbors pos)
              do (let* ((nhex (aref board n))
                        (nplayer (car nhex))
                        (ndice (cadr nhex)))
                   (when (and (not (eq player nplayer)) (> ndice dice))
                     (return t))))))

有意思的是,关于启发式作者这么说:在开发这个例子时,我模拟了使用不同版本score-board的各种对手,这个版本效果很好,开发启发式算法不是什么科学。囧~

惰性化get-ratings和rate-position函数

    (defun get-ratings (tree player)
      (take-all (lazy-mapcar (lambda (move)
                               (rate-position (cadr move) player))
                             (caddr tree))))
    (defun rate-position (tree player)
      (let ((moves (caddr tree)))
        (if (not (lazy-null moves))
          (apply (if (eq (car tree) player)
                   #'max
                   #'min)
                 (get-ratings tree player))
          (score-board (cadr tree) player))))

现在可以试试和计算机过招了。

    (play-vs-computer (game-tree (gen-board) 0 0 t))

据说先行者有优势,计算机大概有3/4的几率获胜。

alpha-beta 算法[4]

@此部分不只所云,请见谅。@

AI实际上执行一种深度优先搜索。

alpha-beta算法是把已知的一定更差的子树从决策树中剪掉的算法,熟称剪枝算法。

本游戏中游戏树的顶端上是最大最小算法,非顶端上是score-board评分……

    (defun ab-get-ratings-max (tree player upper-limit lower-limit)
      (labels ((f (moves lower-limit)
                 (unless (lazy-null moves)
                   (let ((x (ab-rate-position (cadr (lazy-car moves))
                                              player
                                              upper-limit
                                              lower-limit)))
                     (if (>= x upper-limit)
                       (list x)
                       (cons x (f (lazy-cdr moves) (max x lower-limit))))))))
        (f (caddr tree) lower-limit)))

    (defun ab-get-ratings-min (tree player upper-limit lower-limit)
      (labels ((f (moves upper-limit)
                 (unless (lazy-null moves)
                   (let ((x (ab-rate-position (cadr (lazy-car moves))
                                              player
                                              upper-limit
                                              lower-limit)))
                     (if (<= x lower-limit)
                       (list x)
                       (cons x (f (lazy-cdr moves) (min x upper-limit))))))))
        (f (caddr tree) upper-limit)))

    (defun ab-rate-position (tree player upper-limit lower-limit)
      (let ((moves (caddr tree)))
        (if (not (lazy-null moves))
          (if (eq (car tree) player)
            (apply #'max (ab-get-ratings-max tree
                                             player
                                             upper-limit
                                             lower-limit))
            (apply #'min (ab-get-ratings-min tree
                                             player
                                             upper-limit
                                             lower-limit)))
          (score-board (cadr tree) player))))

这三个函数怎么实现及实现什么……不知道,深感自己英语不行啊,大段大段看完不知道在讲什么,哪天有兴致了对照对弈程序基本技术再看吧……I am confused now.[6]

改进我们的handle-computer函数

    (defun handle-computer (tree)
      (let ((ratings (ab-get-ratings-max (limit-tree-depth tree *ai-level*)
                                         (car tree)
                                         most-positive-fixnum
                                         most-negative-fixnum)))
        (cadr (lazy-nth (position (apply #'max ratings) ratings) (caddr tree)))))

现在把游戏面板扩大到5x5

    (defparameter *board-size* 5)
    (defparameter *board-hexnum* (* *board-size* *board-size*))

由于我们记忆化的原因,之前的4x4面板会被缓存。为了修正这个问题重新定义neighbors函数即可。

实验新的经过改进的游戏

    (play-vs-computer (game-tree (gen-board) 0 0 t))

小结

本章我们使用惰性求值方法改进我们的游戏,同时通过一些优化限制AI引擎搜索的决策树数目,我们学到了以下几点:

  • 惰性列表使你有可能使用无穷的列表和数据结构,并且很有效率
  • 一旦你有了lazy宏和force函数,你就可以基于此创造更复杂的惰性列表库
  • 启发性算法是不完美的算法,通过一些创造性的想法可以显著提高代码的性能。在我们的例子中我们使用启发式的算法来为游戏树的顶端评分。
  • 一旦我们把游戏转化为惰性树,为了限制AI思考的移动的深度我们可以优雅地[5]修剪游戏树。
  • Alpha-beta算法让我们更多地优化了性能,通过修剪不会影响AI最后所思考的移动的评分。

废话

说实话,看不懂了,愈发的看不懂。生命中某种虚空感强烈的袭来,明知自己做的是“没有意义”,也没有人在意的的东西,可我就是关心那些。

有时候真是不想理人,与很多人不怎么谈得来,我不喜欢到头来毫无建树的胡扯,也不喜欢扯不喜欢的东西。可有时无话可说无人可诉,人与人的差别就是这么大,不知何时。

有时侯如此疯狂,讨厌别人的干扰,不能容忍自己浪费生命。在他人眼里我不也是在浪费生命?我不知道,安慰我的人永远安慰我,另一个部分人永远看不起我。

我应该追求哪个世界与人生?一边是迷人的,我不知道余生还有多长,不想放手错过它,但它只在我的梦中。一条在横亘在这个世界,我却没有一丝爱意。

也许一切都是宿命。