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

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


15Puzzle(80手でした) 投稿者:高橋謙一郎  投稿日:03月29日(木)21時29分17秒

「おっ凄い!」最悪の事態(15パズルの最長手数=78手)は回避出来たようです。
deepgreenさんから解いてみてほしいという面を解いたら最短解は80手でした。

  0 12  9 13
 15 11 10 14
  7  8  6  2
  4  3  5  1
(WD=33/33,ID=29/29) LowerBound=66
[80 moves] time=4669sec
 12   9  13  14   2   1   5   3   8  11
  9  13  14   2   1   5   3   8   4   7
 15  12  13   9  10   1   5   3   8   4
  7  15  12  13   9  14   1   6   4   7
 11  12  13  10  14   1   6   5   3   4
  7  11  12  14   5   7  11  12  15  13
 10   9   1   6   2   3   4   8  12  15
 14  10   9   5   6   2   3   4   8  12

私としても初めて目にする最短解80手の問題です。予想では最長手数は90手を
超えるだろうと思っていただけに、この80手問題の存在を目にした程度でホッ
としている自分は何なのかと思ってしまいます。?!不思議にうれしい。

実行時間は約1時間20分。まだまだ厳しい現状ではありますが、上限値を
ベースにしたdeepgreenさんの最長手数面を確定させる構想の理論は完璧です。
なんとかしたいという想いが益々が沸いてきます。

# 週末に現在の私のソースをアップしようと思ってます。


15Puzzle関連論文 投稿者:あら  投稿日:03月29日(木)15時16分57秒

15Puzzle面白そうだなと思ってWebを調べてみたところ、
以下の論文にたどり着きました。
参考になると思います。

http://citeseer.nj.nec.com/32578.html
http://citeseer.nj.nec.com/gasser95harnessing.html


re:15Puzzle-Solver 投稿者:deepgreen  投稿日:03月28日(水)22時27分45秒

こんばんは、deepgreenです。

高橋さんのSolverは、すごい成果ですね。
この15パズルの最長手数問題に取り組んだ当時には夢想だにできない性能です。
いまでも信じられない位です。

(1) UBcheckのその後

  MD   問題数    結果
  60   41,472    82手以下の問題しか存在しない(84手以上は存在ない)
  59   331,776        83手以下の問題しか存在しない(85手以上は存在しない)
              83手の可能性のある問題は52問存在する
  58  2,678,400        82手以下の問題しか存在しない(84手以上は存在しない)    
  57 (途中で中止)  約4M個の問題を調べた範囲では、83手以下の問題のみ

  なんとなく、80手あたりかなという感触? 
  78手という結果だけは避けたいなぁ

(2) できたら、この問題を解いてください(少し前に、1昼夜かけても解けなかった問題)

    *  c  9  d
    f  b  a  e
    7  8  6  2
    4  3  5  1

  多分、78−82手です(記憶違いでなければ)

(3) Uline(最長手数問題の探索)
  MDを基本にした探索は、所詮参考にしかならないので、まじめに最長手数問題を
  探索することを考える必要がある。現時点で考えているのは、以下のような手順です。

  (再掲:UBcheck)
   
    X −(a)−> subgoal −(b)−> goal

    subgoalとしては、以下の2パターンを考えました。

     1234     1xxx
     xxxx     5xxx
     xxxx     9xxx
     xxxx     dxxx

  15パズルの問題を上記のsubgoalまでの手数αとsubgoalからgoal
  までの手数βのペア(α,β)で分類する。0<=α<=46、0<=β<=53であるから、
  47x54の長方形のいずれかのマスに配置されることになる。

 【Uline】
  U=α+βを考える。(これは、UBcheckの返却値に他ならないが)
  Uが最大となるのは、α=46、β=53であり、U=99となる。Uの値に応じて
  (α,β)の組がいくつか決まることになる。現時点の最長手数は78手であるから
  それ以上の解をさがすには、U>=78の範囲を調べればよい。
  (つまり、78<=U<=99が探索範囲)
 
 【問題面の生成】
  上記は、問題面が与えられたときの話としてすすめましたが、最長手数の問題を探索
  するには、(α,β)から問題面を生成する必要があります。
   (1)goalからsubgoalへの変換は、βとUBcheckの(b)のテーブル
      を使用すれば可能です。下図のxの部分が決まる。
       1234 
       xxxx 
       xxxx 
       xxxx 
   (2)subgoalから問題面への変換は、UBcheckの(a)のテーブルだけでは
      不足で(0,1,2,3,4のみなので)、逆変換のマップを別に用意する必要が
      あります。(a)のテーブルを作成するときに同時に作成できる。

 【探索範囲】
   実際に、U>=80の範囲でどのくらいの問題が存在するかをしらべてみました。

     U count total
   +++ 99  (        0,        0) 
   +++ 98  (       40,       40) 
   +++ 97  (       94,      134) 
   +++ 96  (     5900,     6034) 
   +++ 95  (    16922,    22956) 
   +++ 94  (   160213,   183169) 
   +++ 93  (   460953,   644122) 
   +++ 92  (  2277313,  2921435) 
   +++ 91  (  5622308,  8543743) 
   +++ 90  ( 19731609, 28275352) 
   +++ 89  ( 42406243, 70681595) 
   +++ 88  (117330785,188012380) 
   +++ 87  (229318503,417330883) 
   +++ 86  (528165205,945496088) 
   +++ 85  (965488281,1910984369) 
   +++ 84  (1920079055,3831063424) 
   +++ 83  (3332088901,7163152325) 
   +++ 82  (5877064347,13040216672) 
   +++ 81  (9714781332,22754998004) 
   +++ 80  (15534323773,38289321777) 

   結果は、U=80だけでも、約16G個、U>=80では、38G個
   15パズル全体では、約10T個なので、全体の0.4%まで絞りこめた事になる。   
  
   仮に、UBcheckで更に10000分の1に絞れたとしても、数M個の問題を
   Solverで解かなければならない。

   まだ,先は遠いようです。とりあえず、U>=84をしらべてみようかと考えています。
   うまくすれば、84手以上の問題は存在しないといえるかも?(甘いかな?)

   


re:15Puzzle-Solver(WD補足) 投稿者:高橋謙一郎  投稿日:03月28日(水)00時20分13秒

下のWD(WalkingDistance)の説明は自分で読み返してあまりにも意味不明すぎました。
「着想の発端は下のURL」ですので、ここを見て何か感じとっていただければと。。。

ただし、私は幅優先探索で小規模なテーブルを事前に作成しておくことでWDを実現させて
います。計算式だけで求めている訳ではありません。

http://web2.incl.ne.jp/yaoki/slide.htm


re:15Puzzle-Solver 投稿者:高橋謙一郎  投稿日:03月27日(火)23時42分56秒

15パズル高速ソルバー開発に、また新たな進展がありましたので報告します。

■MDは上下動と左右動に分割すべし
前回報告したID(InvertDistance)は上下動と左右動を別々に求めて両者を合算
していますが、MD(ManhattanDistance)も実は上下動と左右動の合算によるので
あることを再確認しましょう。合算した結果どうしを比較してより厳しい値を
LowerBoundとするよりも、上下動どうしのMDとIDを比較し、左右動についても
同様にして得た「結果の両者を合算」してLowerBoundを求めた方がより良い結果
を得ることが出来ます。

           [Fig.1]          [Fig.2]
      私が提示した78手問題  deepgreenさんが提示した78手問題
          0 15 14 13         15 11 14 13
         12 11 10  9         12  0  9 10
          8  7  6  5          8  3  6  5
          4  3  2  1          4  7  2  1

1.(MD,ID)合算後に比較 76秒           2969秒
2.(MD,ID)比較後に合算 68秒           2469秒


■WD(WalkingDistance)
LowerBoundを得る、また新たな概念を見つけました。見つけたというよりも無理
にひねり出した感があります。プログラム的にも手の込んだ方法なので掲示板
での説明はちょっと困難なので触りの部分だけを簡単に説明します。

MDを上下動と左右動に分割してMDを改めて眺めて見ると「MDって随分あまいなぁ」
と思えてなりません。下のFig.3ではMD=4ですが「たった4手で解ける訳がない!」

     [Fig.3]
      1  2  3  0
      5  6  7  8
      9 10 11 12
     13 14 15  4

上下動だけに着目した(左右動は考えない)場合、最低でも11手は必要になる。
これがWD(WalkingDistance)です。つまりFig.3の場合、上下動のWDは11となります。

WDはMDの完全上位互換の値をたたき出します。この時点で私のプログラムからはMD
は完全に消滅しました。私自身ビックリした成績がこれです。

            [Fig.1]   [Fig.2]
1.(MD,ID)合算後に比較  76秒    2969秒
2.(MD,ID)比較後に合算  68秒    2469秒
3.(WD,ID)比較後に合算   9秒     371秒 <-ここ

■次の課題
初期LowerBoundが小さいくせに最短手数の長い問題というのはあるものです。
この掲示板を見ていないだろうと思われるBINGOさん出題による次のFig.4です。

     [Fig.4]
      1  5  9 13
      2  6 10 14
      3  7 11 15
      4  8 12  0
  (WD=20/20,ID=12/12) LowerBound=40

もう解は得ましたが依然として一昼夜ものです。こういう問題にも何か弱点があるはず!


WD(WalkingDistance)の詳しい解説はID(InvertDistance)も含めていずれHPにアップ
しようと思います。が、その前にdeepgreenさんから「15パズルの最長手数問題」が
解決されてしまいそうな予感も、、、、


re:15Puzzle-Solver  投稿者:deepgreen  投稿日:03月23日(金)01時44分07秒

こんばんは、deepgreenです。

高橋さんのID(invertDistance)は,非常に素晴らしい着想です。
これで私の悩み(速いSolverがほしい)が解決しそうです。


re:N=17(ナンバープレイス) 投稿者:高橋謙一郎  投稿日:03月23日(金)00時27分01秒

あらさん、こんばんは。

N=19を7個も見つけるとはスゴイ腕前ですね。15パズルの最長手数問題に行き詰まるか
解決するか、何かしらのタイミングがないと「究極のナンプレ問題」に進めそうにあり
ません。申し訳ありません。気にはしているのですが頭と体がふたつほしいです。


re:15Puzzle-Solver(訂正) 投稿者:高橋謙一郎  投稿日:03月22日(木)23時19分21秒

失礼しました。IDの説明にある斜軸変換とは縦横変換のことです。


re:15Puzzle-Solver 投稿者:高橋謙一郎  投稿日:03月22日(木)23時13分58秒


 これは面白い展開になってきましたね。上限値に着目したのは素晴らしいです。
当時、私は上限値をあまり気にしていなかったので盲点でした。MD=58以下の面
にとんでもなく手数のかかる面があるのか、それとも4×4の最長手数そのもの
が80〜84程度なのか。今年中にはかなりの成果が出そうですね。

ところで、私は高速ソルバーの開発に力を注いでいたのですが、その中からある
程度の成果が出た事柄を書いてみます。

■縦横変換
左上から右下への対角線を軸にして盤を反転させるのが縦横変換です。
このとき盤の数字そのものも変換させます。その数字の変換には変換表があり、
完成局面を単純に縦横変換させて得られます。例えば3×3の最長手数面は2つ
ありますが、この縦横変換を行うと2つの面は全く同じ面であることが分かりま
す。
               縦横変換      数字変換
   6  4  7      6  8  3      8  6  7
   8  5  0  ->  4  5  2  ->  2  5  4
   3  2  1      7  0  1      3  0  1
(最長手数面1)              (最長手数面2)

数字変換表
    0   1   2   3   4   5   6   7   8
    0   1   4   7   2   5   8   3   6

4×4の最長手数面の候補群から、この変換によって約半分を切り捨てることが
可能になります。

■ID(InvertDistance)
現時点でLowerBoundを得るのにMD(ManhattanDistance)とPDB(PatternDataBase)
がありますが新たな概念として「転倒距離(InvertDistance)」というものが存在
することを発見しました。
 先ず転倒数を数えます。転倒数の意味が分からない場合は「4x3の最長手数
探索プログラム」の説明を見てください。さて、ピースの上下動によって転倒数
は、-3,-1,+1,+3の変化があります。このことから「最低限必要な上下動」の回数
は、転倒数/3によって得られることになりますが、この計算が割り切れなければ
余りを加算します。次に「最低限必要な左右動」の回数を得るために斜軸変換を
行い同様の計算を行うと最低限必要な左右動の回数が求まり両者を合算した値が
ID(InvertDistance)になります。例えばCマガ2000/11に載せた78手の問題[Fig.1]
はMD=58ですがIDを計算すると70になります。さらにこのIDはMDと同様に親局面か
らの差分のみで求められるという利点もあります。ちなみにこの問題はMDとIDを
使って76秒で解けました。

     [Fig.1]
       0 15 14 13
      12 11 10  9
       8  7  6  5
       4  3  2  1
     (MD=58,ID=70)
     LowerBound=70

■逆解き
ありきたりな発想ですが逆解きも検討しています。かなり技巧的な技を使っている
のですがプロトタイプでのテストでは結構いい成果が出ていますが、もう少し検討
してから報告します。


re:15Puzzle-Solver   投稿者:deepgreen  投稿日:03月22日(木)01時43分53秒

こんばんは、deepgreenです。

とりあえず、85手以上の問題があるかどうかを探ってみました。

MD=60の問題(全部で 41,472個)には、85手以上の問題は存在しない。
MD=59の問題(全部で331,776個)にも、85手以上の問題は存在しない。
(MD=58の問題は未調査)

ことがわかりました。 探索時間は、約4300秒です。

少し仕組みを説明します。

ある15パズルの問題が与えられたとき、その問題が高々何手で解けるかを判定する関数
(UBcheck:UpperBound check)をつくりました。たとえば、前回の問題の場合は、

  高橋さんが解いた78手の問題   最短手数78手の問題  
   (MD=58)         (MD=60) 
    *  f  e  d              f  b  e  d
     c  b  a  9             c  *  9  a
     8  7  6  5             8  3  6  5
     4  3  2  1             4  7  2  1

      UB=86−>84        UB=82−>82
   
 高橋さんの問題は、初期状態では86手以下となりますが、少し局面を展開すると84手
 以下の問題とわかります。(判定時間は150ms) 私の問題の方は初期状態で82手
 以下の問題と判断できますが、少し局面を展開しても変わりませんでした。 
 (コストの割には、よい上限値をもとめることができる)

 UBcheckを使って、MD=60,59の問題で85手以上となるものを探索すると
 上記の結果がえられました。
 
【UBcheckの仕組み】
 途中にsubgoalをおき、問題面からsubgoalまでの最小手数とsubgoal
 からgoalまでの最小手数の和を求めるだけです。高速化のために、2つのテーブル(a),
(b)を準備してテーブルの検索だけで済むようにしてあります。多分、1つの局面なら数μs
 でもとめることができるでしょう。

   X −(a)−> subgoal −(b)−> goal

 subgoalとしては、以下の2パターンを考えました。

   1234     1xxx
   xxxx     5xxx
   xxxx     9xxx
   xxxx     dxxx
 
 補足)(b)のテーブル作成には、高橋謙一郎さんの4x3の最長手数探索プログラムを
    利用させていただきました。(HPに公開されているもの)
    おかげで、少し改造する程度ですみました。ありがとうございます。 


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