筆者：村田
こんにちは。
カニ坂RockFesという地元福生の音楽イベントに遊びに行ってきました。多摩川河川敷で開催され、今年で32回目だそうです。雨が心配でしたが、なんとか曇空をキープしてくれました。夏の終わりにしては涼しすぎる週末でしたが熱い演奏を楽しみました。メインステージのバンド演奏だけでなく、小さなテントでフォーク演奏もやっていて、これもまたフェスっぽくて良かったです。
さて、さめがめの続きなのですが、前回のプログラムにはバグがありました。どういうことか、前回作ったneighbor/5をテストしてみましょう。
?- board(B), neighbor(B, 0, 0, [], N).
B = [[g, b, r], [g, g, r], [r, b, b]],
N = [ (0, 0), (1, 1), (0, 1)]
と、ここまでは良かったのですが、実は上記結果はバックトラックします。一つ目の結果が出力された後、";"を入力すると次の結果が表示されます。
?- board(B), neighbor(B, 0, 0, [], N).
B = [[g, b, r], [g, g, r], [r, b, b]],
N = [ (0, 0), (1, 1), (0, 1)] ; %% <- ここで";"を入力
B = [[g, b, r], [g, g, r], [r, b, b]],
N = [ (1, 1), (0, 1)] %% <- バックトラック
２つ目の結果は誤った答えです。neighbor/5は指定したコマの隣接コマを返してくれる述語ですが、複数の答えはあり得ず、答えは一つでなければなりません。なぜこうなってしまうのか。バックトラックについてはPart1でも少し触れていますが、もう一度復習しましょう。例えば以下のような述語familyがあった場合、
family(sazae).
family(masuo).
family(tarao).
家族は何か？の問いの答えをバックトラックで求めることができます。
?- family(X).
X = sazae ; %% <- ";"を入力
X = masuo ; %% <- ";"を入力
X = tarao.
Prologがsazaeという答えを見つけてくれた後、他にもfamily(X)を満たすXが無いか探しにいってくれるのがバックトラックです。
では、neighbor/6の定義のどこに原因があるのが見てみます。例えばneighbor/6呼び出し時の第1引数が"l"の場合に、
neighbor(l, Board, X, Y, Crumb, Neighbor) %% ①
という定義①にパターンマッチするだけでなく
neighbor(_, _, _, _, Neighbor, Neighbor). %% ②
という番兵用に用意していた定義②にもマッチしてしまいます。②は①がマッチしなかった場合に、エラーとならないように定義したものです。しかし、バックトラックが動いてしまったことで、①にマッチしたにもかかわらず、②にも余計にマッチしてしまうという問題が発生したのです。"_"は何にでもマッチしてしまうので、こういう思わぬバックトラックを引き起こしやすいので要注意です。
それでは対処を考えます。②の定義は番兵としての役割があるので削除するわけにはいきません。バックトラックを抑制することで対処したいと思います。バックトラックは「カット」という"!"記号を用いることで抑制することができます。例として、先のfamily定義を以下のように直してみましょう。
family(sazae).
family(masuo) :- !. %% <- カットしてみる
family(tarao).
すると以下のように
?- family(X).
X = sazae ;
X = masuo.
sazaeにマッチした後はバックトラックしてmasuoにもマッチしますが、masuoにマッチした後はバックトラックが抑制され以降のマッチは発生しなくなります。
カットを理解したところで、neighborのどこにカットを入れるのが良いでしょうか。以下のようにneighbor/6の最後にカットを入れてみましょう。これで適切なNeighborが見つかった後にバックトラックしてしまうことを防げます。
%% 左側に同じコマがあるかチェック
neighbor(l, Board, X, Y, Crumb, Neighbor) :-
X1 is X - 1,
not(member((X1,Y), Crumb)),
piece(Board, X, Y, P),
piece(Board, X1, Y, P),
neighbor(Board, X1, Y, [(X1,Y)|Crumb], Neighbor), !.
これは素直な対処でわかりやすいですが、neighbor(r, ...)、neighbor(u, ...)、neighbor(d, ...)にも同様にカットを入れる必要があります。それよりも以下のようにneighbor/5にカットを入れれば1箇所の修正で済みます。
%% 上下左右に同じコマがあるか再帰チェック
neighbor(Board, X, Y, Crumb, Neighbor) :-
neighbor(l, Board, X, Y, Crumb, Crumb1),
neighbor(r, Board, X, Y, Crumb1, Crumb2),
neighbor(u, Board, X, Y, Crumb2, Crumb3),
neighbor(d, Board, X, Y, Crumb3, Neighbor), !.
なお、どこにカットを入れるべきかを判断するのは慣れないと難しいかもしれません。いくつかカットを入れてみて動きを観察したり、バックトラックがどういう経緯で発生したのかをじっくり考えることが大切です。では修正版neighbor/5をテストしてみましょう。
?- board(B), neighbor(B, 0, 0, [], N).
B = [[g, b, r], [g, g, r], [r, b, b]],
N = [ (0, 0), (1, 1), (0, 1)].
今度はバックトラックせずに唯一の解を見つけてくれました。
ここまでで隣接コマをリストで取得することができるようになりました。ところで、隣接コマは[(0, 0), (1, 1), (0, 1)]のようにXY座標で表現されているのに対し、ボード上のコマは[[g, b, r], [g, g, r], [r, b, b]]のようにコマの色で表現されています。ボード上のコマもXY座標で表現できるようにしましょう。(次回の記事で使う予定です)
インタフェースは盤面(Board)をもらって座標リスト(PosList)を返すようにします。
poslist(Board, PosList) :- ...
この述語はBoardが２次元配列ですので、２重ループ構造になります。まずは内側の列(X)に対するループから書くと考えやすいでしょう。コマを座標に置き換えるわけですが、順番に置き換えるので、X座標もY座標もループのインデックスそのものです。したがって引数からもらうようにしましょう。それと、以下の第１項のパターンマッチを[_|T]とし、H要素を捨てている理由は、コマ自身が何か(r/g/b)は座標に関係ないためです。
poslist([_|T], X, Y, [(X,Y)|PosList]) :-
X1 is X + 1,
poslist(T, X1, Y, PosList). %% Xインデックスを増やしながら回す
poslist([], _, _, []). %% 末尾[]にマッチする番兵
次に外側の行(Y)に対するループを考えます。
poslist([H|T], Y, PosList) :-
poslist(H, 0, Y, PosList1), %% 各行は上で定義したposlist/4を使用
Y1 is Y + 1,
poslist(T, Y1, PosList2),
append(PosList1, PosList2, PosList).
poslist([], _, []).
ポイントは最後にappendを使う点です。簡単な例でその必要性を考えてみます。List1=[1,2,3], List2=[] としたとき、appendを使わず[List1|List2]とするとどうなるでしょうか。
List = [List1|List2].
List = [[1,2,3]].
このようにListは２次元リストになってしまいます。appendを使うと
append(List1, List2, List).
List = [1,2,3].
このように1次元リストになります。今回は盤面上のコマの位置を１次元リストで欲しいのでappendを使います。おっと、poslistの呼び出し口となるposlist/2の定義が途中でした。
poslist(Board, PosList) :-
poslist(Board, 0, PosList). %% Y=0からループ開始
それではテストしてみます。
?- board(B), poslist(B, L).
B = [[g, b, r], [g, g, r], [r, b, b]],
L = [ (0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (..., ...)].
Prologが長いリストを省略表示していますが、最初の6つくらいを見ると3x3ボード上のコマをXY座標で表していることが分かると思います。
最後はボードからコマを削除する述語を作ります。コマはリストで与えることにします。まずはインタフェースを考えます。
remove(Board, DeleteList, RemovedBoard) :-
こちらも行と列の２重ループ構造になります。列(X)のループを考えましょう。まずは削除リストに含まれない場合の定義を見てください。
remove([H|T], DeleteList, X, Y, [H|RemovedLine]) :-
not(member((X,Y), DeleteList)), %% 削除リストに含まれない
X1 is X + 1,
remove(T, DeleteList, X1, Y, RemovedLine).
not(member(...))によって削除リストに含まれない場合は、第１項のHを戻り値である第５項に含めてます。すなわち削除しないということです。次に削除リストに含まれる場合の定義を見てください。
remove([_|T], DeleteList, X, Y, RemoveLine) :-
member((X,Y), DeleteList), %% 削除リストに含まれる
X1 is X + 1,
remove(T, DeleteList, X1, Y, RemovedLine).
こちらは第１項のHを第５項に含めず、削除しています。行末の番兵も定義しておきましょう。
remove([], _, _, _, []).
どんどんいきます。行(Y)のループを書いてみます。
remove([Line|TailBoard], DeleteList, Y, [RemovedLine|RemovedBoard]) :-
%% 行の中の削除対象コマを削除する
remove(Line, DeleteList, 0, Y, RemovedLine),
Y1 is Y + 1,
remove(TailBoard, DeleteList, Y1, RemovedBoard). %% 次の行へ
remove([], _, _, []). %% ボード終端にマッチする番兵
こちらは変数名を[H|T]よりも分かりやすい名前にしました。忘れずに行ループの入り口となるremove/3も定義しておきましょう。
remove(Board, DeleteList, RemovedBoard) :-
remove(Board, DeleteList, 0, RemovedBoard).
ではテストしてみます。いつもの3x3ボードに対し、"g"の位置を手動で指定して削除してみましょう。
?- board(B), remove(B, [(0,0), (0,1), (1,1)], R).
B = [[g, b, r], [g, g, r], [r, b, b]],
R = [[b, r], [r], [r, b, b]]
"g"を削除できたようですね。さて一見うまくいっているようですが、これでは不十分です。さめがめのルールを思い出しましょう。縦一列の全てのコマが消えたら、その列の右側のコマが左にスライドするのでした。これをremove/3で表現したいのです。今のコードのままで、例えば1行目が全て消えたとしましょう。
?- board(B), remove(B, [(0,0), (1,0), (2,0)], R).
B = [[g, b, r], [g, g, r], [r, b, b]],
R = [[], [g, g, r], [r, b, b]]
結果(R)の1個目が空リストとして残ってしまうためにスライドしていません。というわけで空リストを削除しましょう。リストから要素を削除するdelete/3という述語があります。
?- delete([1, a, 3], a, R).
R = [1, 3].
これを使ってremove/3の最後で[]を除去してみましょう。
remove(Board, DeleteList, RemovedBoard) :-
remove(Board, DeleteList, 0, RemovedBoard1),
delete(RemoveBoard1, [], RemoveBoard).
もう一度同じように1行目を全て消してみます。
?- board(B), remove(B, [(0,0), (1,0), (2,0)], R).
B = [[g, b, r], [g, g, r], [r, b, b]],
R = [[g, g, r], [r, b, b]]
削除後にきちんとリストが縮まり、さめがめのスライドのようになりました。
今回はここまでにします。それにしても猛暑から一転、涼しいというか肌寒いくらいですね。皆さん風邪など引かぬよう。
以上。
