■ [TCO][MM] TCO13 Marathon Round2 
http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15648
問題
yowaさんのスライドを参照。
http://topcoder.g.hatena.ne.jp/yowa/20130516
やったこと
まず問題読んで、これ去年のRound1と似てるなあ、はいはいビームサーチでしょ、と書いてみたらなぜか50点くらいしか出なくて涙目
評価関数みたいなので探索順序を決めるDFSを書いてみる→73点くらい
それから探索順序をいろいろ工夫してみるけど全然スコア上がらなくて早くも心が折れそうになる
ランキングを見ると64点くらいの人が多数現れていて、この人たちは一手ごとに一番たくさん鏡が壊れるところを選ぶGreedyをやってるのだろうと推測される
ビームサーチでそれより低いスコアしか取れないのはありえないので、なんかおかしいのだろうと書き直してみる→85点くらい出た。どこかでバグってたらしい
同一盤面除去をやるとあっさり90点越えた
ちょこちょこ評価関数を調整して97点くらいになったので提出
DFSで悩んでたのも、その間に偶奇性とか評価関数の要素を考えられたから無駄ではなかったと思うが
あとはC++で書き直しての高速化と、Nの偶奇で係数を分けたりの細かい調整で103点くらいまではチマチマ伸ばしたけど最後の方は全然改善しなくなってしまった
評価関数、探索順序について
- 評価関数の要素にはこれらを使った
- 残った鏡の数（少ない方が良い）
- 行・列ごとの鏡の数の偶奇（偶数の方が良い）
- 空になった行・列の数（多い方が良い）
- 同じ盤面から分岐する数は一定以下になるよう制限を付けた
- 評価関数の高い順に残すのではなく、いくつか下の方からもランダムにとってくる
- これが効くのって評価関数がいまいちだからだよね…
評価関数の要素に、鏡が固まって残っていること、例えば16個残っていたら2*8よりも4*4の方が良い、ということを含ませようとしたけどうまくいかなかった。
評価の計算方法があまりうまくなかった。参照：https://twitter.com/tomerun/status/334719466153848832
二乗和は、数が大きい方を大きく評価しすぎてしまう。小さいところがあるのが悪い、というのを評価したいのだから不適切だった
このあたりの数式的な考察がテキトー過ぎてよくない
高速化について
- 盤面の持ち方は、各マスが上下左右の隣接する鏡までの距離を持つ2Dリンクリスト的なので
- 盤面の同一性判定はZobrist Hashingで
- 使用済みのハッシュ値は全体で1つのsetに入れるのではなく、残っている鏡の個数で区別してN*N個のsetに分けて入れる（setは重い）
- 盤面のメモリは最初に全部確保しておいて使い回す
- 評価のためのビームのシミュレートは、壊す→戻す のではなく、「何回目のシミュレートで壊されたか」情報を盤面と別にマスごとに持っておくことで、元に戻すフェーズを無くした
- 鏡を壊した数が4個以下のビームについては、それが出てきたところから入れるビームは同じ経路を逆に辿るだけなので省略する
- ある盤面から1手進めるとき、盤面をコピーしてビームをシミュレートして新しい盤面を作るのだけど、同じ親から別れる盤面のうち1つだけは、盤面をコピーするのではなくswapで済んでコピーコストを減らせる
- 盤面の中に、同じ行・列に他の鏡がない孤立した鏡がある場合は、適用する遷移はその孤立した鏡を壊すビームだけにする
結果
- provisional score : 103.88（100ケースの合計）
- provisional rank : 7
- final score : 2094.61（2000ケースの合計）
- final rank : 7 / 247
- レーティング : 2326->2354 highestを2だけ更新
