ホームページへ戻る  書き込みリストへ戻る
「コンピュータ&パズル」訪問者の自由メッセージコーナー

お気づきの点や感想要望などなんでもOK!


re:15Puzzle 投稿者:高橋謙一郎  投稿日:04月03日(火)22時44分24秒

あらさん、大変貴重な情報をありがとうございます。

正直言って、貴重な情報というよりも訃報みたいに肩の力がぬけてしまいました。
気を取り直してソルバー造りの観点から論文の概要と感想を書かせていただきます。

■MD(Manhattan Distance)
MDの意味は想像したとおり各駒のホームポジションまでの単純な距離の総和を求めるものでした。

■LC(Linear Contict)
MDの上位版として「Linear Contict」という概念があるようです。厳密に翻訳した訳ではありませんが、
複数の駒が交差しようとした場合のロスを考慮したもののようです。例えば1と3の駒が下図に位置に
あったとしてMD=4ですが、この2つの駒が最短経路で交差することは出来ないので遠回りせざを得ない
分のロスを考慮した小規模のテーブルを作っているようです。尚、2駒交差、3駒交差、4駒交差まで
あるようです。WDよりも性能が良いかは不明です。

3□1□
□□□□
□□□□
□□□□

■PDB(Pattern database)
これは既にご存知のとおりです。(ギガバイトマシーンが必要です。)

■LDB(Local Database)
PDBとほぼ同じ発想ですが各駒を下図のようなグループ分けをしてデータベースを作ったようです。
発想的にはWDやとしひでさんのQDと似ています。ただし、ギガバイトのマシーンを必要とするようで
最大値は70と書いてありました。最大値こそIDやWDと同じですが結果的にこれが相当の効果をもたらし
たと、うかがい知ることが出来ます。もっとも、としひでさんのQDが完成したならばQDのほうが優秀に
なると想像しています。

1ABB
AABB
CCDD
CCD□


なお、ID(Invert Distance)に気づいたのは私だけのようです。全くこのような解説は見つけられません
でした。最大値が70もあるのに...
ざっと見た感じはこの問題に着手する私達の時期が遅かったという、なぐさめに似たような印象です。

「上限値からのしぼり込み」に関する詳しい説明はほとんどないようですね。最長手数=80を立証した
別の論文を見ないといけないようです。とりあえず、deepgreenさんからの3つの問題を解きました。

*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

1番目と3番目の80mevesの問題は確かに論文の中にありました。
私としては、deepgreenさんがUB>=84の大量の候補群から17個にしぼりきった方法論にとても興味があります。
是非、HPで解説をお願いしたいです。それから万が一の為(万に一つも無いでしょうが)17個のパターン
を教えていただけないでしょうか。とにかく解いてみます。


re:15Puzzle 投稿者:あら  投稿日:04月03日(火)12時39分55秒

あらです、説明が不足していたようです。

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であることが示された
との記述があります。


re:15Puzzle 投稿者:としひで  投稿日:04月03日(火)10時49分29秒

説明が不明瞭でした。
まず、ピースを(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ですがもう一方が未だ求まっていません。
下限値を求めるのに時間がかかっていては本末転倒です。


re:15Puzzle  投稿者:deepgreen  投稿日:04月03日(火)01時31分04秒

こんばんは、deepgreeenです。

高橋さん、どうもありがとうございます。

Ulineの深い探索が終わりました。その結果、84手の可能性のある問題は
189個から17個になりました。
これはもう時間の問題です。この中に82手の問題があることを祈りたい気分です。

残念ながら、結果ファイルを会社に忘れてきましたので、明日upさせてください。
とりあえず、最初の3問を以下にお知らせします。

//以降はコメントです。

*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

Solverの方は、まだ材料がありそうで楽しみです。
何とか最終結論にたどり着きたいものです。


re:15Puzzle 投稿者:高橋謙一郎  投稿日:04月02日(月)22時19分36秒

あらさん、としひでさん、ありがとうございます。

あらさんから教えていただいた論文は、おそらくまともなものは
「Searching with Pattern Database」だけのような感じです。
そもそもの発端がこの論文にあって七転八倒しながらこの論文を
超えようとしている訳です。残念なことにこの論文の主題になって
いるPDBはメモリ量(1GB以上必要)の制約で実装できてませんが
その発想だけは引き継いで、なんとかここまでたどり着いている
状況です。実は既にこの論文を超えてしまった思いさえありますが
deepgreenさんの解析力を傍観しているだけでは寂しいので私は
高速ソルバーの開発に専念してしまいました。

そして、少し息切れぎみに頭の回転がにぶってきているところに
としひでさんが何やら面白いことを考えてくれたようです。
ちょっと理解出来てませんが、こうやってアイデアがつながって
くれるととても嬉しいです。確実にあの配置は天敵です。
対称変換(以前に書いた縦横変換)して同型になるあたりに悪魔の
一端がうかがえます。いい結果報告を期待しています。


re:15Puzzle 投稿者:としひで  投稿日:04月02日(月)18時21分52秒

新しくObliqueDistanceというものを考えました。
1の距離が[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を求めることができなかった、ということです。
幅優先で表制作に取り組み中ですが、これもまた時間がかかりそうです。


re:15Puzzle(U>=84scan) 投稿者:高橋謙一郎  投稿日:04月02日(月)01時12分07秒

deepgreenさん、こんばんは。

すばらしい結果が出てますね。189個といった充分に手の届く範囲です。

人海戦術には喜んで参加させていただきますので問題図を例えば下図のような
ベタででも教えていただければ毎晩マシンを走らせてみます。

123456789abcdef*

# つい先ほど私のソルバーをHPにアップしました。


re:15Puzzle(U>=84scan) 投稿者:deepgreen  投稿日:04月02日(月)00時48分58秒

こんばんは、deepgreenです。

【訂正】
 先日書いたUline毎の問題の数に誤りがあることが判明しました。
 先日のデータは参考値と考えてください。(すみません)

【Uline>=84のスキャン結果】
 Ulineを完成させて、84手以上の問題が存在するかどうかをスキャンした結果です。
(U>=84の範囲で問題を生成し、UBcheckで84手以上の問題を抽出)

 (1)85手以上の問題は存在しないことが判明
 (2)84手の可能性のある問題は、以下の189個存在した。  
     U=94  10個
       92  25個  探索範囲:U=99〜84(問題数:約3.75G個)
       90  29個  探索時間:21.5H
       88  46個  探索速度:99−90の範囲 12000個/秒
       86  64個       89−84の範囲 65000個/秒
       84  15個  UBcheckの効果:約1/20M個
     合計   189個

  今、一番深い探索でもう一度スキャンをしています。
  問題数を絞ってから高橋さんのSolverに解法をお願いしようと思います。
    (すみません。すっかり当てにしています)

  現時点で、最長手数は80−84の範囲に絞られた。

  多分、上記の189個の問題の中に84手の問題は存在しないであろう(MD探索からの推測)
    でも、この中から82手の問題が見つかってほしい。

  Uline,UBcheckおよび高橋さんのSolverの現時点の性能を考えると、
  82手位までが限界のような気がします(人海戦術をやったとして)
  もしかしたら、結論が出せるかもしれないというギリギリのところにいるようです。
 


15Puzzle 投稿者:としひで  投稿日:03月31日(土)06時37分15秒

みなさんどんどん先に進まれて、取り残されてしまってます。
MDだけしか搭載してない私のソルバーでは
   4321
   8765
   CBA9
   EFD*
を解くのに33時間もかかってしまいました。
高橋さんのソースはぜひ見てみたいです。


re:15Puzzle(80手でした)  投稿者:deepgreen  投稿日:03月30日(金)02時36分53秒

こんばんは、deepgreenです。

高橋さん、ありがとうございました。予想通りの結果となり、一安心です。
つぎは、82手の問題をさがしましょう。


 ホームページへ戻る  書き込みリストへ戻る