nakatani @ cybozu labs

# カレントに 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).

分散ノードを指定して実行した場合、プロセスの構成は以下のようになっています。

manager
 ├server1(self: 'sokoban1@192.168.0.1')
 │ ├ solver1
 │ ├ solver2
 │ └ solver3
 └server2('sokoban2@192.168.0.2')
    ├ solver4
    └ solver5

solver は実際の解法処理を行うプロセスで、start() の第１引数にて指定したプロセス数の分だけ立ち上がります。

solver はまず直上の server に request メッセージを送って問題(枝)を要求、server は手持ちの問題があれば solver に solve メッセージで返し、無ければ manager に request を送って要求します。
manager は request を受け取ったら、別の server に手持ちの問題がないか request を送り、add メッセージで返ってくればそれを要求側に返し( add )、無ければ（タイムアウトしたら）また別の server に問い合わせます。

solver は問題を受け取ったら( solve )、押せる荷物のリストを作成、それぞれの荷物を移動させたものを新しい問題として server に返し( add )、また新しい問題を server に要求します( request )。

主要なメッセージを図示するとこんな感じ。実際には他にも解けた場合のメッセージや、終了する場合のメッセージなどがあります。


solver が受け取るメッセージは solve しかなく、メッセージループが短くてちょうどいいので、簡単に見てみます。

solver_loop(Server, TIMEOUT, COUNT) ->
  receive
    {solve, PRE_BRANCH, Maxsteps, Parcels} ->                   % server から solve 受け取り
      BRANCHES = solve(Server, PRE_BRANCH, Maxsteps, Parcels),  % 解法 -> 新しい枝リスト
      if length(BRANCHES)>0 -> Server ! {add, BRANCHES};        % 新しい枝を server に返す
        true -> pass end,
      Server ! {request, self()},                               % 次の枝を要求
      solver_loop(Server, 1000, COUNT+1)

    after TIMEOUT ->
      erlang:monitor(process, Server),
      receive
        {'DOWN',_,_,_,_} -> exit(self())
      after 500 -> ok
      end,
      Server ! {request, self()},
      solver_loop(Server, TIMEOUT+1000, COUNT)
  end.

solver_loop() の引数は（親 server の Pid、タイムアウト、処理した枝数）となっています。
これらは process dictionary に積んだ方がいいのかなあと思いつつ、Erlang にはステートが無かったんと違ったん？　的疑問から逃れられなくて、引数で持ち回るようにしてしまいました。

receive {solve, PRE_BRANCH, Maxsteps, Parcels} -> で server からの solve メッセージを受け取ります。
PRE_BRANCH の中にマップの現在の状態、プレイヤーの位置、歩数、履歴などが格納されているので、これを solve() にて解かせます。
solve() 関数は解法処理そのものですが、分散まわりとは関係ないので説明省略(笑)。新しい枝のリスト BRANCHES が返ってきますので、これを Server ! {add, BRANCHES} としてサーバに送りつつ、Server ! {request, self()} で新たな問題を request しています。

とても簡単な構造で分散が実現できているのがわかるんじゃないでしょうか。

ちなみに、after は solver がひまひましててタイムアウトした場合の処理です。
主にまだ枝数が少なくて回っていない序盤や、解き終わって処理する枝が残っていない終盤にあたりに仕事が回ってこない可能性があるので、そこら辺を意識した処理が書かれています。


親 server は solver と同じ node 内にありますが、server と manager は別々のノードにあることもあります。
でもこの場合でも相手の Pid さえ持っていれば、メッセージ送信は同じノードか別のノードかを全く意識することなく、 Pid ! message で送ることが出来るので、とてもプログラムしやすかったです(違いはプロセスを起こすときの spawn にノードを指定する引数を付けるか付けないかだけ)。

逆に、困ったのがメッセージの送信そのものは成功・失敗を拾えないところ。エラーハンドリングは対象となるプロセスを別途監視することで行う（監視方法は色々用意されている）のですが、間接的になるため、いろいろなケースを考えると複雑にならざるを得ず。まあ、メッセージ送信そのものについてもハンドリングするとなると、そのIDが必要となり……と今のシンプルなメッセージングがスポイルされてしまう可能性も高いので、難しいところではあります。
でも、同期メッセージとかもあると、やっぱりちょっと嬉しかったかも。