2.7 掃除機問題(1)

AIMA lisp

サンプルコード見たらdefstructureとか使ってて泣いた。まあ、common lispなら標準だし、CLISPでも使えばいいんだけど。。サンプルコードはさっくり無視して、道をつくる - xyzzysims制作中 - 人工知能一般で作ったコードを流用することにしよう。それまでに作った関数やマクロは今回も用いる。


問題を整理するとおよそ次のようになる。

  • A Bの広場がある。広場はそれぞれ汚れていたりいなかったりする。
  • A Bはこの順に隣接している。
  • 掃除機vacuumはどちらか広場にいる。
  • 1000ステップ中、各ステップ後にどちらが綺麗であれば得点が入る。
  • 掃除機は1ステップ毎に左右に移動、もしくは掃除することが出来る。何もせずに待機することを選んでも良い。
  • 掃除機は地形のみわかっていて、初期の汚れや自分の位置はわからない。
  • 掃除機は自分の居る広場がどちらか、その場所が汚れているかどうかが分かる。


・・・これって最初の具合によっては何もしなくてもポイントが入るんじゃないのかなあ。両方汚れてても一回吸えばいいし。まあ、続きの問題で色々条件変えるので、問題の性質はあとで考えよう。とりあえず今回は適当に動くだけの掃除機にする。流用する環境の都合で、広場がroom、vacuumがpersonになるけど、あまり気にしなくていいだろう。

(setq *world*
      '(world
        (room a b)
        (person vacuum)
        (way right left)
        (path (a . b) (b . a))
        (right (a . b))
        (left (b . a))
        (in)
        (sordid)
        (point)
        (turn)
        (record)))

(defun initialize (world)
  "環境の初期化"
  (macrolet ((init (where &rest args)
               `(treat (key ,where world)
                  (rplacd key nil) ,@args)))
    (init 'sordid
      (dolist (a (findd 'room key))
        (if (zerop (random 2)) (pushd a key))))
    (init 'in
      (let ((p (findd 'room world)))
        (pushd (cons 'vacuum (elt p (random (length p)))) key)))
    (init 'point)
    (init 'turn)
    (init 'record))
  world)

(defun update (world)
  "環境のチェック・更新"
  (treat (key 'turn world)
    (pushd 1 key))
  (let ((p (if (> 2 (length (findd 'sordid world))) 1 0)))
    (treat (key 'point world)
      (pushd p key))
    p))

(defun score (world)
  "スコア計上"
  (format t "turn: ~A score: ~A"
          (apply '+ (findd 'turn world))
          (apply '+ (findd 'point world))))

(defun act-vacuum (world)
  "掃除機の動作"
  (let ((act (select-act-vacuum world)))
    (case act
    ('left #1=(go-way world 'vacuum act))
    ('right #1#)
    ('suck (treat (key 'sordid world)
             (delete (treat (where 'in world)
                       (findd 'vacuum where)) key))))
    (treat (key 'record world)
      (pushd act key))
    act))

(defun select-act-vacuum (world)
  "掃除機の動作選択"
  ;本来はworldの中身を見て判断する。
  (elt '(left right suck wait) (random 4)))

;シミュレーション実行系
(progn
  (initialize *world*)
  (dotimes (_ 1000)
    (act-vacuum *world*)
    (update *world*))
  (score *world*))