お気づきの点や感想要望などなんでもＯＫ！
あらさん、大変貴重な情報をありがとうございます。 正直言って、貴重な情報というよりも訃報みたいに肩の力がぬけてしまいました。 気を取り直してソルバー造りの観点から論文の概要と感想を書かせていただきます。 ■MD(Manhattan Distance) MDの意味は想像したとおり各駒のホームポジションまでの単純な距離の総和を求めるものでした。 ■LC(Linear Contict) MDの上位版として「Linear Contict」という概念があるようです。厳密に翻訳した訳ではありませんが、 複数の駒が交差しようとした場合のロスを考慮したもののようです。例えば１と３の駒が下図に位置に あったとしてMD=4ですが、この２つの駒が最短経路で交差することは出来ないので遠回りせざを得ない 分のロスを考慮した小規模のテーブルを作っているようです。尚、２駒交差、３駒交差、４駒交差まで あるようです。WDよりも性能が良いかは不明です。 ３□１□ □□□□ □□□□ □□□□ ■PDB(Pattern database) これは既にご存知のとおりです。(ギガバイトマシーンが必要です。) ■LDB(Local Database) PDBとほぼ同じ発想ですが各駒を下図のようなグループ分けをしてデータベースを作ったようです。 発想的にはWDやとしひでさんのQDと似ています。ただし、ギガバイトのマシーンを必要とするようで 最大値は70と書いてありました。最大値こそIDやWDと同じですが結果的にこれが相当の効果をもたらし たと、うかがい知ることが出来ます。もっとも、としひでさんのQDが完成したならばQDのほうが優秀に なると想像しています。 １ＡＢＢ ＡＡＢＢ ＣＣＤＤ ＣＣＤ□ なお、ID(Invert Distance)に気づいたのは私だけのようです。全くこのような解説は見つけられません でした。最大値が70もあるのに．．． ざっと見た感じはこの問題に着手する私達の時期が遅かったという、なぐさめに似たような印象です。 「上限値からのしぼり込み」に関する詳しい説明はほとんどないようですね。最長手数=80を立証した 別の論文を見ないといけないようです。とりあえず、deepgreenさんからの３つの問題を解きました。 *cadfbe978624351 //UB : 84 / 92 No.1 maybe 80-82 -> LB : 66 / 80moves 2038sec *f9dcbae37654821 //UB : 84 / 90 No.1 maybe 78-82 -> LB : 66 / 78moves 195sec *c9dfbae37624851 //UB : 84 / 90 No.2 maybe 76-82 -> LB : 66 / 80moves 8516sec １番目と３番目の80mevesの問題は確かに論文の中にありました。 私としては、deepgreenさんがUB>=84の大量の候補群から17個にしぼりきった方法論にとても興味があります。 是非、ＨＰで解説をお願いしたいです。それから万が一の為(万に一つも無いでしょうが)17個のパターン を教えていただけないでしょうか。とにかく解いてみます。
あらです、説明が不足していたようです。 http://citeseer.nj.nec.com/cache/papers2/cs/11310/http:zSzzSznobi.ethz.chzSzralphzSzPHD95.pdf/gasser95harnessing.pdf の89ページには80手の問題が9問あります。 http://citeseer.nj.nec.com/cache/papers2/cs/779/http:zSzzSzwww.tcs.hut.fizSzpubzSzpaperszSz15puzzle.pdf/on-sliding-block-puzzles.pdf の8ページ目には Upper Boundsが80であることが示された との記述があります。
説明が不明瞭でした。 まず、ピースを(1),(2,5),(3,6,9),(4,7,a,c),...と斜めに分けます。 それをWDの1段目、2段目と同じように考えてシュミレーションすれば、新たな下限値の候補が得られます。 ピースの分け方は90度回転させて(4),(3,8),(2,7,c),(1,6,b,#),...としても同様です。 この2つの方向の距離が、あの悪魔の問題だと(0,50以上)となります。 全ての場合のテーブルが用意できれば、WD,IDで取りこぼしてしまう局面のいくつかは拾うことができそうです。 ODを求めるに当たって、問題点はWDよりずっとたくさんメモリを食うということです。 あの悪魔の問題のODの一方は0ですがもう一方が未だ求まっていません。 下限値を求めるのに時間がかかっていては本末転倒です。
こんばんは、deepgreeenです。 高橋さん、どうもありがとうございます｡ Ｕｌｉｎｅの深い探索が終わりました。その結果、８４手の可能性のある問題は １８９個から１７個になりました。 これはもう時間の問題です。この中に８２手の問題があることを祈りたい気分です。 残念ながら、結果ファイルを会社に忘れてきましたので、明日ｕｐさせてください。 とりあえず、最初の３問を以下にお知らせします。 //以降はコメントです。 *cadfbe978624351 //UB : 84 / 92 No.1 maybe 80-82 *f9dcbae37654821 //UB : 84 / 90 No.1 maybe 78-82 *c9dfbae37624851 //UB : 84 / 90 No.2 maybe 76-82 Ｓｏｌｖｅｒの方は、まだ材料がありそうで楽しみです。 何とか最終結論にたどり着きたいものです。
あらさん、としひでさん、ありがとうございます。 あらさんから教えていただいた論文は、おそらくまともなものは 「Searching with Pattern Database」だけのような感じです。 そもそもの発端がこの論文にあって七転八倒しながらこの論文を 超えようとしている訳です。残念なことにこの論文の主題になって いるPDBはメモリ量(1GB以上必要)の制約で実装できてませんが その発想だけは引き継いで、なんとかここまでたどり着いている 状況です。実は既にこの論文を超えてしまった思いさえありますが deepgreenさんの解析力を傍観しているだけでは寂しいので私は 高速ソルバーの開発に専念してしまいました。 そして、少し息切れぎみに頭の回転がにぶってきているところに としひでさんが何やら面白いことを考えてくれたようです。 ちょっと理解出来てませんが、こうやってアイデアがつながって くれるととても嬉しいです。確実にあの配置は天敵です。 対称変換(以前に書いた縦横変換)して同型になるあたりに悪魔の 一端がうかがえます。いい結果報告を期待しています。
新しくObliqueDistanceというものを考えました。 １の距離が[Fig.1],[Fig.2]となるような距離を考えます。 斜め方向にどれだけ解から離れているかを表しています。 [Fig.1] [Fig.2] 0 1 2 3 0 1 2 3 1 2 3 4 1 0 1 2 2 3 4 5 2 1 0 1 3 4 5 6 3 2 1 0 これだけではMDの下位概念に過ぎませんが、 MD->WD同様の考え方を用いると、[Fig.3]のOD > 52であることがわかりました。 これは10手以上の前進なので、ある種の問題に関してかなりの高速化が期待できます。 [Fig.3] 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 0 (WD=20/20,ID=12/12,OD>52) LowerBound=52 問題点は、ODを求めるテーブルサイズが7440760のデータベースが必要で、 しかも簡単な反復深化では、[Fig.3]のODを求めることができなかった、ということです。 幅優先で表制作に取り組み中ですが、これもまた時間がかかりそうです。
deepgreenさん、こんばんは。 すばらしい結果が出てますね。１８９個といった充分に手の届く範囲です。 人海戦術には喜んで参加させていただきますので問題図を例えば下図のような ベタででも教えていただければ毎晩マシンを走らせてみます。 123456789abcdef* # つい先ほど私のソルバーをＨＰにアップしました。
こんばんは、deepgreenです。 【訂正】 先日書いたＵｌｉｎｅ毎の問題の数に誤りがあることが判明しました｡ 先日のデータは参考値と考えてください。（すみません） 【Ｕｌｉｎｅ＞＝８４のスキャン結果】 Ｕｌｉｎｅを完成させて、８４手以上の問題が存在するかどうかをスキャンした結果です。 （Ｕ＞＝８４の範囲で問題を生成し、ＵＢｃｈｅｃｋで８４手以上の問題を抽出） （１）８５手以上の問題は存在しないことが判明 （２）８４手の可能性のある問題は、以下の１８９個存在した。 Ｕ＝９４ １０個 ９２ ２５個 探索範囲：Ｕ＝９９〜８４（問題数：約３．７５Ｇ個） ９０ ２９個 探索時間：２１．５Ｈ ８８ ４６個 探索速度：９９−９０の範囲 １２０００個／秒 ８６ ６４個 ８９−８４の範囲 ６５０００個／秒 ８４ １５個 ＵＢｃｈｅｃｋの効果：約１／２０Ｍ個 合計 １８９個 今、一番深い探索でもう一度スキャンをしています。 問題数を絞ってから高橋さんのＳｏｌｖｅｒに解法をお願いしようと思います。 (すみません。すっかり当てにしています） 現時点で、最長手数は８０−８４の範囲に絞られた。 多分、上記の１８９個の問題の中に８４手の問題は存在しないであろう（ＭＤ探索からの推測） でも、この中から８２手の問題が見つかってほしい。 Ｕｌｉｎｅ，ＵＢｃｈｅｃｋおよび高橋さんのＳｏｌｖｅｒの現時点の性能を考えると、 ８２手位までが限界のような気がします（人海戦術をやったとして） もしかしたら、結論が出せるかもしれないというギリギリのところにいるようです。
みなさんどんどん先に進まれて、取り残されてしまってます。 MDだけしか搭載してない私のソルバーでは ４３２１ ８７６５ ＣＢＡ９ ＥＦＤ＊ を解くのに33時間もかかってしまいました。 高橋さんのソースはぜひ見てみたいです。
こんばんは、deepgreenです。 高橋さん、ありがとうございました。予想通りの結果となり、一安心です。 つぎは、８２手の問題をさがしましょう。