お気づきの点や感想要望などなんでもＯＫ！
> 出来る事なら、消していただけるとありがたいのですが・・・。 クリアー達成登録をした直後に表示される順位表はリロード(再読込み) しないと自分の名前が表示されない場合があるようです。 ４０７位を生かして後の２つは次の人達に移行しておきした。 気にせずに是非フリーク版に挑戦してみて下さい。 # 私事ですがＦＬＡＰＰＹ９５の5-06は無事通過！
ＷＡＴＴＡの上級編をクリアーしたは良いが、 間違って入力をし、重複させてしまいました。 ４０７位〜４０９位です。 皆さん、本当にごめんなさい。 出来る事なら、消していただけるとありがたいのですが・・・。
「思考型パズルゲームで遊ぼう」コーナーの全クリアー登録を再開しました。 特にＷＡＴＴＡに人気が集中してますが、このゲームは元々ＦＬＡＰＰＹの 魅力に取り付かれた自分が同じような「ヒラメキ発想」を必要とするパズル ゲームを作りたいと言うスタンスを持って作りました。 (初代)ＦＬＡＰＰＹの全200面は解けたものの「ＦＬＡＰＰＹ９５」は未だ 全クリアー出来てません。どなたかＦＬＡＰＰＹ９５を全クリアーした方の 自慢話をお待ちしてます。ちなみに私は「５−０６」でストップしてます。
大きな勘違いがありました。ＩＤＡ＊サーチですので上限値を気にする必要は ありません。高橋さんの推測があっていると思います。 ＰＤＢという考えは私には新しいアイデアでした。それにしても一連の迷走状態 は恥ずかしいかぎりです。どこかでこのアイデアを活かせるといいのですが、。。。 高橋さん、どうもありがとうございました。
作者の論文をじっと眺めて(さらに自動翻訳ソフトを使って)、私の最終推測は、 deepgreenさんの推測とは全く異なるのですが、 (１)ＰＤＢは２つ作っておく。target pattern は下図のとおり。 ＊ｘｘ３ ＊ｘｘｘ ＊：スペース ｘｘｘ７ ｘｘｘｘ ｘ：残りの数字 ｘｘｘｂ ８９ａｘ ｃｄｅｆ ｃｄｅｆ 周辺ＰＤＢ 角ＰＤＢ (２)下限値を見積る時この２つのＰＤＢを参照して得られた値の内より厳しい （より大きい値）方を取る。作者によると、この２つのパターンは下限値 を厳しく見積るにはベストの関係にあるらしい。(訳せゴマはそう訳した) Intuitively, there two are likely to be among the best at providing tight lower bounds for the search. (３)下限値を見積る時にＭＤでも計算してみる。つまり周辺ＰＤＢと角ＰＤＢ とＭＤの３つの内、以後絶対に必要な手数がより厳しい（より大きい値） を下限値に採用して、次の枝刈り式を使いＩＤＡ＊サーチする。 [現在までの手数]＋[下限値]＞[今回の探索の深さ] (４)あくまでも、最初に見つかった解が最適解となる。 要点は、１手動かすたびに下限値を見積るがその時「何種類かの下限値の見積り 法を試してその内より大きい値を採用する」ということのような気がします。 ただし、それらしい事が書いてあると思われる部分（１ページ分）だけを訳した 結果と私の想像の合成によります。どうやら私の訳した部分の後に「上限値」に 関することが書いてあるようなので、deepgreenさんはその部分に重点を置いた ようですね。私は力尽きて読めませんでした。 ところで、そろそろ私も倉庫番に帰ろうと思います。アイデアが溜まってきたの と時間も作れそうなので．．．．
今年の前半は倉庫番をエンハンスしようと思っているので、１５パズルに あまり深入りするつもりはなかったのですが、脱線してしまいそう。。。 ＭＤ(Manhattan distance)は、高橋さんの定義で合っていると思います。 （論文が見つからないので想像の域をでませんが） ＰＤＢからsubgoalまでの最大手数は６１手、subgoalからｇｏａｌまで （＝８パズル）は最大３１手なので、１５パズルは最大９２手となります。 ＊の位置関係を考えると最大は９０手になると論文に書いてあります。 （最後のところは理解できてません） いずれにせよ、高々９０手で解けてしまうというのは意外な結果です。 ＰＤＢのコストに関する高橋さんのご指摘は、もっともですね。ＰＤＢの コストはtarget patternに近づくほど小さくなるので、subgoal−＞goalを 無視した分精度が落ちてしまいます。ＭＤの方が良いケースも十分考えら れます。私の推測は、 （１）maxhand = 91 （最大値＋１） （２）max(PDBのコスト、ＭＤ）を使って枝刈りをする （３）サーチでsubgoalが見つかった時は、maxhandを修正する （subgoalからgoalは８パズルとして事前に解いておく） （４）サーチ＞ maxhandとなったら終了で、最後に見つけた解が 最短解となる ＰＤＢのコストdatabaseは約５２０ＭＢになるのでちょっとやってみようか と気軽に手を出せる範囲ではありません。でも、チョット、。。。
ごめんなさい。とんでもないウソを書いてしまいました。 > 下限値の算出は常に動的であり１手動かす度に計算されます。その計算は前回 > 書いた通り、target patternの構成要素の７枚の駒についてはＰＤＢを参照 > して、残り８枚の駒についてはＭＤを使って求め、その２つをたし算します。 この考えは間違いでした。target patternの構成要素の７枚の駒についてＰＤＢ を参照して得られた下限値である最短手順には,構成要素以外の駒の動きも含んで います。従って、残り８枚の駒についてはＭＤを使って求めた下限値とどこかで 重複している可能性があります。単純に２つをたし算するのは間違いでした。 益々分からなくなってきた．．．．．．．．
説明がちょっと足りなかったようなので補足します。(正直、熱くなってます!) ＩＤＡ＊サーチにおける枝刈りは、あくまでも次の条件式が満たされた時です。 [現在までの手数]＋[下限値=以後絶対必要な手数]＞[今回の探索の深さ] 下限値の算出は常に動的であり１手動かす度に計算されます。その計算は前回 書いた通り、target patternの構成要素の７枚の駒についてはＰＤＢを参照 して、残り８枚の駒についてはＭＤを使って求め、その２つをたし算します。 そして最初に見つかった解が最適解となり探索を終えます。 ----------------------------------------------------------------- 「これって結構いいアイデアかなぁ」と再認識しました。ロジックに勘違いは ないと思います。作者が研究をしようとした最初の思い付きは、正にこの考え をひらめいたのが最初の動機なのかなあと想像しています。これを起点として さらに研究を深めて探索量を「１／１０００」にまでしてしまったような気が します。 １５パズルのソルバーロジックは汎用性が高いので本当に面白い。特に今回の deepgreenさんの考察には背筋に衝撃が走りました。deepgreenさんの考察に 追加で考察してしまいましたが、でもまだ実際にプログラムを書いて試してみ ようと言う気になれない、何かまだ足りない気がしているのも事実です。
今回の説明を読んで一瞬感動してしまいましたが、どうも今回の考え方も何か ちょっと違うような気がするのです。 どんな初期状態であったとしてもその配置はＤＢの中に最初から存在すること になり、直ぐにsubgoalまでの下限値（どうしても必要な手数）が得られます。 subgoalからｇｏａｌまでの下限値は０なので、初期状態が与えられた瞬間に ＤＢを参照するだけでｇｏａｌまでの下限値が得られることになります。 この下限値が、ある駒が現在の位置からｇｏａｌの位置に達するまでの単純な 距離(縦座標の差＋横座標の差)を[１]から[15]までの駒について計算した値の 合計値(この値の事をＭＤと想像で呼ぶ)よりも大きければ枝刈り効果は確かに 大きくなります。 しかし、必ず大きくはなりません。例えば初期状態が初めからtarget pattern の形になっていれば下限値は０になります。しかし、target patternの構成要 素以外の部分がｇｏａｌの配置と異なっていれば、ＭＤの方が大きくなります。 それでこんな方法はどうでしょう。target patternの構成要素の７枚の駒につ いてＤＢを参照して下限値を得て、残り８枚の駒についてはＭＤで下限値を求 めてその２つを足し算して全体の下限値を得ているのではないでしょうか。 英語が全く読めないので、あくまでも私の想像です。ＭＤとは本当は何なのか も想像なので何とも想像だらけです。
すみません。恥ずかしながら、ＰＤＢの理解が全く誤っていました。 前の話はすべて忘れてください。大変申し訳ございません。 target pattern ：ゴール状態と一部分が一致するようなパターン(subgoal) （ｇｏａｌ） (subgoal) ＝ target pattern ＊１２３ ＊ｘｘ３ ＊：スペース ４５６７ ｘｘｘ７ ｘ：残りの数字(don'tcare) ８９ａｂ ｘｘｘｂ ｃｄｅｆ ｃｄｅｆ pattern database : target patternの構成要素（*,3,7,b,c,d,e,f)を任意の （ＰＤＢ） 位置にならべたpattrnのすべての集合 パターンの例 （Ａ） （Ｂ） ｘ３ｘｘ ＊ｘｘｃ ｃｘｄｘ ｘｘｘｄ ｘｆｅｘ ｘｘｘｅ ７ｂ＊ｘ ３７ｂｆ ＰＤＢのすべてのpatternについてコスト（そのpatternからsubgoalにいたる 最小手数）を求め、データベースを作成する。このデータベースはゴールまで の距離の下限値（どうしても必要な手数）となる。 (初期状態） ＰＤＢ (subgoal) （ｇｏａｌ） ＊４８ｃ ＋−−−＋ ＊ｘｘ３ ＊１２３ １５９ｄ ＝＝＞ ｜（Ａ）｜ −−＞ ｘｘｘ７ −−＞ ４５６７ ２６ａｅ ｜（Ｂ）｜ ｘｘｘｂ ８９ａｂ ３７ｂｆ ＋−−−＋ ｃｄｅｆ ｃｄｅｆ ＜−−−−−−−−−−−＞ この部分の最小手数をＤＢ化 初期状態からＩＤＡ＊サーチでｓｕｂｇｏａｌを探索しますが、そのときの 枝刈りとしてＭＤ(Manhattan distance）ではなく上記のデータベースを参照 します。 高橋謙一郎さんの「ＭＤより精度の高いLower Bound Estimaterが重要」という ご指摘は大当たりでした。鋭い洞察力ですね。