29-3. 論理プログラミング言語「Prolog」（その３：グラコロバーガーの合成で学ぶ探索の基本形）

数理モデル / 論理

2021/12/01

概要
参考文献
探索の基本形
グラコロバーガーの合成
おわりに

概要

前回まではPrologをPythonで再現しながら学んでいましたが、早くもPythonでの再現を諦めました。今回はPrologで探索を学びます。

参考文献

Ivan Bratko(著)、安部憲広(翻訳)『Prologへの入門 (PrologとAI)』近代科学社

探索の基本形

次のようなゲームを考えます。

２つのスイッチをONにすると宝箱が下りてきて、centerで受け取れます。

Prologで次のように書きます。

/* 終了条件 */
check(state(center,on,on)).

/* 優先順位の高い動作から順に定義 */
action(state(left,off,X),
       push,
       state(left,on,X)).
action(state(right,X,off),
       push,
       state(right,X,on)).
action(state(_,X,Y),
       walk,
       state(_,X,Y)).

/* 再帰的探索 */
check(State1):-
  action(State1,_,State2),
  check(State2).

上から順に参照されるため、まず終了条件を書きます。

/* 終了条件 */
check(state(center,on,on)).

state(自分の位置, 左スイッチの状態, 右スイッチの状態) を表しており、どういう条件が揃えばクリアかを定義します。この状態にマッチすればYesを返して探索が終了します。

次に状態を変化させる行動を列挙します。

/* 優先順位の高い動作から順に定義 */
action(state(left,off,X),
       push,
       state(left,on,X)).
action(state(right,X,off),
       push,
       state(right,X,on)).
action(state(_,X,Y),
       walk,
       state(_,X,Y)).

このとき、優先度の高い行動を上に書くようにします。walkが上にあると永遠に歩き続ける無限ループになってしまいます。（同じ道を２度通らないように設計すればその限りではありませんが、今回は最小コードなので）

また、アンダーバーの使い方には注意が必要です。アンダーバーは任意の状態ですので、うっかりした箇所にアンダーバーを使ってしまうとゴールまで近道してしまいます。任意ではない箇所にはXのような変数を指定します。

最後に探索を行う再帰的な処理を書きます。

/* 再帰的探索 */
check(State1):-
  action(State1,_,State2),
  check(State2).

一連のコードは、正直なところ三日三晩にらめっこしても意味を解釈できませんでしたので、こういう定型文なんだと思うことにしました。このあたりが納得できる教科書があれば教えてください。

実行コマンドは次です。

/* 実行コマンド（ゴールできるか？） */
?- check(state(center,off,off)).

yes

初期状態を与え、「ゴールできる経路があるか？」というYes/No質問しています。終了条件にマッチすればYesが返ってきます。

さて、途中の経路を確認するには「trace.」でデバッグモードに入ってから実行します。

?- trace.
?- check(state(center,off,off)).

（前略）
  Match   : check(state(center,on,on)).
 [8] 5 Succ  : check(state(center,on,on))
 [7] 4 Succ  : check(state(right,on,on))
 [5] 3 Succ  : check(state(right,on,off))
 [4] 2 Succ  : check(state(left,on,off))
 [2] 1 Succ  : check(state(left,off,off))
 [1] 0 Succ  : check(state(center,off,off))
yes

下から読んでいくと、期待通りに行動していることが分かります。

グラコロバーガーの合成

次に、グラコロバーガーの合成経路を探索してみましょう。グラコロバーガーには小麦粉が多く使われていることが知られています。

次のように書きます。stateは(小麦粉,塩,パン,マカロニ,グラタン,グラコロ,グラコロバーガー) を意味しており、それぞれ所持していればその名称が、なければnoneが入ります。

/* 終了条件 */
check(state(_,_,_,_,_,_,gurakoroburger)).

/* 優先順位の高い動作から順に定義 */
/* グラコロバーガー */
action(state(A,B,bread,C,D,gurakoro,none),
       cook,
       state(A,B,none,C,D,none,gurakoroburger)).
/* グラコロ */
action(state(A,B,bread,C,gratin,none,D),
       cook,
       state(A,B,none,C,none,gurakoro,D)).
/* グラタン */
action(state(flour,salt,A,macaroni,none,B,C),
       cook,
       state(none,none,A,none,gratin,B,C)).
/* マカロニ */
action(state(flour,salt,A,none,B,C,D),
       cook,
       state(none,none,A,macaroni,B,C,D)).
/* パン */
action(state(flour,salt,none,A,B,C,D),
       cook,
       state(none,none,bread,A,B,C,D)).
/* 食材調達 */
action(state(none,A,B,C,D,E,F),
       get,
       state(flour,A,B,C,D,E,F)).
action(state(A,none,B,C,D,E,F),
       get,
       state(A,salt,B,C,D,E,F)).

/* 再帰的探索 */
check(State1):-
  action(State1,_,State2),
  check(State2).

何も所持していない状態から実行します。

?- trace.
?- check(state(none,none,none,none,none,none,none)).

  Match   : check(state(none,none,none,macaroni,gratin,none,gurakoroburger)).
 [40] 23 Succ  : check(state(none,none,none,macaroni,gratin,none,gurakoroburger))
 [38] 22 Succ  : check(state(none,none,bread,macaroni,gratin,gurakoro,none))
 [36] 21 Succ  : check(state(flour,salt,none,macaroni,gratin,gurakoro,none))
 [35] 20 Succ  : check(state(flour,none,none,macaroni,gratin,gurakoro,none))
 [33] 19 Succ  : check(state(none,none,none,macaroni,gratin,gurakoro,none))
 [31] 18 Succ  : check(state(flour,salt,none,none,gratin,gurakoro,none))
 [30] 17 Succ  : check(state(flour,none,none,none,gratin,gurakoro,none))
 [28] 16 Succ  : check(state(none,none,none,none,gratin,gurakoro,none))
 [26] 15 Succ  : check(state(flour,salt,none,macaroni,none,gurakoro,none))
 [25] 14 Succ  : check(state(flour,none,none,macaroni,none,gurakoro,none))
 [23] 13 Succ  : check(state(none,none,none,macaroni,none,gurakoro,none))
 [21] 12 Succ  : check(state(none,none,bread,macaroni,gratin,none,none))
 [19] 11 Succ  : check(state(flour,salt,none,macaroni,gratin,none,none))
 [18] 10 Succ  : check(state(flour,none,none,macaroni,gratin,none,none))
 [16] 9 Succ  : check(state(none,none,none,macaroni,gratin,none,none))
 [14] 8 Succ  : check(state(flour,salt,none,none,gratin,none,none))
 [13] 7 Succ  : check(state(flour,none,none,none,gratin,none,none))
 [11] 6 Succ  : check(state(none,none,none,none,gratin,none,none))
 [9] 5 Succ  : check(state(flour,salt,none,macaroni,none,none,none))
 [8] 4 Succ  : check(state(flour,none,none,macaroni,none,none,none))
 [6] 3 Succ  : check(state(none,none,none,macaroni,none,none,none))
 [4] 2 Succ  : check(state(flour,salt,none,none,none,none,none))
 [3] 1 Succ  : check(state(flour,none,none,none,none,none,none))
 [1] 0 Succ  : check(state(none,none,none,none,none,none,none))
yes

下から読んでいくと、余計なものを作りながらも、グラコロバーガーを完成させています。

なお、材料の無駄がないように終了条件を以下に変更すると探索に数秒かかり、一晩中 trace. しても追いきれないくらいの探索量になりました。（LOOP = 6433813）

/* 終了条件 */
check(state(none,none,none,none,none,none,gurakoroburger)).

?- leash1(s), trace.   % トレースの自動スクロール＋出力をSuccのみに限定
?- check(state(none,none,none,none,none,none,none)).

おわりに

今回は「探索」の基本形を確認しました。次回があるかどうかは未定です。