猿はバナナを獲れるか？

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

学生の多くは、

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

          if 猿が箱の位置にいて、バナナの下以外にいたら
              then 猿は箱をバナナの下へ押していく.
          .............

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

Ｐｒｏｌｏｇでも「猿バナナ」について考えてみます。

6.1 Ｐｒｏｌｏｇで猿バナナのプログラムを作る

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

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

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

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

今回の「猿バナナ」では、猿の世界を時間の経過とともに変化しうる状態と考えてみましょう。状態を表すのは対象の位置です。例えば、初期状態は

猿はａ地点にいる。
猿は床の上にいる。（箱の上ではない）
箱はｃ地点にある。
猿はバナナを持っていない。

となります。つまり、

猿の水平位置（ａ地点、ｂ地点、ｃ地点など）
猿の垂直位置（床の上、箱の上）
箱の（水平）位置（ａ地点、ｂ地点、ｃ地点など）
猿の手の状態（バナナを持っている、持っていない）

という４つの要素により、猿の世界の状態を決めることができるわけです。そこで、この４つの情報を１つの構造にまとめて表現すると便利です。そこで、構造stateを次のように定義しましょう。

          state(猿の水平位置,猿の垂直位置,箱の位置,猿の手の状態).

このように定義すると、初期状態は

          state(a,floor,c,empty).

と記述することができます。

次に猿の動作の規則について考えてみます。先ず、目標状態\footnote{グラフ理論の授業を思い出してください。初期状態からいろいろな状態を経て、目標状態に至る経路を見つけることが問題を解決することでしたよね。まさか、忘れてないよね!?}はどうなるでしょう。これは、猿がバナナを持った状態です。即ち、構造の最後の成分がbananaである任意の状態

          state(_,_,_,banana).

と定義します。ある状態から別の状態へ変化させる動作には何があるのでしょうか。これには、次の４つが考えられます。

バナナを獲る。
箱に乗る。
箱を押す。
歩く。

これらの動作の全てがどの状態でも可能であるというわけではありません。猿がａ地点にいて、箱がｃ地点にある状態では、猿が箱に乗るという動作は不可能です。「バナナを獲る」という動作に関しては、猿がバナナの真下の箱に乗っていて、且つバナナを持っていない、という状態のときに可能なのです。ある動作がどのような状態のときに可能なのか、そしてその動作の結果、状態はどのように変化するのか。このような動作と状態の関係をchangeという構造で規則化しましょう。

          change(動作,動作前の状態,動作後の状態).

バナナを獲るという動作をgraspと表現します。すると、graspに関する動作規則は

          change(grasp,
                 state(b,box,b,empty),
                 state(b,box,b,banana)).

となります。

猿がある位置Ｐｌａｃｅ１から別の位置Ｐｌａｃｅ２へ歩くという動作の規則も同様に表現することができます。猿が歩くにあたって、箱の位置や猿がバナナを持っているかいないかということは無関係です。したがって、猿がＰｌａｃｅ１からＰｌａｃｅ２へ歩く、という動作をwalk(Place1,Place2)とすると、

          change(walk(Place1,Place2),
                 state(Place1,floor,Box,Hand),
                 state(Place2,floor,Box,Hand)).

となります。この節が表現しているのは、

この動作の実行により、猿はＰｌａｃｅ１からＰｌａｃｅ２へ移動する。
猿は動作前も動作後も床の上にいる。
箱はある位置Ｂｏｘにあって、動作後も変わらない。
猿の手の状態は動作後も同じままである。

です。私たちがこのような動作を考えるとき、箱の位置や手の状態が変化しないことなどは「当たり前のこと」として、つい失念しがちです。しかし、プログラミングでは、「当たり前だから書かなかった」は通用しません。書かなければ、規定しなかったことになるだけです。規定しなかったことについて、正しい動作が得られなくとも仕方ありません。それはプログラマのミスです。

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

《演習問題》

climbとpush(Place1,Place2)の動作規則を規定しなさい。

猿の世界の状態と猿の動作の規則を規定しました。それでは、ある状態にいる猿がバナナを獲れるかどうかについて考えましょう。つまり、猿のおかれた状態を入力し、その状態から猿がバナナを獲れるのであればｙｅｓ、そうでないならばｎｏと答えるような関数を考えます。これをgetbananaとしましょう。

          getbanana(State).

ここで引数Ｓｔａｔｅは猿の世界の状態です。getbananaがStateについて判定するには、次の２つの方法があります。

猿がバナナを持っていれば、getbananaは真です。これは、次のようになります。
```
          getbanana(state(_,_,_,banana)).
```
他の状態の場合には、何らかの動作を行って状態を変化させることが必要となります。変化後の状態については、また別途判定すればいいことです。これをＰｒｏｌｏｇで表現すると、次のようになります。
```
          getbanana(State1):-
              change(Operate,State1,State2),
              getbanana(State2).
```
最初にgetbananaで指定された状態State1を何らかの動作Operateによって状態State2に変化させ、このState2を引数に指定して、getbananaを再帰呼び出しします。その結果、最終的にstate節の第４パラメータ、即ち猿の手の状態がbananaになればｙｅｓとなって、猿がバナナを獲れたことが判ります。

getbananaの定義では再帰を用いています。これはdescendantの定義に似ています。Ｐｒｏｌｏｇでは再帰は頻繁に用いられますから、このような考え方に慣れておく必要があります。

それでは、「猿バナナ」のプログラムをまとめてみましょう。

          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),               % 箱をＰ１からＰ２へ押す
                 state(Place1,floor,Place1,Hand),
                 state(Place2,floor,Place2,Hand)).
          change(walk(Place1,Place2),               % Ｐ１からＰ２へ歩く
                 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 Ｐｒｏｌｏｇはどのようにして答えを得たのか

初期状態では、猿はａ地点にいて、箱はｃ地点にありました。この状態で猿がバナナを獲れるかどうかＰｒｏｌｏｇに質問してみましょう。

          ?- getbanana(state(a,floor,c,empty)).

Ｐｒｏｌｏｇの答えはｙｅｓです。では、この答えに到達するために、Ｐｒｏｌｏｇインタプリタ内部ではどのような処理が行われたのでしょうか。Ｐｒｏｌｏｇが初期状態から始めて目標状態に至る探索過程を図に示します。

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

図6.1　猿バナナの探索木

目次に戻る