Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

General Problem Solver Ver.1をRubyで実装する

はじめに

そういえば、最近になって『ベイマックス』を見て、「やっぱり人工知能最高だな!」という間違った感想を抱き、勢い余って『実践Common Lisp』という人工知能関係における鈍器のような教科書を買ってしまった。

その中で、一般問題解決マシーンが面白かったので、いい機会だし、元々何かの言語で実装されたものを他の言語に書きなおすのは、普通に勉強になるなあ、という気持ちにより、Common LispのコードをRubyで書いてみている。で、それの成果を今回はセーブがてらメモしておく、というのが今回の記事の意図となる。

そもそもGeneral Problem Solverとはなにか

General Problem Solverとは、与えられた状態からゴールに到達できるかどうかを調べるプログラムのことを指す。例えば、与えられた状態とは「家に息子がいる、車が壊れている、所持金が豊富にある」といった、そういう一連の状態とし、ゴールというのは、「息子を学校にいる」といった状態のことを指す、という風にだ。そ

して、ゴールに到達するための操作を定義することができる。例えば「車が正常に動いていれば、「息子を学校に送る」といった操作ができて、「車が壊れている」ということに対して、「修理屋に車を直してもらう」という操作ができるようにする。

この時、任意の操作と引き換えに、状態を変化させることができる。「修理屋に車を直してもらう」なら、「車が壊れている」という状態と、「所持金が豊富にある」という状態が消え、その代わり「車が正常に動く」という状態が手に入る。このような操作の一連を通じて、ゴールに到達できるかをチェックするのが、このプログラムの重要な目的である。

説明だけ聞いていると抽象的でよくわからない(自分も一読して「なにこれ」と思った)のだけれど、これをカードゲームとして捉えるとわかりやすい。手元には、今の状態を表しているカードがあって、それらを交換しながら、与えられたゴールの手札にするみたいなのを想像するといいのではないか、という理解になっている。

実際に書きなおしてみる

実際の正しいコードは『実用Common Lisp』を見てもらうとして、実際のRubyのコードを見てもらったほうが手っ取り早いので、そのリンクをGistにリンクしておく。そこで、ちょっと考えたことをメモしておく。

状態をインスタンスの中に閉じ込める

たぶん『アンダースタンディング・コンピュテーション』を書き写したことによって、理解が増えたことがひとつあって、それが「状態はインスタンスに閉じ込めて、その内部で操作する」という方法。元々のCommon Lispの本だと、スペシャル変数と呼ばれるものに展開するのだが、そうした場合に、どうしても複数の環境を比較することが難しくなるという点があるし、そもそも「グローバル変数は気持ち悪い」という主観的なアレもあり、状態はインスタンスに閉じ込めるというのは「あー、なるほどなあ」と思ったりした。確かに、オブジェクト指向では当たり前のことだったりするんだけど、他の言語から書き写すと、その辺りがクリアになってよかった。

その値を操作したらスッキリなるのは誰なのか

Common LispにもStructure(構造体)を定義するようなものがあるのだが、それに対して「どういう操作を施すのか」といったとき、そのデータがなんであるかはともかくとして、そのような操作をしてみるという方法になりがちなのだと思う。もちろん、現在の関数型言語は、たぶんそこまで雑ではないとは思うんだけど、ただオブジェクト指向ほど、構造体と関数(言い換えれば、そういうのをメソッドという?)の関わりが密接ではない。例えば、元のCommon Lispのコードは下のようなものになっている。

(find-all goal *ops* :test #'applopriate-p)

(defun appropriate-p (goal op)
  (member goal (op-add-list op)))

このとき、opという構造体とappropriateという関数は、直接に密接な関係はない。同じような構造体を保持しているなら、原理上、この関数は如何なるopに対しても利用できる。とはいえ、Rubyに直したとき、この関数はopと密接な関係にあると理解して、この関数をop構造体のメソッドとして生やしたほうがよいのではないか、という発想が思い浮かんだので、そのように書き直している。

class Operator < Struct.new(:action, :preconds, :addlist, :dellist)
  def appropriate? goal
    self.addlist.include? goal
  end

  def to_s
    self.action.to_s.gsub('_', ' ')
  end
end

僕は、いわゆるLispのような関数型とオブジェクト指向の「スタイルの違い」について、「関数型言語」はそいつにどういうことができるか、という側面に観点があるのに対して、オブジェクト指向はそいつに何ができるのかという側面に観点が集まるといった仮説を与えたのだけれど、たぶんそういう側面が一番出ているコードだと思う。

それで、このコードは一体何をしているものなんだ?

確かに、このコード自体は、実装自体は44行という非常に短いコードではあるんだけど、挙動を追うのにはとても大変なコードだなあ、と一読して思った。一瞬読むと、このコードがどうして状態を変化させながら、なぜ「息子を学校に送り届けることができる」という結論を出せるのかというのが不思議になっていた。で、ちゃんと状態変化を追いながら見ていった結果、次のようなことがわかった:

  • あるゴールが到達するために必要な条件を、「今の状態に含まれているかどうか」というチェックと、「他の操作に含まれているかどうか」をチェックする
  • もし含まれているならばサブゴールとして、もう一度「今の状態に含まれているのか」というチェックならびに、「他の操作に含まれているか」ということをチェックする

要するに、一度ゴールの諸条件からサブゴールを次々と設定し、そして現在の状態と繋がったら、現在の状態を変えながら一気に駆け上がっていく、という方法をとっているようだ。

もしかしたら、ちゃんと情報科学をやっている人ならば、この辺り当たり前なのかもしれないけれど、自分としては「なるほど、上手いなあ」と思って、この方法に舌を巻いたりしていた。

わざわざVer.1と言っているのは何故なのか

たぶん、この記事を読んだ時に、わざわざ何故Version番号を降っているのか、ということを考えるかもしれない。それは何故かというと、このGPSプログラムは不完全であるからだ。

その辺りについて『実用Common Lisp』では、その旨を書いてある。例えば、その一つに「状態が変わらない操作については意味があるのか」という問題もあるのだけれど、今回の場合、たぶんわかりやすいのは「ある条件が解決したあとに、次の条件を消費して解決すると、全体が解決したようになってしまう」という問題だと思う。

ある条件が解決したあとに、次の条件を消費して解決すると、全体が解決したのようになってしまう

このGeneral Problem Solverは、配列で複数の状態が渡せるようになっていて、複数の条件が解決できるかどうかもチェックできる。このとき、例えば、下のような条件を与えたとする:

testdata = [Operator.new(:drive_son_to_school,
                         [:son_at_home, :car_works],
                         [:son_at_school],
                         [:son_at_home]),
            Operator.new(:shop_installs_battery,
                         [:car_needs_battery, :shop_knows_problem, :shop_has_money],
                         [:car_works]),
            Operator.new(:tell_shop_problem,
                         [:in_communication_with_shop],
                         [:shop_knows_problem]),
            Operator.new(:telephone_shop,
                         [:know_phone_number],
                         [:in_communication_with_shop]),
            Operator.new(:look_up_number,
                         [:have_phone_book],
                         [:know_phone_number]),
            Operator.new(:give_shop_money,
                         [:have_money],
                         [:shop_has_money],
                         [:have_money])]

gps2 = GPS.new([:son_at_home, :car_needs_battery, :have_money, :have_phone_book], test_data)
p gps2.solve? [:have_money, :son_at_school]
p gps2.state

このとき、全てが解決したときに[:have_money, :son_at_school]が含まれていることが期待されるのだが、しかしこれらが含まれないまま、解決したことになってしまう。だからといって、逆に[:son_at_school, :have_money]だったらいいのかというと、これもまた微妙で、というのは、この状態は解決しないのだが、その解決しないということがわかるのが、条件を解決しきった後だったりする(そもそも解決順でこのように結果が変化してしまうこと自体が問題だとも言える)。

まとめ

設計としてよかったことは、上記のような状態を設計するさいに、割とインスタンスでフラグを立てたりするような設計にしたりしがちなのだけれども、そうではなくて、上のように配列でキー毎に持てばいいというのは気が付かなくて、それ自体については「なるほどなー」と考えたりしていた。また、上のように、割と簡単に、一般問題解決機みたいなのを実装できるのか、というのも学びがあった。

今度はVer.2を作ってみたいと思う。

実用 Common Lisp (IT Architects’Archive CLASSIC MODER)

実用 Common Lisp (IT Architects’Archive CLASSIC MODER)