TopCoderのMarathon Match 123に参加しました。
問題はJewels。マッチ3パズルです。*1
結果は登録176人、提出67人中の6位。
レート1658→1924(黄)
考察
当方、パズルはパズドラを嗜んだ程度*2で、ぷよぷよもテトリスもからっきしです。
とりあえず得点を見ると[(消した線の長さ-2)^2] * [Chain数] の合計ということで、とにかく大きいコンボを1発でも決めることが大事だと分かります。*3
盤面を見てコンボを探索するよりも、固定コンボを埋め込む方策が強そうですね。
大体同じコンボを繰り返すということで、
Score = [コンボの平均得点] * [コンボの実行回数]
となります。
上記の計算式より、
- コンボの平均得点を最大化する(厳密には平均得点/手数のコスパを最大化する)
- コンボの実行回数を最大化する(実行までの手数を最小化する)
という2つの問題をそれぞれ解くことになりそうです。
ここでL字などの複雑な形の得点が読み解けなかったのでテスターを使って手で問題を解いてみたところ、縦と横はそれぞれ独立した点が入ることと、Chainは消した連結成分の数ではなく落下が発生した回数であることが分かりました。コンボ作るの難しそうだな？
実装
とりあえず考えている方針で上手く回るかを見るために簡単なコンボパターンを埋め込んで回してみようということで、先に簡易的な（？）実装を行いました。セル毎に目標色を設定して、最後にコンボ始動用に発火する２点を交換する感じです。
この辺りでテスターを見やすくするために宝石の画像に数字を書きこみました。
回してみた感じ、以下の点がネックになりそうでした。
- 移動しようとすると3つ揃えてしまうケース
- 特定色の宝石が足りないケース
- 行き場の無い宝石の追い出しが無限ループするケース
また、以下の改善点がありそうでした。
- 交換する２マスの両方にメリットがある交換をする
- 等価の盤面（色違いや左右反転）を評価して移動回数を減らす
- 落ちコン*4でコンボが破壊されるのを防止する
問題点についてはパターン側で色の数を偏らせないようにしたり、盤面全体を使わずに余裕を持たせることで多少の数の変動に対応できるようにしました。それでも宝石不足が発生したときは、余っている色の宝石を消すようにしました。また、無限ループっぽいなと思ったら強制的にコンボを始動させるようにしていました。*5
移動の効率化についてはルール決めで２マスに得がある移動を優先したり、パターンの色C種類と実際に使う色C種類で不整合セル数の最小マッチングをしました。
落ちコン対策は、セル毎に禁止色のマスクを作ることで屋根と壁を作りました。ただ完全に防げるわけではなく、屋根が破壊されたうえで更にちょうどいい色の宝石が降ってきてコンボパーツが破壊されてしまうことがあります。しょうがないね。
パターン作り
手、もといExcelで作りました。
色々と試行錯誤した結果、1chain目で土台を破壊してコンボ始動し、2chain目で大量に列消し、3chain目以降で3セルずつ消してchain数を稼ぐようにしました。
MM123、Seed2でこんな感じでした。
— いなにわ (@inani_waon) 2021年2月3日
Excelをキメるゲームです…。 pic.twitter.com/omHw8J7zZu
コンボの最後に列消しを行う形だと消す列数が制限されるうえ、落ちコンで事故が発生して期待した点数が出ないことが多かったです。
やれなかったこと
- 不測の事態*6で挙動不審になりやすい件への対応
- 連結成分単位での色の割り当て
- 残り時間が少ないときに小さいコンボを組んだりして小さく稼ぐ
- シミュレータを走らせてさいきょうのパターンを見つける
みんなの方針を見て
見た限り、ほぼ全員がパターン埋め込みをしていました。強めの人々は連結成分単位で色の割り当てをしていたようで、この辺りは典型なのかなと思いました。やり方は分かったので次があれば頑張ってみたいです。
あとはもう強いパターンを組めたかどうかという世界のようです。
感想
これはこれで楽しいけど、これはプログラミングコンテストなのか…？
