TopCoderのMarathon Match 122に参加しました。
TopCoderは初参加です。
問題はSuperMinesweeper。クソデカマインスイーパーです。
結果は17位でした。（登録162名、投稿87名）
レート0→1,658(黄)
問題考察
マインスイーパー、以上。となるのでパラメータの考察を。
N
盤の1辺のサイズ。10～50。
大きいほど時間がかかる、多様な盤面を含む、初期位置が隅になりにくい。
D
セルの数字が示す範囲（後述）1,2,4,5,8,9,10。
大きいほど完全特定しにくい？
M
爆弾の数。N*Nの0.1～0.3倍。
大きいほど数字セルが減り情報が減る、運任せが失敗しやすい。とても影響が大きい。
Score
安全セルを開けた数 * (1 / 地雷を踏んだ数)
地雷を踏まないのが最も良く、1個踏むと全て開けても0.5。地雷を踏んでしまった場合は次のペナルティが相対的に軽くなるので、積極的に開けていくことになる。
数字の範囲
安全なセルには距離がabs(x1-x2)^2+abs(y1-y2)^2以内のセルの地雷数が表示される。式を書くより図の方が分かりやすいので下記参照。
D = 1
□■□
■◇■
□■□
D = 2
■■■
■◇■
■■■
D = 4
□□■□□
□■■■□
■■◇■■
□■■■□
□□■□□
D = 5
□■■■□
■■■■■
■■◇■■
■■■■■
□■■■□
D = 8
■■■■■
■■■■■
■■◇■■
■■■■■
■■■■■
D = 9
□□□■□□□
□■■■■■□
□■■■■■□
■■■◇■■■
□■■■■■□
□■■■■■□
□□□■□□□
D = 10
□□■■■□□
□■■■■■□
■■■■■■■
■■■◇■■■
■■■■■■■
□■■■■■□
□□■■■□□
やったこと
完全情報フェーズ
確実に地雷が無いセル、有るセルを特定する。基本的に出来る事は2つしかなく、自明なルールによる一定範囲内の個数特定と、有り無しを仮定した総当たり。総当たりは強いが時間がかかるため、軽くて雑な絞り込み＞重くて丁寧な絞り込みの順で行い時間を節約する。1セル開けることでヒントが増えて更にセルを開けることが出来るので、軽くて雑な絞り込みも多様性があればそれなりの総合力になる。以下の順で行い、途中で何かが判明した場合は先頭からやり直した。
・数字セルの周囲が全て安全、または危険の判断
・残り地雷が0なら全て安全
・数字セル2つの関係から、共通領域・数字セルAのみにかかる領域、Bのみにかかる領域の地雷最大数と最小数を計算
・数字セル1つの範囲内を総当たり(K≦22) K=不明セル数
・数字セル2つの範囲の和を総当たり(K≦22)
・3x3領域を総当たり
・残領域全てを総当たり(K≦26)
・数字セル全ての範囲内を総当たり(K≦26)
・5x5領域を総当たり(K≦18)
・→これでも何も分からない場合は不完全情報フェーズへ
不完全情報フェーズ
セルを開けた場合の期待値を雑に計算。しかしセルの座標ではなく全く関係ない添字を計算に使用しており、何故動いているのか分からない。直すと弱くなる…。
期待値が悪くしかならないケースのほか、Score0.4で打ち切るが、D=1かつM/NN>0.25のケースは地雷踏み連発で破滅しやすかったのでScore0.1で打ち切るようにした。
全列挙実装
以下の手順で行った。
・全列挙する不明セル群（以下、不明セル群）の座標をListに積む。
・不明セル群に対するD範囲内の数値セルを抽出する。
・各数値セルに所属する不明セルのListのindexをビットパターンにして覚えておく
・2^[不明セル群の個数]だけカウンタ++しながらループする
・実はこのカウンタ値はそのまま、どのindexの不明セルを地雷扱いするかのパターンになる
・数値セルのパターンとAndを取ると不明セル群内の地雷数が判明するので、上限数、下限数をチェックする
ただしこれだけではパターン数が膨大なため、代表的な数値セル1つを抜き出し、その地雷を許容する最大/最小数をチェックすることである程度高速化した。
Good
・領域の形に依存せず、全列挙自体を最小の手間で行える（5x5、D範囲内、残り全部など）
Bad
・部分的な制約を無視して全列挙する（1の数字セルの周りに地雷を3個置くパターンを延々試したりする）
・言うほど最小の手間ではない（高速化とデバッグにコンテスト期間のほとんどを費やした）
・3x3版は＞＞9重ループ＜＜
やりたかったこと
１．自明なルールを論理的に分解。
処理時間がかかりそうなのと、ビット周りの実装に手間取りそうなこと、{1,0,1,0}か{0,1,0,1}みたいなパターンに弱そうなことから総当たりを優先した。実際は6時間くらいで高速なものを実装している人もいたので可能だったのかもしれない。
２．運任せの細かな確率計算。
確率だけ計算出来たところで、という感じだったので他を優先した。数字セルの範囲内にある不明セル数が100を超えると時間も不安だし。
３．運任せ後の盤面構築。
色々試したものの上手く性能向上せず、膨大な時間がかかりそうだったので断念。
４．地雷数の制約を考慮した全列挙
絶対バグらせると思って投げ捨てた。処理時間が間に合うかも不安だったし。
感想
問題として良かったか？と言われると良くなかった気はするけどそれなりに楽しかったです。C#（を使いこなす技術）の限界を感じる…。
たのしい
・パーツをたくさん作って繋げられるゲーム。
・座標毎に再考フラグを管理して無駄な処理を削ったりする作業。
たのしくない
・人間の能力があまりに足りないのでトレースしにくい。
・副作用の塊みたいな入出力。
・運任せフェイズの運任せ感。
・C#、立っているビットのカウントくらい高速にやろうや…。
・BitArray君、All、Any、Equality、ビット数カウントくらい積んでほしい。
・Topcoder君のUI。もうちょっとなんとかなりませんか…。
