■ [MM]Marathon Match 53 
しばらくマラソンはお休みのつもりだったけれど、大型連休と重なったので参加しました。
問題
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=13795&pm=10410
一人遊びゲーム。ランダムに与えられるタイルを、ある規則に従ってN*Nの平面上に置いていく。何回かは続けてパスできるけどパス回数を使い切ったらおしまい。できるだけ長く続けましょう、という問題（いろいろ端折ってるおおざっぱな説明）。
方針
次のタイルは何かに関する情報は得られないので、一手ごとにその時点での盤面の情報だけを基にして置く場所を決めないといけない。
盤面がどれだけ有利な状態かどうかの評価関数を作って、評価が一番高いところに置いていく、という感じで。
一列そろえることはあまり考えずともよさそうです。とにかく長く続けられるようにしておいたら、自然とラインはできて消滅していくので。
評価関数の調整は主に試行錯誤です。あとは、スタートして10手くらいで詰んじゃってるような上手くいっていないケースをローカルのテスト結果から見つけて、どうして詰んじゃったのかをビジュアライザで確認して、それを回避するような処理を入れていきました。
履歴
| 日付 | 使った時間 | やったこと |
|---|---|---|
| 4/30（木） | 3h | 環境構築、自明解（とにかく最初に見つかった配置可能位置に置く）で提出。30点くらい |
| 5/1（金） | 3h | 次のターンでパスしないといけなくなる可能性を最小にする位置に置くようにした。50点くらい |
| 5/2（土）- 5/4（月） | 20hくらい | 評価関数を計算するためタイルを仮置きするとき、盤面のコピーが重くてTLEしてたのが発覚。 毎回盤面全部をコピーするのではなく差分管理するようにして高速化すると、最悪でも5秒程度で収まるように。 あとは評価関数の改善を入れていって80点台に |
| 5/7（木） | 3h | すでにたくさん囲まれている箇所に優先的に置くようにしたらけっこう上がった。80点台後半 |
| 5/8（金） | 5h | もうパスできない状況かどうかで評価関数を変えてやると少し改善。90点overで暫定1位に |
| 5/9（土）-5/13（水） | 20hくらい | 改善要素が思いつかなくなったのでひたすらパラメタ調整でチューニングするもほとんど上がらず。 どんどん抜かれていきました。 |
そのほか評価関数のポイント
- （ワイルドカード以外）どのタイルも置けない箇所がとにかくできないようにする
- 置けるタイルが1種類・2種類だけという場所もできるだけできないように
- 開始直後に詰んじゃうケース対策は、「ワイルドカードの隣を使うのはこれ以上パスできなくなったときの最後の手段にする」という方針で回避できるものが多かった
- 縦横同時消しはボーナスがあるので、ダブルリーチになるような状況は多少プラスに
- 10000ターンで打ち切りなので、打ち切り直前の局面では長く続けることよりも一列そろえることを優先する
結果
暫定スコア 87.28 （最良を100とした相対評価）
暫定順位 5/131
感想
- スコアリング方法がちょっと特殊だったので、改善度がローカルテストで測りがたかったです
- 追われる身は気分的につらい。スロースターターの方が穏やかな気持ちで戦えますね。次からはちょっと潜伏気味で提出していこう
- 最後のパラメタ調整は半分自動化半分手作業でちまちまやったけれども、山登り法とか使ってプログラム的に決めてやるべきものなんだと思います
- 今回もまた最後のほうでソースコード管理がぐだぐだになってしまった。次回こそはちゃんとバージョン管理システム使う
- ビジュアライザのマニュアルモードでやったら自分が組んだアルゴリズムに結構負けて「情報科学すげー」と思った
今回は連休中だったせいか日本人の参加が多かったようです。もっと参加者増えてくれるといいなぁ。
SRMと違ってちょっとミスってても0点になりませんよ！ 完全に自分のペースで取り組めますよ！ Pythonも使えますよ！
