買い物ログ別館/Kaimono-log bekkan

GDD DevQuiz、今年の本命はスライドパズル。拡張された15パズルです。まずはJavaで解いて、最後にgo言語で上積みしました。

Java実装
Go実装

問題文は以下のとおり。

幅が 3 マスから 6 マスで、高さが 3 マスから 6 マスのボードが与えられます。 各マスは、パネルが置かれているか、壁があるか、空白であるかのいずれかです。 パネルには 1 から 9 あるいは A から Z のいずれかの文字が書かれており、同じ文字の書かれたパネルは存在しません。 壁は 0 個以上存在し、空白のマスはただ 1 つだけ存在します。 例えば、次のようなボードが与えられます。ここで、壁は = で、空白は 0 で表されています。

40=
215
=86

空白は、上下左右のマスのパネルと入れ替えることができます。上のマスのパネルと入れ替えることを U とよび、同様に、下左右のマスのパネルと入れ替えることをそれぞれ D, L, R とよぶものとします。壁を空白やパネルと入れ替えることはできません。
パズルを解くというのは、与えられたボードの各マスを操作して、ゴール状態に持っていくことです。
ゴール状態とは、上の行から各行順番に、左から右に 1, 2, 3, 4, ..., 9, A, ..., Z という順にパネルが並び、最も右下のマスに空白が配置された状態のことです。壁のあるマスに対応するパネルは存在しません。例えば、左上のマスが壁であれば、ボード上に 1 のパネルは存在しません。
(中略)
いま、使うことができる L, R, U, D それぞれの総数があたえられます。 この総数は全パズルで共有されています。 例えばあるパズルを解くために L を使い切ってしまった場合、 他のパズルでは L を使うことはできません。 この総数を超えないようにしながら、なるべくたくさんのパズルを解いてください。

このパズル、5000問あるのです。そして一問が0.01点。100問といてやっと1点。手で解くことをある程度防ぐ設問ですね。

15パズルでの評価関数は各駒のゴールに対するマンハッタン距離合計を使うのがポピュラーな模様。その方向で、A*探索をRubyで試しに実装してみてあまりの遅さに音をあげてすぐにJavaにうつりました。

まずはメモリをじゃぶじゃぶつかって試みてみました。この時点で一晩で1000問程度回答。かなり厳しいです。

次はゴール状態から初期状態に向かってのA*探索を同時に走らせる双方向A*探索してみました。これでもくろみ通り、探索空間が小さくなってかなり成績があがり、3300問程度。その後はパラメータを少し調整し、メモリを増やすなどして、4300問まで頑張りました。

メモリ使いすぎで探索中にMacBook使えないのが辛くて、こんどはメモリをあんまり使わない反復深化深さ優先探索(IDDFS)を実装してみました。が、新たな解はほとんどみつけてくれません。

このあたりで飽きたのでgoでIDDFSを実装しなおして遊んでいたら「探索したノード数が一定数を超えたらその時点で評価値最良のノードひとつだけ残してそこから再度探索する」という乱暴な枝狩りをおもいつきました。これがそれなりに効果的で、最終的には4818問で終了しました。

この問題、30人近くが5000問すべてを解いています。そのひとたちは、そもそもメモリの使い方を最初からすごくしぼっていて、私の無駄遣い富豪プログラミングとは一線を画している様です。評価関数もいろいろ工夫されています。コード公開しているひと多数なので、後でじっくりみてみようと思ってます。