競技プログラミングにおいて焼きなまし法に堕ちずに落とすコツ

フューチャーアーキテクト Advent Calendar 2017の21日目¹の記事です。

昨年はゲームAI系の長期コンテストについて書きました。
今年は競技プログラミングにおける、データサイエンス系の長期コンテストにおける主要なアルゴリズム「焼きなまし法」について書きます。
なお、コンテスト内容や焼きなまし法についての説明は他の素晴らしい記事をご覧下さい。

焼きなまし法を使って見たものの上手く行かなかったあなたへ

topcoderマラソンマッチを初めとした、データサイエンス系の長期コンテストでよく起こる悲劇が下記ではないでしょうか。
適切な解法が　"焼きなまし法だった" or "焼きなまし法じゃなかった"

乱択アプローチを試みる焼きなまし法は、多くの最適化問題に対し何も考えずにそれなりの答えを出せる手法であり、上手く乱択先を絞れると探索系のアルゴリズムでは詰めきれない部分まで最適解に寄せることができます。
扱えるようになれば強力な武器になりますが、一方で、何となく答えが出てしまって次の工夫が思い付かず、温度調整などで期間を溶かしてしまう…。そんな、あなたを堕落させる危険性の高いアルゴリズムでもあります。

なんでもかんでも焼きなまし法に依存してしまうと、初回スコアから点数が伸びず、ぐだぐだとパラメータ改善を繰り返す日々が続き、結果レートが伸び悩む…。そんな、焼きなまし法に"堕ちる"ことを防ぎ、一見焼きなまし法では扱えないような問題を焼きなまし法で解けるようにする=焼きなまし法に"落とす"ための私なりの考え方をまとめられたらと思います。

焼きなまし法と相性の良い問題/悪い問題

ある状態Aから、少しだけ変化した状態A'に遷移した時のスコア変化を元に、最適解へ近づいていこうというのが、焼きなまし法のアプローチです。

相性の良い問題

状態Aと状態A'の関係性がなるべく近い状態（近傍）であり、各状態間のスコア変化が滑らかな問題です。多くの場合、スコアを得るのに特別な制約が無く、手順に依らずにスコアが決まる問題が該当します。

相性の悪い問題

状態Aと状態A'の関係性が離れており、各状態間のスコア変化が激しい問題です。多くの場合、特定の条件を満たして初めてスコアが得られたり、手順によってスコアが変わってしまう問題が該当します。

例えば、落ち物ゲーの代表である「ぷよぷよ」。高スコアを取るには大連鎖を組む必要がありますが、連鎖は任意のぷよが少しずれただけで崩れてしまいます。このことから、状態空間に対してそのスコア変化は激しいものとなります。

~~※早急にイメージ図を補填します。~~しました！

アルゴリズム：焼きなまし法

相性が悪くなさそうな問題であれば、実際に検証してみましょう。
私がコンテスト開始時に、検証のためによく使う焼きなまし法の型（≠ライブラリ）が下記です。（各項目は名称から察して下さい。）

Sample.java

double C = SIMULATE_TIME * 10_000; // かける値は適当。

Node SA(Node n) {

  double score = eval(n);
  double tmpScore;

  long endTime = startTime + SIMULATE_TIME;
  long currentTime;
  double forceLine;

    while (currentTime < endTime) {

      int change = rnd.nextInt(n.next);
      tmpScore = evalChange(score, change);

      currentTime = System.currentTimeMillis();
      forceLine = (endTime - currentTime) / C;
      if (score >= tmpScore || forceLine > rnd.nextDouble()) {
        score = tmpScore;
        n = nextState(n, change);
      } else {
        // rollback
      }
    }
  return n;
}

最大のポイントは温度調整を省いていることです。
状態の遷移を確率化し、次の状態は現状よりスコアが悪化する場合、開始直後は頻繁に強制遷移させ、終盤になるに連れてその確率を低くしていきます。
当然、スコアの悪化度合いを考慮していないため、大きくスコアを落とす場合でも確率的に遷移を許してしまいますが、焼きなまし法を用いた場合の傾向を測るには十分です。

こいつは焼きなまし法に落ちるのか？

「当たるまでガチャれば確率100%。」
近年のソーシャルゲームブームで、そんな悪魔的な言葉を耳にするようになりました。

乱択アプローチである焼きなまし法にも同じ理論が適用できます。つまり、できるだけ試行回数を稼ぐことが重要です。

「今だけSSR確率100%UP！」
また、ユーザーの動機付けのために定期的にイベント開催を行うソーシャルゲームも多く見られます。普段は無課金でもこの時ばかりは課金してしまうユーザーも多いのではないでしょうか。

乱択アプローチである焼きなまし法にも同じ理論が適用できます。つまり、できるだけスコア更新確率の高い手に絞ることで、少ない試行回数で高いスコアを取ることができます。

試行回数を増やす

試行回数を増やす方法は主に以下のものがあります。

• 差分のみ状態更新できるようにする
• 現在時刻等ループ毎の更新が不要なものの更新頻度を下げる
• そもそもの処理の高速化

私のやり方は、差分のみの状態更新処理を実装した時点で、焼きなまし法によるスコア更新が収束してるかどうかをチェックします。簡単なチェック方法は、当初制限時間いっぱい回した時のスコアと、10倍の制限時間内で回したスコアの点差を確認することです。

スコア更新が収束している場合、試行回数は十分確保できる問題であることがわかります。焼きなまし法に適した問題とみなし、各試行でより最適解に近づく&遠ざからないよう、工夫を凝らしていきます。²

スコア更新確率を増やす

スコア更新確率を増やす手法は、問題のコンテキストに強く依存してしまうため、本当に意味のある部分までは踏み込めませんが、良く使うのは
「スコア変化の無い状態遷移は省く」
という改善です。

多くの状態遷移がスコア変化の無い問題であれば、ここを削ることでぐっとスコアの伸びと収束の早まりが期待できます。

※AtCoderの長期コンテスト「Hokkaido Univ.& Hitachi 新概念コンピューティングコンテストその１」で、同様の考えがスコアにかなり効いたようです。私はリアルタイムで参加出来なかったので、気が向いたら加筆します。

あいつを焼きなまし法に落とせるか？

この問題が焼きなまし法に落ちるわけがない。そんな問題でも、上位陣は焼きなまし法で解いてしまうことがままあります。

私の経験則ですが、下記のような問題は一考する余地があります。（後半のものほど高難易度）

• 状態空間が広すぎて収束が見込めない問題
• 出力要素間に順序関係が存在し乱択では上手く寄せていけない問題
• スコアを得るために制約が存在する問題（New）
• 出力要素の変化により状態が大きく変わってしまう問題

状態空間が広すぎて収束が見込めない問題を落とす！

粒度を荒くすることで、相対的に状態空間を狭めましょう。

※topcoderマラソンマッチ第92回「Lighting」が該当します。私にとって思い出深いコンテストです。余裕ができたら加筆したい。。。

出力要素間に順序関係が存在する問題を落とす！

時間経過により焼きなまし対象範囲を変化させたり、各範囲の確率を偏らせたりしましょう。

例1：開始直後は順序関係における頭の部分のみ対象とし、時間経過と共にお尻の方まで対象範囲を広げる。
例2：順序関係における頭の部分の確率を高くし、お尻の方ほど確率を低くする。

※Atcoder chokudai contest3が該当します。余裕ができたら加筆したい。。。
※そもそも作問者の想定回はビームサーチだったそうです。

スコアを得るために制約が存在する問題を落とす！

2つアプローチがあると思っています。

1. 元の評価とは別の評価軸を用意し、最終的には制約が満たされるように整える。
2. 制約を満たす状態を維持できる状態遷移しか行わない。

2つ目について、topcoderマラソンマッチ第96回「GarlandOfLights」が該当するので少し説明します。
GarlandOfLights：概要
目的：特定のタイルを並べてなるべく長い輪っかを作る。
スコア：最も長い輪の長さ。

これをタイルの置く順番で単純に焼きなまししてしまうと、輪がぷつぷつ切れてしまい、全くスコアが伸びる方向に収束していきません。そこで、輪の制約を維持できる遷移のみを近傍とします。（下記は一例。縦横斜め、色変え等が可能。）

近傍を輪の制約を満たすにしぼり、スコアのなだらかな状態空間とすることで、焼きなましに落とせるようになります。

※イメージ図として、相性の悪い状態空間の図の底の部分を切り取ってつなぎ合わせてみました。それなりに焼きなましできそうな状態空間に近づきましたね。
※実際の問題の状態空間は、トゲトゲしたものではなく階段状になります。

出力要素の変化により状態が大きく変わる問題を落とす！

出力要素自体を焼きなますのではなく、近傍状態を取れるよう別の要素を用意して焼きなまします。得られた結果は出力時に出力要素に変換します。

※AtCoderの長期コンテスト「Hokkaido Univ.& Hitachi 新概念コンピューティングコンテストその２」で、近しい考えが出ていました。
※もっと適切な問題がないか検討中です。

最後に

ここまで読んで頂きありがとうございました。
色々と準備が間に合っておらず、概念的な話のまま残してしまったものも多く申し訳ないです。。。

焼きなまし法について、私自身とても苦手意識が強いですし、焼きなまし法を用いたコンテストの戦績は良いとは言えません。そんな筆者がなんとか戦えるよう考えてきた要素をまとめてみました。
至らぬ所も多いと思いますので、是非ご意見・ご指摘下さい。

AtCoderでも長期コンテストが開催され、これまでアルゴ中心だった方の中から長期コンテストに参加されるようになった方も多いのではないでしょうか。
そんな方々が焼きなまし法に堕ちてしまわぬよう、本記事が少しでも道標となれば幸いです。

1. 一年ぶりの筆者の誕生日です。プレゼントとして「いいね」を頂けると、ぼっち誕生日会が盛り上がります。 ↩

2. 工夫の凝らし方は問題依存が強いので、本記事では扱いません。
   　
   明らかにスコア更新が収束していない場合は、別のアプローチを検討すると共に、後述する焼きなまし法に"落とす"方法を模索します。
   ※topcoderマラソンマッチ第94回「ConnectedComponent」が該当します。焼きなまし法に見せかけたビームサーチ問題でした。 ↩