AHC038でビームサーチをしてみよう！

(AHC038画像、GIFはAHC公式Visualizerよりお借りしています)

（上の出力は、最終的に出来たサンプルコードのものです！）

はじめに

　初めまして（orお久しぶりです）。これはAHC038でビームサーチを打ってみよう！という記事です。ビームサーチを既にご存じな方には新しい情報はないかもしれませんが、ぜひ見ていってください。

　コンテスト後の解法ツイートを眺めますと、「貪欲をある程度まで改善させてきたがビームサーチには手を付けられなかった」というお話をよく目にします。貪欲が高速で強ければビームサーチで化ける可能性もあるのではないかと思うので、ビームサーチをやったことがない・知らないという方にぜひ一度試してほしくてここに書き残しておきます。普段は半分自分の備忘録として書いていますが、今回は8割くらい「まだ試したことがない人に参考にしてほしい」というつもりで書いてます。

　この記事では、言葉の厳密さや定義の厳密さといった部分は甘めに見ていただいて、気持ちを伝えられたらなと思っています。ここでは、感覚を伝える前半はコンテスト的でない抽象的な例を用いているため、今回のAHC038を知らずとも見やすい内容かと思います。後半の実際に組み立てるところでは、具体的な対象としてAHC038を用いています。

（執筆時点ではまだ行われていませんが、AHC038に対応するAHCラジオがあります。このラジオでは問題の解説や関連トピックが聞けるのでいつもお世話になっています。これを見てからAHC038でビームを打ってみるといいのかも？）

ビームサーチって？

　ビームサーチは、

・保持している途中盤面を取得します。

・各盤面から有効な手をいくつも試し、それぞれ次段階の途中盤面として保存します

・次段階に進みます

というのが基本的な流れになります。貪欲法を、「盤面を一つだけ持っておき、その盤面から最も良い手を選択して新たな途中盤面として保存する」と考えると、ビームサーチは貪欲の延長戦のようにあるように見えるかと思います。

　ところで、上の説明には「どこまで保存するか」という重要なところが抜けています（全部の盤面を保存するのでは、全探索になってしまいます）。こちらを説明するのに使われるのが以下の用語です。解法ツイートなどで流れてくることもあるんではないでしょうか。

• 盤面評価：途中盤面のよさを評価する値
• 深さ：初期盤面からの進み具合・段階
• ビーム幅：各「深さ」に対して保持しておく途中盤面の数

これらを用いて説明すると、「各深さで、盤面評価の高い順に、ビーム幅分だけ途中盤面を保存する」というのがビームサーチの方針です。ビーム幅1のビームサーチ=貪欲法になります。

　なんと、ビームサーチの基本的な説明はこれで終わりです。

参考として、ビーム幅2のイメージを載せておきます。（左から右に行くほど深さが深くなっていき、上のものほど評価が高い盤面という扱いです）

ビームサーチの強み

　前章ではビームサーチの形を紹介しましたが、ここでは、例をもとに強みを考えてみます。

頓死のリスクがある場合に対応できる

　ビームサーチは複数の盤面を候補として持っているため、一部の盤面で詰んでしまっても続行が可能です。とくに、「貪欲がかなりうまくいくがたまに地雷を踏んで大撃沈してしまうような問題」においてはビームサーチは最強格の方針になります。

　例として、「ハイスピードなレースゲーム」が挙げられます。ハイスピードなレースゲームでは基本的にカーブの内側を攻めながら速度を可能な限り上げるのが最も速いですが、貪欲にカーブしようとすると次のカーブで耐えられずクラッシュしてしまう可能性があります。ビームサーチでは、ちょっと前にアクセルを外していた世界線や、事前に少し外側に膨らんでいた世界線などが有力候補として残っており、これらの生き残った世界線からまた分岐を繰り返すことで、また多様な有力候補が補充されます。

ビーム幅2でのイメージです。ここでは「欲張りすぎて次がない」として、「とれるアクションがない」という形にしていますが、「遷移先の評価値がめちゃくちゃ低い」というパターンもあります。

手の評価を雑にできる

　貪欲法では、複数の盤面を持てないために一手一手を外さないように慎重に評価する必要があります。例として、前述の例では大撃沈を防ぐために、先読みを含むような複雑な評価指標が考えられます。一方でビームサーチではよさげな盤面のうちどれかが当たれば大きな問題はないため、ふんわりとよさそう・よくなさそうを評価できれば十分強力になります。

ビームサーチの深さ・盤面評価

　これはビームサーチをするうえで一番難しいところかと思います。実際、明確な正解が一通りに決まっているわけではなく、「深さ・盤面評価のかみ合わせ」が良いものをとってくるというものになります。ここでは、二つの組み合わせパターンを紹介します。

深さ:時間・コスト, 盤面評価: 進捗

このパターンは、時間・コストとして整数のものがとってこれる場合に使用可能です。

深さ:進捗, 盤面評価: 時間・コスト

このパターンは進捗として整数のものがとってこれる場合に使用可能です。

結局、進捗と時間・コストはどちらも少なくとも小数で表現しておく必要があるので、近い整数に丸め込んだり、数字をn倍したりでどちらでも対応できなくはないです。ただ、向いているのがどちらかというのはあり、基本的に深さ側は

• 行動を行うごとに最低1増えるもの
• 値がある程度小さいもの（10^5とか言われるときついです）
• 同じ深さ同士で状態の良さの比較がしやすいもの

であるとよいです。ビームサーチの以下の特性がそれぞれに対応しています。

• 「ある深さのすべての候補盤面から有効な手を試して次の深さに進む」を繰り返すアルゴリズムであるため、深さを逆戻りや停滞は基本許されない
• 各深さでビーム幅分状態を保存することになるので、手を試す回数は(深さ)×(幅)×(各盤面から試したい手数)となる
• 各深さでは上位ビーム幅分のよさげな盤面を保持する

特に、行動を行うごとに1増えるようなもの（つまり行動数）が非常に都合がよいので、そのうえで深さが上の条件を満たすように「行動」の概念を考えることがほとんどです。（少なくとも初めてのビームサーチではこのタイプのものを強くお勧めします）

深さが1ずつ増えるとは限らないようなビームサーチはこんな感じです。（煩雑になるのに対して、より適切な深さの定義で行ったほうがパフォーマンスが高いことも多いため、特に強い理由がないときは選ばないほうが無難です）

AHCで実際にビームを打つ

　ここまでは具体的な話をせずに説明をしてきましたが、「実際のところどう実装するの？」というのが一番の疑問点かと思います。ここでは、AHC038においてビームを打ってみます。サンプルコード(Go言語)にかなり多めに説明を入れるため、AHC038にすでに何らかの形で解を出した方なら他言語の方でも内容を見つつビームが打てるんではないかと思います。

　前章までの内容を前提として用意しているので、適宜読み返していただけると。

1．ビームの深さ・評価関数を決める

今回は「アームを操作した回数」というものが深さの条件にぴったりな気がします。アームの操作がそのまま最小化したい対象になるので、あとは同じ深さ内で、「どれだけ進捗が進んでいるか」をもとに盤面を評価・比較したいです

対応する盤面評価は少し検討が必要です。ぱっと二つ思いつくかなと思います。

• 「M個のたこ焼きを拾い、M個のたこ焼きを置く問題」とみたとき、2M段階の進捗のうちどこまで進んでいるか
• 「M個のたこ焼きを正しい位置まで動かす問題」とみたとき、あと合計何マス移動する必要があるか」

私が採用したのは前者でした。いくつか理由がありますが、どちらかというと後者に難しさがあり、具体的には以下のような部分が懸念点として考えられました。

・定義の仕方によっては、M個のマッチングで距離総和を最小化する問題などとみることができるが、それ自体が時間のかかる問題であるため、近似する代替のものが必要である

・木の回転は遠くの距離を一気に移動できる操作であり、どのたこ焼きをどこへ運ぶかは距離が近さよりは木の形とのかみ合わせのほうの影響を受ける

2．木の形を考える

たこ焼きを運ぶ最中に木の形は変更できないので、最初に決めてしまいましょう。最終的に適切な木を選定するところが大事になってきますが、今回は妥当な木でビームを打ちたいだけなので、

この図の一番左の木を採用します。この形になった経緯は割愛しますが、箒型には以下のような利点があります。

• かたまったエリアのものをまとめて拾う・置くことができる
• 箒の柄？の部分の回転の組み合わせで、遠くのいろいろな候補へ移動させられる

3．盤面の保持の仕方を考える

行動によって変動する部分のデータ

通常のビームサーチでは、盤面を何度もコピーすることになるので可能な限り情報をコンパクトにしたほうが良いです。ここでは天下り式に与えますが、操作を行うごとに変動する部分は

・根の座標　長さ2の配列

・各頂点の相対的な回転角　長さVの配列

・各頂点がたこ焼きを持っている状態か　長さVの配列

・各マスにたこ焼きがあるか　長さN,Nの二次元配列

・累計操作回数　整数

・（進捗　整数or小数）　

になります。これをひとまとめにして構造体にします。私はなぜかこれをGameStateと名付けてます。

行動を試す間変動しない部分は別の構造体で保存しておきます。

木のデータ

木のデータは

・葉じゃない頂点の数　整数

・各頂点の親の頂点番号　長さVの配列

・各頂点の長さ　長さVの配列

で表現できます。

木以外の変わらないデータ

ここには入力で受け取ったものを（必要に応じて加工して）保存しておきます。

記載漏れもあるかもしれませんが、おおよそ以下が固定情報になります。

・たこ焼きの目標配置　長さN,Nの二次元配列

・たこ焼きの初期配置　長さN,Nの二次元配列

・たこ焼きの数　整数

・盤面のサイズ　整数

・使える頂点数　整数

4.気合で書く

もう方針は立ちましたので、あとは書くだけです。最初は気が滅入る実装作業ですが、手を動かしてみたら意外と早く終わることもあります。ので、気合で完成させます。（今回、この記事に合わせて再走しました・・・）

ここにAHC038におけるGo言語でのサンプルコードを載せておきます。TryPossibleActions()が途中盤面に対して候補手を列挙している部分になります。

（気になるところから見てもいいですが、main関数から順に使われている関数を見ていくと理解しやすいと思います）

Submission #58872607 - Toyota Programming Contest 2024#10（AtCoder Heuristic Contest 038）

高速化の工夫などはほとんど入れていないため8件TLEが発生していますが、そのうえで延長戦順位表において31G(71位)を達成しています。本番だとこの時点で黄パフォになります！

ぜひ、ここを起点に自分だけのビームサーチを考えていってください！

今後の改善方針

とはいえ、ここでいきなり投げるのもどうかと思うので、改善方針を書いておきます。

まず前提として、8件もTLEしてしまっています。これだけで8G失っているのは非常に痛いので、この解消を目指すと効果的だと思います。そのうえで、ビームサーチの典型的な改善方向としては

• 高速にすることでビームの幅を増やす
• 盤面の評価や多様性の確保によりより好ましい途中盤面たちを保存する
• 各盤面での候補手として、もっと良いものを採用する

が挙げられます。今回の問題ではこのほかに

• 木をもっと良い形にして効率的にたこ焼きを運ぶ

というのもあるかと思います。

実際にTLEをなくす

「よくわからんがとりあえず成功例を見て次につなげたい」という方のために、ここで実際に直します。

goのpprofでどこで時間がかかっているか確認すると、

ボトルネックについては使用言語や個人の実装方法依存するので一概に言えませんが、TLEしているコードでは、TakoyakiPlateの上書きやTakoyakiPlateの配列確保に時間をかけています。また、その源流がGameState(状態を格納する構造体)のコピーであることも上図からわかります。GameStateのコピーは有効手を検討するたびに発生しているので、時間をとっているのももっともですね。

　ここでは以下の改善をします。（割と今回の問題に限らず色々なコンテストで似たような改善ができます）

• 葉の回転方向を決めたときに拾う数・置く数がわかるので行動を実行する前に評価値を計算し、見込みがないなら試さない（より賢い変更としては、Action、どのpossibleStateに対して適用するか、評価値の三つだけをqueueに突っ込み、最終的に上位になったものだけgameStateをコピーして実行するというのがあります）
• 各要素1bitでデータを表すことでTakoyakiPlateをN,Nの二次元配列ではなくNの配列に抑える

逆に時間に余裕が出てきそうなのでビームの幅を300にしてしまいます。（言語、実装によります）

（コードは以下。エディターで差分が見れる人はエディタにコピーして確認したほうがいいかも）

Submission #58876594 - Toyota Programming Contest 2024#10（AtCoder Heuristic Contest 038）

これを提出すると・・・

延長戦で39G(46位)になります！本番で提出していたら2300くらいのパフォーマンスが出ます。

実際に改善を入れる

「よくわからんがとりあえず成功例を見て次につなげたい」という方のために、ここで改善も一つだけ試してみます。

TLEをなくした後のプログラムの出力を見るとこんな感じの動きをしています。

(seed=2)

3つの葉をかなり限界まで利用していて、とても効率がよさそうです。

一方で気になるのが、最後の10~20手ほどです。空きマスが少なくなってきたということもあり狙ったところへ入れる必要が出てきますが、アームの長さの限界もあるため、最後の数個は特に入れるのに苦労している印象を受けます。ここで、これに対する解決策として候補手の選び方、盤面評価の部分で以下の工夫を入れます。

• 葉の回転を決めるときに、できるだけ中心から遠いものをとってくる
• 進捗が同じもののうちでは、これまでとってきた・置いてきたたこ焼きについての中心から総和が大きいものがよいとする

葉の回転の工夫については、decideGreedily()内で3方向すべて試すことで、たこ焼きの評価値については、GameStateにBonusValueという変数を追加してActionを適用するごとに足すことで対応します。

もちろん乱数次第ではありますが、seed=2が91手から83手になりました！

最終提出の自分のプログラムがだいたい79~81手なのでかなり良い結果です。

実際に提出してみます。（コードは以下）

Submission #58878428 - Toyota Programming Contest 2024#10（AtCoder Heuristic Contest 038）

（乱数でTLEしたりしなかったりしますが）見事延長戦で40G(40位)になり、橙パフォーマンスまであと0.5Gほどまで来ました。これに何か改善を加えて橙パフォといったところです。本番は一週間以上ありますので、実装が苦手でも頑張れば（生活を破壊すれば）ここまで順位表を登れる気がしてきませんか？

（自分の最終提出（最終3位）はこの延長線上にあるので、ぜひさらに伸ばしていただけると・・・！）

終わりに

　今回は通常のコンテスト後のPostMortemに代わりビームサーチ入門記事を書いてみました！といいつつ、自分の解法の核の部分は説明できたので実質PostMortemになってるかも？

　問題について。問題文を読んだ時の絶望から一転、ビームサーチを書いてみると人知を超えた動きを軽々とやってのけてくれて、出力を見るのがとても楽しい問題でした！毎度面白い問題を用意してくださりありがとうございます！

　ここまで読んでくれた方に向けて。かなり長めの記事になってしまいましたが、読んでいただきありがとうございます！「一度成功体験を積む」というのがコンテストの結果を伸ばすにあたってかなり重要だと思っているので、この記事で成功体験を積んでもらえればと思います！（参考にして結果が出せたらぜひ報告していただけると筆者が喜びます）