Prologの勉強をはじめた。
勉強をはじめるにあたって色々文献を漁っているとPrologを「AIプログラミング」と呼称する文献（多くは90年代の本）が多いことにちょっと驚いた。
90年代の第二世代人工知能ブームの中心にいた「エキスパートシステム」の多くがPrologで実装されたこともあって、当時は「人工知能＝Prolog」だったのだなと少し感慨深くなった。
宣言型/論理型プログラミング言語に触れるのはPrologが初めてなので、当初はかなり面食らったが慣れてくるとその推論の巧みさにハマってきた。
状態空間および推移規則を定義することで、ある状態から望ましい状態までのパスを自動的に推論してくれるのはすごい。あと、想像以上に柔軟に規則を定義できるため、幅広い応用ができそうだ。（90年代当時の興奮を実感）
勉強の一環として様々な論理パズルを解くプログラムをPrologで実装していこうと思う。
今回はその第1弾として川渡り問題クラスの「オオカミとヒツジとキャベツ」を取り上げる。
論理パズル「オオカミとヒツジとキャベツ」
■問題
オオカミとヒツジとキャベツを連れた旅人が、川の左岸にやってきた。
川を渡りたいが、使えるボートは自分の他に動物1頭もしくはキャベツ1個しか運べない。
ボートを漕げるのは旅人のみである。
旅人がいないときにオオカミとヒツジを岸に残すと、オオカミがヒツジを食べてしまう。
旅人がいないときにヒツジとキャベツを岸に残すと、ヒツジがキャベツを食べてしまう。
誰も（何も）食べられることなく全員で右岸に渡るにはどうしたらよいか?
川渡り問題として知られる論理パズルクラスの、いちばん古典的かつシンプルなバージョン。元々は「オオカミとヤギとキャベツ」であったが、個人的な好みでヤギの代わりにヒツジにした。wikipediaにも載っているほど有名な問題なので、解答自体はオンラインですぐ検索できるし、論理パズルとしては優しい部類に入るためわざわざProlog上で実装しなくてもすぐ解けるだろう。
厄介なのはヒツジ。放っておくとオオカミに食べられたり、キャベツを食べたり。なので、ヒツジをどのように動かすか（右岸に連れて行ったり、左岸に戻したり）が解答の肝となる。
実行環境
未知の言語であるPrologを勉強するにあたってローカル実行環境を整えるのが億劫だったので、ネットで検索していたら、SWISHなるものを発見。
これはクラウド上でSWI-Prologを実行できる素晴らしいサイト。サイト上でコーディングし、実行することが可能。まだ試していないが、クラウド上にファイルを保存することで、だれでも閲覧可能な状態にすることもできるとのこと。
エディタも（最低限ではあるものの）色分けをしてくれるためありがたい。
ちなみに、SWI-Prologとは、「多くのUNIXやMS-Windows で利用することが出来るエジンバラProlog (DEC-10 Prolog) 記法を採用したProlog処理系であり、ISO規格 にも準拠している」、らしい。（詳細はこちらを参照）
Prologコーディング
いよいよコーディングをはじめる。初心者ということもあり、参考文献で上げた書籍とお気楽 Prolog プログラミング入門; パズル「農夫と狼と山羊とキャベツ」というサイトを参考にした。Prologの情報があまり出回っていない中でとてもお世話になりました。サイトに本稿のパズルの解答コードが載っているため、危うくそのままコピペしそうになる衝動をこらえ、なんとかできる限り自分で実装してみた。
状態の定義
Prologコーディングは「状態の定義」および「状態から状態への推移規則の定義」という流れが基本であるため、まずオオカミとヒツジとキャベツ問題を定式化するための状態を定義する。
ここでは単純に、旅人、オオカミ、ヒツジ、キャベツが各状態においてそれぞれ左岸にいるのか、右岸にいるのかをリストとして表わすことにする。
つまり、[left, right, left, right]という状態は、旅人は左岸、オオカミは右岸、ヒツジは左岸、キャベツは右岸にいる状態を表わす。
これにより、パズルの初期状態が[left, left, left, left]であり、実行可能な推論規則を使ってゴールの状態である[right, right, right, right]へ辿り着くことが、この問題の解答となる。
推移規則の定義
推移規則についてはいくつかの要素に分けることができる。
1. ボートを使った移動によりある状態から次の状態へ推移する規則の定義
2. 旅人の目を盗んでオオカミがヒツジを、ヒツジがキャベツを食べてしまう状況の定義
3. （上記を所与として）どのような条件が満たされると次の状態への推移が成功し、最終的にゴールの状態へとたどり着くことが可能かの定義
4. 出力の定義
1. 移動の定義
移動については、move(元の状態、行動、行動後の状態)という述語で定義する。この述語で元の状態から「ある行動」を選択することにより行動後の状態へと推移することを記述する。
パズルを解くにあたっての一つ注意点は、「何も運ばず旅人のみが移動する」という術語を定義し忘れないことである。これがないとパズルが解けなくなる。
- 何を運ぶか：{何も運ばない、オオカミを運ぶ、ヒツジを運ぶ、キャベツを運ぶ}
- どちらの岸に運ぶか：{右岸に運ぶ、左岸に運ぶ}
により異なるMoveがあるので、下記8つのmoveを定義する。
* お気楽Prologプログラミングではどちらに運ぶかについては術語を分けない形で記述しているため、4つの術語で移動を定義しているが、今回はどちらに運ぶかも明示したかった（アウトプットとして出力したかった）ので8つ定義した。
% 移動
move([left ,W,S,C] , alone2Right, [right,W,S,C] ). % 旅人のみ右岸へ移動
move([right,W,S,C] , alone2Left, [left ,W,S,C] ). % 旅人のみ左岸へ移動
move([left ,W,left,C], sheep2Right, [right,W,right,C] ). % ヒツジを右岸へ移動
move([right,W,right,C], sheep2Left, [left ,W,left,C] ). % ヒツジを左岸へ移動
move([left,left,S,C], wolf2Right, [right,right,S,C] ). % オオカミを右岸へ移動
move([right,right,S,C], wolf2Left, [left,left,S,C] ). % オオカミを左岸へ移動
move([left,W,S,left], cabbage2Right, [right,W,S,right] ). % キャベツを右岸へ移動
move([right,W,S,right], cabbage2Left, [left,W,S,left] ). % キャベツを左岸へ移動
PrologではHTMLと同様、%と/* */でコメントアウトできる。
Prologでは小文字から始まる文字で定数を、大文字から始まる文字で変数を定義する。一つ目のMoveは旅人のみ左岸から右岸へ移動する術語である。元の状態を[left, W, S, C]と定義しているのは、旅人（リスト1つ目の項）は、移動前には左岸にいなければいけないこと、そしてオオカミ、ヒツジ、キャベツは左岸、右岸どちらにいても構わないことをそれぞれ変数W, S, Cで表している。
元の状態からalone2Rightという行動を行うことで行動後の状態[right, W, S, C]へと推移する。注意すべき点として、旅人の状態がleftからrightへ変化した以外は何も変化していない点がある。オオカミ、ヒツジ、キャベツは元の状態、行動後の状態いずれでも「同じ変数」W, S, Cが割り当てられている。これはalone2Rightという行動がオオカミ、ヒツジ、キャベツの状態を変化させない、という制約を表している。この制約を入れないと、alone2Rightという行動がオオカミ、ヒツジ、キャベツの状態に「関わらず」旅人が左岸から右岸へ移動する、という意味になってしまい、例えばオオカミを左岸から右岸へ連れていく、という行動もまたalone2Rightという行動を記述するMove術語において真である、と認識されてしまう。
alone2Rightと同様に他の術語も定義した。
2. 「食べられる」状態の定義
次に、オオカミがヒツジを、ヒツジがキャベツを食べてしまう状態を定義する。この論理パズルを解くためには、何も食べられることなく全てが右岸に移動する必要があるため、ある状態から次の状態に推移した際に、行動後の状態で「食べられる状況」が発生しないことを保証する必要がある。
そのため、まず「食べられる状況」を定義して、それの否定を推移規則の中に埋め込むことにする。（「食べられない状況」を定義してそれを直接埋め込むことでもよいが、個人的には食べられる状況を定義する方が分かりやすいと思ったので、このような形にした）
% 食べられる状況
eatCabbage([H,_,S,C]) :- H \== C, S == C.
eatSheep([H,W,S,_]) :- H \== S, W == S.
eatCabbage([H,_,S,C])とeatSheep([H,W,S,_])という二つの術語で食べられる状況を定義した。コード上の_は無名変数と呼ばれ、コード上で一度しか現れない変数に名前を振ることなく定義できる便利な記号である。（eatCabbage([H,_,S,C])の代わりに、eatCabbage([H,W,S,C])と定義しても特段問題はないが、SWI-Prolog上では「1度しか現れない変数があります！」と注意されるので、極力無名変数を使っている）
eatCabbage([H,_,S,C]) :- H \== C, S == C.の:-は論理学における「ならば（⇒）の左右反転」を表している。:-の右側のカンマは「かつ（∧）」を意味しているため、論理学的には下記のように記載できる。
(H ≠ C) ∧ (S = C) ⇒ eatCabbage([H,_,S,C])
つまり、「旅人がキャベツと同じ岸にいない」かつ「ヒツジがキャベツと同じ岸にいる」ならば「キャベツが食べられる」は真である、ということを定義している。eatSheep([H,W,S,_])も同様に定義した。パズルを解くためには、この2つの術語が「常に偽」となるような状態を維持することが条件となる。
3. ゴールまでの推移の定義
ここのパートが一番Prologらしい部分だと思う。ある状態から最終的にゴールの状態まで正しく推移できるパスを記述する。
% ゴールまでの推移
cross([[Action | State] | History]) :-
State == [right, right, right, right], !,
printAnswer([[Action | State] | History]).
cross([[Action | State] | History]) :-
move(State, NewAction, NewState),
not(eatCabbage(NewState)),
not(eatSheep(NewState)),
not(member([_ | NewState], History)),
cross([[NewAction | NewState], [Action | State] | History]).
cross([[Action | State] | History])というのがゴールまでの推移を記述する術語になる。おなじ術語が2度定義されているが、ここら辺の理解が肝になる。
Prologでは[A|B]でリストの冒頭項目Aとその他残りの項目Bを定義することができるので、[[Action | State] | History]は、下記のようなリストを定義する。
[[行動、行動後の状態]_t,[行動、行動後の状態]_{t-1},[行動、行動後の状態]_{t-2},...]
まず一つ目のcross([[Action | State] | History])で最終状態を定義している。cross[・]が最終状態となるのは、行動後の状態が[right, right, right, right]となる場合なので、右項1行目で最終状態を定義している。その後ろにある!はPrologにおける「カットオペレータ」と呼ばれるもので、カットを活用することで不要なバックトラックを制御することによってコードの実行効率をあげることができる。ここではゴールに辿り着いたことが判明したら、ゴールに辿り着く前の推移規則はスルーするためにカットを利用している。
なお、カットについてはかなり奥深く理解が難しい部分もあるので、こちらの記事なども参照してください。
2行目のprintAnswer([[Action | State] | History])については、ゴールに辿り着いたあと、ゴールまでの軌跡を出力するための術語である。Prologは何もしないと、ゴールに辿り着いたらtrueと出力されて終わってしまうので、どのような経路を経てゴールまでたどり着いたかを明記するためにprintAnswer術語を作成した。詳細は後で定義する。
2つ目のcross([[Action | State] | History])で、最終状態以外の状況を定義している。ここではPrologで非常によく利用される「再帰的定義」を活用している。再帰的定義はちょっと理解が難しいところがあるが、数学的帰納法に考え方が近いため数学的帰納法を念頭に考えると理解が進むと思う。再帰的表現の基本構造を論理学的に表記すると、下記のようになる。
(行動後の状態) ∧ (元の状態から行動後の状態への行動) ⇒ (元の状態)
「行動後の状態」と「元の状態からの推移規則」がいずれも問題ない（真である）ならば、「元の状態」も真である、という推論を記述している。このように状態を再帰的に定義していくことで、現在の状態がゴールへ向かう正しい状態にあるかを推論していくことができる。
再帰的定義の強力な部分は、「何度推論規則を適用しても構わない（ゴールに至るパスがどの程度長いかをあらかじめ定義する必要がない）」点だと思う。この何度でも利用可能な再帰的定義により推論の推論の推論の推論・・・といった一連のプロセスを記述することができ、結果としてコードがシンプルな割に芳醇な推論プロセスを記述できるのだ。
コードの解説に戻るが、move(State, NewAction, NewState)で元の状態から行動後の状態への正しい行動が存在することを保証している。次にnot(eatCabbage(NewState))とnot(eatSheep(NewState))で、行動後の状態でキャベツもヒツジも食べられないことを保証する。eat***(・)の部分で定義したのは「食べられる」状態だったので、not(・)でその否定が真となる状態を記述している。
次のnot(member([_ | NewState], History))は川渡り問題特有の問題に対応した部分で、過去と同じ状態を繰り返す、いわゆる無限ループを避ける術語である。member(a, B)は「aがBの要素に含まれるかどうか」をチェックする関数であり、not(member(a,B))で「aがBに含まれないこと」を確認している。ここで各要素は[行動 | 行動後の状態]で定義されていて、調べたいのは「行動後の状態が、過去に一度も現れなかったか？」なのでnot(member([_ | NewState], History))でそれを確認している。注意点はActionについては不定変数を使う必要がある点であり、これをnot(member([NewAction | NewState], History))としてしまうと、「行動と行動後の状態の『ペア』が過去に一度も現れなかったか？」を確認してしまうことになる。そうすると、行動後の状態が同じだったとしても行動が異なる場合はokとなり、無駄な移動が生成されてしまう可能性がある。（実際はじめは不定変数を使わずコードを書いてしまって、真の解答よりも長いパスの解答を出力してしまった）
最後のcross([[NewAction | NewState], [Action | State] | History])で再帰的表現を定義している。行動後の状態を所与とした場合、そこからゴールまでのパスが存在することを保証している。また、リスト冒頭に[NewAction | NewState]を加えることで、過去の推移を蓄積している。
4. 出力の定義
最後に出力を見やすくするための定義を付けた。
「3. ゴールまでの推移の定義」でも書いた通り、Prologの通常の出力は「true / false」という味気ないものなので、ゴールに至るまでのパスも出力できるようにした。
% 出力
printAnswer([]) :- !.
printAnswer([[Action | State] | Rest]) :-
printAnswer(Rest),
write(Action), write( ' ' ), write( ==> ), write( ' ' ), write(State), nl.
第1行目で出力するものが何もない状況を定義し、その場合には2行目以降をスルーするためカットを追加した。
2行目以降で出力を定義している。リストはゴールからスタートまでを逆順にリスト化しているので、再帰的定義を使って、初期状態からゴールまでの推移を出力できるようにしている。
答え出力
Prologでは上記のような様々な術語を定義したのち、?-の後に質問を記載することでその質問が真となるかどうかを自動で推論してくれる。
SWISHでは質問を記入するコンソールが右下に設けられているため、そこにcross([[start| [left,left,left,left]]])と打ち込むことで探索を開始する。これは[left,left,left,left]という状態からはじめて、[right,right,right,right]に辿り着くパスは存在するか？という質問を投げていることを意味する。初期状態の行動は何でもいいので仮にstartと置いた。
Prologの出力結果は以下である。
?- cross([[start| [left,left,left,left]]])
start ==> [left, left, left, left]
sheep2Right ==> [right, left, right, left]
alone2Left ==> [left, left, right, left]
wolf2Right ==> [right, right, right, left]
sheep2Left ==> [left, right, left, left]
cabbage2Right ==> [right, right, left, right]
alone2Left ==> [left, right, left, right]
sheep2Right ==> [right, right, right, right]
true
1行目で質問を投げかけ、2行目以降が出力結果となる。
2行目で初期状態を定義して、3行目以降、「行動 ==> 行動後の状態」を出力している。
7ステップで全員が右岸に辿り着き、探索を成功で終了している。
論理パズルとしてのポイントは、冒頭でも書いた通りヒツジを頻繁に動かすという点と、2ステップ目と6ステップ目で何も持たずに右岸から左岸へ戻るアクションが必要という点だろう。
簡単な論理パズルを解くのに結構時間がかかったが、Prolog初心者とても勉強になった。
参考文献
コーディングにあたっては下記文献およびサイトを参照した。
- Ivan Bratko(1990)「Prologへの入門 (PrologとAI) 」, 近代科学社
- お気楽 Prolog プログラミング入門; パズル「農夫と狼と山羊とキャベツ」
「お気楽Prologプログラミング入門」のサイトにはコピペするだけで実行できるコードがあるのでそちらも是非参照してください。