Erlang の「軽量プロセス間の非同期 tuple メッセージのやりとりによる分散」というのが今やっていることの色々参考になるんじゃないかという気がして、少し勉強ということで
"Programming Erlang" をせっせと読んでみました。
＃Erlang のメッセージは別に tuple じゃなくてもなんでも送れます。一応念のため。
いきなり余談。"Programming Erlang" の書籍版はまだ出てないんですが、直販で $45.95、amazon.com だと $36.95 なのに、amazon.co.jp だと ￥7264 もするのはなぜ！？ まあ、PDF版 ( $22.50 ) を買ったので関係ないんですが。 （5/18 追記：Amazon に Programming Erlang をリコメンドされたのでふと見てみたら￥4,118 になってました。これなら書籍でも良かったかな～）
ちなみに、PDF 版を購入すると特典として「全ページ」に自分の名前を入れてくれます(笑)。買ってからダウンロードできるまでにえらい時間かかるなあと思ったらそんな事してたのね。
閑話休題。中谷は何か作ってみないとわからない人なので、分散に向いている何か題材は……という頃合いに
こんな記事 を見かけてしまうわけです。
あー大昔に作ったなあ。あの頃は X68000 だったのでメモリがなく、深さ優先で作るしかなかったんだけど、200～300歩クラスの問題なら解けるところまではなんとかたどり着いたなあ（しみじみ）。
というわけで、「分散対応 倉庫番 solver for Erlang」です。
まあ Erlang の勉強の題材としてということなので、単純幅優先＆枝切り無しという solver としてはおもちゃなレベルなんですが、荷物３、４個の問題ならだいたい十数秒クラスで解けます。
注目を浴びている理由の 対C10K なネタじゃなくてすいません(笑)。
ソース：
solver2.erl
関数型言語でまともにコードを書くのは初めてなので(XSLT除く)、おいおいなんだこりゃというところがぽこぽこあるでしょうが、生暖かくスルーするか添削してもらえると嬉しいです……
まずはシングルプロセスでの実行方法。
# カレントに solver2.erl を置いて、erlang を起動
$ erl
% モジュール読み込み
> c(solver2).
% 組み込まれているテスト用問題の解法を実行
% ######
% #@ .#
% # +++#
% # . .#
% ######"
> solver2:test4().
solution: 22 steps ([{5,3,"v"},{4,3,"^"},{4,2,">"},{3,3,"v"}]), goal (3, 3)
solution: 22 steps ([{5,3,"v"},{4,3,"^"},{3,3,"v"},{4,2,">"}]), goal (4, 2)
finish.
% 自分で問題を指定して解法を実行
% ##########
% #@.. # #
% # +++ #
% ##. #####
% ######
% ・制限歩数 50
% ・自ノードで１プロセス実行
% 解法は複数出力されます。最短解法のみコピペ。
> solver2:start( [{self,1}],
> ["##########","#@.. # #","# +++ #","##. #####","###### "],
> 50).
solution: 35 steps ([{4,3,"v"},
{5,3,">"},
{3,3,">"},
{4,4,"<"},
{4,3,"^"},
{6,3,">"},
{7,3,">"},
{8,3,"<"},
{7,3,"<"},
{6,3,"<"},
{5,3,"<"},
{4,2,"<"},
{4,3,"^"}]), goal (4, 3)
問題は下記のように記述します。ちなみに上記問題は自作ｗ
プレイヤー初期位置がゴール上な場合が記述できないですが、まあいいや。
# : 壁
@ : プレイヤー初期位置
+ : 荷物
. : ゴール
* : ゴール上にある荷物
解法結果は（歩数、解法履歴、最終のプレイヤー位置）が出力されます（最終のプレイヤー位置は意味なかったなあ……）。
解法履歴は荷物の座標と、その荷物をどの方向に動かすかで表示されています。座標は左上を（１，１）としています。
では、続いて分散実行の方法。
# マシン２にてノード名とクッキーを指定して erlang 起動
# 以降、マシン２は手を触れる必要はありません。
# マシン２台無ければ同じマシンでも可
$ erl -name sokoban2@192.168.0.2 -setcookie solver
# マシン１にてノード名とクッキーを指定して erlang 起動
# setcookie には上と同じ値を指定
$ erl -name sokoban1@192.168.0.1 -setcookie solver
% マシン１にてモジュール読み込み
> c(solver2).
% マシン１にて分散解法実行
> solver2:start( [{self,1}, {'sokoban2@192.168.0.2',1}],
> ["##########","#@.. # #","# +++ #","##. #####","###### "],
> 50).
start() の第１引数で {ノード名, プロセス数} を列挙することで、指定されたノードにて分散解法が開始されます。モジュールは自動的にマシン１からマシン２に渡されて読み込まれるようになっているので、マシン２は本当に erlang を起動しておくだけでＯＫです。
手元の環境では上記問題は１台実行で１１秒、２台実行で７秒だったので、確かに分散の効果ありありって感じです(笑)。
というわけで、ここからはプログラムの説明。
