Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017の反省

AtCoderで初の本格マラソンマッチ。楽しかったです。13位/302。最近のマラソンマッチ不振を考えれば良い結果だったけど、反省点も多かったです…。
(方針の公開がOKになったので、公開します。2ndがあるので、ちょっと迷いましたが、北大日立さんにとって良い結果が出たほうが、今後さらなるマラソン開催にもつながるので、公開します。)

ファーストインプレッション(2017/11/16)

  • どういうデータなのか?
    • 辺の数とか、平均でいくらぐらいなんでしょう? →辺は思ってたより多い。100本以上辺があるのは普通。
  • 最適解がわかるケースを逆につくれば便利。最適解を知っていれば、焼きなましをやってみたときに、うまくいってるかわかる。
    • King's graphから作る
    • 一定条件を満たせば、そこから辺を足しても最適解をキープすることは可能?より一般的&難しい問題が作れる
      • 三角不等式を満たすものは除去してもいい?
    • このときに意図的に最適解をつくる操作が、逆の操作が近傍として有力な可能性はある。
  • より簡単なケースで考えてみる。
    • King's Graphではなくグリッドグラフにマッピングする場合は?二部グラフに持ち込める?
      • 最大流かカット系で楽にできないか?
      • 使えなくても、初期解として有効な可能性があるので、無駄にはならないと思う。
  • 過去の反省
    • 類問の解法に固執しすぎ。
      • 今回のは、TCO17 MM Round 1 TCO17 Marathon Round 1 (GraphDrawing) の反省 - じじいのプログラミングに似てる気もする。そうすると優勝したchokudaiさん解の重力モデルか焼きなましの中間っぽいのが有効なのか?
      • ただ、ちょっと条件がちがっただけで、解法が全然違うことがある。まっさらでスタートしたほうがいいのでは。
  • 方針
    • ベタに行けばこの問題は、ただの焼きなまし。そして、最後に焼きなましの解をダメ押しでGreedyするの忘れずに。
    • 粗いグリッドで焼きなましから、徐々に細かいグリッドにして焼きなまし。
      • ただし、先日tomerunさんと似た解法だったのにもかかわらず、自分だけ大敗したので、ちゃんと敗因を確認すること。特に、細かいグリッドになったときに調整できるかどうかもポイント。
  • ランダムグラフの頂点間距離は使える?
  • 高得点辺だけを使ったのGreedy・焼きなまし
    • 1点や0点の辺は無視してもいいくらい。というか0点は最初から削っていいのでは。
  • 何を焼きなまし?(「近傍の種類の多さが重要」と昔Komakiさんが言ってた)
    • 頂点ベース
    • 頂点ベース(位置を気にする。近傍は近くの点)
    • 辺ベース
    • 15点→0点で、辺をじょじょに開放
    • 場所を後から、配置する解法はないか?よく、「置く場所を決める焼きなまし」→「何を置くか決める焼きなまし」のように、2段階に分けると良いこともある。

Submission 1 (2017/11/18) 52935点

同じ番号の頂点をマッピング。同点のみなさん多数。

その後、多忙で無事乗り越えたものの、休日に冷房病になってしまい、計1週間休み。すごく警戒してたのに…。

Submission 2 (2017/11/25) 129838点

場所2箇所の交換(頂点あるなしは気にしない)を100万回する山登り法。

Submission 3 (2017/11/25) 148673点

場所2箇所の交換(頂点あるなしは気にしない)を、9秒間する焼きなまし法。

Submission 4 (2017/11/26) 152871点

焼きなまし法の、温度を5度→1度にする。わりと効果があった。

ビジュアライザ

このタイミングでビジュアライザも追加する。 Siv3Dを今回も使いました。感謝→ Siv3D · GitHub)ビジュアライザは、

  • 押すボタンごとに、いろんな近傍への遷移をリアルタイムで試せる。
  • 頂点ごとに最高点と現在の得点を追加。ちなみに、最高点はベスト8の総和。

f:id:shindannin:20171130222251p:plain

ただ、ビジュアライザをつくっても、なぜ問題が起きてるのかにちゃんと着目した情報を表示して、本質を見抜けないと意味がないので、気を付ける。
このchokudaiさんの記事はおすすめ(というか、悪い例にでてくるモデルは、たぶんわしじゃ…。)
chokudai.hatenablog.com

焼きなまし法の温度と得点、統計情報(どの近傍で、どれだけ上がったか)等も、グラフプロットに追加すればよかった。

Submission 5 (2017/11/26) 159335点

動かす頂点Aと、元グラフでつながっている頂点Bの隣に移動。上位の人が多く使っていた有効な近傍。

セカンドインプレッション(2017/12/26)

  • 焼きなまし温度調整必須
  • 15点の辺だけ使って、辺を少なくして、橋・関節点で分けて、
  • 浮いている点の15とかは重要?
  • 15,15,15,15,15,15,15,15,15,15,15,15,15,15,5,5,5 みたいなときは代替があるので、あとで決めていい
  • 塊ごと移動できない?
  • 番兵で、範囲チェックのifを減らせ
  • 範囲広すぎだと、ダメかもしれない。60x60ではなく、範囲を狭くしたら。
  • 範囲なしにして、あとからくっつけたほうがいいかも。

Submission 6 (2017/11/27) 159913点

  • 元グラフでつながっている頂点Bは、高得点ベスト8の隣接頂点から選ぶ。かつ、焼きなまし法を2倍高速化

★★★★ 高速化がどれだけ効果的か検討する。
のも重要です。ためしに10秒だけやってる計算を、あえて100秒とかに伸ばしてみて、結果がどうなるか見てみましょう。

  • 時間をかければかけるほどスコアが伸びる
    • 高速化しよう&スコアが素早く伸びるように次の状態を決めよう。山登り法に変えるのも良い。
  • 時間をかけてもスコアが伸びない & スコアが高い
    • 最適解がでてる可能性が高い。計算を打ち切って、余った時間を他に使う
  • 時間をかけてもスコアが伸びない & スコアが低い
    • 次の状態の決め方、スコア関数の見直しを再検討する。焼きなまし法を使わない法がよいときもあるのも忘れずに。

を試した。なんと計算時間を10倍にすると、30ケースあたり平均+5000増える!!(実際には30ケース*10セット)1位が狙える位置に行くことがわかる。

でも、10倍高速化するのは無理だろうなという考えと、まだ試してないアイディアがいっぱいあるので、まずそちらからやることにした。これが敗因の1つ…。
10倍で効果があるのだから、せめて、計算時間を5倍にしたら、計算時間を2倍にしたら、どれだけ増えるのか試して、それをみて高速化にどれだけ作業するか考えるか判断すれば良かった。

失敗したアイディア集

ここから点数がさっぱり増えなかった、ボツアイディア集。反省点の1つとして、結果の確認とまとめを、もうちょっとちゃんとしてれば良かった。失敗したアイディアの中では、点がほとんど変わらなかったものもあるけど、これは下手すると最終盤でちょっと点数を上げたいときに有効な場合もあるので。

初期値

初期値がわるいとダメなケースもある。特に、今回のは、わりとバラバラに頂点が飛んで非効率に見えたので、初期位置を中央に固めた。でも、すぐに結局バラバラに飛んで行って、スコアが上がらなかった。

バラバラにならないようにする。

中央に行くほどボーナス点をつけたり、KingGraphの隣に頂点があるときにボーナス点をつけた。バラバラになりにくくなったけど、スコアはだいぶ下がった。バラバラシャッフルっぽい動きは有効だったっぽい。

頂点Aを意図的に選ぶ。

頂点得点の最大値(頂点の辺ベスト8の合計)をあらかじめ計算しておき、交換する頂点を、以下のような基準で選ぶけど、これもだいぶ点が下がった。

  • 低得点率(現在の得点 / 最大値)
  • 得点差(最大値 - 現在の得点 )

yowaさんのなんか他の人の解法をみるに、全てを均等回数を選んだほうがいいという議論もあるらしい。


次回は要検討。

隣接頂点Bの選び方

Submission 6「元グラフでつながっている頂点Bは、高得点ベスト8の隣接頂点から選ぶ」の部分が、あまりに雑だったので、ここはスコアは伸びるかなと思ったけど、伸びなかった。辺得点x,y,zだったら、選択確率は、pow(x,t)/(pow(x,t)+pow(y,t)+pow(z,t))のようにして、tを調整した。tが0なら全部等確率1/3, tが∞なら最高辺得点のだけが確率1になる。でも、スコアは伸びなかった。

さまざまな近傍

「近傍をたくさん作ったほうが勝つ」と、Komakiさんが昔言ってたので、いろいろ足した。

  • 2-Swap
    • 隣り合う2点を交換。A→B, B→A
  • 3-Rotate
    • 三角の形で隣接する3点を、A→B, B→C, C→Aのように移動。ある頂点Aを固定すると、三角形の選び方は12パターンある。
  • 4-Rotate
    • 四角の形で隣接する4点を、A→B, B→C, C→D, D→Aのように移動。
  • スライド
    • 縦 or 横 or 斜めに一列にならんだx点(2点~4点)を一方向に押してスライドさせる。A,B,C,Dと並んだ場所で、A,B,Cが頂点があって、Dが空きのとき、C→D, B→C, A→Bと移動させる。

それぞれに対して、全てのマスが頂点埋まっているバージョンと、そうでないバージョンを試した。また、近傍については確率で選んで調整する(辺隣接ワープ 95%, 2-swap 4%, 3-Rotate 1%とか、そんなかんじ)

  • 空きマスが一部ある場合の結果は、概してよくなかった。
  • 2swapについては、低得点の際には効果があるように見えたが、マッチの終盤にはほぼ意味がなくなったので、最終的には、これらの近傍は全てボツとなった。

また、本当なら、別な動きをする近傍をいろいろ作ったほうがいい。今回の3-Rotate, 4-Rotateは、2-swapで2回,3回で代用可能かつそれなりの確率で起こりうるので、あまりよくない近傍(ただ、それでも1回は試すべき。)

レプリカ交換法

ほぼやけくそ。N個の焼きなまし法を同時に走らせる方法。それぞれ別な温度を固定でもつ。一度やってみたかったので、やった。
レプリカ交換法 - Wikipedia
得点差に応じて、温度を入れ替える(状態を入れ替えるより簡単。)
これは、あまり有効でない。中途半端な得点の解がたくさんできるだけだった。特に、今回のように時間をかければスコアが伸びるケースでは、時間が1/Nになるのはもったいない。1つに集中して時間をかけたほうがいい。ただ、並列計算とかできる環境であれば、有効なケースもあるのかも。

プロファイラで高速化。

この時点で、最終日で、残り4時間ぐらいになってしまった…。Visual Studioの標準機能のプロファイラを使って、高速化する。しかし、時間が足りず、結局、以下の2つは高速化せずに終わってしまった。

  • 番兵で範囲チェックをなくす
    • ファーストインプレッションにも書いたのに。時間がなくなってしまった。番兵など、最終盤で、高速化するにはバグを埋め込むリスクが高いところは、もっと早めに高速化やったほうがいい。
  • 焼きなましのexpの式
    • あわててテーラー展開したやつを書いたけど、点が下がったので、怖くなったので、やめた
    • 焼きなましのexpの式なんて毎回使うのに、高速化を最終盤にしようとして、おざなりになるのを繰り返してるのは、本当にダメである…。効果が少なくても、1度作れば一生使えるのは、暇なときにしっかり作りましょう。

自分のは、7000万回程度しか回らなじゃった。他の人は2億~4億ぐらい回っている。その中でもっとも怪しいのが、ケチらずintとかdoubleとか大きい方を使っていたこと。一般に、プロファイラはボトルネックにはすぐにきづくが、全体的に遅くなってる要素には気づきにくいので、要注意。ただ小さい型を使うのが、これだけ早くなるのは意外。キャッシュミスあたりが予想されるけど、今回のフィールドは小さいので、過小評価してた。自分がなんか誤解している可能性も高い。要調査。

その他

  • お尻に火がついたのが、いつもより少し早かった。
  • 若くないので、体調管理は大事。冷房病は徹底した温度管理で避けよう。
  • 昔は、夜遅くなっても次の日なんともなかったけど、今はリバウンドがくるので、ちゃんと早めに寝たほうがいい。
  • AtCoderさん、ありがとう!マラソンマッチでこんな問題を受注できるとは、本当にすばらしい。