猿はバナナを獲れるか?

以前に授業でやった「猿バナナ」を思い出しましょう。部屋の中に猿がいます。箱があります。猿の大好物のバナナが天井からぶら下がっています。猿が箱をバナナの下へ押していき、この箱の上に登って手を伸ばしたらバナナをつかむことが出来ます。さぁ、この猿の行動をシミュレートしたプログラムをC言語で作ってみよう.......というのをやりましたね。

学生の多くは、
          if 猿が箱の位置以外にいたら
              then 猿は箱の位置へ移動する.

          if 猿が箱の位置にいて、バナナの下以外にいたら
              then 猿は箱をバナナの下へ押していく.
          .............
と考えました。この場合の猿は、プログラムの起動と同時に一目散に箱のところへ行き、箱をバナナの下へ押してきて、箱に登り、バナナをゲットしました。大変に賢い猿です。でも、それって「賢い」の?じゃあ、「賢い」ってどういうこと?「知識」を持っていること?じゃあ、「知識」ってなに?ということについて考えましたね。

Prologでも「猿バナナ」について考えてみます。

6.1 Prologで猿バナナのプログラムを作る

C言語では「知識を処理する」ためにGPS(general problem solver)という機構を考えなければなりませんでした。Prologでは磯野家や遊幽の例にあるように「知識を処理する」のは比較的簡単です。

本章での目的はPrologのマッチングとバックトラックの機構がどのように使われるかを知ることです。Prologのような非手続き的な言語でプログラムを作って、そのプログラムの手続き的な振る舞いを調べてみます。

問題のシチュエーションを復習します。猿は部屋のa地点にいる。部屋のb地点にはバナナが天井からつり下げられている。猿は空腹でバナナが欲しい。しかし、どういう訳か、猿が精一杯背伸びしても丁度届かないところにバナナはある。部屋のc地点には猿が使えそうな箱がある。猿には次の行動が可能である。即ち、床を歩く、箱に乗る、箱を押して歩く。もし、バナナの下で箱の上に立てれば、バナナをつかむことができるだろう。さて、猿はバナナを獲ることができるだろうか。

プログラミングという作業において、使用するプログラミング言語の概念を用いて、問題の適切な表現法を発見するという作業は大変重要です。C言語のような手続き型の言語を先に学習している場合はなおさら、Prologのような非手続き型の言語に相応しい表現方法を考える作業は重要となります。

今回の「猿バナナ」では、猿の世界を時間の経過とともに変化しうる状態と考えてみましょう。状態を表すのは対象の位置です。例えば、初期状態は となります。つまり、 という4つの要素により、猿の世界の状態を決めることができるわけです。そこで、この4つの情報を1つの構造にまとめて表現すると便利です。そこで、構造stateを次のように定義しましょう。
          state(猿の水平位置,猿の垂直位置,箱の位置,猿の手の状態).
このように定義すると、初期状態は
          state(a,floor,c,empty).
と記述することができます。

次に猿の動作の規則について考えてみます。先ず、目標状態\footnote{グラフ理論の授業を思い出してください。初期状態からいろいろな状態を経て、目標状態に至る経路を見つけることが問題を解決することでしたよね。まさか、忘れてないよね!?}はどうなるでしょう。これは、猿がバナナを持った状態です。即ち、構造の最後の成分がbananaである任意の状態
          state(_,_,_,banana).
と定義します。 ある状態から別の状態へ変化させる動作には何があるのでしょうか。これには、次の4つが考えられます。 これらの動作の全てがどの状態でも可能であるというわけではありません。猿がa地点にいて、箱がc地点にある状態では、猿が箱に乗るという動作は不可能です。「バナナを獲る」という動作に関しては、猿がバナナの真下の箱に乗っていて、且つバナナを持っていない、という状態のときに可能なのです。ある動作がどのような状態のときに可能なのか、そしてその動作の結果、状態はどのように変化するのか。このような動作と状態の関係をchangeという構造で規則化しましょう。
          change(動作,動作前の状態,動作後の状態).
バナナを獲るという動作をgraspと表現します。すると、graspに関する動作規則は
          change(grasp,
                 state(b,box,b,empty),
                 state(b,box,b,banana)).
となります。

猿がある位置Place1から別の位置Place2へ歩くという動作の規則も同様に表現することができます。猿が歩くにあたって、箱の位置や猿がバナナを持っているかいないかということは無関係です。したがって、猿がPlace1からPlace2へ歩く、という動作をwalk(Place1,Place2)とすると、
          change(walk(Place1,Place2),
                 state(Place1,floor,Box,Hand),
                 state(Place2,floor,Box,Hand)).
となります。 この節が表現しているのは、 です。私たちがこのような動作を考えるとき、箱の位置や手の状態が変化しないことなどは「当たり前のこと」として、つい失念しがちです。しかし、プログラミングでは、「当たり前だから書かなかった」は通用しません。書かなければ、規定しなかったことになるだけです。規定しなかったことについて、正しい動作が得られなくとも仕方ありません。それはプログラマのミスです。

他の2つの動作、箱に乗る(climb)、箱を押す(push(Place1,Place2))も同様に規定できます。



《演習問題》



猿の世界の状態と猿の動作の規則を規定しました。それでは、ある状態にいる猿がバナナを獲れるかどうかについて考えましょう。つまり、猿のおかれた状態を入力し、その状態から猿がバナナを獲れるのであればyes、そうでないならばnoと答えるような関数を考えます。これをgetbananaとしましょう。
          getbanana(State).
ここで引数Stateは猿の世界の状態です。getbananaがStateについて判定するには、次の2つの方法があります。 getbananaの定義では再帰を用いています。これはdescendantの定義に似ています。Prologでは再帰は頻繁に用いられますから、このような考え方に慣れておく必要があります。

それでは、「猿バナナ」のプログラムをまとめてみましょう。
          change(grasp,                             % バナナをつかむ
                 state(b,box,b,empty),
                 state(b,box,b,banana)).
          change(climb,                             % 箱に乗る
                 state(Place,floor,Place,Hand),
                 state(Place,box,Place,Hand)).
          change(push(Place1,Place2),               % 箱をP1からP2へ押す
                 state(Place1,floor,Place1,Hand),
                 state(Place2,floor,Place2,Hand)).
          change(walk(Place1,Place2),               % P1からP2へ歩く
                 state(Place1,floor,Box,Hand),
                 state(Place2,floor,Box,Hand)).

          getbanana(state(_,_,_,banana)).         % 猿はバナナを入手した
          getbanana(State1):-
              change(Operate,State1,State2),      % Operateにより状態は変化した
              getbanana(State2).                  % 新たな状態について考える
この場合、change節が知識ベース、getbanana節が推論機構ということになります。

6.2 Prologはどのようにして答えを得たのか

初期状態では、猿はa地点にいて、箱はc地点にありました。この状態で猿がバナナを獲れるかどうかPrologに質問してみましょう。
          ?- getbanana(state(a,floor,c,empty)).
Prologの答えはyesです。では、この答えに到達するために、Prologインタプリタ内部ではどのような処理が行われたのでしょうか。Prologが初期状態から始めて目標状態に至る探索過程を図に示します。

この場合、Prologは1回バックトラックしただけで、かなり効率よく正しい動作の系列を発見できました。猿は必ずバナナを獲ることができるのでしょうか。あてもなく、部屋の中を歩き回ってしまったり、箱を押して回ったりすることはないのでしょうか。実は、これはプログラムにおけるchange節の記述順序に依存しているのです。では、次章でPrologの探索過程をもっと詳しく調べてみましょう。

猿バナナの探索木
図6.1 猿バナナの探索木




目次に戻る目次に戻る