AI研究

強制手による死チェック

強制手が実行できない場合、それは死と判断できます。

　　Ａ）
　　　■■■■■■■
　　　■－－－－－■
　　　日－日－－－■
　　　■－－－－－■
　　　■－－－－－■
　　　■■■■■■■

Ａは、強制手の押し先に障害物（荷物か壁）があります。

　　Ｂ）
　　　■■■■■■■
　　　■－－－－－■
　　　日－－日－－■
　　　■■■■■■■

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

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

　　　■■■■■■■
　　　■－－－－－■
　　　日－十田－－■
　　　■■■■■■■

強制手つづき

強制手の理論は、部屋の広さによりません。どれだけ広くても、入り口がひとつであれば同じです。以下、「？」は、その向こうで領域が閉じていることを示しています。

　　　■■？？？
　　　■－－－？
　　　日－－－？
　　　■－－－？
　　　■？？？？

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

　　　■■？？？
　　　■－－－？
　　　－日－－？
　　　■－－－？
　　　■？？？？

強制手の理論

久しぶりにかきます。私の考える概念に「強制手」というものがあります。
簡単に言うと「いずれ必ずしなければいけない行動」です。

　　Ａ）
　　　■■■■■
　　　■－－－■
　　　日－－－■
　　　■■■■■

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

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

　　Ｂ）
　　　■■■■■
　　　■－－－■
　　　－－日－■
　　　■■■■■

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

よって、Ａの状態とＢの状態は同一視して、探索空間を減らすことができます。
ということは、Ａを見つけたらさっさと押してＢの状態にすべきです。
私はこの理論を「強制手」と呼んでいます。

無駄なスペース

またまた、最小化して考えて見ましょう。
以下の×印は、無駄なスペースです。

　　Ａ）
　　　－－■－
　　　－－×■
　　　■××■
　　　－■■－
　　Ｂ）
　　　－－■－
　　　■××■
　　　■××■
　　　－■■－
　　Ｃ）
　　　■×■－
　　　■××■
　　　■××■
　　　－■■－
　　Ｄ）
　　　－■■－
　　　－－－－
　　　■××■
　　　－■■－

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

　　Ｆ）
　　　－－■－
　　　－－△■
　　　■△－－
　　　－■－－

先に示した、局面の優劣に関するパターンと比べてみてください。
ある程度形が一致するはずです。

押したほうがいい形たち

局面の優劣に関するパターンは、算出方法はややこしいです。自動化はまだアイデアがありません。
机上では、以下のようなものを考えています。いずれも、荷物を右に押します。

　　　－－■－
　　　－－－■
　　　日－－■
　　　■■■－

　　　－－■－
　　　■－－■
　　　日－－■
　　　－■■－

　　　－■－－
　　　■－－－
　　　日－－■
　　　－■■－

　　　－■■－
　　　－－－■
　　　日－－－
　　　■■■■

　　　－■■－
　　　■－－■
　　　日－－－
　　　－■－－

　　　－■－－
　　　■－－■
　　　日－－■
　　　－■－－

ほかにもありそうです。

押したほうがいい理由

主題を変えて、局面の優劣について再び。視点を変えて説明します。

　　■■■■■
　　－－－－■
　　－日－－■
　　■■■■■

この形では、とりあえず荷物を奥に押し込んだ方がいいことは既に述べました。
最小化して理由を検討してみます。

　　　－－■－
　　　－－－■
　　　■－－■
　　　－■■－

この形において、無駄なスペースがあります。

　　　－－■－
　　　－－×■
　　　■××■
　　　－■■－

この×印のスペースは、利用できないので、埋めても問題ありません。

もとの形において、荷物を奥に押し込む手は、無駄なスペースを埋め、かつ他に利用されうる領域を広げるものです。
また、どちらにしろ将来逆方向に押すことになりますが、それを妨げることにはなりません。
以上より、とりあえず押したほうがいいと言えます。

過去の算出結果との一致

「過去の算出結果との一致」を考えます。
前提として、過去の算出結果をデータベースなどに記録しておくことが必要です。

たとえば、3種3x3の算出では、2種3x3の算出結果を利用できます。
3種4x3では、2種3x3と3種3x3と2種4x3の結果を利用できます。

わかりやすく、2種3x3を過去の算出として、説明します。
この形が算出済みです。

　　　－日日
　　　日－日
　　　日日－

これを含む形ならば、解けないものと判断できます。

たとえば2種3x4では

　　　－日日－
　　　－日－日
　　　－－日日

3種3x3では

　　　－日■
　　　日－日
　　　日日－

といったものが対象です。

この場合パターンが1個しかないのでそれほどの効果は期待できませんが、数が多いと効果があるかも知れません。また、対象が大きくなるほど効果が出てくると思われます。

3種5x2答え

3種5x2で算出されたのは、これでした。

■－日－■
－■日■－

この形は「固定の予備状態」として知っていましたが、予測の時点では忘れていました。自動算出はやっぱり頼りになりますね。

2種4x3

2種4x3で、死に手パターン算出までやりました。

---------------------------
全組み合せ： 4096 (= 2^12)

重複排除後： 1120 / 4096

荷物が無し： 1 / 1120
集四など死： 285 / 1120
上記の残り： 834 / 1120

重複排除後： 812 / 834

解があった： 810 / 812
解答できず： 2 / 812
---------------------------

算出パターンは以下の2つです。
１）
　－日日
　日－日
　日日－
　－－－
２）
　日日－
　日－日
　日－日
　日日－

見ての通り、１は3x3で算出されたものと同じです。
「過去の算出結果との一致」の処理が必要ですね。規模が大きくなるにしたがって、重要になってきます。

3種5x2

3種5x2の死に手パターン算出をやってみました。事前予測では、以下のものひとつだけが算出されると考えていました。

　■－日－■
　－■■■－

しかし結果は違いました。プログラムによって新事実が判明したことになり、嬉しい結果となりました。内容は後日改めて投稿します。予想してみてください。