CODERS OF THE CARIBBEAN
CodinGameの10日間コンテスト。↓こんな感じで船を操舵して樽を拾ってHPを回復しつつ砲弾・機雷で相手を潰すゲーム。
https://www.codingame.com/replay/212959177
世界11位 / 国内1位 でした。
アルゴリズム概要
3手読みのchokudaiサーチでした。ホントは全探索したかったんですが3隻+3手だと時間的に無理だったので時間管理が楽なchokudaiサーチを採用しました。
1手につき味方全隻のTurnLeft・TurnRight・Faster・Slower・Waitの組み合わせを探索してます。(つまり3隻なら1手が53=125パターン)
探索の結果TurnLeft・TurnRight・Faster・Slowerが選ばれた場合は普通にその通り行動するんですが、Waitが選ばれた場合は、機雷を置いて効果のある場面なら機雷を置いて、それ以外だったら砲撃するみたいな行動をとります。
探索の最中、敵のターンは基本的に流すだけですが、最低限砲撃を避ける・機雷を避けるという行動は取らせるようにしてました。
機雷の置き方
敵の進行方向上に置けるなら置くって感じでした。また、劣勢時に敵が近くに居ない場合は、砲撃しても無駄なので機雷をばらまいてました。
砲撃地点の選び方
基本的には敵の未来位置に対して砲撃するだけです。未来位置付近に機雷が置いてあった場合は爆発巻き込み狙いで機雷を砲撃します。 敵が近くに居なくて自分が優勢のときは機雷の除去に走ります。また、自分より敵に近い樽を見つけたら容赦なく樽を砲撃しました。
評価関数
- ラム量がベース
- 速度が0ならペナルティ
- 味方同士が近づきすぎたらペナルティ
- マップの端に突っ込んだらペナルティ
- 敵のケツに突っ込んだらペナルティ(機雷警戒)
- 速度0の敵に砲弾を飛ばしてたらボーナス
- 樽に近いとボーナス
- 優勢時は敵から離れればボーナス
- 劣勢時は一番ラム持ってる敵に近づくとボーナス
シミュレータのデバッグ
これは前回のCodinGameでもやってたんですが、シミュレーションした盤面と実際の盤面を比較して差異があったらエラーログを飛ばすってことをやってました。これやると、完璧と思ってたシミュレータのバグがボロボロ見つかったので、これやるのは必須と言っていいんじゃないでしょうか?
反省
αβやっても良かったんじゃないか?
3手読む必要が本当に合ったのか?(でも3手読みたい場面があったのは確か)
自殺してラムを生み出す手法は軽く導入しただけだったけど、もっと注力しても良かったかも。