カテゴリ:アルゴリズム( 8 )
マッチング回数
このパターンでの基準座標は2つでした。
改めて、4つ3x3パターンについて基準座標を数えると、A,B,C.Dでそれぞれ2,2,4,2です。よって、マッチングの回数は2*8+2*8+4*8+2*8=80ということになります。
1手ごとにマッチングをするとしても、たいしたコストではありません。どの程度の効果があるかは検討の余地がありますが、これによって還って解けなくなる、という心配はありません。メモリの圧迫はなく、消費するのは時間だけだからです。
[PR]
by sokoban | 2005-02-06 23:12 | アルゴリズム
動かした荷物についてのマッチング
3x3パターンマッチングについてです。ここではこの形を例にします。

 -■-
 日-■
 日日-

さて、動かした荷物を基準としたマッチングでは、基準座標を決めます。このパターンでは、3つの座標がありえます。以下に×印で示しました。

1)
 -■-
 ×-■
 日日-
2)
 -■-
 日-■
 ×日-
3)
 -■-
 日-■
 日×-

このパターンは線対称なので、(1)と(3)は同じです。よって、基準座標は2つです。
それぞれについて回転・反転の8つの形でマッチングをすることになります。
なお、(2)は線対称なので、反転形を省くことができます。
[PR]
by sokoban | 2005-01-14 02:01 | アルゴリズム
8つの形
あるパターンについて、それを反転したり回転したりして出来上がる形は、最大7つあります。単純なマッチングでは、オリジナルとあわせて8つの形を一度に利用できれば、効率がよくなります。
ここで言う「単純なマッチング」は、面全体に対してパターンに合うものを探すだけのことを指しています。
「動かした荷物についてのマッチング」を行う場合は、8つの形の使い方がちょっと違います。荷物の位置を「基準座標」とし、それを軸に反転・回転するというイメージです。
[PR]
by sokoban | 2004-12-10 01:39 | アルゴリズム
パターンマッチング
実際のパターンマッチングはどのようなものでしょうか。いくつかポイントがあります。キーワードを列挙すると、こんな感じでしょうか。

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

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

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

応用になると複雑なので、今のところは触れません。基本について書いて行こうかと思います。
[PR]
by sokoban | 2004-12-04 02:55 | アルゴリズム
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-15 00:19 | アルゴリズム
単数チェック
荷物がひとつについての死に手チェックは、すべて同じ方法でできます。ゴールから引いてできる地図を作って利用するのです。

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

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