プログラミングを頑張る日記

プログラミングを勉強して、ハッカーになろう

Common Lispを頑張る(59)

やります「Land of Lisp」、本日はダイス・オブ・ドゥームの改善です

メモ化

クロージャ

最適化を始める前に、ついにクロージャの登場です。
クロージャはlambdaで関数が作られるときに外界の情報を補足したもの」という説明があります。
とりあえず例を。

CL-USER> (defparameter *foo* (let ((x 5))
                               (lambda () x)))
*FOO*
CL-USER> (funcall *foo*)
5
CL-USER>

xを定義して、それをラムダ式で返してくるだけの関数を作り、funcallで呼び出しています。
xはletで定義されているのに、後のfuncallでの呼び出しの時でもxが5であることを覚えている! というのがポイントのようです。
funcallで呼び出した時にletがまた動いていたりはしないんですかね。

CL-USER> (defparameter *hoge* 5)
*HOGE*
CL-USER> (defparameter *foo* (let ((x *hoge*))
                               (lambda () x)))
*FOO*
CL-USER> (funcall *foo*)
5
CL-USER> (defparameter *hoge* 10)
*HOGE*
CL-USER> (funcall *foo*)
5
CL-USER>

なるほど。疑ってもうしわけない。

さて、何故このようになるのか。ガベージコレクタと絡めると理解しやすいそうです。
ガベージコレクタはどこからも参照されていないメモリを見つけたら自動的に解放してくれる仕組みですが、
上記のようなレキシカル変数は、let式を抜けたあとでもlambdaの中で参照されているため
lambda式自体がガベージコレクタに解放されるまでは残り続けるということです。わかりやすい。
これを利用することで関数呼び出し間でちょっとした情報を保持することができるので楽しいって話ですね。

メモ化

クロージャを利用した最適化のテクニックがメモ化です。
関数型のコードでは関数の振る舞いは渡された引数にのみ依存します。関数は値を計算して返すだけです。
同じ値が来たら常に同じ値を返す…。
ということは、一回来たことのある引数だったらわざわざ新しく計算し直さなくていいのでは?
というのがメモ化のようです。

まずは与えられた場所に隣接しているマスを返すneighors関数をメモ化しましょう。
マスの場所はころころ変りませんから妥当ですね。元を再掲します。

CL-USER> (defun neighbors (pos)
           (let ((up (- pos *board-size*)) ;対象のマスの上下を定義
                 (down (+ pos *board-size*)))
             (loop for p in (append (list up down)
                                    (unless (zerop (mod pos *board-size*)) ;posが左端でなければ
                                      (list (1- up) (1- pos))) ;左上と左側のマスを追加
                                    (unless (zerop (mod (1+ pos) *board-size*)) ;posが右端でなければ
                                      (list (1+ pos) (1+ down)))) ;右側と右下のマスを追加
                  when (and (>= p 0) (< p *board-hexnum*))
                  collect p)))          ;ゲーム盤に収まるマスを集めてリストにする
NEIGHBORS
CL-USER>

これがこうなるようです。

CL-USER> (let ((old-neighbors (symbol-function 'neighbors))
               (previous (make-hash-table)))
           (defun neighbors (pos)
             (or (gethash pos previous)
                 (setf (gethash pos previous) (funcall old-neighbors pos)))))
WARNING: redefining COMMON-LISP-USER::NEIGHBORS in DEFUN
NEIGHBORS
CL-USER>

理解しなくてはいけないのは、old-neighborsの部分でした。
symbol-functionは引数のシンボルに束縛されている関数を取り出すコマンドであり、
それで元々のneighborsをold-neighborsに束縛します。
それとpreviousというハッシュテーブルを作成し、neighborsが呼ばれるたびにその引数をキーにした値があるか
previousから調べ、なければ旧式の関数を使い結果をpreviousに保存します。
うーん、クールな動き。

さて、それよりメモ化すべきようなものがある気がしますね。game-tree関数です。
同じ手順でいけるのかな。

CL-USER> (let ((old-game-tree (symbol-function 'game-tree))
               (previous (make-hash-table :test #'equalp)))
           (defun game-tree (&rest rest)
             (or (gethash rest previous)
                 (setf (gethash rest previous) (funcall old-game-tree rest)))))
WARNING: redefining COMMON-LISP-USER::GAME-TREE in DEFUN
GAME-TREE
CL-USER>

危ない。ここでequalpを使う理由は、キーに配列が含まれているからだそう。
https://lisphub.jp/common-lisp/cookbook/index.cgi?%E9%85%8D%E5%88%97%E4%B8%AD%E3%81%AE%E8%A6%81%E7%B4%A0%E3%82%92%E6%8E%A2%E3%81%99
上記リンクでも同じようなことが例として出ています。比較難しい。

あと、rate-positionもメモ化の効率が高いそう。
再帰しまくる系の関数たちはメモ化の効率がいいというか、普通に動かしていたら効率が悪いのでしょうな。
ちょっとこれまでより難しそう。

CL-USER> (let ((old-rate-position (symbol-function 'rate-position))
               (previous (make-hash-table)))
           (defun rate-position (tree player)
             (let ((tab (gethash player previous)))
               (unless tab
                 (setf tab (setf (gethash player previous) (make-hash-table))))
               (or (gethash tree tab)
                   (setf (gethash tree tab)
                         (funcall old-rate-position tree player))))))
WARNING: redefining COMMON-LISP-USER::RATE-POSITION in DEFUN
RATE-POSITION
CL-USER>

…。参考書に頼る前にちょっと落ち着いて見てみます。
tabを作るところまでは問題ありません。
playerをキーにprevousを検索して見つかった値をtabにセット、値が見つからなかったら、
まずprevious内にplayerをキーとした空のハッシュテーブルを作成。更にそれをtabにセット。
引数の内、treeをキーにtabを検索、見つからなければtreeをキーに以前のrate-positionを実行した結果を保存。

まずplayerで検索することで検索を効率化しているのかな。2人いるとしたらまとめて検索する量の二分の一にできますもんね。
整理。previousはキーがplayerで、値が...値はtabか。gethashなら共有してそうだしそうでなければ説明がつかない。
tabはキーがtree。値が指し手の評価値。

参考書を確認したら大体合っていそう。
ゲームツリーが巨大すぎるのでそのまま検索すると結局効率が悪くこうなるとのこと。

明日は末尾最適化とやらからやっていきます。またまたワクワクするワード。おやすみなさい。