■ [TCO][MM] TCO14 Marathon Round1 
http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15938&pm=13132
問題
yowaさんのスライドを参照。
http://topcoder.g.hatena.ne.jp/yowa/20140424
やったこと
問題読む→はい、いつものビームサーチのパターンですね
2次元グリッド上でなんかゲームやって、1手ごとならビームサーチ、全体を構成するのなら焼きなまし、というパターン最近多すぎて飽きてきた…
ターン数が10000と多くて、評価関数で色々やろうとするとビーム幅小さくなってどうやってもスコア下がってしまうので、評価関数はごく簡単にしてひたすら高速化を頑張った
探索空間
C=4の場合は1手で消せるところ、C=5,6の場合は1手か2手で消せるところを全探索
始めは高速化のため、前回動かしたところの周辺だけ探す、ということをやっていたけれど意味なかった
ビーム幅は、時間をいっぱいまで使えるよう実行中に残り時間を見ながら動的に変える
評価関数の要素
データ構造と探索方法
struct Board{
uint64_t f[20]; // 各セルがどの色か。最高6色、番兵として使う無効分も入れて7色なので1セル3bitで収まる。周囲2マスずつ番兵にするので20*20分確保
uint64_t v[15]; // 各2×2の領域がどのような状態か。15×15個分確保。
// 3つ同色のパターン:4個、2つ同色*2のパターン:3個、2つ同色*1のパターン:6個、同色無しのパターン:1個 で合計14個なので1つ4bit
uint64_t v2[15]; // 高速化用。基本的にはvと同じだけど、一度探索してみた結果1手や2手では消せないとわかった箇所は、
// 0（無効を意味する）で上書きして再度調べないようにする
};
探索するときは、たとえばv2が「3箇所そろっていて右下だけ違う色」を示しているときは、次のような状態になっている。
AA AB
下の図のXの箇所を調べ、そこの色がAだった場合、それをBの箇所に持ってくる動きを候補として採用する。
AA_ ABX _X_
C=5,6でXの箇所が候補にならなかった場合は、次に、2手で揃えられる箇所として、下の図のYの位置も調べる。
__Y__ _AAY_ YABXY _YXY_ __Y__
v2が「2箇所そろっている」の場合も、同じように2手で揃えられるパターンを全列挙してそこに揃えたい色が入っているかを調べる。
反省
- 同一盤面の除去をやらなかった
- 評価関数のパラメタ調整をやらなかった
同一盤面の除去を軽く入れてみたら2%くらい上がったので、もっとこの辺をちゃんとやっていたら通過ラインくらいまで行けていた可能性もある。
詰めが甘いです
