<   2004年 11月 ( 17 )   > この月の画像一覧
見つけた論文
倉庫番関係の論文を見つけました。小田原大氏の研究です。本文は見られませんが、抄録があります。

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 | アルゴリズム
単数チェック
荷物がひとつについての死に手チェックは、すべて同じ方法でできます。ゴールから引いてできる地図を作って利用するのです。

角)
 ■-
 日■
壁際)
 ■-日--■
 ■■■■■■
袋小路)
 -■■■■
 -■--■
 大日--■
 -■--■
 -■■■■

袋小路は人の位置が関係します。そのため、地図ひとつでは死かどうか判別できません。荷物に対して人の位置は4方向まであるので、地図を4つ作っておけば判別できます。
[PR]
by sokoban | 2004-11-14 23:12 | アルゴリズム
凡例
キャラクタの意味を示しておきます。

荷物・・・・・・・日
ゴール・・・・・・十
番人(人)・・・・大
壁・・・・・・・・■
スペース・・・・・-
ゴールと荷物・・・田
番人と荷物・・・・木

以上は、基本キャラです。今後、説明用の専用キャラが出てきますが、それは後日。
[PR]
by sokoban | 2004-11-14 00:40 | 解説
予備状態
押すと固定の死や袋小路などの死に手になってしまう。

固定の予備)
 ■-日-■
 ■■日■■
袋小路の予備)
 ■■■■
 ■---
 ■-日日
 ■■■-
 --■■
[PR]
by sokoban | 2004-11-13 23:47 | 死に手パターン
袋小路
明治大論文で「袋小路」と名づけられた、「回復できない閉空間」。人の位置によっては死でなくなる。
閉空間を回復しようと押してみても、どうしても固定の死になってしまう。パターンはほぼ無限に存在する。

 -■■■■
 大日--■
 -■■■■

 ■■■
 日-日
 日日大

 大日日
 日-日
 日日-

 ■■■■■
 ■--日-
 ■--日-
 ■--日大
 ■■■■-
[PR]
by sokoban | 2004-11-13 23:23 | 死に手パターン
壁が増えた死
荷物が不動になることによって、壁と同じになってしまう。つまり、迷路が変化したことによる死。
以下の例では、人の位置が関係する。

荷物に到達できなくなった)
 -■■■■■--
 ■-----■■
 ■十日---田田
 ■■■■■■-大
荷物をゴールに運べなくなった)
 -----■-
 ■■■■■田大
 -十日--田-
 ■■■■■--
[PR]
by sokoban | 2004-11-13 22:35 | 死に手パターン