ホームページへ戻る１５パズル自動解答プログラムの作り方現時点において幅優先探索では４×３(１１パズル)の最長手数解を求めるのが限界のようです。４×４(１５パズル)になると幅優先探索はもう使えません。そこで反復深化を使います。反復深化は同じ探索を繰り返し実行しますからソルバーとしてはとても遅いものになりがちなので「なんとか工夫して少しでも高速なソルバーを作る」これがここでのテーマとなります。
深さ優先探索に「深さ制限」を設け、その「深さ制限」を徐々に大きくしながら探索を何度も繰り返すのが反復深化(IDA*)という探索アルゴリズムです。反復深化には「最短解が求められる」「局面を保存する場所が要らない」「プログラムが簡単に書ける」といった利点がありますが、同じ探索を何度も行うので「探索時間がかかり過ぎる」それから「堂々巡りする探索の流れを防げない」という欠点があります。ただ、堂々巡りを防げないと言っても次の１手で親局面に戻ってしまう「１手の手戻り」程度なら簡単に防止できます。それだけの工夫でもかなりの時間を短縮出来るようです。
反復深化には常套手段ともいえる枝刈り法があります。たとえば「５パズル」を解いている途中を示した下図で１の駒が最後にたどりつく場所まで２マス離れているので「最低でも２手」は絶対に必要となります。
最初の空きマスの位置によって解の手数が偶数か奇数か決まってしまいます。ボードのマスに白黒の市松模様を付けたとして、１手動かす度に空きマスの位置は市松模様上の白黒を交互に移動するので、空きマスの最終地点が黒で最初の地点も黒なら解の手数は偶数になり、最初の地点が白なら解の手数は奇数になります。したがって、深さ制限の初期値を0か1にした後は増加量を＋２として深さ制限を大きくしていくことが出来ます。さらに欲を言えば初期値は問題面でのLowerBound値から開始した方が良いでしょう。
MDとは全く異なる考え方を持ちLowerBoundとして採用できる「転倒距離」という別の概念が存在します。 先ず転倒数を数えます。転倒数の意味が分からない場合は「１１パズルの最適解が最長手数となる面の探索」の説明を見てください。さて、駒の上下動によって転倒数には、-3,-1,+1,+3の変化が生じます。このことから「最低限必要な上下動の回数」は、転倒数÷3の計算によって得ることができます。さらにこの計算に余りが生じればその余りを加算することができます。例えば転倒数=7なら+3+3+1で最低3回、転倒数=8なら+3+3+1+1または+3+3+3-1で最低4回の上下動が必要になるのです。
例えば参考文献(2)に載っている78手の問題(下図)はMD=58ですがIDを計算すると70になります。さらにこのIDはMDと同様に親局面からの差分のみを考慮して求められるという利点もあります。尚、このIDの最大値は70です。
ID(InvertDistance)は上下動と左右動を別々に求めて両者を合算していますが、MD(ManhattanDistance)も実は上下動と左右動の合算によるものであることを再確認しましょう。MDを上下動と左右動に分割して改めて眺めて見ると「MDって随分あまいなぁ」と思えてきます。下の図ではMD=3ですが「たった３手で解ける訳がない！」
「空きマスのある段」と隣接する上か下の段から駒をそこに移動してくることができます。上の例では「２段目」にある「２段目に属する駒」を「１段目」に移動する方法しかありません。それが１手という考え方になります。 さて、このような探索を「完成された状態から」の逆解きで幅優先探索を実行し、結果をデータベースとして保存しておきます。データベースといってもデータ量はわずか24964パターンだけでした。
このデータテーブルを参照すれば任意の状態からMDより質の良い「最低限必要な上下動の回数」を得ることができます。（もちろん左右動についても同様）これがWD (WalkingDistance)です。
MDやIDは親局面との差分のみを計算してその値を得ることが出来ましたが、WDのようにデータテーブルを参照してその値を得ようとした場合、参照に係るコストは意外に大きなものがあります。１６個のマスのすべてをスキャンしてテーブルを参照するためのキーを求める必要があります。 しかし、ここで参照キーを計算無しの一発で知ることが出来るうまい方法があります。 参照するレコードの中にはWDの値だけでなく次の手(上下左右)によって次局面となる局面の参照キーをリンクさせておけばよいのです。 WDテーブルの場合は「上か下かにＮ段目に属する駒を移動する」という８通りの選択に基づいた次局面の参照キーをレコードに書き込んでおくことになります。最もこんな贅沢な双方向リンクリスト構造を形成出来るのはWDのデータテーブルが24964個しかないからです。
IDとWDのうち、より厳しい値(大きい値)をLowerBound値にして枝刈りさせる反復深化のプログラムは、例えばこのようなものです。 ソルバー本体は[puz15sv.c]です。コンパイルして実行させるには、先にpuz15wd.cを実行して得られるpuz15wd.db (610KBのWDテーブル)を同一フォルダに置いておく必要があります。 さて、このソルバーはどの程度の性能があるのか。そもそもこのプログラムは「１５パズルの最長手数は何手？」という究極問題を解く目的のためのパーツとして作ったものです。その目的からすれば、このプログラムはまだまだ遅すぎて使い物になりませんが、通常のソルバープログラムとしてはそれなりの性能になったのではないかと思っています。
注意) ID (InvertDistance)とWD (WalkingDistance)は私のオリジナルです。転用・流用の際は必ずこのページを参考文献として明記してください。
このプログラムには天敵とも言える悪魔のような問題面があります。それが下の問題面です。WDもIDもまるでザルのように手数を取りこぼしてしまいます。これを解決するには参考文献(1)の主題となっているPDB(PatternDataBase)を追加する必要があるでしょう。(そのバージョンは「ＰＤＢを使った１５パズル自動解答プログラム」をご覧下さい。) 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 0 (WD=20/20,ID=12/12) LowerBound=40 [72 moves] time=77565sec (約２１時間３３分) 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それにしても「１５パズルの最長手数は何手？」というテーマですが、現時点で８０手の問題は発見されています。また参考文献(1)には最長手数は９０手以下であると書いてあります。つまり８０手〜９０手の範囲内に獲物は潜んでいます。 サムロイドがこの１５パズルを考案したのは1878年のことです。１００年以上の魔法が解ける瞬間は近いのでしょうか。(下の追記を見てください)
１９９７年にスイスの研究チーム(Adrian Brungger, Ambros Marzetta, Komei Fukuda, Jurg Nievergelt)によって「１５パズルの最長手数は８０手」であることが立証されていました。NEC製CENJU-3という並列コンピュータ(CPU=64個-128個)を使用して２３０日間かかる探索を３日間で処理したとのことです。 ホームページへ戻る | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
