2008年5月13日(火)
15パズルを解かせるプログラムはある程度工夫しても実行時間が かなりかかるものとなる。また、プログラムも少し工夫しないと 同じような記述を何度も繰り返す羽目になるので、前回のハノイの塔 のプログラムでもう少し工夫の方法を練習する。 それから、組み合わせの数が圧倒的に少ない8パズル(15パズルの縮小版)を 題材にプログラミングを始め、最後にそれを15パズルに拡張する方針をとる ことにする。
ここでは、述語を「hanoi1」とする。 まず、何回動かしたかの数を受け取るために引数を一つ増やす。つまり、
hanoi1(円盤の枚数, 棒1, 棒2, 棒3, 移動回数)
とする。そして、単純に考えると円盤が1枚だけの場合は1回動かせば 良いので、移動回数として1となれば良い。あと、再帰で hanoi1が 条件部に含まれる時はそれぞれの移動回数が得られるので、それらの数と、 move の1回を合計したものが移動回数となる。よって以下のように なる(moveの定義は同じなので略す)。
hanoi1(1, A, C, B, 1) :- move(1, A, C).
hanoi1(N, A, C, B, Z) :- N1 is N - 1,
hanoi1(N1, A, B, C, X),
move(N, A, C),
hanoi1(N1, B, C, A, Y),
Z is X + 1 + Y.
基本的にはハノイの塔を攻略する試行錯誤法の手法の延長で15パズルも 解かせることができるが、次のような点に注意が必要である。
まず前者に関しては円盤の動かし方を6通りそれぞれに 規則節を書くのではなく、動かし方そのものを一通りの規則節にまとめ、 どの棒を対象にするかを番号などで与えるように改良する。これをハノイの塔 のプログラムで行ってみる。
前回進めた方法では述語の引数と各棒の状態を対応させていた。この方式は 述語の記述がシンプルでわかり易いが、対象とする棒を一般化するには工夫が必要 となる。そこで、すべての棒の状態を合わせて次のように一つのリストで表すように 変更する。
pole([棒1, 棒2, 棒3], …)
ここで、「…」の部分には前回の深さ（手順の数）の制限を設けたり、 堂々巡りを避けるために増やした引数が入る。例えば、4枚の円盤がすべて 棒1に挿してある場合は、
pole([[1, 2, 3, 4], [], []], …)
のようになる。
Step 1によって棒NがリストのN番目の 要素に対応するようになった(Nは1から始まるとする)。 そこで、次に円盤の移動元と移動先を試行錯誤で選ぶためには、何番目と 何番目がそれぞれ移動元と先になるか、その番号を試行錯誤の際に生成すれば 良い。まず棒の番号は1〜3なので、その番号を生成するだけなら、前回の gennum4を使うこともできるし、1〜3の数値を引数とした事実節を3つ 定義しても良い。または、リストの要素を選び出すmemberを使うことも できる。ここでは、1〜3の番号を生成する述語を num3という名前で 定義するとすれば以下の3通りが少なくとも考えられる。
% gennum4を使う方法
num3(N) :- gennum4(N1, 2), N is N1 + 1. % gennum4は0から生成するので1を加算
% 事実節を3つ定義する方法
num3(1).
num3(2).
num3(3).
% member を使う方法
num3(N) :- member(N, [1, 2, 3]).
これだけでは、1〜3のうちの番号を一つ生成するだけなので、 これを使って移動元、先の番号を生成するような述語を定義する。 その際、その2つの番号は必ず異なるので、
direction(I, J) :- num3(I), num3(J), J \= I.
のようにすれば良い。ただ、実際に使おうとすると、これだけでは足りず、 その回では使わない残りの棒がどれかということも必要になる。そこで、3つの 異なる番号を生成することになる。
direction(I, J, K) :- num3(I), num3(J), J \= I, num3(K), K \= I, K \= J.
なおこれは1〜3から3つを選ぶ順列の生成なので、この方法以外にも 様々な方法が考えられる。
さて、これで候補となる棒の番号まで得られたので、これに基づいて 実際にリストで表現されている状態から対応する各棒を取り出すには、 SWI-Prologに準備されている述語nth1を用いると便利である。 第1引数に要素の番号、第2引数にリスト、第3引数に指定された要素の値 となる。最初の要素は1番である。なお、nth1とほぼ同じ定義 となる述語nthは次のようになる
nth(1, [X| _], X).
nth(N, [_| L], X) :- nth(N1, L, X), N is N1 + 1.
nth1を用いることで、第I番の棒(これもリスト) をリストLから取り出しそれをAに 受け取るには、
nth1(I, L, A)
と書くだけで良い。
試行錯誤でハノイの塔を解かせる場合の1回の移動を示すルールは 一般には次のようになる。
pole(状態, …) :- 深さ制限条件,
移動元と移動先の選択,
移動後の状態の生成,
堂々巡り禁止条件,
pole(移動後の状態, …),
画面表示.
ここで、「移動元と移動先の選択」は既に前のStepで示しているが、3つの 棒それぞれの値を取り出すとすると、次のようになる。
direction(I, J, K), nth1(I, 状態, A), nth1(J, 状態, B), nth1(K, 状態, C)
そして、移動後の3つの棒の状態をそれぞれA1, B1, C1とすれば、 移動後の状態をL1とすると、これは次のように生成できる
L1 = [_, _, _], nth1(I, L1, A1), nth1(J, L1, B1), nth1(K, L1, C1)
なお、ここで棒を表すA/A1, B/B1, C/C1は実際には何番目の棒かが I, J, Kによって決まるのである。また、「L1 = [_, _, _]」 については実際にはなくても良いが表示内容に未決定変数が含まれるのを 避けるために用意している。
あとは、A, B, Cから移動後のA1, B1, C1を導き出せば 良いことになる。directionによって 対応する棒はすべての順列を生成するようになっているので、移動そのもの については一通りだけ表せば良い。そこで、Aから Bに移動 させる場合のみを表現する。するとC = C1であり、あとは Bが空の場合とそうでない場合の2通りを表せば良いので、それを別途 move(A, B, A1, B1)となるような 規則として定義する。
move([A| AL], [], AL, [A]).
move([A| AL], [B| BL], AL, [A, B| BL]) :- A < B.
前Step の内容を組み立てるとまず規則は次のようになる。なお状態を Lとしておく
pole(L, …) :- 深さ制限条件,
direction(I, J, K), nth1(I, L, A), nth1(J, L, B), nth1(K, L, C)
move(A, B, A1, B1),
L1 = [_, _, _], nth1(I, L1, A1), nth1(J, L1, B1), nth1(K, L1, C)
堂々巡り禁止条件,
pole(L1, …),
writeln(pole(L1)).
以上のものに、深さ制限条件とそれに必要な引数(gennum4参照)を つけ、次に堂々巡り禁止条件とそれ用の引数を付与すれば完成である。
深さ制限は既にgennum4などに例が含まれているので、説明を略す。
堂々巡り、すなわち一回動かした円盤を次の段階でまた元に戻すようなことを 阻止しないと試行錯誤の繰返し回数が非常に多くなり、ハノイの塔レベルの問題でも 解くのに時間がかかるようになる。これを禁止するには前の状態を覚えておけば 良い。
前の状態を覚えるにはPrologでは次の2通りの方法がある。
後者の方が効率良くできる場合もあるが、バックトラックとの関係を 十分に考えて設計する必要がある。そこで、ここでは前者の方を用いる ことにする。
これまでに辿ったことのある状態の履歴をリストHとすると、 次の状態L1 がその中にないかどうかを確かめるには
not(member(L1, H))
で良い。これが真になれば、HにはL1が含まれていないことが わかる。で、次の状態について確かめさせるための再帰の際には、
[L1| H]
を新たな履歴として渡してやれば良い。最初の問い合わせでは履歴は 空になるので、空リスト[]を渡すこと。
なお、このようにすると再帰が深くなると履歴のリストが長くなるので、 memberで確かめること自体に時間がかかるようになる。問題の性質に よっては、履歴全部を残していくのではなく、一つ前に戻るのだけを 阻止する方が効率が良いこともあり得る。その場合は、Hに 一つ前の状態を入れることにしておいて、「L1 \= H」を 確かめ、そして再帰の際にはL1を渡してやれば良い。
ここでは8パズルを例に説明するが、縦横の升目の数を別にすれば基本的には 同じ方法でそのまま15パズルに適用できるものである。
8パズルの完成盤面は以下のようになる。
| １ | ２ | ３ |
| ４ | ５ | ６ |
| ７ | ８ |
まずは、この盤面をリストで表現する。最も単純には、左上から各行の順に 駒の番号を並べれば良い。ここで空きになっている升をどう表すかであるが、 「9」を入れても良いが特別な値ということで「0」を入れることにする。つまり、 上の盤面を「[1, 2, 3, 4, 5, 6, 7, 8, 0]」と表す。また、
| １ | ２ | |
| ４ | ５ | ３ |
| ７ | ８ | ６ |
の場合は、「[1, 2, 0, 4, 5, 3, 7, 8, 6]」となる。
実際のパズルでは数字のかかれた駒を滑らせるが、この見方を変え、 空きの升を隣の升の駒と入れ替えると考えれば良い。そうすると、 入れ替えるべき元の升を探すのは、前述のnth1を利用することが できる。つまり盤面を表すリストをLとすると、
nth1(I, L, 0)
とすれば、0が入っているのは何番目の要素なのか、つまり空き升の位置が I に入るわけである。
空き升を隣と入れ替えるわけであるが、四方自由にというわけにはいかない。 そこで、制約を事実と規則で与えることにする。まず移動の制約は升の 位置がどの端にあるのかによって決まるので、上端、左端、右端、下端になる場所 (要素番号)を指定する。例えば、
top(1).
top(2).
top(3).
left(1).
left(4).
left(7).
right(3).
right(6).
right(9).
bottom(7).
bottom(8).
bottom(9).
のようにすればよい。引数の番号は駒の番号ではなく、升の位置を 左上から順に番号付けしたものである。左上が1番、右下が9番となる。
これに基づいて移動の制約、あるいは移動先を算出する規則節を定義する。 例えば、右への移動については右端ではないことが条件になるので、条件として 「not(right(I))」となる。そして右に移動する場合は升の位置を表す番号が 一つ大きくなるので、右への移動可能であることを表す規則は
movable(I, J) :- not(right(I)), J is I + 1.
となる。ここで、movable(I, J)は、第I番の升から第J番の升に移動 可能であることを表す。
以下、同様に左、上下についても定義できる(左の場合は1減らし、 上下は3ずつ増減させることになる)。
ここまでで空き升(値0の升)を特定し、そこから空き升を移動させる先の候補を 選び出すところまでができる。あとは、空き升の移動元と移動先を指定して 入れ替える操作が必要となる。これについてはリスト処理のテクニックの問題 であるので、簡単な考え方と実際に動くプログラム例を示す。
必要なのは、リストにおいて2つの要素の場所を指定して、その要素を 入れ替えるというものである。一気にこれを完成させるのは大変なので、 まず下請けとして、リストのある指定した番号の要素を値を別の値で置き換える replaceという述語を定義する。
replace(1, [B| L], A, [A| L], B).
replace(I, [X| L], A, [X| R], B) :-
I > 1,
I1 is I - 1,
replace(I1, L, A, R, B).
replace(I, L, A, R, B)はリストLの第I番 の要素をAで置き換え、以前に入っていた値が Bに、置き換えた 結果のリストがRに入るというものである。
これを使って定義した次のswap(L, I, J, R)は、 リストLの 第I番と第J番の要素を入れ替え、結果のリストを R に入れるというものである。
swap(L, I, I, L) :- !.
swap(L, I, J, R) :-
I > J, swap(L, J, I, R), !.
swap([A| L], 1, J, [B| R]) :-
J1 is J - 1, replace(J1, L, A, R, B), !.
swap([A| L], I, J, [A| R]) :-
I1 is I - 1, J1 is J - 1,
swap(L, I1, J1, R).
このswapを使えば、盤面の空き升と隣の駒の入れ替えができる。
8パズルの盤面から次の盤面へ遷移する1ステップを表現した規則節の 一般形はつぎのようになる。
述語名(盤面, …) :-
深さ制限条件,
値0の升の場所の特定,
移動先の選定,
升を入れ替えて次の盤面を得る,
堂々巡り禁止条件,
述語名(次の盤面, …),
画面表示.
あとは、最後に到達すべき最後の盤面を事実として次のように与えておく。
述語名([1, 2, 3, 4, 5, 6, 7, 8, 0], …).
なお、深さ制限条件だけでは8パズルの盤面によっては一晩かかっても 解に到達しない場合があるので注意すること。例えば、 「[0, 1, 2, 3, 4, 5, 6, 7, 8]」には22手ほどの 手順が必要でその例にあたる。ただし、堂々巡りを回避すれば数十秒で 解ける。
8パズルから15パズルには単に盤面を 3x3 から 4x4 に変えれば良い。ただし、そのままだと組み合わせの数が増える分だけ 時間がひたすら増えてしまう。盤面の場合の数だけで比較しても 9! と 16! と大きな差があるからである。
そのため、明らかに調べなくても良いパターンなどが簡単に わかるのであれば、その盤面になれば後はやらずに別の盤面にさっさと 移るなどの「枝刈り」が高速化のために重要になる。ここでは、その高速化の ためのヒントをあげておくので、取り組む際には適宜文献などを 調べたり、自分で考えてみること。
15パズルでは16!のすべての盤面から解にたどり着くことが可能には なっていない。半分の盤面で解にたどり着くことが不可能である。以下は その典型的な盤面を示す。
| １ | ２ | ３ | ４ |
| ５ | ６ | ７ | ８ |
| ９ | １０ | １１ | １２ |
| １３ | １５ | １４ |
これはスライドパズルの偶奇性などと呼ばれる性質で、不可能かどうかを 判定するには駒の並びの反転数などを調べる方法がある。 延々と待たされて結局解が得られないというのを避けたければこれによる判定を 組み込むと良い。(なお、組み込まなかった場合、解にたどり着けないと「No」 と表示される。これは指定した手数以内に解にたどり着くことができなかったことを 示す。)
今の状態(盤面)から最後の盤面にたどり着くまでに最低でも何手必要なのか 数えることができれば、それが深さの制限を越えた段階でその盤面から求める のを止めて、別の盤面に取り掛かることができる。
基本的な考え方は以下の通りである。ある駒がxにあったとして、最後の盤面では それはyになければならないとする。そうすると少なくともxからyに移動する分の 手数を経ないと最後の盤面にたどり着くことができないはずである。 この時のxの位置に空き升があったとして、その升をyにまで移動させるのに 必要な手数をマンハッタン距離(ディスタンス)とも呼ぶ。
この必要な手数を各駒に関して計算し、その総和が最後の盤面に達するまで 最低でも必要な手数になるとされる。これによって深さ制限の数に達するまで 試行錯誤する前に望みのない盤面から求める手順を切ることができる。
毎回、各駒の距離を計算して総和するのでは効率が悪過ぎるので、 普通は最初に計算した後は移動による変化を加減して各場面の数とする。
ここまでで深さ制限を設けて、ある手数以内(深さ制限)で15パズルを解くこと が一応できるようなプログラムができる。これを利用して、ある盤面が 与えられた時にそれを解くために必要な最短の手数とその手順を得ることを 最終目標とする。
既に深さ制限を設けているプログラムがあるので、これを使うとある手数以内 に解が求められるかどうか、そして求められた場合はその手順がわかるように なっている。これを利用する。
盤面をメモリ上に展開できるような場合は、展開した上で探索をするのが 効率が良い。しかしながら、15パズルになると盤面が多過ぎるので、 まだ展開するにはメモリが足りない。そこで、反復深化という手法を用いる。
反復深化とは、特に難しいものではなく手数の上限をまずは十分小さいものを 与えて解かせ、とけなければ手数を徐々に増やしていって最初に解けた時の手数を 最短とするものである。すなわちある述語pが引数に 深さ(手数)の上限値と解が得られた時の手数をとるとすれば、一般的に
反復深化(…, 最大値, 必要な手数) :-
gennum4(N, 最大値),
p(…, N, 必要な手数).
のようにすれば良いことになる(「…」はその問題をとくのに必要な パラメータ)。
反復深化法によって、15パズルの盤面を解く最短手順とその手数を求める プログラムを完成させよ。そして完成したプログラムによって以下の盤面を 解く最短手順とその手数を求めよ。
2番目は結構時間がかかるので、注意せよ。まずはもっと簡単な3〜4手で済む例 で確認してから、実行してみること。なお、高速化のためのヒントの部分は 実装していなくても構わない。
レポートには授業名、課題名、学籍番号と氏名を明記し、プログラムと その簡単な説明と使い方、上の二つについてそれぞれの 最短手順とその手数、そしてtime述語で計測したそれを解くまでに かかった時間を明記すること。そして、動作確認用に作成したプログラムの ファイルも添付すること。また、上記以外のより手数が多くかかる盤面に チャレンジした場合はそれについても同様に報告として入れること。
締切はとりあえず6月末日とするが、後半の課題のこともあるので、 早めに済ませることをお奨めする。
提出は阪口宛に電子メールで送付すること。電子メールのSubject(タイトル、 件名)は「REPORT」とすること。なお、レポート本文をMS-Wordなど で作成して添付ファイルとして提出しても良い。ただし、その場合はメールの 本文にも授業名、課題名、学籍番号、氏名を明記すること。
解を解かせる場合に、ログインした状態を維持するのは大変であり、 何らかの原因でセッションが切れると実行も止まってしまう。SWI-Prolog の場合、以下のように実行するとバックグランドで実行できるので、 ログアウトしても止まらない(コマンドのパスを設定したと仮定しているので、 そうでない場合はディレクトリ名から入力すること)。
% nohup pl -s プログラムファイル名 -t 質問式 > ファイル名 2>&1 &
ここで「プログラムファイル名」はProlog のプログラムを保存している ファイル名、「ファイル名」は実行結果を保存するためのファイル名である。 また、「質問式」は「?-」の後に入力する式であり、括弧などが ある場合は全体をシングルクォート(')で囲むこと。
なお、実習室の端末をLinuxで起動して、その端末上で実行した場合、 その端末の電源を切ったり、再起動を行うと全てのプロセスが停止する。 従って、バックグラウンドで実行する場合は、常に稼働しているサーバ icho.ipe.tsukuba.ac.jp にsshでログインし、そこで実行する方が良い。
以上の他、課題遂行にあたって質問・相談などあれば阪口まで