2017年2月26日~3月5日に開かれた競技プログラミングコンテスト、codingame「ghost in the cell」の備忘録です。
結果
世界24/3508位、日本3/81位でした。
今回のお題は、ロジスティクス(兵站)を競うゲームだったと理解しています。
考えたこと・やったこと
初日
ぱっと見で、好きな部類のゲームでした。既存のゲームでは、下記のFlashゲームが一番近いんじゃないかと思います。
http://www.bubblebox.com/play/action/20130192.htm
この手のゲームは、自分のユニットをなるべく遊ばせないようにする(陣地からなるべく動かす、移動は最小限に)のが重要なのは知っていたので、スタートダッシュで最寄りの陣地からユニットを移動させるようにして暫定世界一を取りました。
2日目
オブジェクト指向にリファクタリング。この時、初日のコードとまったく同じ挙動を維持します。(初日のコード結果がそのままテストケースになる。)
合わせて、コーナーケース部分の挙動の確認と、実装アイディアをメモっておきます。
↓実際のメモ(✓マークは、最終的に実装したもの。ついてないのは未対応。)
■ルール
一度取ったら、兵士0でも自分の陣地。
ボムは発射陣地は見えるので、ターン毎の着弾予測は可能。
距離は最大20。
兵士のバトル後にボムの爆発判定。
中立に同時についた場合は、プレイヤー同士で潰し合う。■必須
✓ターン毎の予測★
✓どっちの兵士数が多いか
✓どっちの生産力が多いか
影響の無い範囲で、常に飛ばしておく※隠しておく?
✓前線の考え方。最寄りの敵陣より数を減らさない。
✓前線に兵を集める
最短での兵力増強★
✓ぎりぎりでの兵力増強
incを早めるため、一箇所に集中して投資
ボムを投げたあとに即座に畳み掛ける
✓自陣単位ではなく、ターゲット単位で行動を決める。
広いステージではinc中心、狭いステージではincよりもアタック。
★後出しした方が良いステージの攻略
期待値を求める。距離と生産数の関係。
✓敵陣を攻めるときは、最寄りの陣地まで一度行く。
✓移動時間が元の以下なら経由地を挟む。
✓中立地は、最小コストになるタイミングで取る。
✓所有者が変わることを考慮した予測ユニット数を出す。
✓ボムが見えているとき、可能性のある陣地は、敵の襲来を相殺する。
✓ボムの着弾先に送らない。バグ
✓生産maxなのに兵を送らない事がある。
✓ボム時の兵士予測にバグ。
✓ボムの可能性があるなら、兵士を動かす
✓ボム時の敵兵相殺
密集ステージは、前線に兵士を残す。incも控えめ
☓id0は、自陣が十分整ってから攻める。
ボムのうち先に兵士を送らない
取り返せる陣地にボムを打たない。■やりたい
✓中央を足掛かりに攻める。
中央の立地がイマイチ(遠い)な場合は中央を後回しにする。
✓ボムの着弾地予測、ボム避け。
不利な状態からの挽回策(今は特に無い)
相手に中立地点の敵を倒させ、乗っ取る。
ボムの先投げ、ボムの後投げ。
攻防の集中する自陣にボムを打ち、敵の予測を外す。
ボムを打つと同時に敵に押し寄せる。
捨てる工場の判断。※行動の優先順
敵がまとまってきた時に、ちょうどボムで殺る。
取られてもいいから取り返す。
掠め取って、すぐ戻る。
ボムの初激2発打つか?
3~5日目
必須の実装アイディアをコードに起こし、防御力を高めていきます。
この工程は実装すればするほど単純に強くなるので楽しい。
1週間のコンテストなので、どれだけアイディアを実装できるかの勝負と考え、シミュレータや先読みは一切行わず、ルールベースオンリーで行こうと決めました。この実装戦略は当たりだったと思います。
6~8日目(最終日)
今回のゲームの核となる、ロジスティクス(兵站)を競いにいきます。
基本的に、攻める側は移動時間のロスがあるため、相手にきっちり守られるとユニット数の自然増加の分だけ損をします。ただ、有利な陣地を先取りすることでリードタイムを短縮でき、相手が対応仕切れない速度で攻めることができます。
有利な陣地とは多くの場合中央(id:0)の陣地です。
ただ、防御時とは異なり、攻めと引きのバランスが難しく、残りの時間で十分に完成度を高められませんでした。これは実装順の戦略ミスです。(もっと防御を完璧にしておくべきだった。)
結果、上位にもそこそこ勝つけど、下位にもそこそこ負けるAIとなり、レートを安定して稼げませんでした。
終戦。
ソースコード
(githubアカウント作らないと…)
最後に
ここまで読んで頂きありがとうございました。
お題の「Ghost in the cell」は通期コンテスト化しているので、気になる方は参加可能です。
https://www.codingame.com/multiplayer/bot-programming/ghost-in-the-cell
また次回のcodingameゲームAIコンテストは4/15~開催です。
https://www.codingame.com/contests/coders-of-the-caribbean