simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

MM136 HungryKnights 参加記

問題

www.topcoder.com

今回のスコア計算では同色の移動を連続で行うことで指数的にスコアが増える仕様となっていたので、出来るだけ長い同色消しの経路を作成する必要がありました。

方針

基本的な方針はビームサーチでの経路探索になります。

スタート地点の選択

長い経路を作りたいので、盤面にあるマスの色をカウントして一番多い色から消していきます。どのマスからスタートするかはランダムに決定しました。

移動先の決定

現在位置からの移動の候補は 8種類あり、移動先が同色かそうでないかで処理を分けます。

同色の場合

同色の場合は特に処理を行わずそのまま移動します。

違う色の場合

色が違う場合は別のマスから対象の色を持ってきて遷移するようにします。

移動先が別の色でこのままだと連鎖が途切れてしまう。

別のマスから同じ色の駒を持ってくる。

移動が可能になる。

この「別の駒を持ってくる処理」については連鎖中に行ってしまうと連鎖が途切れてしまうので、まとめて連鎖用の経路の前処理として実行します。

評価関数

処理後の盤面評価についてですが主に以下の点を重視しました。

  • 残っているマスの個数
    • マスが残っているほど移動に自由が効いて連鎖を作りやすくなる
  • 画面端に近いマスを消していると高得点
    • 画面端のマスは残りやすいため、なるべく残らないように評価を高くしておく
  • 次に消す予定の色を残すようにする
    • 他の色でも大連鎖を組みたいのでなるべく残すようにする
    • その色だけではなくて周辺のマスも消さないようにする

その他

細かいスコアを取るためにやったこと、連鎖スコアに比べると些細なものなのであまり細かく詰めてはいない。

貪欲

連鎖も作れなくなったあとは残った駒を貪欲に消していきます。

挿入

最終的に使われない駒で、その周辺で処理を挿入できそうな箇所があれば変更を行います。

右上の青が最後まで使われなかった場合

「紫」→「黄色」と移動を行っているが、「青」→「黄色」 +「紫」→「青」 のほうがスコアが高くなる場合は「青」→「黄色」の処理を挿入する。

事前同色消し

残った駒の周辺に同じ色の駒がある場合は事前に同色消しを行っておきます。

先程と同様に青が残っている状態

事前に同じ色を使って消しておくことで 1点もらえる

感想

ビームサーチで評価関数勝負かと思ったら 1位は焼きなましだった。2色同時探索はちょっと実装しようかなと思ったけど、焼きなましはちょっと思いつかなかった。とりあえず実装してみてどのぐらいのスコアが出るかは確認したほうが良かったかもしれない。(初手のビームサーチで良いスコア取れたからそれに引きずられた感はある)

2割、3割スコアが離れてたら方針を疑ったかもしれないけど 1割以内で Psyho さんだったしなんかいい感じの評価関数があるのかなと思ってしまった。