Ken's Cup 2019 参戦記

公開日:2019-06-12
最終更新:2019-06-12

Ken's Cupとは?

  • 名古屋大学のとある研究室で14年間毎年開催されているゲームAI系コンテスト
  • 研究室に配属されたばかりの学部生のプログラミング修練が第一の目的、研究室間交流が第二の目的(のはず)
  • 当日発表したスライドはこちら https://www.slideshare.net/taiyohara/kenscup2019

ゲーム概要

種類 HP 攻撃力 スコア
戦艦 3 3 2.5
護衛艦 2 2 2
海賊船 1 2 1.5
潜水艦 1 1 1
  • 自分の船の情報は完全に把握できるが、敵の船の位置や種類はほとんどわからない
  • 1ターンにできることは、以下のいずれか
    • 1つの船を隣接8マスのいずれかに移動
      • そこに敵の船があった場合、衝突とみなす
      • 衝突したときは、両方の船のHPから衝突相手の攻撃力分を減らす
    • 1つの船で隣接8マスのいずれかに攻撃
      • 攻撃に成功したら、相手のHPから攻撃した船の攻撃力分を減らす
    • パス
  • HPが0以下になった船は、撃沈として盤面から除去する
  • ターンの始まりに以下の情報を知ることができる
    • 自分の船それぞれの位置と残り体力
    • 自分の船それぞれの周囲8マスにどれだけ敵の船がいるか
      • その種類やHPなどは知らされない
      • 敵船について情報を得る唯一の手段
  • 勝利条件は以下の通り
    • 相手の船をすべて撃沈したら勝利
    • 200ターン経過したときに撃沈していない船のスコアの合計が大きい方が勝利
    • 200ターン経過してスコアの合計が等しい場合は、より各船が中央(3,3)に近い(マンハッタン距離の和が小さい)方が勝利
    • それも等しい場合は引き分け
  • 1手にかけられる思考時間は250msec、言語はC#限定

結果

  • 7プレイヤーが総当たりして1位タイ。直接対決の結果から優勝。

戦略

陣形

  • 中央に船を集める。具体的には、上の方に自分の船がいるとすると
y\x 0 1 2 3 4 5 6
0 . . . . . . .
1 . . . . . .
2 . . . .
3 . . . . . . .
4 . . . . . . .
5 . . . . . . .
6 . . . . . . .
  • まずはこの陣形を作れるように移動する

攻撃

  • 陣形を組んだ後は、攻撃を考える
  • まず各船の隣接8マスの情報を使って、フィールドの全マスに重みを与える
  • 敵が確実にいない場所は重み=0
    • 自分の船がある場所
    • ある味方の船で、敵の船が周囲に1つもいないと判定されたときの8方向
  • 敵がいるかもしれない場所については
    • 中央(3,3)とのマンハッタン距離をhとして 7 - h の値を加算
    • 複数の船から重複して報告されたマスはそのまま重複して加算する
    • 例えば、船A 船B が周囲に1つ敵船があると報告され、船Cが周囲に敵船がいないと報告された場合は、以下の通りの重みになる
y\x 0 1 2 3 4 5 6
0 . . . . . . .
1 . 3 8 0 0 0 .
2 . 4 A B C 0 .
3 . 5 12 0 0 0 .
4 . . . . . . .
5 . . . . . . .
6 . . . . . . .
  • 最後に攻撃力の高い船から順に調べていって、敵のいる可能性のあるマス(重み>0)に対し、重みでルーレット選択して確率的な攻撃を行う

まとめ・感想

  • 海戦ゲーム勝ちました
  • ひさしぶりにゴリゴリのルールベースAIで戦って勝てた
  • 他の参加者も、それぞれの陣形を組んで陣形に近づいたものを攻撃する「待ち」タイプのAIを組んだ人が多かった
    • 四隅に引きこもる「穴熊型」
    • 自陣の最奥で1マスごとに飛び飛びで配置する「一間トビ型」
    • 最後の200ターン目付近になってきたら中央に進出する動きも多かった

実は

  • ルールを勘違いしていて、前日まで相手の情報も完全に見えるものだと思ってました
  • そのルールのつもりで組んだ機械学習の話も後日まとめます
記事が少しでもいいなと思ったらクラップを送ってみよう!
10
+1
論文紹介、知った技術、競技プログラミング参戦記書いていきます

よく一緒に読まれている記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる

技術ブログをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

技術ブログを開設する

Qrunchでアウトプットをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

Markdownで書ける

ログ機能でアウトプットを加速

デザインのカスタマイズが可能

技術ブログ開設

ここから先はアカウント(ブログ)開設が必要です

英数字4文字以上
.qrunch.io
英数字6文字以上
ログインする