Xmas Rush

CodinGameの10日間コンテスト。アイテムを集めるゲーム。

f:id:y_kwn:20181217212006p:plain

リプレイ ： https://www.codingame.com/replay/360798673

世界29位/1229人、日本2位/40人でした。上位層に全然ついていけなかったので悔しい結果です。

ルール

大きく分けてPUSHターンとMOVEターンに別れていて、その2つのターンを繰り返します。

PUSHターン：いずれかの行列をPUSHして迷路をずらします。このときの行列の指定は敵味方同時に行います。敵味方で同じ行or列が指定されたら何も起きません。

MOVEターン：プレイヤーを20歩動かすことが出来ます。アイテムが3つ指定されるのでそのアイテムを回収するのが目的です。回収すると次のアイテムが指定されます。

最終的に12個のアイテムを回収したほうが勝利します。

アルゴリズム

minimaxっぽいことやりました。計算時間は余裕だったので枝刈りとかやってないです。

PUSHターン

自分のPUSH(max) → 敵のPUSH(min) → アイテム回収MOVE(一意に定まる) → 自分のMOVE(max)

という探索をやりました。2手読みとかやってみたんですけど性能落ちたので採用してないです。

MOVEターン

アイテム回収MOVE → 自分のMOVE(max) → 自分のPUSH(max) → 敵のPUSH(min) → アイテム回収MOVE → 自分のMOVE(max)

という探索をやりました。

評価関数

  • 回収したアイテムの個数がベース
  • 自分が端にいてNEXTに自分のアイテムがあったらそこそこプラス
  • 自分が動ける範囲が広かったらちょっとプラス
  • 指定アイテム周辺の道が繋がってたらほんのちょっとプラス
  • 相手を邪魔するより自分の得点を稼ぐムーブをしたかったので、自分に関する評価値はちょっと増やした

小手先テクニック

  • 行のPUSHが優先されるのでNEXTが自分のアイテムでかつ横端にいると100%アイテムを回収できる。
  • よく行列がかち合って数ターンロック状態になるけど、ロック状態のときは相手は自分と同じ行or列を指定しているはずなので、敵の動き予測が2パターンまで絞れる。
  • 敵がアイテム回収を先行している場合、敵の指定アイテムを記録しておくことで自分の次の指定アイテムを予測できる。

反省