パズルなどの問題を解く場合、最短手数を求めるのに適したアルゴリズムが 幅優先探索 です。ただし、生成する局面数が多くなると大量のメモリを必要とするため、メモリが不足するときには使うことができない、という欠点があります。逆に、深さ優先探索 の場合、メモリの消費量は少ないのですが、最初に見つかる解が最短手数とは限らない、という問題点があります。
それでは、メモリを大量に使わなくても、最短手数を求めるアルゴリズムはないのでしょうか。実は、とても簡単な方法があるのです。それは、深さ優先探索の「深さ」に上限を設定し、解が見つかるまで上限値を段階的に増やしていく、という方法です。たとえば、1 手で解が見つからない場合は、2 手までを探索し、それでも見つからない場合は 3 手までを探索する、というように上限値を 1 手ずつ増やしていくわけです。この方法を反復深化 (iterative deeping) といいます。
反復深化は、幅優先探索と同様に最短手数を求めることができますが、局面を保存する必要がないため大量のメモリを必要としない、という点が長所です。ただし、すでにお気づきの方もいるでしょうが、同じ探索を何度も繰り返すため実行時間が増大する、という欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。
それでは反復深化を使って、積木の移動の最短手順を求めてみましょう。積木の配置は前回と同じです。図を再掲します。
■ ■
■ ──→ ■
■ ■
───── ─────
ｘ ｙ ｚ ｘ ｙ ｚ
(初期状態） (最終状態)
図：積木の移動
反復深化のプログラムはとても簡単です。設定した上限値まで深さ優先探索を行う述語を作り、上限値を 1 手ずつ増やしてその述語を呼び出せばいいのです。プログラムは次のようになります。
リスト：反復深化による探索
search_id(Limit, Depth, [State | History]) :-
Limit == Depth,
State == [[red, blue], [blue, green], [green, z]], !,
print_answer([State | History]).
search_id(Limit, Depth, [State | History]) :-
Limit > Depth,
block(B),
not(member([_, B], State)),
move_to(P),
B \== P,
not(member([_, P], State)),
move_block(B, P, State, NewState),
% check_state(NewState, History),
Depth1 is Depth + 1,
search_id(Limit, Depth1, [NewState, State | History]).
引数 Limit が上限値で Depth が深さ（手数）です。Depth が Limit までいったら、最終状態（ゴール）に到達しているかチェックします。そうでなければ、次の規則で探索を続けますが、Depth が Limit より大きくなった時点で探索を打ち切ります。反復深化の基本はこれだけです。とても簡単ですね。
それから、反復深化では深さが制限されているため、同一局面のチェック check_state を省略してもプログラムは正常に動作します。無駄な探索が行われることになりますが、 同一局面のチェックに時間がかかるような場合では、チェックを省略した方がかえって高速に解けることもあります。
最後に、上限値を 1 手ずつ増やすプログラムを作ります。これは述語 between を使えば簡単です。
リスト：上限値を増やして探索を行う
search_main :-
between(1, 8, N),
write(N), nl,
search_id(N, 0, [[[red,blue],[blue,green],[green,x]]]).
述語 between(L, H, V) は、整数 V が L から H の範囲内 (L =< V =< H) であれば真となる述語です。詳しい説明は 繰り返し の「整数値の繰り返し」を読んでください。これでプログラムは完成です。
それでは実行結果を示します。
?- search_main. 1 2 3 4 5 [[red, blue], [blue, green], [green, x]] [[red, y], [blue, green], [green, x]] [[red, y], [blue, red], [green, x]] [[red, y], [blue, red], [green, z]] [[red, y], [blue, green], [green, z]] [[red, blue], [blue, green], [green, z]] Yes
5 手で解くことができました。これが最短手順です。この問題は簡単なので、とくに工夫しなくても反復深化で高速に解くことができます。ところが、複雑な問題を反復深化で解く場合、枝刈りを工夫しないと高速に解くことはできません。そこで、「6 パズル」を例題にして、反復深化の常套手段である下限値枝刈り法を説明します。
「6 パズル」は「15 パズル」の変形バージョンです。六角形に変形した盤面を使って、1 から 6 までの数字を並べます。
４───６ １───２ ０───１
／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼
５───１───３ ──→ ３───４───５ ２───３───４
＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／ ＼ ／
２───０ ６───０ ５───６
(1)初期状態 (2)完成形 (3)座標
図：６パズル
上図は 6 パズルをグラフで表したものです。0 が空き場所を表します。初期状態 (1) では、1, 2, 3 の駒を空き場所に動かすことができます。6 パズルは、単純に考えると駒の配置は 7! = 5040 通りとなります。これならば簡単に解くことができそうです。最初に単純な反復深化を使って、初期状態から完成形に到達する最短手順で求めます。盤面はリストで表し、その位置関係は座標 (3) のように定義します。
まず、お馴染みの隣接関係を定義しましょう。
リスト：隣接関係の定義 next(0, 1). next(0, 2). next(0, 3). next(1, 3). next(1, 4). next(2, 3). next(2, 5). next(3, 4). next(3, 5). next(3, 6). next(4, 6). next(5, 6). neighbor(X, Y) :- next(X, Y). neighbor(X, Y) :- next(Y, X).
駒の移動は、動かすことができる駒を探すよりも、空き場所を基準に考えた方が簡単です。探索するときは、空き場所の位置を引数に記憶しておきます。そして、新しい局面を作るときは、空き場所に隣接している場所を述語 neighbor で求め、そこにある駒を空き場所へ移動させればいいわけです。
次に、駒を移動して新しい局面を作る述語 move_piece を作ります。
リスト：駒を移動する move_piece(_, [], []). move_piece(Piece, [0 | Rest], [Piece | Rest1]) :- move_piece(Piece, Rest, Rest1), !. move_piece(Piece, [Piece | Rest], [0 | Rest1]) :- move_piece(Piece, Rest, Rest1), !. move_piece(Piece, [X | Rest], [X | Rest1]) :- move_piece(Piece, Rest, Rest1).
move_piece(Piece, State, NewState) は、駒 Piece を空き場所へ移動して新しい局面 NewState を作ります。実際の処理は、State を NewState へコピーするときに、Piece と空き場所 0 を交換するだけです。
最初の規則が再帰の停止条件です。次の規則で、空き場所 0 を見つけた場合は、その位置に Piece をセットします。3 番目の規則が Piece を見つけた場合で、その位置に 0 をセットします。それ以外の場合は最後の規則が実行されて、State と同じ要素 X をセットします。
それから、述語 move_piece は再試行する必要がないので、2, 3 番目の規則でカットを使って再試行を禁止していることに注意してください。
ここまで作ることができれば、あとのプログラムは簡単です。反復深化による探索は次のようになります。
リスト：反復深化による探索
search_id(Limit, Limit, State, _, MoveList) :-
State == [1, 2, 3, 4, 5, 6, 0],
!,
reverse(MoveList, Result), write(Result), nl.
search_id(Limit, Depth, State, Space, [PrevPiece | MoveList]) :-
Limit > Depth,
neighbor(Space, Postion),
nth0(Postion, State, Piece),
PrevPiece \== Piece,
move_piece(Piece, State, NewState),
Depth1 is Depth + 1,
search_id(Limit, Depth1, NewState, Postion, [Piece, PrevPiece | MoveList]).
述語 search_id(Limit, Depth, State, Space, MoveList) は、引数が多くてちょっと複雑ですが、内容はそれほど難しくはありません。Limit が反復深化の上限値、Depth が深さ（手数）、State が現在の局面、Space が空き場所の位置、MoveList が動かした駒の履歴を表します。
最初の規則が、上限値に達した場合です。局面 State が最終状態（ゴール）に到達したら、MoveList を逆順にして移動手順を表示します。今回は単純に動かす駒を表示するだけです。興味のある方は、この移動手順から局面を再現するプログラムを作ってみてください。
次の規則で、Depth が Limit よりも小さければ、駒を移動して新しい局面を生成します。述語 neighbor で空き場所の隣 Postion を求め、その位置にある駒を述語 nth0 で Piece にセットします。
反復深化では深さが制限されているため、同一局面のチェックを行わなくてもプログラムは正常に動作します。そのかわり、無駄な探索はどうしても避けることができません。6 パズルや 15 パズルの場合、1 手前に動かした駒を再度動かすと 2 手前の局面に戻ってしまいます。完全ではありませんが、このチェックを入れるだけでもかなりの無駄を省くことができます。プログラムでは、MoveList に移動した駒を格納しているので、駒 Piece が 1 手前の駒 PrevPiece と同じ場合は動かさないようにチェックしています。
最後に、上限値を 1 手ずつ増やすプログラムを作ります。
リスト：上限値を増やして探索を行う
search_main :-
State = [4,6,5,1,3,2,0],
between(Low, 16, N), write(N), nl, search_id(N, 0, State, 6, [0]).
最初に search_id を呼び出すとき、MoveList にはダミーとして [ 0 ] を渡すことに注意してください。そうしないとプログラムは動作しません。リストの要素は 1 から 6 以外の値であれば何でもかまいません。それから、空き場所の位置を間違えないように気をつけてくださいね。心配な方はプログラムで求めるように修正してください。
それでは実行結果を示します。実行マシンはあいかわらずのオンボロ (Pentium 166 MHz) です。
?- time(search_main). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [0, 1, 3, 1, 2, 5, 3, 6, 1, 2, 5, 6, 4, 1, 2, 5] Yes
15 手で解くことができました。実をいうと、6 パズルの最長手数は 15 手で、配置は全部で 24 通りあります。問題はその中のひとつです。実行時間は約 234 秒でした。やっぱり、単純な反復深化では時間がかかりますね。そこで、下限値枝刈り法を使って、6 パズルの高速化に挑戦しましょう。
下限値枝刈り法は難しいアルゴリズムではありません。たとえば、5 手進めた局面を考えてみます。探索の上限値が 10 手とすると、あと 5 手だけ動かすことができますね。このとき、パズルを解くのに 6 手以上かかることがわかれば、ここで探索を打ち切ることができます。
このように、必要となる最低限の手数が明確にわかる場合、この値を下限値 (Lower Bound) と呼びます。この下限値を求めることができれば、「今の移動手数＋下限値」が探索手数を超えた時点で、枝刈りすることが可能になります。これが下限値枝刈り法の基本的な考え方です。
下限値を求める方法はいろいろありますが、今回は各駒が正しい位置へ移動するまでの手数を下限値として利用することにしましょう。次の図を見てください。
4(1)───6(2) １───２
／ ＼ ／ ＼ ／ ＼ ／ ＼
5(2)───1(1)───3(2) ──→ ３───４───５
＼ ／ ＼ ／ ＼ ／ ＼ ／
2(2)─── ０ ６───０
(1)初期状態(下限値 10 手) (2)完成形
図：下限値の求め方
たとえば、右上にある 6 の駒を左下の正しい位置へ移動するには、最低でも 2 手必要です。もちろん、ほかの駒との関連で、それ以上の手数が必要になる場合もあるでしょうが、2 手より少なくなることは絶対にありません。同じように、各駒について最低限必要な手数を求めることができます。そして、その合計値はパズルを解くのに最低限必要な手数、つまり下限値として利用することができます。ちなみに、上図の初期状態の下限値は 10 手になります。
下限値の求め方ですが、駒を動かすたびに各駒の手数を計算していたのでは時間がかかりそうです。6 パズルの場合、1 回にひとつの駒しか移動しないので、初期状態の下限値を求めておいて、動かした駒の差分だけを計算することにします。各駒の移動手数は述語 distance に定義します。
リスト：移動手数 distance(1, [0,1,1,1,2,2,2]). distance(2, [1,0,2,1,1,2,2]). distance(3, [1,2,0,1,2,1,2]). distance(4, [1,1,1,0,1,1,1]). distance(5, [2,1,2,1,0,2,1]). distance(6, [2,2,1,1,2,0,1]).
上リストを見てください。distacne の第 1 引数が駒の種類、第 2 引数はリストでそれぞれの位置での移動手数を表しています。
駒 Piece を空き場所 Space に動かす場合、下限値は次のように求めることができます。
リスト：下限値の求め方 distance(Piece, List), nth0(Postion, List, N1), nth0(Space, List, N2), NewLow is Low - N1 + N2,
Postion は駒の位置を表し、Low が下限値を表します。駒 Piece の移動手数リストを distance で求めます。そして、位置 Postion と Space での移動手数を、述語 nth0 を使って N1 と N2 に求めます。あとは、N1 と N2 の差分を計算すれば新しい下限値 NewLow を求めることができます。
次は、初期状態の下限値を求める述語 calc_distance を作ります。次のリストを見てください。
リスト：移動手数を計算
calc_distance(_, [], MD, MD).
calc_distance(N, [0 | Rest], MD, Z) :-
N1 is N + 1,
calc_distance(N1, Rest, MD, Z).
calc_distance(N, [Piece | Rest], MD, Z) :-
distance(Piece, List),
nth0(N, List, D),
MD1 is MD + D,
N1 is N + 1,
calc_distance(N1, Rest, MD1, Z).
第 1 引数 N が位置を表し、第 2 引数が盤面を表すリストです。リストの先頭から順番に駒を取り出して移動手数を求め、それを第 3 引数に足し算します。空き場所 0 は移動手数を求める必要がないので、2 番目の規則でスキップします。もしくは、述語 distance にダミーデータ distance(0, [0,0,0,0,0,0,0]) を定義して、この規則を省略してもかまいません。お好きな方法を選んでください。
次に、下限値枝刈り法を行う述語 search_low を作ります。
リスト：下限値枝刈り法による反復深化
search_low(Limit, Limit, State, _, MoveList, _) :-
State == [1, 2, 3, 4, 5, 6, 0],
!,
reverse(MoveList, Result), write(Result), nl.
search_low(Limit, Depth, State, Space, [PrevPiece | MoveList], Low) :-
Limit >= Depth + Low,
neighbor(Space, Postion),
nth0(Postion, State, Piece),
PrevPiece \== Piece,
move_piece(Piece, State, NewState),
Depth1 is Depth + 1,
/* 下限値を更新 */
distance(Piece, List),
nth0(Postion, List, N1),
nth0(Space, List, N2),
NewLow is Low - N1 + N2,
search_low(Limit, Depth1, NewState, Postion, [Piece, PrevPiece | MoveList], NewLow).
search_low の引数 low は局面 State の下限値を表します。そして、Depth + Low が上限値 Limit より大きくなったならば、探索を打ち切ります。あとは、駒を動かして新しい局面 NewState を生成し、その下限値 NewLow を求めるだけです。
最後に、search_low を呼び出す述語 search_main を作ります。
リスト：上限値を増やして探索を行う
search_main :-
State = [4,6,5,1,3,2,0],
calc_distance(0, State, 0, Low),
between(Low, 16, N), write(N), nl, search_low(N, 0, State, 6, [0], Low).
述語 calc_distance で初期状態の下限値 Low を求めます。下限値がわかるのですから、上限値 Limit は 1 手からではなく下限値 Low からスタートすればいいでしょう。
それでは実行結果を示します。
?- search_main. 10 11 12 13 14 15 [0, 1, 3, 1, 2, 5, 3, 6, 1, 2, 5, 6, 4, 1, 2, 5] Yes
実行時間は Pentium 166 MHz で約 0.2 秒でした。単純な反復深化と比べて 1000 倍以上の高速化に、M.Hiroi も驚いてしまいました。6 パズルの場合、下限値枝刈り法の効果は極めて高いようです。
もっと大きなパズル、たとえば 8 パズルになると最長手数は 31 手で、下図に示す 2 つの局面があります。
┌─┬─┬─┐ ┌─┬─┬─┐
│８│６│７│ │６│４│７│
├─┼─┼─┤ ├─┼─┼─┤
│２│５│４│ │８│５│ │
├─┼─┼─┤ ├─┼─┼─┤
│３│ │１│ │３│２│１│
└─┴─┴─┘ └─┴─┴─┘
図：31 手で解ける局面
この局面を同じ下限値を使って解いてみると、SWI-Prolog で左の局面が約 11 秒、右の局面が約 20 秒でした。下限値の求め方は単純ですが、8 パズルでも十分に効果がありますね。8 パズルの最長手数については、Puzzle DE Programming の 幅優先探索の高速化(1) をご覧ください。
15 パズルになると、インタプリタでは時間がかかるので、Ｃ言語などのコンパイラでプログラムを作成します。ただし、今回説明した移動手数を下限値とする方法では、局面によっては非常に時間がかかる場合があります。15 パズルを高速に解くには、下限値の精度を高める工夫が必要になります。
15 パズルの解法は、高橋謙一郎さんが精力的に取り組まれていて、その成果は高橋さんの Web ページ コンピュータ＆パズル の １５パズル自動解答プログラムの作り方 で公開されています。高橋さんは精度の高い下限値を求めるため、ID (Invert Distance) や WD (Walking Distance) という新しい方法を考案され、それらを使った解法プログラムは抜群の性能を発揮しています。15 パズルの解法に興味のある方はぜひ参考にしてください。