MC Digital プログラミングコンテスト2023（AHC019）参加記
自分にしてはまたいい順位が取れたというのと、比較的上位寄りの人で解法が被っていなさそうだったので書きました。図を書く余力がなくて文字ばっかりになってしまったので、わかりづらいかもしれません…
問題
結果
Pretest / System Test ともに 21位 / 738 でした。問題を読んだ時の印象から考えるといい順位だったので嬉しかったです！
解法
準備
上のように正面・右側のシルエットの組とその投影前のブロックが置ける空間のことをまとめて、本記事では「シーン」と名付けています。
要約
- Monte Calro Tree Search (MCTS) を使って、各シーンに共通のブロックを置いていく乱択貪欲を時間いっぱい繰り返しました。
- MCTS のノードは共通のブロックの作り方を表していて、0-indexed で 0 段目をroot とすると、奇数段目で共通ブロックの開始位置とブロックの方向、偶数段目でブロックの大きさを調節します。
- 共通ブロックの作り方は、BFS で出来る限りサイズを大きくしてシルエットを埋めていき、シルエットが全部埋まった後で小さいブロックを逐次的に膨らませます。
- 他にも、貪欲としてプレイアウトの質を高めるための工夫をしたり、MCTS の子ノードを展開する数を減らすためにいろいろ工夫しました。
ベースとなる乱択アルゴリズム
大まかに、①シーン内のシルエットを全て埋める、②小さいブロックの体積を増やす、の流れです。
まず、各シーンで共通のブロックを一つずつ配置していきます。ブロックの配置を決めるためには、具体的には以下の4つを決めます。
- シーン1のブロックの開始位置
- シーン2のブロックの開始位置
- シーン1内のブロックに対してシーン2内のブロックが向く方向
- ブロックの体積
それらをランダムに決めたうえで、各ブロックの開始位置から BFS で共通ブロックを切り出していき、上で定めた指定の体積になるまでブロックを拡大していきます。
次に、①を繰り返して両シーンの全てのシルエットが埋まった段階で、体積が最も小さいブロックを選択して体積を適当に1増やすという操作を、ブロックの体積増加ができなくなるまで繰り返します。これは、小さいブロックの体積を増やすことがスコア上昇に大きく寄与するためです。
以上の2ステップを時間いっぱい繰り返す乱択がベースのアルゴリズムです。
MCTS を使う動機
探索を行う際にそれまでの探索で得た良い形を保存したいです。完全な乱択アルゴリズムだとそれができないけど局所探索ではできるので、このままだと局所探索より性能として劣ってしまいそうです。そこで、せめて最初の方に置いたブロックが結果的に良かったのかを判断していい形として保存するためにMCTS を採用しました。
特に今回のように制約が厳しい問題では、期待値としていいスコアが出ることと最良スコアが更新できることは分けて考えた方がいいとは思うのですが、根本的な解決方法がわからないうえに結果としてただの乱択貪欲よりはスコアが出たのでそのまま採用しました。こういう雑ないい状態の保存方法ではブロックの調整を行うなどは狙ってできないので意図的に設計したアルゴリズムのスコアに到達するのは難しいとは思いますが、どうやっても局所探索できるイメージが湧かなかったので諦めるしかなかったです。
MCTS を使う上での課題
今回対策した範囲でいうと、大きく2つあります。
1つ目に、ベースとなる乱択アルゴリズムではブロックを切り出すために4つの情報を決める必要があり、これをそのまま MCTS のノードとして持たせると明らかに子ノードの数が多すぎて性能が出ません。MCTS を実行するには各子ノードで最低でも1回はプレイアウトを行う必要があるので無駄な探索を含んでしまいそうですし、特定ノードで行うプレイアウトの回数もある程度積まないと ucb1 等のスコアが意味をなさなくなるので、できるだけ子ノードの数を減らす必要があります。
2つ目に、単純な乱択で良いスコアを出すためにはランダムに生成したブロックの全てについて正しい置き方をする必要があり、良い解を作る観点では分が悪いです（極端な話でいうと、何か一つブロックの体積をランダムに1と選択すると、それだけでスコアが悪化する）。少し余計に時間がかかったとしてもプレイアウトの質を何らかの意味で高める必要があります。
工夫の一覧
ブロックの方向をシルエット被覆面積が多い1方向に限定
ブロックを置くために決める情報のうち「シーン1内のブロックに対してシーン2内のブロックが向く方向」は24パターンありますが、そのうち限界まで大きいブロックを作った際のシルエットが被覆できる面積が多いものだけを選択しました。動機としては、被覆面積が多いほどブロックの個数が少なくプレイアウトを終えられることが期待されそうだったり、被覆面積が多く作れるところを選んでおけば後ほどブロックを縮めたい場合にも自然に対応できるだろうということ等がありました。
これは、MCTS のノード展開の時にもプレイアウトの時にも利用しています。
MCTS のノードを「ブロックの体積」「ブロックの位置」に分割
例えば、ブロックの開始位置の組が100パターン、ブロックの体積が平均的に最大20だとして、これを全パターン組み合わせて作ってしまうと2000個のノードが展開されてしまいます。前述のように、各ノードに最低数回は通さないと意味をなさないと思うと、現実的に良し悪しの比較評価をするには少し辛いです。そこで、0-indexed で 0段目をルートノードとすると、以下のように MCTS の木の深さを奇数段目と偶数段目で変えました。
- 奇数段目：ブロックの開始位置と方向だけ決める（方向は、前述のようにシルエットの被覆面積が最大の方向に固定）
- 偶数段目：ブロックの大きさだけ決める
偶数段目は4つ全ての方向が決まっていますが、奇数段目でプレイアウトをする際はブロックサイズを決める必要があるので、プレイアウトの方法と同様にして毎回ランダムにブロックサイズを決めます。こうすることで、評価値の期待値が悪そうな位置についてはブロックの大きさを調整せずに済むので、全パターン展開するよりも枝刈の度合いが高まることが期待できます。先の例でいうと、ブロックの開始位置の組100パターンのうち、有望なパターンだけ体積を調整するためのノードの展開がなされることが期待されます。
ブロックの開始位置の片方をシーンの端点に限定
各シーンでのブロックの開始位置の組を列挙する時、各シーンで原理的に置ける点を列挙すると置ける箇所が膨大になってしまい展開するノードの数が多くなってしまうため、置ける位置の組を制限したいです。
例えば、端（= シーン内で原理的に置ける位置を3次元のグリッドグラフとしてみた時、次数が小さいマス）からブロックを埋めていくような操作ができると、候補が著しく削減できて嬉しいです。しかし、ビジュアライザなどで見ても探索の過程で両シーンとも端にブロックが置かれるとは限らないため、これを採用すると多様性の面では大きく損なわれてしまいそうです。
そこで「片方のシーンは端から、もう片方のシーンは任意」という組の取り方を採用しました。これなら、1つのシーン内の探索過程には常に端の方にあるブロックは存在しますので、大きく自由度を損ねることなく組の数を削減できることが期待できます。
これは、MCTS のノード展開の時にもプレイアウトの時にも利用しています。
ブロック位置の組を、たくさんシルエットが埋められる組に限定
MCTS の奇数段目として子ノードを展開する時、ブロックの開始位置を端点に限定しても多くなってしまう場合があったので、展開するノード数が一定以上になった場合は埋められるシルエットの面積が大きい候補だけを残しました。
小さいブロックサイズの候補を削除
MCTS の偶数段目やプレイアウトの過程でブロックサイズを決める時、例えばサイズ1のブロックを選択するメリットはありません。そこで、選択するブロックサイズにも以下のような制約を設けました。
- そもそも作れる最大ブロックサイズが小さかったら、常に最大で作る
- 原理的に作れるブロックサイズが十分大きかったら、確率 p で最大サイズ、残りは最大サイズの半分から最大サイズ位まで一様ランダムにブロックサイズを選択
ブロックの各開始位置を何回かランダムに選択して、シルエットの被覆面積が多い開始位置を選択
プレイアウトの過程を観察すると、原理的に小さい体積しか作れないブロック位置をたまたま選択してしまったためにスコアが一気に悪化するようなケースが散見されました。そこで、ブロックの方向選択のように「たくさんのシルエットが被覆できるブロックが偉い」という立場に立って、非復元抽出で何回か位置選定をやり直してその中で最大面積が被覆できる場所を選びました。
ブロック構築直後、シルエットの被覆度合いが変わらない範囲でブロックの体積削減
ビジュアライザで観察すると、何もしないとシルエットが埋め終わった後で小さいブロックの体積を膨らませる際に余剰の体積が残りませんでした。可能であれば、プレイアウトの過程でシルエットを埋めつつも後に生じる小さなブロックのために余剰の空間が残った状態にしたいです。
そこで小さいブロックのへ割り当てる空間を広げるために、ブロックを一度構築した直後、シルエットを被覆できた面積が減らない範囲でブロックの BFS の探索履歴の木としての葉ノードから削除します。
離れ小島の削除
あまり該当シードは多くないのですが、シーン内部で原理的に置ける場所のグリッドグラフを考えた時に連結成分のサイズが小さい離れ小島のような場所が存在することがあります。ここにブロックの開始位置を設定してしまうとどうあがいても大きなブロックが作れないので、シーン完成が不可能にならない範囲で探索の事前に削除しました。
回転による近傍変化を事前計算
プレイアウトの際にブロックの向く方向を変えながら探索するのですが、回転行列を使って向きを作っていたのでこのままだと近傍のマスへアクセスするために行列ベクトル積を都度計算する必要があり、行列のサイズが小さいとはいえ計算が重いです。そこで、高速化とコード単純化のために以下のように探索中に回転に必要な情報の前計算をシーンごとに行いました。
- 原理的に置ける座標位置に対して番号を振る
- 以下のテーブルを事前計算する
- neighbor[p][axis][dir] := 座標に振られた番号 p について、座標の対応 24 パターンのうち axis 番目に対応する、上下左右奥手前6方向のうち dir 番目の方向に位置する座標番号
こうすることで、共通ブロックを切り出す操作の過程で3次元や回転を意識せずに実装できました。
パラメータ調整
Optuna 使って500テストケースでパラメータ調整しました。スコアに対して3～4%程度は寄与しているので、寝ている間に色々やってくれるのは本当にありがたい…
所感
- コンテスト後半で、いい感じのブロックでシーンが埋められるようになったのをビジュアライザで確認できた時はかなり嬉しかった
- 以前コンピュータービジョンを勉強していた時に回転行列を履修していたので、ここでほとんどロスなく実装できたのは結構嬉しかった
- 終始良く作られた局所探索に勝てないだろうなーと思っていたので、最後の土日は追い上げがずっと怖くてヒヤヒヤしていました
- ただし、僕が局所探索するよりは乱択貪欲の方がマシそうと思っていたので、その感覚自体は間違っていなかった気もする
- 局所破壊再構築やりたかったけどできるイメージ持てなかったのは正直悔しかったから、次に使えそうな長期コンがあったら今度こそ経験積みたい
