TCO18 MM Lightning 2 KnightsAndPawns 参加記録
問題文：
http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17225&compid=66697
順位表：
http://community.topcoder.com/longcontest/?module=ViewStandings&rd=17225
大学のテスト・レポートとかぶっていてだいぶつらい
問題概要
H*Wのボードにいくつかのポーンが置かれている。ここにいくつかのナイトを置いていく。このとき、すべてのナイトについて、攻撃できる駒の数がちょうど２でなくてはならない。置くコマ数を最大化せよ。
解法
とにかく時間がないので実装が簡単でパラメータ調整でゴリおせそうなものを目指しました（パラメータ調整は大学のレポートなどと並行してできるので）。
一般的な考察
・ナイトのattack数が2ということは、attackしているナイト同士を結ぶとパスができて、パスは閉路であるかポーンを端点としていると言えます。
・3つ以上のポーンを攻撃するマスはそもそも考慮に入れる必要がありません。
validと準valid
validな状態とは、非負スコアが得られる状態、すなわちすべてのナイトのattack数が2である状態です。これに対しすべてのナイトのattack数が2以下である状態を準validと呼ぶことにします。
焼きなまし
僕の解法が全体としてやっていることは焼きなましです。以下に示す状態遷移を繰り返して準validな状態を得た後、validな状態に直すところまでを一遷移として、焼きなましをします。
状態遷移
状態が準validであるとします。基本的な考え方は、「新たにナイトを置いていきたいが、準validな状態を保持したい」です。
attack数が1であるナイトを一つ選び、その近傍にナイトを一つ置きます。選んだナイトをA、Ａの近傍に置いたナイトをB、さらにＢの近傍にあってAでないもの（ナイトorポーン）をCとします。ＡとＢを設定すると、
- そもそもＣが存在しない。
- Ｃとして考えられるものがちょうど1つ存在する。
- Ｃとして考えられるものが2つ以上存在する。
のどれかが成り立ちます。
1の場合は簡単で、Aのattack数が2、Bのattack数が1、それ以外は影響なしなので準validな状態は保たれています。
2の場合は、Aのattack数=2、Bのattack数=2、Cのattack数+=1、となります。Cのattack数が1増えるということは、attack数が3になる可能性があります。その場合、Ｃがナイトであれば準validでなくなってしまいます。そこでＣの近傍であってBでないもの2つのうち一つを消します。もし両方ともポーンであるならば、Ｃを消してしまいます。
3の場合は、そもそもBの候補として除外しておくことにします。
以上の挙動は、以下のように説明できます。
・ナイトが作るパスの端を伸ばしていって、ほかのパスにぶつかったらそのパスを切って切り口につなぐ。ほかのパスの端点とぶつかったら2つのパスをつないで一つのパスになる。
この操作において、ナイトの数が減ることはありません。
そもそもＡの候補がない場合ですが、適当な空きマスを選んでナイトを置き、上述の2の場合と同様な処理を施すことで、状態を変化させることができます。
準validからvalidを得る
準validな状態からattack数が1以下のものを消していくと、最終的にvalidになります。これは不完全なパスをすべて消すことに対応し、得られたvalidな状態は、消す順番などに依らず準validな状態に対して一意に定まります。
焼きなましの一遷移
焼きなましの一遷移は、「準valid保持の状態遷移を20回程度繰り返したのち、上述した方法でvalid解を得る」です。遷移回数は100万回ほどになりました。
細かい工夫
大学レポートと並行しながらやっていた関係で、なんでうまくいくか考察できていない部分が工夫点のほとんどになってしまいました。すべて挙げるときりがないので一部だけ書きます。
・一定期間ベストを更新しないときロールバック処理を行いました。ロールバック直後、ランダムなナイトの消去操作を何回か行いました。また、ロールバック直後の状態遷移の回数をマスの大きさぐらいまで増やしました。
・状態遷移において、低確率でattack数１のナイトを消去するようにしました。
example test
Example scores:
0) 15.0
1) 1335.0
2) 3457.0
3) 1426.0
4) 2001.0
5) 173.0
6) 1389.0
7) 258.0
8) 230.0
9) 1528.0
seed2
