はじめに
こんにちは、ALGOARTIS でアルゴリズムエンジニアとして働いている itigo です。
ALGOARTIS では日々の学習の一環として、AtCoder で開催された各コンテストについての勉強会を開催しています。
この記事では、先日開催されたAtCoder Heuristic Contest 058勉強会の様子を公開します！
また、今回の問題は私 itigo が writer をしたものになっています。この問題が作問されるまでの体験や裏話、感想もここで記載していきます！
問題概要
- 機械を用いてりんごを大量生産したい。
- 機械は「りんごを作る機械」と「りんごを作る機械を作る機械」と「りんごを作る機械を作る機械を作る機械」...といった形で階層構造になっている
- 機械は各ターン 1 つだけ、りんごを消費して強化できる
勉強会参加メンバーの解法
今回の勉強会には、エンジニア 10 人が参加しました。
大きく分けて貪欲法、ビームサーチ法、焼きなまし法の三種類の解法が出てきたのでそれぞれ紹介します。
貪欲法
- ターゲットを作り、ターゲットが購入できるまでのターン数を最小化する
- 次のターン以降何も行わなかった場合の50ターン後のりんごを最大にするものを強化
- 貪欲で作った後に購入種類を焼きなまし
- 基本は次のターン以降何も行わなかった場合最終的なりんごの数を最大にするものを強化
- 集中投資先のidを全探索する、集中投資先に関しては購入する時の評価値を1000倍にする
- 序盤に早く集中投資先に到達すべく、序盤数十ターンでは数十ターン後のりんごの数を最大化するように評価した
ビームサーチ法
- 最終的なりんごの数を評価関数にビームサーチ
- actionはid,レベルを指定して、それが強化できるようになるまで待つ
- zobrist hashでハッシュ化
- 最終的なりんごの数を評価関数にビームサーチ(O(1)で求められる)
- 一つのIDに集中投下することを前提にビームサーチ。どのIDに投資するかは全探索
- 最終的なりんごの数を評価関数にchokudaiサーチ
- 80ターン目以降は特定のIDしか購入できないと言う制約を付ける。どのIDに固定するかは10通り全探索
焼きなまし法
- ローリングホライゾン焼きなまし
- 「現在ターンから20ターン分の操作列を焼いて、10ターン分適用して現在ターンを10ターン進める」を繰り返す
- シミュレーションにO(TNL)かけてると、全ターン一気に焼くのは厳しいだろうの気持ちになり、前から順に行動を確定していく方針を採用
- レベル上げする対象の (id,lvl) のペアの順番を焼きなましする
- iteration は 1 ~ 3 万回くらい
- 近傍はinsert, remove, swap, change
- 操作列を焼きなまし
- 初期解は無し、iterationは6万回くらい
- 近傍: 1点変更, 隣接swap, insert, erase
- 効率の良いIDが選ばれやすいように採用確率を細工する。各IDが採用される確率はA^1.5*(C0C1C2C3)^0.25の相乗平均にする
- 二段階の焼きなましを行う
- 一段階目では購入する対象のIDの順序を焼きなまし。列内のID順に、そのIDの中で買えるものの最もレベルが高いものを購入。近傍は変更,順序移動,swap,ある点以降のIDを全て同じものに変更を行う。この一段階目の焼きなましにより大局的にどのIDに投資するべきかを探索する
- 二段階めでは購入する対象のIDとレベルも含めて焼きなましを行う
どの ID に集中投資するか次第で局所解にハマってしまいがちな問題でしたが、みなさんそれぞれ異なるアプローチで局所解の脱出を試みており、それぞれの考え方を聞くのは非常に楽しかったです。
特に今回の場合、「如何に上手い貪欲を設計して良い投資戦略を発見するか」や「如何に上手い焼きなましを設計して局所的な集中投資から脱出するか」といった工夫のうまく行き具合がかなり順位に直結していました。勉強会メンバーそれぞれの工夫とそこに至る考察過程を聞くことができたのはかなり有意義でした。
ちなみにこの日、自分はすでに解説放送で解法を解説済みだったので代わりに作問体験記的なことを喋っていました。その内容をより詳細にまとめたものを下に記します。
作問体験記
作問の流れ
作問は次の流れで行われます。
- wata さんに DM を送る
- 作問用のツールキットを貰える
- 便利で、比較的簡単に judge ツールやビジュアライザを作れる
- なんとなく浮かんだ原案を試す意味でも wata さんに連絡してツールを貰ってみよう
- 原案の問題、テストプレイと考察、アピールポイント、(できれば)judge と入力を作成し、wata さんに提出
- ここで wata さんから go サインが出るとコンテストに向けた作問作業が始まる
- 追加のテストプレイ、問題文作成、tool 類の作成、ビジュアライザの作成
- コンテスト観戦、解説放送
以下自分の場合はどのような流れだったかを体験記として書いていきます。
作問原案ができるまで
事の発端は 11 月の頭、ALGOARTIS 社の全社合宿でのことでした。行きのバスで隣に座ったおふとんらぼさんと二時間くらいひたすら雑談していた中で、「itigo さん次の AA 社の AHC の作問とかしないんですか？」という話題になりました。おふとんらぼさんの巧みな話術(?)により私の中で作問のモチベーションがかなり湧いてきました。この瞬間から頭の片隅で作問のことを考えながら箱根を楽しむ合宿がスタートしました。
さてどんな問題を作ろうかと考えていたときに、自分が元々プレイしていたインクリメンタルゲームの存在を思い出しました。Antimatter Dimensionsや新しい放置ゲームといったゲームです。これらのゲームでは今回の問題の肝である「生産機を生産する生産機を生産する生産機...をコストを払って強化する」という営みが行われます。以前これらのゲームをプレイしながら「このゲーム、うまく設定したら AHC の問題にできそうだよなぁ」と考えたことがありました。この生産機の問題設定で問題を考えていき、いろんなパターンを検討しました。「生産機のつながりを巨大な DAG にしたらどうなるか」や「生産機から複数種の生産機が作れたらどうなるか」などです。その中で今回の問題設定のように「複数の生産機のパスから良いものを選ぶ問題」が面白そうだと思い、この設定で固めていくことになりました。
作問作業
原案が思いついたので wata さんに X で DM をします。
DM をすると作問用のツールキットがもらえたので、問題文と judge ツールと超簡単なビジュアライザを作ったのち、4 時間自分で解いてみてその結果と考察を書いて wata さんに提出しました。
しばらくして wata さんからフィードバックが返ってきました。
実はこの時点の原案では実際の問題と異なり機械のコストのランダム性を 1.5 倍(本番では 100 倍)しか持たせていませんでした。この設定では一番大きい ID に全力投資するだけのケースがほとんどになってしまいました。
この時点のフィードバックを要約すると、「設定自体は面白く、考えることも多くて楽しかった」とのことでした。一方で「やるべきことがワンパターンになってしまい現状でほとんど最適解に近い。コストの重みを変えるなどしたら良くなりそう」という指摘もありました。
そこでこのフィードバックを元に設定を試行錯誤した結果、本番の設定に辿り着きました。再びテストプレイしてもらったところ「考えることが多くて面白い」というフィードバックをもらい AHC058 で採用する運びになりました。この時はめちゃくちゃ嬉しかったです。
ちなみにこの時点で自分のテストプレイではかなり時間をかけて 839807064 点(本番 16 位相当)の焼きなまし法でした。しかし wata さんがテストプレイすると 841415855 点(本番 15 位相当)のビームサーチが返ってきました。悔しい気持ちになると同時に、ここまで方針が違っても近いスコアが出るのかと驚きました。
その後、テストプレイを続けて想定解法のスコアを向上させつつ問題文作成やビジュアライザの作成、tool 類のバグ修正などを行なっていきます。
この工程は過去の AHC を使った example のコードがあるのでそれを元に実装を進めます。wata さんから改善案のフィードバックが貰えるのでまたそれを実装していくという流れで難なく進められ、コンテストが完成しました。
作問作業を進めていくとどんどん「この問題みんなどのくらい解けるんだろうなぁ」という疑問が強くなっていきました。人々がこの問題を解いてくれるコンテストが非常に楽しみになり、12 月最大の楽しみコンテンツになっていました。
デスゲーム主催者ってこんな気持ちなのかな？
本番
コンテスト当日になりました。自分は AtCoder 本社で wata さんと 4 時間観戦することになりました。
観戦で人々がどんな解法で解いてくるか楽しみでした。一方、コンテスト 1 時間半後の解説放送にてドヤ顔で話したかったので「頼む、想定解優勝してくれ」と思いながら見守っていました。
「問題の詳細を考察し尽くした後で初見の人々が解いている様子を眺める」という体験は多分作問しない限り不可能です。かつめちゃくちゃ楽しいのでみなさんぜひやってみましょう。
結果的に想定解法は AI の fishylene を含むと最終 5 位に終わりました。想定では大局的な投資戦略は焼きなましで求めるのが難しいと考えていました。しかし上位陣は巨大な近傍を取り入れることで投資戦略ごと焼きなまして、自分の想定を軽々と超えていきました。自分が作り設定した問題で、長時間考えた解法を超越する賢い解法が生み出されていきました。その様を見ることができたのは滅多に得られない感動的な体験でした。
感想
原案を考える時のウキウキ感、問題設定を詰める時のワクワク感、自分で作った問題を自分で改善していく楽しさ、最終的にコンテスタントが解いているのを眺めるドキドキ感。作問の一連の流れはかなり楽しく貴重な経験になりました。
参加してくださった皆様ありがとうございます。
また、皆様も是非作問をしてみてゲームマスター感を味わってみるのはいかがでしょうか？
Discussion