問題

www.topcoder.com

方針

2種類のビームサーチによる探索

通常のビームサーチ
最長パスを見つけるためのビームサーチ

ビーム幅がある程度確保出来る場合は通常のビームサーチをそうでない場合は最長パスを見つけるためのビームサーチを使用しました。

最長パスの探索

今回の問題ではなるべく大きな値の石を置くことで獲得出来るスコアが増えるので、大きな値の石を置くために最長パスを探索しました。

パスの伸ばし方

パスを伸ばすのは 1の石を使うことで可能となります。

任意の石の周辺の空きマスに対して +1 した石を置きます。

このままでは「2以上の石を設置する場合は周辺に 2個以上の石が必要」という条件に反するので、さらに周辺のマスを探索して 1が置けるマスを探して設置します。

条件に反していない場合はそのまま +1 した石を置き続けることが出来ます。

このように 1の石の周辺は +1 した石が置きやすくパスを伸ばすのに非常に役に立つので、この動作を続けることで長いパスを作成することが可能になります。

ビームサーチによるパスの探索

パスの伸ばし方はわかりましたが適当に探索してもいい感じのパスを見つけてはくれないので 2つほど大きな指標を与えてなるべく大きなパスを見つけてくれるようにしました。

石を置く際にはなるべく斜め置きを避けるようにする
なるべく外側からマスを埋めるようにする

探索については以下の通りです

画面端の任意の位置を選択してそこから開始
周辺 8マスの空きマスを探索し「現在の値 + 1」の石を置く
- 周辺に 1の石がない場合は 1の石を置ける場所を探して置く

斜め置きを避ける

石の影響範囲の関係上、斜めに移動するよりは縦 or 横に移動するほうが 1の石をより効率的に利用出来るので斜め移動に対してペナルティを与えています。

斜め移動と横移動を比べると横移動のほうが効率よく 1の石を利用できている。

外側のマスを埋めるようにする

長いパスを作ってもらうためになるべく端を詰めながら移動して欲しかったので、グリッドの中央からどれだけ離れているのかを各セルに対してスコア化してその合計値を評価しました。

こうすることでなるべく端のマスを通りながら移動する経路を評価することが出来たと思います。

この探索で見つける経路は以下のようなイメージになります

パスの反転

この探索で見つけたパスは基本的に「外側 -> 内側」へと向かうのですが、この状態だと値の大きな石が中央付近に来ることになります。値の大きい石の周辺は周辺の合計値が大きくなってしまうので利用が難しく空きマスを多く無駄にしてしまう可能性があります。そのため、なるべくブロックの多いマスに追いやって影響を弱くしたいです。

幸い、見つけたパスは始点と終点をちょっと変更すれば逆向きに出来ます。逆向きにすることで「内側 -> 外側」に向かう経路となり大きい値の石を画面端に追いやることが可能となり影響力を弱めることが出来ます。

逆向きにした経路

最初から「内側 -> 外側」に向かう経路を探索すればよいのではと思うのですが、自分の評価関数だと「内側 -> 外側」の経路を作ろうとするとうまく画面端にピッタリくっつくような経路が出来なかったのでこのような反転処理を入れています。

残った空きマスを探索して石を置く

経路を作り終わった後は残りのマスをビームサーチで探索して得点が大きくなるように石を置きます。

時間制限まで処理を繰り返す

ここまでの処理が 1セットで、後は制限時間の間「経路の初期位置」「斜め移動のペナルティの値」「画面端ボーナスの値」をランダムに変えながら繰り返して一番高いスコアが得られたものを採用します。

通常のビームサーチ

「グリッドのサイズが小さい」 or 「ブロックの比率が高くて最長経路の探索が困難」な場合は普通のビームサーチで探索を行いました。

こちらに関しては特筆することも無く。評価としては主に以下の通り

盤面の石の値の合計値
画面端に値の大きい石が存在しているかどうか

後は zobrist hash による重複排除を行っています。

感想

問題自体はシンプルだったが、シンプルが故に評価が難しかったです。小さいサイズでのビームサーチの結果を見るに最長経路を作るよりかはいかにして空きマスを少なくするのかが重要っぽい感じではあるのだが、いい感じの評価関数を見つけれられずに終わった。最長経路を作らずにビームサーチをしたほうが得点は高くなるのでなるべくビームサーチに置き換えたかったがどうしてもグリッドサイズが大きくなるとビーム幅が十分に確保できなくなってしまうので諦めた。

そのビームサーチも評価関数があまり良くなさそうなので改善する余地はいくらでもありそう。「評価関数を良くする」->「ビーム幅が少なくても高スコアが取れる」->「ビームサーチ出来るグリッドのサイズが増える」->「得点がUP」という感じになるはずなので後半は評価関数の改善に主に力を入れてたけどダメだった。

Seed 1: 263.0
Seed 2: 289489.0
Seed 3: 154934.0
Seed 4: 174324.0
Seed 5: 154501.0
Seed 6: 10181.0
Seed 7: 1289.0
Seed 8: 5684.0
Seed 9: 11545.0
Seed 10: 97828.0