IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

    First AI in lisp

    Reverland (lhtlyy@gmail.com)发表于 2012-06-08 00:00:00
    love 0

    创造一个智能的对手

    我们的Dice of Doom游戏树代码有个分开的游戏树生成使向游戏引擎添加AI很容易。事实上,让我们跟着作者添加23行代码来实现AI!!

    让我们先看看AI如何决定移动:

    • 查看每个可允许的移动
    • 对每一步的后的board评分
    • 选择分值最高的移动

    看起来很容易,那么怎么实现评分?如果一步后就赢了,很容易评分。如果不是的话怎么办?我们的移动将取决于对手的移动,为了不陷入不断考虑对手的境地中,提出一种算法。

    最小最大算法

    当赛场上只有两个玩家时,有这么个规则:对他人好的对我不好。这意味着我们可以采取如下模式决定对手的移动:

    • 查看每个可行移动
    • 对每一步后的board评分
    • 选择最小的评分的移动

    综上,这就是最大最小算法。这很关键,结果是我们可以避免分别为自己和对手计算评分,然后向下搜索游戏树中好的移动变得更简单和更快。为了让算法成为代码,还需要做少许调整。

    将最大最小算法转化为代码

    (defun rate-position (tree player)
      (let ((moves (caddr tree)))
        (if moves
          (apply (if (eq (car tree) player)
                   #'max
                   #'min)
                 (get-ratings tree player))
          (let ((w (winners (cadr tree))))
            (if (member player w)
              (/ 1 (length w))
              0)))))
    (defun get-ratings (tree player)
      (mapcar (lambda (move)
                (rate-position (cadr move) player))
              (caddr tree)))

    创造一个有AI的游戏循环

    先写个电脑处理函数,像我们的handle-human函数,首先找出每个移动的评分,然后选择评分最高的移动。

    (defun handle-computer (tree)
      (let ((ratings (get-ratings tree (car tree))))
        (cadr (nth (position (apply #'max ratings) ratings) (caddr tree)))))

    最后,创造一个游戏环境即游戏循环

    (defun play-vs-computer (tree)
      (print-info tree)
      (cond ((null (caddr tree)) (announce-winner (cadr tree)))
            ((zerop (car tree)) (play-vs-computer (handle-human tree)));因为游戏中player1即代码0为人类玩家
            (t (play-vs-computer (handle-computer tree)))))

    finished!!

    试试人类vs电脑游戏

    在repl中输入

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

    写在最后

    终于考完试了,好久没看这本书。发现很多东西都生疏了,还好作者每次解释都很详细。这一章一看了好久,回头看看common lisp,东西真是相当之多……正好从图书馆找到HTDP的中文版,看完这本书全面转向scheme。

    最后引用首爱默生《人生苦旅》中的诗:

    我们把美归于简单

    不含多余部分

    边界清晰

    与一切相关联

    是中庸之道



沪ICP备19023445号-2号
友情链接