inani_waonの日記

コンテスト覚書

MM125 Lines 参加記録

TopCoderのMarathon Match 125に参加しました。

問題はLines。ボールを5つ繋げると消えるパズルです。

www.topcoder.com

 

 

提出53人中、Provisional4位、最終順位6位でした。

ルール

ボールは空きマス4近傍を距離無限で移動できます。

・ボールを5つ以上直線に繋げた場合は、ボールが消えてその数に応じた点が入ります。

・ボールを5つ繋げない移動をした場合は、ボールが3つランダムに生成されます。

　・ボールの生成により5つ繋がった場合も、移動で5つ繋げた場合と同様に消えます。

1000回移動するか、盤面がボールで埋まるとゲーム終了です。

 

あとこれはコンテスト終了後に把握した情報ですが、縦横斜めの複合で消すと別々に計算されるのではなくて消した総数に応じた点が入るっぽいです。†本質†情報では？

 

考察

序盤考察

MM123の焼き直しっぽい。というかサンプルコードのクラス名をJewelsから直し忘れていますね？

消す長さボーナスは、長さ5で10点、長さ9で38点、長さ11で71点と、MM123に対して緩やか(?)な伸び。また、ボールの消去を伴わない移動をするとボールが3つ湧いてくるので、MM123のように固定盤面を埋め込んで再現するのは無理そう。

実はボールの生成により2ライン以上を同時に消したり長さ11で消すことが出来る。長さ11の消しは同じ色のボールが偶然2か所に同時湧きしないと実現しないので切っていいかな。

縦横斜めの複合消しもボールが少なくて済むけど、閉路を生みやすそう。←この考察はルールの把握を間違えています。

ボールは消去を伴わない移動でのみ増加し、得点はボールを消すことでのみ増加する。そのためボール生成による消去が発生すると手数あたりのボール総数が増え、得点アップにも繋がりそう。

すぐ消す色と長く消す色を分けたり、マップ端で長く消すのを組んで中央では雑に消す、みたいな区分けをすると良いかも？

難しそうだけどとても面白そうな問題に見える。

中盤考察

フォーラム情報で、MM5と問題モロ被りであることが判明。公平を期すため、MM5の方針紹介スレッドが公開される。MM5フォーラムではこの辺りが有益情報に見えた。

・評価は長さを5乗した(17位、青)

・3手読みした(1位、赤)

・同じ色の交差部分にペナルティを与えた(1位、赤)

17位の人も1位の人も言ってることは一緒で、正方形的な物を作るのを避けて細長く連結しましょうということだと思われる。

終盤考察

生成による消しは、盤面がある程度埋まっていないと全然関係ない場所に生成される方が多いので期待できないうえ、盤面が埋まっていくと今度は加速度的に移動が制限されて手詰まりになるので利用は難しい。

1000ターン生き残るだけで3800点くらい入るので、これを伸ばすよりはより多くのケースで長生きすることを目標にした方がよさげ。

 

 

やったこと

Step1

まずは1手読み貪欲。ボールの移動自体が可能かは、空きマス同士を連結するUnion-Find木を作って確認した。*1長さ5の領域を全走査して、単色（1色+空きマス）であれば[ボールの最大の連結長^3]を評価として、その総和を取る。ボールを消した場合は[実スコア*100]を評価に足す。まだ高速化も不十分で、実はN11のケースではTimeoutしていた。

Step2

やる気を無くす。ぼくのかんがえたさいきょうのほうしんとほぼ同一のものが全体公開されてしまった。MM5って15年前だし、人員も変わってると考えたら仕方ないのかな…。

Step3

飛び石的な配置も評価できるようにした。長さ5の領域毎のパターンは、単色に限定すれば31パターンしかない*2のでビットパターン毎に評価を埋め込んだ。基本的にはボールの数で指数的に評価が増えるようにして、隙間があれば評価を少し下げた。

Step4

ビームサーチした。深さは2で固定で、幅はNによって決める。N=7であれば30、N≧10であれば4。多様性確保のため、[移動先の座標]毎にベストを4個取って、更にその中身をマージして、[消去発生][消去非発生]毎にそれぞれ幅の半分を取る。*3つまり、N=7であれば消去発生時と消去非発生時をそれぞれ上位15個まで持つ。N=11などは時間が間に合っていないので、1ターンあたり10msを目安として間に合わなさそうな場合は[ビーム幅を半分にする]または[深さ1にする(1手貪欲化)]で遅れを取り戻す。また、2手目で得られる評価は0.8倍とした。

ちなみに何のためにビームサーチ（複数手読み）するのかというと、邪魔なボールを動かすためや、長さ6以上で消す準備のライン延長をするため。

 

細かいパラメータ調整

・パターン毎の評価

十字や正方形を作りたくないので原則長くなるごとに8倍。4個揃いだけ4倍なのは消去スコア計算との兼ね合いだけど、もっと良いパラメータはあるかもしれない。これでも油断すると正方形的なものを作ってしまう。

const int partScore_1 = 10;
const int partScore_2 = 80;
const int partScore_1_1 = 60;
const int partScore_1_1_1 = 560;
const int partScore_2_1 = 560;
const int partScore_2_2 = 2240;
const int partScore_3 = 640;
const int partScore_3_1 = 2240;
const int partScore_4 = 2560;

・消去評価

原則[実スコア*800]としたが、無理ゲー(1000ターン完走できない)ケースでは短く消す方が嬉しいように式を弄った。*4

　・通常ケース

　　(len * len - 7 * len + 20) * 800

　・無理ゲーケース

　　((len - 1) * (len - 1) - 7 * len + 39) * 800

 

高速化

・差分計算

消去が発生しない場合、移動元と移動先の座標を含む領域だけを再計算すれば良い。更に言えば、その領域計算は開始時に1回だけ纏めてすれば良い。

・連結数による足切り

同色が繋がっている数で色・座標毎に現在価値を決め、現在価値より2以上低い場所への移動を禁止した。ただし、より長い色の線を塞いでいるものを除ける操作は許可。

・消去操作による足切り

原則的に消去操作の方が圧倒的に評価が高いので、1手目で消去できるのにしなかった場合は2手目で必ず消去操作を行うことにした。また、時間切れで1手読み化している場合も、消去操作を見つけた場合は以後消去操作のみチェックするようにした。

 

やってみたけどダメだったこと

・斜めの評価を下げる

斜め配置は閉路を作りがちなので控えてくれると助かると思ったけどスコア上はそんなことはなかった。

・四隅に何かあると微ボーナス

端に詰めたり長く消す狙いだったけどスコア低下した。

・空きマスを評価

空きマス同士が連結していたら～みたいな感じで評価していたけど、重いうえにスコア低下した。評価方法が上手ければ上手く行ってたかも。

 

やりたかったこと

・２手目のペナルティを可変にする。

C3で盤面がガラガラで次に出現するボールが全て2手目で動かすのと同じ色というケースとその逆では、2手目に想定通りの手を打てる確率が全然異なる。ただこれを調整すると普段の消す消さないの挙動が不安定になるので手を付けられなかった。

・端に寄せる配置を高く見積もる。

長く消すためには端を埋めて最後に真ん中を詰めるという操作が必要だが、評価関数の都合上、外周2マスは評価が低くなりがちなので、真ん中を先に埋めて長さ6～7でしか消せなくなることが多かった。

・長さ5の領域内が多色だったときの評価

最終的に一律で0としたが、工夫すれば伸びていたかも。

　・（評価が長さ^3だったときの検証）長さ^1とする

　　スコア+1%だったけどあまりに誤差だったので外した。

　・-10点とする

　・2マス目で多色を検出したら-50点、3マス目で検知したら-40点、…

　・隣接なら-50点、1マス空いていれば-40点、…

　　2番目が一番良かったけど、あまりに根拠が不明確だったので外した。

 

他の人の解法を見て

え、斜めの方がいいの？（閉路が出来やすくないですか？）

端に寄せて真ん中を開ける方針だとその方が良いのかな。評価の組み合わせ相性は大事ですね。

ビジュアライザが動いて楽しい、それはそう。

 一番邪魔な場所に出てくるボール、嫌すぎる。(もしかして3ターン読みしてますか)

 

評価が難しいときはモンテカルロ、それはそう。

 4個揃えたけどあと1個が絶対に入らないみたいなのが稀によくあったので、これを計算出来てるのは強いですね。1000ターンもたないケースに強そう。

 

総合的に見ると処理時間内で読みの精度を高めるための工夫がそれぞれ違う感じで面白いですね。

 

こちらはTopCoderのフォーラム（要ログイン）

https://discussions.topcoder.com/discussion/4777/post-your-approach

 

感想

MMはTesterの機能が充実していて、純粋に問題を解くことに専念出来るのでありがたいですね。

MM5との問題被りというか、それによる情報公開で実装するだけゲーになった（実際はそうでもなかった？）ことでモチベーションが一時消失しましたが、15年前に当時の計算資源で同じ問題を解いてる人たちもいたんだな、ということに思いを馳せたりしながらなんとか完走しました。

最終形はハイパーパラメータだらけなので、もっと上手い方法は無いのかという感じでしたが、やること自体はシンプルに出来た（探索手法はそうでもない）ので理想の戦い方にちょっと近づけたかな、と思います。

 

*1:移動元の4近傍のrootいずれかが、移動先のrootと同じなら移動可能。

*2:32でないのは、全部埋まってるケースは消えるので。

*3:消去発生パターンの数が少ない場合はその分消去非発生に幅を割り当てる。

*4:完走出来る目安はN7C3,N8C4,N9C5,N10C5~6,N11C6。これよりCが大きいものは無理ゲー。