codingame -Mean Max- 参加記
この記事はKogakuin Advent Calendar 2017 ６日目の記事です。
Kogakuin Univ Advent Calendar 2017 - Adventar
今回は世界111/2512位、日本5/67位でした。前回から随分と順位が下がってしまい、悔しいですね。
今回のゲーム
貴重な水を相手より多く集めろ！ってゲームです。（映画MadMaxのパロディらしい）
３種類の車を操って、灰色のタンク車を倒すことで水が出現します。
↓のゲームのプレイ映像を実際に見てもらったほうが雰囲気はわかります。
Coding Games and Programming Challenges to Code Better
今回のゲームの特徴（ゲームAI作成の視点から）
・車はx,yそれぞれ-6000~6000の範囲の座標を持つ（状態数が多い！）
・車を３台同時に操る必要がある
・車たちは簡単な物理演算にしたがって動く
・１対１ではなく、３人のプレイヤーで戦う
・各車はそれぞれ妨害スキルを使用することが出来る
各車が出来ることは２つ
１：指定した(x,y)の方向に向かって、指定した量のアクセルを踏む
２：指定して(x,y)の地点にスキルを放つ
となっています。
今回の方針
シミュレーションベースではなくルールベースでやってみました。理由は１ターンあたり制限時間50msで車の行動選択肢が多く、シミュレーションはできないだろうと思ったため。（上位陣はシミュレーションがほとんどらしく、この判断ミスが最大の敗因ですね）
実装
Reap→Dest→Doofの順に行動を決めています。
１つの車あたりの処理
１：行き先を決める（Reap→Wreck、Dest→Tank or Wreck、Doof→敵Reap）
２：１ターンで進むであろう（適当予想）移動ベクトルを求める
３：移動ベクトルを加算した時に、他の車と衝突しなくなるまで移動ベクトルを回転させる
４：現在の車の速度を考慮して、求めた移動ベクトル通りに進むように、加速ベクトルを求める
今回は４番について詳しく解説します。
行き先ベクトルをそのまま加算しても、車はその方向には進みません。現在の車の速度ベクトル＋移動ベクトルとなってしまうためです。
正しく移動させるには、以下のような加速ベクトルを求める必要があります。
この加速ベクトルを求めるには、余弦定理を使います。今回は式変形したこちらを使います。
式の各変数を以下の図のように当てはめます。
ここで、|b|を最大の600と決めます（移動は常に最大加速で進みたいので）。するとcの長さが決まり、-a+c=bによってbの速度ベクトルが求まります。
この速度ベクトルを出力すると、行き先ベクトル方向にきれいに進むようになりました。
細かく言えば他にも、cの長さが行き先ベクトルより長かった場合の処理（通り越してしまう）や、そもそもbが存在しない場合の例外処理も実装しましたが、（適当な処理でごまかしただけなので）解説は割愛します。
感想
ルールベースを実際にやってみたところ、かなり実装コストが高かったためかなり時間を取られました。１つ１つのルールの実装コストは低めですが、大量のルールを実装しなければならない、といった感じです。
対して、シミュレーションベースは初回にシミュ完成させるまでは実装コスト高ですが、それ以降の実装のノビが良い気がしました。
正直、ルールベースが大変なんてことは常識なのですが、「ちょっと挑戦してみたい」という気持ちが消化できて良かったです。二度とルールベースはやりません。
ルールベースが適切な問題のあるらしいので、これからは問題に対して使用する手法をよく吟味しようと思います。
