ソルバー紹介

ちょっと間があいてしまいました。ネットで見つけた倉庫番ソルバーを紹介します。

http://www.codecola.net/sps/

ソースはありませんが、ウィンドウズ版のソルバーを走らせることができます。ちょっと試した感じでは、なかなかいいのではないかと思います。

サイト内の「info」の項を見ると、死に手の説明が書いてあります。
「puzzles」の項には、私の面セットも入っているようです。
[PR]
# by sokoban | 2005-01-14 01:46 | コラム
8つの形
あるパターンについて、それを反転したり回転したりして出来上がる形は、最大7つあります。単純なマッチングでは、オリジナルとあわせて8つの形を一度に利用できれば、効率がよくなります。
ここで言う「単純なマッチング」は、面全体に対してパターンに合うものを探すだけのことを指しています。
「動かした荷物についてのマッチング」を行う場合は、8つの形の使い方がちょっと違います。荷物の位置を「基準座標」とし、それを軸に反転・回転するというイメージです。
[PR]
# by sokoban | 2004-12-10 01:39 | アルゴリズム
ソルバーの問い合わせ
自分のページでメールアドレスを公開したら、早速問い合わせがありました。ポーランドの研究者で、倉庫番ソルバーのソースを探しているとのことでした。
いい機会なので、明治大論文の紹介ページを復活させました。公開の許可をいただいていて、何年か前までは自分のページ内で公開してたのです。興味あるかたは、アサヒネットの私のページから探してください。

ポーランドの人には、高橋謙一郎さんのページも紹介しました。ソースが公開されているのは、これ。解説も参考になると思います。
http://www.ic-net.or.jp/home/takaken/nt/soko/index.html

もうひとつ、ソース非公開のがあります。こちらの方が新しく、かなりの実績です。
http://www.ic-net.or.jp/home/takaken/so/soko/
[PR]
# by sokoban | 2004-12-09 01:25 | コラム
パターンマッチング
実際のパターンマッチングはどのようなものでしょうか。いくつかポイントがあります。キーワードを列挙すると、こんな感じでしょうか。

・反転
・回転
・荷物OR壁
・基準座標

さらに応用としては、以下のようなことに注意します。

・ゴールの位置
・荷物の数

応用になると複雑なので、今のところは触れません。基本について書いて行こうかと思います。
[PR]
# by sokoban | 2004-12-04 02:55 | アルゴリズム
リンクしました

自分のページからリンクしました。これまでは自分のメモみたいなものでしたが、これからは公開ページということですね。

自分のページは、これです。
http://www.ne.jp/asahi/ai/yoshio/sokoban/
[PR]
# by sokoban | 2004-12-04 02:16 | コラム
見つけた論文
倉庫番関係の論文を見つけました。小田原大氏の研究です。本文は見られませんが、抄録があります。

http://fw8.bookpark.ne.jp/cm/ipsj/search.asp?from=SIGNotes,%20IPSJ-GI&flag=-1&keyword=SIGNotes,%20IPSJ-GI,YM200406

2003年のワークショッで発表されたようです。本文が見たいところですが・・。

http://minerva.cs.uec.ac.jp/~ta-ito/GPW03/program.htm
[PR]
# by sokoban | 2004-11-30 23:38 | 文献
3x3パターン
以下の4つに集約できます。
A)
 -■-
 日-■
 日日-
B)
 -■-
 日-日
 日■日
C)
 -■-
 日-日
 ■日日
D)
 -日日
 日-日
 日日-

なぜこれだけしかないのでしょうか。ある死に手パターンにおいて、任意の荷物を壁に変えても、それは死に手パターンです。また、あるスペースを荷物または壁に変えても、やはり死に手パターンです。ということは、以下のようなありがちなパターンも、上記パターンに集約されるということになります。

B、Cに集約)
 -■-
 日-日
 ■■■
Dに集約)
 -日■
 日-■
 ■■■
[PR]
# by sokoban | 2004-11-22 00:29 | アルゴリズム
パターンマッチング
袋小路などの非固定タイプの死に手判定に、もっとも単純な方法がパターンマッチングです。

パターンはほぼ無限なので、すべてのチェックは無理です。適当なコストで効率的な方法を模索することになります。

とりあえず、パターンデータベースが欲しいところです。3x3のパターンについて机上で考えたことがあるのですが、ゴールが無いものについて数え上げると、意外と少ないということがわかりました。
[PR]
# by sokoban | 2004-11-22 00:23 | アルゴリズム
袋小路の研究
非固定タイプは判定が困難です。代表的なもので、袋小路があります。

パターンマッチングやサブ探索などが考えられますが、多くを判定しようとすると、コストが膨大になります。

明治大論文でサブ探索が提案されています。一押ごとに閉空間の発生を調べ、それを回復できるかどうかを探索する、という方法です。実験結果を見ると、ある程度の成功を収めています。

もちろん完全にはチェックできません。サブ探索のバッファが足りなくなることもしばしばです。といっても当時のことですので、今のメモリ量では変わってくるかも知れません。

世間でも袋小路の研究はまだまだ進んでおらず、これから研究を始める方にはいい題材だと思います。
[PR]
# by sokoban | 2004-11-22 00:06 | 解説
複数チェック
荷物複数のチェックは、一筋縄ではいきません。いろいろ工夫が必要です。
まずは、タイプを固定と非固定に分類します。固定はパターンが少なく、比較的易しく判別できます。

シチョウ)
 パターン無限なので、再帰的なアルゴリズムでチェック。
集四)
 パターンひとつなので、マッチングでチェック。
準集四)
 パターン有限なのでマッチングでもいいが、シチョウと同様にもできる。
[PR]
# by sokoban | 2004-11-15 00:19 | アルゴリズム