前回の倉庫番solver for Erlang は Erlang の勉強のためだった割には Erlang の良さを活かしていないつくりだったので、もう少しまじめに作り直してみました。
ソース： solver3.erl
今回はひとまず分散は置いといて、軽量プロセスの恩恵を発揮させる方向で攻めています。
プロセスの構造は manager と solver の２種類だけ、やりとりされるメッセージは基本的には solver → manager の branch メッセージだけという簡単なものに。
manager は branch メッセージを受け取ったら、最大歩数を超えてないか、解けてないか、探索済みの局面ではないかをチェック、問題なければ solver プロセスを起こしてデータを渡します。
solver はデータを１手進ませた枝（その局面で押せる荷物を全部押してみたもの）を作り、branch メッセージに付けて manager に送ります。
前回のプログラムは solver プロセスの数は固定、生存期間は解法開始から終了までというものでしたが、これは Erlang にはちょっと適してなさすぎでした……。今回、生存期間は１手進ませる間だけ、プロセス数も状況の許す限りという形に変わっています。
また solver の処理そのものも Erlang のリストを間違った形で使っていて（参考１・参考２）、「重量プロセス」になってしまっていたのを改め、タプルで良いところはタプルに、リストを残すところは正しく「リスト」として使うように変更（これが一番大変だったかも。自分の頭の中身から変えていかないといけないので……）。立派な「軽量プロセス」に生まれ変わりました。
これで解法実行すると、解ける問題は数秒で解けるのですが、そうでない問題は瞬間同時プロセス数 1000～1500 くらいでがんがん探索を進めた後、１分くらいでメモリ不足で落ちます（苦笑）。同時プロセス数が 1000 程度で頭打ちになってしまうのも、メモリ不足に陥るのも、どちらも探索済み局面チェックがボトルネックになっていることがわかっているんですが、そこを Erlang でがんばるのは大変そうなので見ないふりしてます……
ともあれ、そのわずかな時間の間に延べ数十万プロセスをハンドリングできているので、さすがは軽量プロセスの面目躍如というのを感じさせられました。
ちなみに探索方式についても、本当の最低限（評価関数すら導入してない……）ではあるんですが、単純な田の字（荷物がかたまって動けなくなった状態）の枝切りと、探索済みの局面チェックだけは行うようにして、ちょっぴり性能向上しています。
解法アルゴリズムの何が楽しいかって、前回のプログラムでは全く歯が立たなかった問題もこういった工夫を加えていくことで、わずか数秒で解けてしまったりするところ。昨日丸一日解法プログラムを走らせていても解けなかった問題が（今回のプログラムはそこまで行く前に落ちますが……）、あっけなくパンと解けたりするとぞくぞくしてしまって、じゃあ次はあの問題だ！ とかなっちゃうんですよね(笑)。
プログラム的にはだらだら長い田の字チェックが追加されているくらいで、それ以外は前回のものよりずっとシンプルになってしまい(プロセスは２種類、メッセージ１種類、solver もループしないし)、わざわざ説明するところがない感じ……
じゃあいっそ、前回は省略してしまった倉庫番解法まわりの説明でもしてみましょうか。
ソース： solver3.erl
今回はひとまず分散は置いといて、軽量プロセスの恩恵を発揮させる方向で攻めています。
プロセスの構造は manager と solver の２種類だけ、やりとりされるメッセージは基本的には solver → manager の branch メッセージだけという簡単なものに。
manager は branch メッセージを受け取ったら、最大歩数を超えてないか、解けてないか、探索済みの局面ではないかをチェック、問題なければ solver プロセスを起こしてデータを渡します。
solver はデータを１手進ませた枝（その局面で押せる荷物を全部押してみたもの）を作り、branch メッセージに付けて manager に送ります。
前回のプログラムは solver プロセスの数は固定、生存期間は解法開始から終了までというものでしたが、これは Erlang にはちょっと適してなさすぎでした……。今回、生存期間は１手進ませる間だけ、プロセス数も状況の許す限りという形に変わっています。
また solver の処理そのものも Erlang のリストを間違った形で使っていて（参考１・参考２）、「重量プロセス」になってしまっていたのを改め、タプルで良いところはタプルに、リストを残すところは正しく「リスト」として使うように変更（これが一番大変だったかも。自分の頭の中身から変えていかないといけないので……）。立派な「軽量プロセス」に生まれ変わりました。
これで解法実行すると、解ける問題は数秒で解けるのですが、そうでない問題は瞬間同時プロセス数 1000～1500 くらいでがんがん探索を進めた後、１分くらいでメモリ不足で落ちます（苦笑）。同時プロセス数が 1000 程度で頭打ちになってしまうのも、メモリ不足に陥るのも、どちらも探索済み局面チェックがボトルネックになっていることがわかっているんですが、そこを Erlang でがんばるのは大変そうなので見ないふりしてます……
ともあれ、そのわずかな時間の間に延べ数十万プロセスをハンドリングできているので、さすがは軽量プロセスの面目躍如というのを感じさせられました。
ちなみに探索方式についても、本当の最低限（評価関数すら導入してない……）ではあるんですが、単純な田の字（荷物がかたまって動けなくなった状態）の枝切りと、探索済みの局面チェックだけは行うようにして、ちょっぴり性能向上しています。
解法アルゴリズムの何が楽しいかって、前回のプログラムでは全く歯が立たなかった問題もこういった工夫を加えていくことで、わずか数秒で解けてしまったりするところ。昨日丸一日解法プログラムを走らせていても解けなかった問題が（今回のプログラムはそこまで行く前に落ちますが……）、あっけなくパンと解けたりするとぞくぞくしてしまって、じゃあ次はあの問題だ！ とかなっちゃうんですよね(笑)。
プログラム的にはだらだら長い田の字チェックが追加されているくらいで、それ以外は前回のものよりずっとシンプルになってしまい(プロセスは２種類、メッセージ１種類、solver もループしないし)、わざわざ説明するところがない感じ……
じゃあいっそ、前回は省略してしまった倉庫番解法まわりの説明でもしてみましょうか。
まず、基本は「プレイヤー移動ではなく、荷物移動による探索」。
プレイヤーがその場で往復移動してしまうなんて単純な場合以外にも、例えば下のような問題があったとき、Ａのように移動して荷物を押す場合と、Ｂのように移動する場合が考えられますが、明らかにＢの方は無駄。
■■■■■■ ■・田 ■ ■ ＠ ■ 田は荷物、＠はプレイヤー ■■■■■■ Ａ Ｂ ■■■■■■ ■■■■■■ ■・田← ■ ■・田←←■ ■ →↑ ■ ■ →→↑■ ■■■■■■ ■■■■■■
これを防ぐために、まず荷物を単なる障害物として移動のみ考え、移動可能範囲とそこまでの最低ステップを計算します。そして、その状態で押すことが出来る荷物を全てリストアップします。
■■■■■■ ■ 2田 2 3■ (数字はその場所までの最低ステップ数) ■ 1 0 1 2■ ■■■■■■
この場合は荷物を「２歩で右に押す」と「２歩で左に押す」という可能性があるので、それぞれが探索における次の局面になります。
これが solver プロセスがやっている基本動作になります。
探索済み局面判定は ets （DBM と連想配列を足して２で割ったようなもの？？）に荷物の配置(画面情報)とプレイヤーの位置をキーに、そこまでの歩数を値にして格納することで行っています（はい、手抜きです。すいません……）。
ポイントは荷物の配置だけでは局面の情報として不十分であるということ。例えば以下の二つは荷物の位置は同じですが、同じ局面ではありません。このため、プレイヤーの位置も局面情報として扱っています。
■■■■■■■■■ ■■■■■■■■■ ■■■■■ ■ ■■■■■ ■ ■・＠ 田 ■ ■・ 田 ＠ ■ ■■■■■■■■■ ■■■■■■■■■
田の字チェックは単純に「押した荷物がゴールの上でなく」「その進行方向の次に荷物か壁があり」「その右（あるいは左）が両方とも荷物または壁なら」もうその荷物は動かせないと判定しています。
本当は「押した荷物がゴールの上だけど」も判定したほうがいいんですが、これまた手抜きです。
■■■■■■■■■ ■■■■■ ■ ■・ ＠田■ ←もう動かない荷物 ■■■■■■■■■
あと、「最も近いゴールまでの荷物移動距離」を出せば確実に性能があがる（というより倉庫番solverとしてやっとまともになる）ことはわかってるんですがやってません……
これは下の図のように最も近いゴールまでの荷物の移動距離をあらかじめ計算しておくというもの。
■■■■■■■ ■■■■■■■ ■■■ ■ ■■■×××■ ■■■田田＠■ ■■■ 3 4×■ ■・ ■ ■・ 1 2 3×■ 数字は最も近いゴールまでの移動距離 ■・ ■ ■・ 1 2 3×■ ×はその場所からゴールへ運ぶ方法がないことを指す ■■■■■■■ ■■■■■■■
これを行うことで、そもそも荷物を運んではいけない場所がわかると同時に、評価関数が計算できるようになります。
また、現在の荷物の位置から「どんなに理想的に移動が出来ても、解けるまで最低あと○手かかる」かも簡単に算出できるようになって、枝刈りに使えます。
さらに、一方通行などを詳細に分析することで、「このエリアには荷物が○個以上存在してはいけない」などといったこともわかります。
■■■■■■■ ■■■■■■■ ■■■ ■ ■■■ ■ ■■■田田＠■ ■■■ ■ ▽のエリアは「荷物は入ってこれるが、出て行けない」 ■・ ■ ■・ ＠ ■ したがって、このエリアには１個の荷物しか存在してはならない ■・▽▽▽▽■ ■・田 田 ■ 右図はまだ荷物は動かせるが、もはや解けない状態になっている ■■■■■■■ ■■■■■■■
いよいよ本番はここからで、定石を導入したり、解けない状態の判定パターンを増やしたり、評価関数を工夫して最短解は出てこないかもしれないけどより多くの問題が解けるようにしたり、あれこれするんですが、そんなことやってたら本題から外れすぎなので……
ああでも、こんな感じでまとめていると、昔の血が騒いでしまう……(苦笑)。