AHC015 プレイアウトを使ったモンテカルロ法による3位解法の解説

2022年10月に開催されたトヨタ自動車プログラミングコンテスト2022 (AtCoder Heuristic Contest 015) の3位解法の解説をします。

まず、シンプルなルールベースによる解法を解説します。これだけで本番100位以内相当のスコアを出すことが可能です。

解法1: 上下に分割する

まず、イチゴ味（タイプ1）のキャンディーを上に集めることを目指します。

このためには、次のキャンディーがイチゴ味の場合は、下に傾けると良いです。すべてのキャンディーが下側に集められ、イチゴ味のキャンディーがその上に配置されるからです。

逆に、次のキャンディーがイチゴ味以外の場合は、上に傾けると良いでしょう。

このルールを実装すると次のような挙動になり、イチゴ味のキャンディーを上に集められていることがわかります。

この解法によって 104M のスコアを出すことができました（コード例）。これは本番286位相当のスコアで、これだけで正の得点を獲得した778人中の上半分に入ることが可能です。

解法2: 上・左下・右下に分割する

よりスコアを高めるためには、イチゴ味のキャンディーだけでなく、スイカ味（タイプ2）とパンプキン味（タイプ3）のキャンディーもできるだけ同じ場所に集めることが必要です。そこで、イチゴ味のキャンディーを上、スイカ味のキャンディーを左下、パンプキン味のキャンディーを右下に、できる限り集めることを考えます。

解法1と同じく、次のキャンディーの種類によって、傾ける方向を決めます。

次のキャンディーがイチゴ味の場合は、解法1と同様に下に傾ければ良いです。

次のキャンディーがスイカ味の場合は注意が必要です。

現在キャンディーが下側に集まっている場合（つまり、最後に下に傾けた後、一度も上に傾けていない場合）は、スイカ味のキャンディーをイチゴ味のキャンディーの上側に配置することを防ぐため、上に傾けましょう。この場合、スイカ味をパンプキン味よりも左側に配置されるようにすることはできませんが、仕方ありません。左右の関係よりも上下の関係を優先することにします。

一方、現在キャンディーが上側に集まっている場合（つまり、最後に上に傾けた後、一度も下に傾けていない場合）は、右側に傾けることで、スイカ味のキャンディーが左下に配置されるようにすることができます。

次のキャンディーがパンプキン味の場合も、スイカ味の場合と同様に、現在キャンディーが下側に集まっているか上側に集まっているかで場合分けしましょう。

このルールを実装すると次のような挙動になり、イチゴ味を上、スイカ味を左下、パンプキン味を右下に、おおまかにですが集められていることがわかります。

この解法によって 133M のスコアを出すことができました（コード例）。これは本番97位相当のスコアで、今回はこのヒューリスティックを発見できれば非常に短いコードで100以内に入ることが可能な回でした。何と盤面のシミュレーションすらしていないのです！

準備: 盤面のシミュレーションとスコア計算

より高度な解法に移る前に、盤面のシミュレーションとスコア計算が必要です。

盤面を傾ける操作は愚直に行ごとまたは列ごとに処理するしかないのですが、最終的にボトルネックになるため、不必要な遅い操作（メモリ確保など）が無いように気を付けましょう。

スコア計算では連結成分の計算が必要になりますが、深さ優先探索または素集合データ構造のどちらでも良いでしょう。

解法3: プレイアウトを使ったモンテカルロ法

では、3位解法となる、プレイアウトを使ったモンテカルロ法による解法を解説します。

ある時点で、次に盤面を傾ける向きを決めるときに、それぞれの向きに傾けたときの最終スコアの「期待値」を計算し、一番期待値が高い向きに傾けることを考えます。もちろん厳密に期待値を計算することはできないので、近似する方法を考えます。

まず、残りのキャンディの個数が N 個ある場合、有り得る残りの入力列は N! 通りあります。もちろんすべてを試すことはできないので、ランダムな入力列をいくつか生成してそれに対するスコアを計算し、平均値を取ることにします。

入力列を固定しただけではスコアを計算することができません。出力列（傾ける方向）も決める必要があります。今の目的は次の出力を決めることなので、次の出力だけを固定し、残りはランダムに選ぶという方針が考えられます。しかし、これではあまりにランダム性が高く、実際のスコアより大幅に悪いスコアになってしまうので、次の出力候補を比較するにはあまり役に立ちません。

そこで、次の出力だけを固定し、残りは解法2のアルゴリズムによって出力を決めることにしましょう。そうすると、高い精度で次の出力を固定したときのスコアの期待値を推定することができるようになります。これが可能なのは「解法2が非常に高速であり、かつ最適解にそれなりに近い」ためです。このように、高速なヒューリスティック（場合によってはランダム）によって出力を決定して最終状態のスコアを計算することを「プレイアウト」と呼びます。プレイアウトは、囲碁 AI などに用いられているモンテカルロ木探索において重要な概念です。興味のある方は調べてみてください。プレイアウトは、途中状態で盤面の良さを評価する評価関数を作るのが難しい場合に有効です。

この解法では、何個のランダム生成列を処理できるかによって性能が変わってきます。また、ゲームの序盤・中盤・終盤でそれぞれどの程度時間を使うかという時間管理も重要でしょう。私は毎回固定で150個のランダム生成列を処理するという方針を実装し、156M のスコアを出して3位を取ることができました。終了後にリファクタリングした後のコード例はこちらになります。