simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

AHC011 Sliding Tree Puzzle 参加記

問題

atcoder.jp

方針

主に 3つのパートで構成されています

  • 与えられたパネルから木を構築する
  • 構築した盤面の各パネルに対して数字を割り振る
  • (N * N - 1) puzzle を解く

木の構築

木の構築は盤面を焼き鈍して作成を行いました。木の条件が厳しそうなイメージだったので「パネルの交換だけで出来るのか?」と疑問だったのですが実装してみたら意外と速く構築出来て驚きました。

近傍としては「2つのランダムなパネルを選択して入れ替える」の 1つでしたが選択時に色々と制限をかけています。

同じ種別のパネルを選択しない

同じ種類のパネルを入れ替えても状況は変わらないのでそれは行わないようにします

確実に悪い配置とわかる場合は除外する

「確実に悪い配置」というのは「そこにパネルを置くと絶対に木が完成しない」状態を指します。

図のように画面端に向かって枝が伸びているようなタイルが存在する場合は絶対に木が完成しないので、このような配置にならないように選択を行っています

どちらかは必ず接続状態を維持するようにする

タイルを交換する際にどちらのパネルも接続状態が途切れてしまう場合は交換を行いません。

例えば緑のマルで囲まれた部分を交換すると両方のパネルとも周辺のパネルと接続状態が途切れてしまいます。このような場合は交換を行わず再度タイルの選択をやり直します。

評価値

盤面状態の評価は「連結成分の個数 + 元の盤面からどれだけ近いか」で計算を行いました。

連結成分の計算は盤面全体を DFS で探索して計算を行っています。

元の盤面状態からどれだけ近いか

今の位置から元のパネルの種類の最短距離を計算してその合計値が少ない状態を良しとしています。

評価値については事前に計算しておきます。図は評価値の事前計算の一例です

種別 9 のタイルについて評価を行います

各マスについて種類 9 のパネルとどれだけ離れているのかを計算し dy * dy + dx * dx の最小値をテーブルに保存しておきます。

盤面評価の際はすべてのマスについてこの値を合計したものを利用しています。(この値が大きいほど元の盤面から乖離している ≒ 元に戻す手数が多いと考えられます)

(コンテストの途中、元の位置の距離 (dy * dy + dx * dx) をコストにしてみましたが、特にスコアに変化がなくただ試行回数が減っただけなのでこの評価値をそのまま採用しています)

焼きなましの打ち切り

盤面構築の際にどんなに試行回数を重ねても連結成分が減らない局所解に陥ることが多々あったので、 10万回スワップを行って 1回もスコアの更新が発生しなかった場合は処理を打ち切りました。

破壊的な近傍を用意して局所解からの脱出を行うよりも再実行のほうがコスパが良かったのでそうしています。

複数繰り返して色々な盤面を得る

1回の焼きなまし処理はだいたい 0.1 sec で終わって、盤面が得られる確率が大体 50% ぐらいだったのでこの処理を設定した時間 (今回は 1.7 sec) が来るまでに複数回実行して、様々な盤面を取得します。

構築した盤面の各パネルに対して数字を割り振る

完成した盤面に対して数字を割り振っていきます。割り振りには最小費用流を使用し、辺のコストには元の盤面からの距離 dy * dy + dx * dx と 1 ~ N のランダムな値で計算しています。ランダムな値を追加しているのは距離だけの評価だと毎回同じ数字の割り振りになってしまい、もし出来上がったものがパズルとして達成不可能な場合に数字を振り直したいのでランダムな値を追加して別の割り振りパターンになるようにしています。

パズルの達成が可能な盤面でコストが一番低くなるものを最終的に解く盤面として採用します。

完成可能かどうかの判定は以下のサイトを参考にしました。

manabitimes.jp

外周に近いマスのコストを高くする

n-puzzle は真ん中を先に揃えても後で壊される可能性が高く、基本的には端から揃えていきたいのでコストを計算するときに端のほうのコストが高くなるように設定しました。

配置コスト 5 + 9 = 14

配置コスト 4 + 10 = 14

画像では両方とも同じコストになるので距離のみの評価だとどちらを選んでも良いのですが、実際にはこの距離コストに係数を掛けたものを利用しています。

係数の値は端に近いほど高くなるように設定しています。(実装的には max(y, N - y + 1) みたいな感じです) この係数を使った場合は以下のような結果になります。

配置コスト(new) (4 * 5) + (6 * 9) = 74

配置コスト(new) (6 * 4) + (4 * 10) = 64

結果として、端のタイルはなるべく短い手数で済むような配置になります。(スコアとしては 2 ~ 3000 点ぐらいの向上)

(N * N - 1) puzzle を解く

盤面構築が終わったら後はパズルを解くフェーズになります。今回はビームサーチを利用しました。序盤は高速化が足りてなくて N が大きいケースでは外堀を埋めるルールベースを書いていましたが明らかに手数が多くて悪手だと感じていたので最低限のビーム幅が確保できる状態まで高速化しました。

評価関数

盤面の評価としては主に元の盤面からの距離から計算されるコストと Linear Conflict を少し改造したものを使用しました。(あと端が揃っているかどうか)

距離による評価

元の位置との縦軸の距離の差分 (dy) 横軸の距離の差分 (dx) を調べて、 dy * dy + dx * dx をコストとして計算します。 dy + dx のマンハッタンディスタンス (MD) の場合だと同じ評価値で揃える難易度が全く異なるものが発生しそうだったので2乗の方を採用しています。

特定のパネルを任意の位置に移動させたい場合に「同じ方向に連続で移動する」という動作がかなり手数を使ってしまうので、それを避けるようになるべく「縦の差分」と「横の差分」の差が少ないほうがコストが低くなるように設定しています。

端を揃えた状態の評価

n-puzzle では端が完成するとそれ以降は端を操作する必要がなくなるので、端が揃った場合はボーナス得点を与えています。

ただ、画像のように一部の端だけが完成し続けると最終的に端を崩さないと完成しない状況になりうるのでこのボーナスは「画面端から距離 Xの場合に有効とする」 といった感じで変数を使って制限を加えていました。(変数の値としては盤面のサイズの半分を超えないように設定しています)

隣接マスの関係性の評価

盤面全体をみて評価出来たほうがより精密に評価を出来るようになるとは思いますが、今回は高速化の都合上 1回の移動で変動したタイルの隣接マスだけを見て評価を行いました。

Linear Conflict

Linear Conflict についてはこちらのページを参考にしました。

michael.kim

隣接マスをみて完成図の同じ行 or 列に所属していて番号が逆転していた場合はペナルティを与えています。

特に、お互いが後 1手で完成する同士であった場合はより重いペナルティを与えています。(角でこれをやられるとかなりの手数を消費するので)

後はお気持ち程度の評価ですが、同じ列 or 行に所属していない場合でもゆるくペナルティを与えています。

本来であれば 97 の左側に来るべきなので減点する。

あと 1手同士が隣接している場合にボーナス

15 puzzle の攻略サイトを調べていると「後から車庫入れ」という形になっているとパズルがスムーズに解けるということだったので「残り 1手同士が隣接している」状態にボーナスを与えました。

studio-boiler.com

なので画像のような盤面状況が評価されることになります。

ボーナスとしては小さい値でしたが外すと 2 ~ 3000 下がったのでそれなりに有効だったみたいです。

zobrist hash による重複排除

同じ盤面を探索しないように zobrist hash による重複排除を行っています。重複排除の処理を外すと得点が 10000 下がったのでかなり効果があったみたいです。

Zobrist hashing - Wikipedia

感想

方針自体は maspy さんが初日に 38,307,047 を叩き出していたのでかなり早い段階で決まりました(n-puzzle を構築してそれを解く)あとは、手数を短くするために盤面構築の精度を上げるか n-puzzle solver の精度のどちらを上げるかでちょっと迷っていましたが最終的には solver の精度を上げたほうが良さそうだと思ったので評価関数を色々試してはみましたが 1位に追いつくことが出来ませんでした。

ビームサーチが題材の場合は評価関数を頑張らないとどうにもならないので(ビーム幅を 10倍にしても 1位のスコアに追いつけない)、15-puzzle の資料を色々読んでいましたが 4 * 4 というサイズの小ささに特化した手法が多くて Linear Conflict のような汎用的なものを見つけることが出来ませんでした。(本当はあったかもしれないけどそこは調査力が無かったということで)

ところで 6/23 2:00 から Marathon Match 137 が始まる予定なので興味がある方は是非参加してみてください。(世界大会に向けての予選なので恐らく強い人がたくさん参加する可能性が高いです)

リンクは参加方法についてのガイドラインになります。

www.topcoder.com

今回の問題では「焼きなまし」と「ビームサーチ」というマラソンマッチにおける基本的な探索手法を同時に扱えたのでとても面白かったです。個人的には AHC の時間制限を 10sec あたりまで伸ばしてくれたら時間管理をもっとゆるく行えて気持ちが楽になりそうだなと思っています。(自分の評価関数だとへたにビーム幅を下げると解が見つからない可能性があったのでこのあたりの調整がちょっと面倒でした)