人気ブログランキング | 話題のタグを見る
強制手による死チェック
強制手が実行できない場合、それは死と判断できます。

  A)
   ■■■■■■■
   ■-----■
   日-日---■
   ■-----■
   ■-----■
   ■■■■■■■

Aは、強制手の押し先に障害物(荷物か壁)があります。

  B)
   ■■■■■■■
   ■-----■
   日--日--■
   ■■■■■■■

Bは、強制手を実行すると固定の死になります。

中にゴールがあっても同じです。
ただし、以下のようなものは死ではありません。

   ■■■■■■■
   ■-----■
   日-十田--■
   ■■■■■■■
# by sokoban | 2007-04-15 10:54 | 強制手
強制手つづき
強制手の理論は、部屋の広さによりません。どれだけ広くても、入り口がひとつであれば同じです。以下、「?」は、その向こうで領域が閉じていることを示しています。

   ■■???
   ■---?
   日---?
   ■---?
   ■????

荷物の位置は、とにかくふたをしているところです。下のは上のと同条件です。

   ■■???
   ■---?
   -日--?
   ■---?
   ■????
# by sokoban | 2007-04-15 10:43 | 強制手
強制手の理論
久しぶりにかきます。私の考える概念に「強制手」というものがあります。
簡単に言うと「いずれ必ずしなければいけない行動」です。

  A)
   ■■■■■
   ■---■
   日---■
   ■■■■■

この状態があったとします。
入り口がひとつの部屋を、ひとつの荷物がふさいでいます。
部屋にはゴールがありません。番人は部屋の外にいます。

必ず以下の状態を経由して、荷物を部屋の外に出さなければ、面は解けません。

  B)
   ■■■■■
   ■---■
   --日-■
   ■■■■■

BはAに対して劣っていません。つまり、Aで解けてBで解けないということはありません。
逆に、AはBに対しても劣っていません。Bで出現する移動可能範囲(スペース)は、
Aと比べても活用できるものはありません。

よって、Aの状態とBの状態は同一視して、探索空間を減らすことができます。
ということは、Aを見つけたらさっさと押してBの状態にすべきです。
私はこの理論を「強制手」と呼んでいます。
# by sokoban | 2007-04-10 02:21 | 強制手
無駄なスペース
またまた、最小化して考えて見ましょう。
以下の×印は、無駄なスペースです。

  A)
   --■-
   --×■
   ■××■
   -■■-
  B)
   --■-
   ■××■
   ■××■
   -■■-
  C)
   ■×■-
   ■××■
   ■××■
   -■■-
  D)
   -■■-
   ----
   ■××■
   -■■-

以下の△印は、どれかひとつは必要がないスペースです。

  F)
   --■-
   --△■
   ■△--
   -■--

先に示した、局面の優劣に関するパターンと比べてみてください。
ある程度形が一致するはずです。
# by sokoban | 2007-01-29 23:35 | 局面の優劣
押したほうがいい形たち
局面の優劣に関するパターンは、算出方法はややこしいです。自動化はまだアイデアがありません。
机上では、以下のようなものを考えています。いずれも、荷物を右に押します。

   --■-
   ---■
   日--■
   ■■■-

   --■-
   ■--■
   日--■
   -■■-

   -■--
   ■---
   日--■
   -■■-

   -■■-
   ---■
   日---
   ■■■■

   -■■-
   ■--■
   日---
   -■--

   -■--
   ■--■
   日--■
   -■--

ほかにもありそうです。
# by sokoban | 2007-01-27 03:19 | 局面の優劣