ＰＤＢを使った１５パズル自動解答プログラム

■理論編(下限値枝刈りのスキップ化)

この考えは１５パズルというよりも反復深化と下限値枝刈りの関係について考察
したもので「ＰＤＢ等を参照するという重い処理」で下限値枝刈りをする場合の
コストの軽減化に関するものです。枝刈り判別式は、

       depth + LowBound > MAX_DEPTH
                                  depth     = 現在の深さ
                                  LowBound  = 以後最低限必要な手数
                                  MAX_DEPTH = 今回の深さ制限

です。さて、初期状態でLowBound=40だったとします。MAX_DEPTHは何度か反復
を繰り返し、次ぎの探索での深さ制限は MAX_DEPTH=50 だったとします。
では最初にとても重要な着目点を明記しておきます。

　「下限値は親局面に対して−１か＋１の値しか取れない」

これはLowBound関数がどのような行程で作ったのかを考えれば一目瞭然です。
すると一番最初に枝刈りが発生する可能性のある地点は最悪の進路を辿った
場合であり、親局面の下限値に単純にプラス１していって、枝刈り判別式が
成立する最初の地点になります。

[Fig.1]     MAX_DEPTH=50 の場合
    depth + LowBound = 計算結果
      0       40        40
      1       41        42
      2       42        44
      3       43        46
      4       44        48
      5       45        50
      6       46        52  <- ここでMAX_DEPTHを超えた

結局、depth=5以下での枝刈りは「絶対に有り得ない」ことになります。
だから、この範囲で下限値を求めて判別式を調べるという重い作業は全く
無駄ということになります。

depth=6になった時に初めて下限値を調べて判別式を適用すれば良いのです。
そしてさらに、ここで実際の下限値がLowBound=42だったとすれば、

[Fig.2]
    depth + LowBound = 計算結果
      6       42        48
      7       43        50
      8       44        52  <- ここでMAX_DEPTHを超えた

となり、次に枝刈りを調べる価値のある地点はdepth=8になります。
このように「枝刈りを調べる地点はスキップ出来る」のです。従来のように
新たな局面を作るたびに枝刈りを調べる方法とこの方法は等価な結果を得ら
れるので「ＰＤＢ等を参照するという重い処理」で下限値を求めなくては
ならない場合には大変に有効な手段だと思われます。

次にLowBound関数には最大値があることに着目して下さい。使用している
LowBound関数の最大値が44だったとすれば[Fig.1]はさらに改善されdepth=6
以下での枝刈りは「絶対に有り得ない」ことが分かります。

[Fig.1の改]
    depth + LowBound = 計算結果
      0       40        40
      1       41        42
      2       42        44
      3       43        46
      4       44        48
      5       44        49
      6       44        50
      7       44        51  <- ここでMAX_DEPTHを超えた

以上の方法を採用することによりＰＤＢを導入しやすくなります。

■実験編(下限値枝刈りのスキップ化)

次にその実験編を報告しますが、いろいろなケースについてテストした結果ではあり
ませんので、ここでの報告には改善も改悪もいろいろあると思います。

そもそもこのダメ押しは悪魔の配置を攻略するのが目的で、究極問題のチェッカー
ソルバーとしては悪魔の配置とは程遠いタイプがほとんどなのでここでのノウハウは
たぶん不要だと思われます。私のテストした限りではＩＤ(InvertDistance)も捨てて
ＷＤ(WalkingDistance)だけで解かせた方が究極問題のチェッカーソルバーとしては
良好な結果が出ています。ＩＤは親局面からの差分のみで求められるものの計算が
ちょっと重いのだろうと思います。


さて、私がテストに用いたＤＢは下図のＬＤＢ(LocalDataBase)タイプの２つです。
　(注意：ただし、ここではあくまでも名称はＰＤＢとしておきます)
悪魔の配置をもろに意識した形になっていて、としひでさんのＯＤ(ObliqueDistance)
と、とても類似しています。実のところ私の理想はとしひでさんのＯＤなのですが
ＯＤだと完全ハッシュ値を求める方法が私には判らなかったので(どなたか分る人はいま
せんか)、やむなくこのようなＰＤＢを用いることにしただけのことです。

     [DB1]             [DB2]
     ＢＡＡＡ          ＡＡＡＢ
     ＣＢＢＡ          ＡＢＢＣ
     ＣＢＢＡ          ＡＢＣＣ
     ＣＣＣ□          ＢＣＣ□
     MAX=56            MAX=58

やはりＷＤの性能がとても良いのでＩＤは捨てています。さらに、探索開始時あるいは
探索途中に、このＰＤＢから得られる下限値がＷＤの下限値を下回ってしまった場合も
動的にＰＤＢの使用を捨てるようにしています。だから悪魔の配置に類似している問題
の場合にしか使われることのない制御構造ですが、悪魔の配置と類似していない問題で
の性能が低下することを恐れたためです。

残念ながら実行結果は「依然として遅い」ということになりましたが２１時間は大きく
下回ったので取り合えずは「よし」としておきます。

  1  5  9 13
  2  6 10 14
  3  7 11 15
  4  8 12  0
(WD=40,DB1=54,DB2=0) LowerBound=54

[72 moves] time=12416sec  (約3時間27分)
 15  14  13   9  10  13  14  11  13  14
 11  15  12  13   7   8  13   7  14   6
  8   3   4  13   7  14   6   8   5  10
  8   6   3   4   2   5   6   3   4   2
  5   6   3   4  15  11   9   8   4   9
  8   4  10   3   2   7  14  15   9  10
  3   2   7   9  10   7   6   5   9  10
 11  12

■ソースコード

　ここで紹介したプログラムはここからダウンロード出来ます。(メモリ64MBあれば実行可能です)

・　puz15wd.c　　WDテーブルを作るプログラム(これは前回のものと全く同じです)

・　puz15db.c　　PDBテーブルを作るプログラム

・　puz15sv2.c　１５パズルを解く新ソルバー本体

　それから、このソルバーの性能ですが、約３時間なんて書くととても遅いようですが、これは特殊なケースであり普通の問題なら充分な使用に耐え得るものだと思います。

　注意) WD (WalkingDistance)は私のオリジナルです。転用・流用の際は必ずこのページを参考文献として明記してください。