ゲームで競技プログラミングできるcodingameが凄く面白いです。
触ったことがない方は是非やってみてください。
https://www.codingame.com
codingameは様々なゲームを選べるのですが、その中のcoders strike backで最高ランクであるlegendに到達したのでやったことをメモしておきます。
coders strike backとは
https://www.codingame.com/multiplayer/bot-programming/coders-strike-back
レーシングゲームのAIを作ります。
各リーグのボスに勝つと昇格できて、少しづつルールが追加されていきます。
最終的には2v2のレーシングゲームになります。
やったこと
1週間でlegend到達。かけた時間は40時間くらいです。
勉強のため触ったことのないgo言語を選びました。
goldまで
bronzeまではすぐに上がれたのですが、silverに中々上がれず、ゴールの履歴を保存しておいて2周目以降のコーナリグに使う機能を実装してようやく上がれました。
silverのボスはそれにうまい感じで減速する機能をつけて突破。
絶対もっと楽に勝つ方法があると思うので知ってる方がいたら教えて欲しいです...
最終的に実装したもの
goldで全情報が与えられて絶望した
codingameのページで見られる動画を参考に戦略を立てました。
走行用と妨害用で役割分担する方式です。
走行の戦略
goldボスの走行アルゴリズムは相当優秀で、最後まで越えることが出来ませんでした
試行錯誤の末実装した機能は、
- 速度ベクトルと目標点の方向がずれている場合、合うように目標点をずらす
- 敵の1フレーム先の位置でシールド判定
- 2個先のチェックポイントの位置を考慮して目標点をずらす
- ブーストは長い直線で使う
- 目標点の位置と機体の向きがずれている場合減速する
になりました。
特に1番の実装によって曲がりきれずチェックポイントを過ぎてしまうことがほとんど無くなって順位が飛躍的に上がりました。
妨害の戦略
妨害の戦略は自信があり、goldの中では一番優秀だったと思います。
実装した機能は、
- 速度ベクトルと目標点の方向がずれている場合、合うように目標点をずらす
- 敵の1フレーム先の位置でシールド判定
- 先頭を走っている相手に対して妨害する
- 相手のチェックポイントに先回りできない場合、2個先のチェックポイントで待ち伏せする
- 自分と相手の距離、そして相手の速度を考慮して相手と衝突できる点を先読みする
4番は動画にあるトッププレイヤーの動きを真似したものです。
これをするだけで相手によってはほとんどゴールできない状態まで追い込むことができます。
終わりに
codingameは定期的にコンテストをやっていて賞品も出るみたいなので、次のコンテストは頑張ってみようかなと思います。
次のコンテストは5/12みたいです。