Prolog Programming

反復深化

パズルなどの問題を解く場合、最短手数を求めるのに適したアルゴリズムが 幅優先探索 です。ただし、生成する局面数が多くなると大量のメモリを必要とするため、メモリが不足するときには使うことができない、という欠点があります。逆に、深さ優先探索 の場合、メモリの消費量は少ないのですが、最初に見つかる解が最短手数とは限らない、という問題点があります。

それでは、メモリを大量に使わなくても、最短手数を求めるアルゴリズムはないのでしょうか。実は、とても簡単な方法があるのです。それは、深さ優先探索の「深さ」に上限を設定し、解が見つかるまで上限値を段階的に増やしていく、という方法です。たとえば、1 手で解が見つからない場合は、2 手までを探索し、それでも見つからない場合は 3 手までを探索する、というように上限値を 1 手ずつ増やしていくわけです。この方法を「反復深化 (iterative deeping)」といいます。

反復深化は、幅優先探索と同様に最短手数を求めることができますが、局面を保存する必要がないため大量のメモリを必要としない、という点が長所です。ただし、すでにお気づきの方もいるでしょうが、同じ探索を何度も繰り返すため実行時間が増大する、という欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。

●プログラム

それでは反復深化を使って、積木の移動の最短手順を求めてみましょう。積木の配置は前回と同じです。図を再掲します。

反復深化のプログラムはとても簡単です。設定した上限値まで深さ優先探索を行う述語を作り、上限値を 1 手ずつ増やしてその述語を呼び出せばいいのです。プログラムは次のようになります。

リスト : 反復深化による探索

dfs(Limit, Depth, [State | History]) :-
    Limit == Depth,
    State == [[red, blue], [blue, green], [green, z]], !,
    print_answer([State | History]).

dfs(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,
    dfs(Limit, Depth1, [NewState, State | History]).

述語 dfs の引数 Limit が上限値、Depth が深さ (手数) です。Depth が Limit までいったら、最終状態（ゴール）に到達しているかチェックします。そうでなければ、次の規則で探索を続けますが、Depth が Limit より大きくなった時点で探索を打ち切ります。反復深化の基本はこれだけです。とても簡単ですね。

それから、反復深化では深さが制限されているため、同一局面のチェック check_state を省略してもプログラムは正常に動作します。無駄な探索が行われることになりますが、同一局面のチェックに時間がかかるような場合では、チェックを省略した方がかえって高速に解けることもあります。

最後に、上限値を 1 手ずつ増やすプログラムを作ります。これは述語 between を使えば簡単です。

リスト : 上限値を増やして探索を行う

ids :-
    between(1, 8, N),
    write(N), nl,
    dfs(N, 0, [[[red,blue],[blue,green],[green,x]]]).

述語 between(L, H, V) は、整数 V が L から H の範囲内 (L =< V =< H) であれば真となる述語です。詳しい説明は 繰り返し の「整数値の繰り返し」を読んでください。これでプログラムは完成です。

●実行結果

それでは実行結果を示します。

?- ids.
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]]
true .

?-

5 手で解くことができました。これが最短手順です。この問題は簡単なので、とくに工夫しなくても反復深化で高速に解くことができます。ところが、複雑な問題を反復深化で解く場合、枝刈りを工夫しないと高速に解くことはできません。そこで、「7 パズル」を例題にして、反復深化の常套手段である「下限値枝刈り法」を説明します。

●7 パズル

「7 パズル」は「15 パズル」の変形バージョンです。

     図 1 : 15 パズル

15 パズルは図 1 に示すように、1 から 15 までの駒を並べるパズルです。駒の動かし方は、1 回に 1 個の駒を空いている隣の場所に滑らせる、というものです。駒を跳び越したり持ち上げたりすることはできません。

15 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、16! (約 2e13) 通りもあります。実際には、15 パズルの性質からその半分になるのですが、それでもパソコンで扱うにはあまりにも大きすぎる数です。そこで、盤面を一回り小さくした、1 から 7 までの数字を並べる「7 パズル」を考えることにします。

15 パズルは 4 行 4 列の盤ですが、7 パズルは 2 行 4 列と盤を小さくしたパズルです。7 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、8! = 40,320 通りあります。ところが 15 パズルや 7 パズルの場合、次のことが証明されています。

『適当な 2 つの駒をつまみ上げて交換する動作を偶数回行った局面にした移行できない』

たとえば、上図のゴールで 6 と 7 を入れ替えただけの配置は、交換の回数が奇数回のためゴールに到達することができない、つまり解くことができないのです。このような性質を「偶奇性 (パリティ)」といいます。興味のある方は拙作のページ Puzzle DE Programming: 偶奇性のお話 をお読みください。

したがって、ゴールに到達する局面の総数は 8! / 2 = 20,160 通りとなります。これならば簡単に解くことができそうです。最初に単純な反復深化を使って、スタートからゴールに到達する最短手順を求めてみましょう。

●反復深化による 7 パズルの解法

7 パズルの盤面はリストを使って表します。隣接リストの定義は次のようになります。

リスト : 隣接リストの定義

% 盤面
% 0 1 2 3
% 4 5 6 7

% 隣接リスト
neighbor(0, [1, 4]).
neighbor(1, [0, 2, 5]).
neighbor(2, [1, 3, 6]).
neighbor(3, [2, 7]).
neighbor(4, [0, 5]).
neighbor(5, [1, 4, 6]).
neighbor(6, [2, 5, 7]).
neighbor(7, [3, 6]).

駒の移動は、動かすことができる駒を探すよりも、空き場所を基準に考えた方が簡単です。探索するときは、空き場所の位置を引数に記憶しておきます。そして、新しい局面を作るときは、空き場所に隣接している場所を 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 番目の規則でカットを使って再試行を禁止していることに注意してください。

ここまで作ることができれば、あとのプログラムは簡単です。反復深化による探索は次のようになります。

リスト : 反復深化による探索

dfs(Limit, Limit, State, _, MoveList) :-
    State == [1, 2, 3, 4, 5, 6, 7, 0],
    !,
    reverse(MoveList, [_ | Result]), write(Result), nl.
dfs(Limit, Depth, State, Space, [PrevPiece | MoveList]) :-
    Limit > Depth,
    neighbor(Space, Xs),
    member(Pos, Xs),
    nth0(Pos, State, Piece),
    PrevPiece \== Piece,
    move_piece(Piece, State, NewState),
    Depth1 is Depth + 1,
    dfs(Limit, Depth1, NewState, Pos, [Piece, PrevPiece | MoveList]).

述語 dfs(Limit, Depth, State, Space, MoveList) は、引数が多くてちょっと複雑ですが、内容はそれほど難しくはありません。Limit が反復深化の上限値、Depth が深さ (手数)、State が現在の局面、Space が空き場所の位置、MoveList が動かした駒の履歴を表します。

最初の規則は、手数が上限値に達した場合です。局面 State が最終状態 (ゴール) に到達したら、MoveList を逆順にして移動手順を表示します。MoveList の末尾にはダミーデータ (0) がセットされているので、それを取り除いていることに注意してください。今回は単純に動かす駒を表示するだけです。興味のある方は、この移動手順から局面を再現するプログラムを作ってみてください。

次の規則で、Depth が Limit よりも小さければ、駒を移動して新しい局面を生成します。neighbor と member で空き場所の隣の位置 Pos を求め、Pos にある駒を述語 nth0 で Piece にセットします。

反復深化では深さが制限されているため、同一局面のチェックを行わなくてもプログラムは正常に動作します。そのかわり、無駄な探索はどうしても避けることができません。6 パズルや 15 パズルの場合、1 手前に動かした駒を再度動かすと 2 手前の局面に戻ってしまいます。

完全ではありませんが、このチェックを入れるだけでもかなりの無駄を省くことができます。プログラムでは、MoveList に移動した駒を格納しているので、駒 Piece が 1 手前の駒 PrevPiece と同じ場合は動かさないようにチェックしています。

最後に、上限値を 1 手ずつ増やすプログラムを作ります。

リスト : 上限値を増やして探索を行う

ids :-
    State = [0,7,2,1,4,3,6,5],
    between(1, 36, N), write(N), nl, dfs(N, 0, State, 0, [0]).

最初に dfs を呼び出すとき、MoveList にはダミーとして [ 0 ] を渡すことに注意してください。そうしないとプログラムは動作しません。リストの要素は 1 から 7 以外の値であれば何でもかまいません。それから、空き場所の位置を間違えないように気をつけてくださいね。心配な方はプログラムで求めるように修正してください。

●実行結果

それでは実行結果を示します。

?- time(ids).
1
2
3

・・・省略・・・

34
35
36
[7,2,1,5,6,1,2,7,4,3,1,2,5,6,2,5,7,4,3,1,5,2,6,7,4,3,1,5,2,6,7,4,3,2,6,7]
% 933,677,443 inferences, 96.256 CPU in 96.267 seconds (100% CPU, 9699925 Lips)
true .

?-

• 実行環境 : SWI-Prolog version 8.4.2, Ubunts 22.04 (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz

15 手で解くことができました。実をいうと、7 パズルの最長手数は 36 手で、その配置は 1 通りしかありません。今回の問題は最長手数の盤面です。実行時間は約 97 秒でした。やっぱり、単純な反復深化では時間がかかりますね。そこで、下限値枝刈り法を使って、7 パズルの高速化に挑戦しましょう。

●下限値枝刈り法

下限値枝刈り法は難しいアルゴリズムではありません。たとえば、5 手進めた局面を考えてみます。探索の上限値が 10 手とすると、あと 5 手だけ動かすことができますね。このとき、パズルを解くのに 6 手以上かかることがわかれば、ここで探索を打ち切ることができます。

このように、必要となる最低限の手数が明確にわかる場合、この値を「下限値 (Lower Bound)」と呼びます。この下限値を求めることができれば、「今の移動手数＋下限値」が探索手数を超えた時点で、枝刈りすることが可能になります。これが下限値枝刈り法の基本的な考え方です。

下限値を求める方法ですが、これにはいろいろな方法が考えられます。今回は、各駒が正しい位置へ移動するまでの手数 (移動距離) ^[*1] を下限値として利用することにしましょう。次の図を見てください。

  1  2  3  4  |  0(0)  7(2)  2(1)  1(3) 
  5  6  7  0  |  4(4)  3(2)  6(1)  5(3)

    完成形         初期状態 : 合計 16

        図 : 下限値の求め方

たとえば、右下にある 5 の駒を左上の正しい位置に移動するには、最低でも 3 手必要です。もちろん、ほかの駒との関連で、それ以上の手数が必要になる場合もあるでしょうが、3 手より少なくなることは絶対にありません。同じように、各駒について最低限必要な手数を求めることができます。そして、その合計値はパズルを解くのに最低限必要な手数となります。これを下限値として利用することができます。ちなみに、上図の初期状態の下限値は 16 手になります。

下限値枝刈り法を使う場合、下限値の計算を間違えると正しい解を求めることができなくなります。たとえば、10 手で解ける問題の下限値を 11 手と計算すれば、最短手数を求めることができなくなります。それどころか、10 手の解しかない場合は、答えを求めることすらできなくなります。下限値の計算には十分に注意してください。

●下限値枝刈り法のプログラム

下限値の求め方ですが、駒を動かすたびに各駒の手数を計算していたのでは時間がかかりそうです。7 パズルの場合、1 回に 1 つの駒しか移動しないので、初期状態の下限値を求めておいて、動かした駒の差分だけを計算することにします。各駒の移動手数は述語 distance に定義します。

リスト : 移動手数

distance(1, [0, 1, 2, 3, 1, 2, 3, 4]).
distance(2, [1, 0, 1, 2, 2, 1, 2, 3]).
distance(3, [2, 1, 0, 1, 3, 2, 1, 2]).
distance(4, [3, 2, 1, 0, 4, 3, 2, 1]).
distance(5, [1, 2, 3, 4, 0, 1, 2, 3]).
distance(6, [2, 1, 2, 3, 1, 0, 1, 2]).
distance(7, [3, 2, 1, 2, 2, 1, 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]) を定義して、この規則を省略してもかまいません。お好きな方法を選んでください。

次に、下限値枝刈り法を行う述語 dfs_low を作ります。

リスト : 下限値枝刈り法による反復深化

dfs_low(Limit, Limit, State, _, MoveList, _) :-
    State == [1, 2, 3, 4, 5, 6, 7, 0],
    !,
    reverse(MoveList, [_ | Result]), write(Result), nl.
dfs_low(Limit, Depth, State, Space, [PrevPiece | MoveList], Low) :-
    Limit >= Depth + Low,
    neighbor(Space, Xs),
    member(Pos, Xs),
    nth0(Pos, State, Piece),
    PrevPiece \== Piece,
    move_piece(Piece, State, NewState),
    Depth1 is Depth + 1,
    % 下限値を更新
    distance(Piece, List),
    nth0(Pos, List, N1),
    nth0(Space, List, N2),
    NewLow is Low - N1 + N2,
    dfs_low(Limit, Depth1, NewState, Pos, [Piece, PrevPiece | MoveList], NewLow).

dfs_low の引数 low は局面 State の下限値を表します。そして、Depth + Low が上限値 Limit より大きくなったならば、探索を打ち切ります。あとは、駒を動かして新しい局面 NewState を生成し、その下限値 NewLow を求めるだけです。

最後に、dfs_low を呼び出す述語 ids_low を作ります。

リスト : 上限値を増やして探索を行う

ids_low :-
    State = [0,7,2,1,4,3,6,5],
    calc_distance(0, State, 0, Low),
    between(Low, 36, N), write(N), nl, dfs_low(N, 0, State, 0, [0], Low).

述語 calc_distance で初期状態の下限値 Low を求めます。下限値がわかるのですから、上限値 Limit は 1 手からではなく下限値 Low からスタートすればいいでしょう。

●下限値枝刈り法の効果

それでは実行結果を示します。

?- time(ids_low).
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
[7,2,1,5,6,1,2,7,4,3,1,2,5,6,2,5,7,4,3,1,5,2,6,7,4,3,1,5,2,6,7,4,3,2,6,7]
% 6,086,436 inferences, 0.694 CPU in 0.694 seconds (100% CPU, 8776087 Lips)
true .

?-

実行時間は約 0.7 秒でした。単純な反復深化と比べ約 140 倍の高速化に、M.Hiroi も驚いてしまいました。7 パズルの場合、下限値枝刈り法の効果はとても高いようです。

●プログラムリスト

%
% seven.pl : 7 パズル
%
%            Copyright (C) 2023 Makoto Hiroi
%

% 盤面
% 0 1 2 3
% 4 5 6 7

% 隣接リスト
neighbor(0, [1, 4]).
neighbor(1, [0, 2, 5]).
neighbor(2, [1, 3, 6]).
neighbor(3, [2, 7]).
neighbor(4, [0, 5]).
neighbor(5, [1, 4, 6]).
neighbor(6, [2, 5, 7]).
neighbor(7, [3, 6]).

% 駒の移動
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).

% 反復深化
dfs(Limit, Limit, State, _, MoveList) :-
    State == [1, 2, 3, 4, 5, 6, 7, 0],
    !,
    reverse(MoveList, [_ | Result]), write(Result), nl.
dfs(Limit, Depth, State, Space, [PrevPiece | MoveList]) :-
    Limit > Depth,
    neighbor(Space, Xs),
    member(Pos, Xs),
    nth0(Pos, State, Piece),
    PrevPiece \== Piece,
    move_piece(Piece, State, NewState),
    Depth1 is Depth + 1,
    dfs(Limit, Depth1, NewState, Pos, [Piece, PrevPiece | MoveList]).

ids :-
    State = [0,7,2,1,4,3,6,5],
    between(1, 36, N), write(N), nl, dfs(N, 0, State, 0, [0]).

%
% 下限値枝刈り法
%

% 移動距離
distance(1, [0, 1, 2, 3, 1, 2, 3, 4]).
distance(2, [1, 0, 1, 2, 2, 1, 2, 3]).
distance(3, [2, 1, 0, 1, 3, 2, 1, 2]).
distance(4, [3, 2, 1, 0, 4, 3, 2, 1]).
distance(5, [1, 2, 3, 4, 0, 1, 2, 3]).
distance(6, [2, 1, 2, 3, 1, 0, 1, 2]).
distance(7, [3, 2, 1, 2, 2, 1, 0, 1]).

% 距離の計算
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).

% 反復深化＋下限値枝刈り法
dfs_low(Limit, Limit, State, _, MoveList, _) :-
    State == [1, 2, 3, 4, 5, 6, 7, 0],
    !,
    reverse(MoveList, [_ | Result]), write(Result), nl.
dfs_low(Limit, Depth, State, Space, [PrevPiece | MoveList], Low) :-
    Limit >= Depth + Low,
    neighbor(Space, Xs),
    member(Pos, Xs),
    nth0(Pos, State, Piece),
    PrevPiece \== Piece,
    move_piece(Piece, State, NewState),
    Depth1 is Depth + 1,
    % 下限値を更新
    distance(Piece, List),
    nth0(Pos, List, N1),
    nth0(Space, List, N2),
    NewLow is Low - N1 + N2,
    dfs_low(Limit, Depth1, NewState, Pos, [Piece, PrevPiece | MoveList], NewLow).

ids_low :-
    State = [0,7,2,1,4,3,6,5],
    calc_distance(0, State, 0, Low),
    between(Low, 36, N), write(N), nl, dfs_low(N, 0, State, 0, [0], Low).