読者です 読者をやめる 読者になる 読者になる

JavaChallenge2012で考えるAI対戦型ゲームのデザイン

Competitive Programming Advent Calendar Div2012の22日目の記事になります。
遅刻しました、申し訳ありません。

最近、自分は2つのプログラミングコンテストProgramming Contest

に運営側として関わらせていただきました。
特にJavaChallenge2012はルールの作成を担当したので今回はAI対戦型コンテストのルール設定について思うことを書きたいと思います。
主にゲームの解説になるので、ルールを読んだ方、参加者以外にはピンとこないかもしれませんがご容赦ください。

JavaChallenge2012とは

ルール概要

詳しいルールはこちらのマニュアルより。

マニュアルによるとGalconっていうゲームとカタンの開拓者達を合わせた感じのゲームらしいです。

マップ詳細
  • HEXマップの頂点と辺部分を使用
  • プレイヤーは2人〜6人まで
  • マップ中にランダムに40個の拠点が置かれる
  • 所有者のいる拠点からは毎ターン資源とロボットが生まれる
  • 各資源は銀行と取引したり、ユーザー間で取引できる
  • 各拠点は初期ロボット数、産出される資源数、産出されるロボット数などが異なる
ルール
  • ロボットを他のプレイヤーのロボットと同じ地点に送ると、対になって消失し、多い方のプレイヤーのロボットが残る。
  • 拠点にある他プレイヤーのロボットより1個以上多くのロボットを送ることで拠点の所有者が交代する
  • 初期配置選択フェーズの後各プレイヤーが順に200ターンの行動を行う
初期配置選択フェーズ
  • 拠点を"プレイヤー1→プレイヤー2→…→プレイヤー6→プレイヤー6→…→プレイヤー1"の順で2つ選択
各ターンの行動

プレイヤー1から行動を開始する。以下の行動は自分のターンに好きなだけ行うことが出来る。

  • ロボットの起動
    • 自分の所有している拠点にいるロボットを別の拠点へと移動させることが出来る。
    • ロボットは1辺を1ターンに1ずつ移動する。
    • 攻め込むルートを指定することも出来るが、省略すると最短ルートを自動的に計算して侵攻する
  • ユーザー間交渉の値段の提示
    • 資源、個数、金額のペアで提示する。その条件は1ターンの間他プレイヤーが確認、取引を受けることができる。
  • 提示されている条件を受ける
    • 提示された資源の個数の一部のみに対して取引を行うことも可能
  • 銀行との売買
    • 資源をお金に換えることが出来る
  • 拠点のグレードアップ
    • 決まった資源を使用して、拠点をグレードアップすることが出来る。資源生産量を2倍,4倍、ロボット生産量が2倍,4倍にするグレードアップがある
勝利条件

200ターンを終えるか,拠点を所有しているプレイヤーが1人だけになった時に終了、以下の基準で順位が決まる(上が優先)

  • 生き延びたターン数
  • 終了時点での制圧数
  • 総ロボット数
  • 資源を売った額+所持金の合計

ルールの設計について

今回JavaChallenge2012のゲームを作るに際して、普通の対人戦ゲームと異なる点として、盤面を数値の形で評価しやすいようなルール設計にすることを考えました。
また一方で、AI対戦型ゲームの場合は人間がロジックを考えるリソース、コード量、実際の計算時間をゲームのどの部分に割くか自由に決めることに注目しました。

今回のゲームでは最初の行動が非常に重要なゲームとして設計しました。イメージとしては初期配置が半分、最初の50ターンの立ち回りが半分ぐらいといったところ。見た目にはどんどん制圧していきマップをトップのプレイヤーの色に染め上げるのは綺麗だけれども、逆転を誘発するルールはなく100ターン経過後のトップと200ターン経過後のトップはほとんど変化していません。

数値化について、、ロボットの所持数、総生産力、各資源の所持数、各資源の総生産力などをAPIから呼び出せ、またゲーム画面上でも確認出来るようになっています。

ルールをモデル化すると、ロボットの個数の差で拠点を制圧する力関係が決まるため、ロボットの個数を増やすことをゲームの目的とみることが出来ます。そして、ロボットの個数を増やすことは各拠点のロボット生産力を合計した、総ロボット生産力を高めることに繋がります。

ロボット生産力を高めるための行動としては、

  • 資源を使って拠点をアップグレードし、資源生産力を増加
  • 資源を使って拠点をアップグレードし、ロボット生産力を増加
  • ロボットを使って拠点を制圧、資源生産量、ロボット生産力を増加

こんな感じでモデル化することが出来ます。初期配置についても、初期のロボット数、ロボット生産力の高さ、資源の内容、資源生産量、また周りの拠点との距離や周りの拠点の生産力、をユーザーが独自で数値化すると、良さげな初期配置の評価が出来たのではないかと思います。

取引については上述の通り、最初の数ターンの行動が非常に大事なので、そこで最善手を選ぶと、銀行との交渉、ユーザー同士の交渉を持ちかける意味はあるように思います。けれども、少なくとも2チームのプレイヤーが取引を実装していないと無駄になることもあり、限られた時間の中で手をつけたチームはほとんどなかったため、今回はルールとしては死んでしまいました。

それ以外では、既に敵に所有されている拠点の場所を考慮したり、敵の侵攻ルートを考慮し消滅を避ける戦術、狙われにくくする戦術などの工夫が上位チームやゲストチームで見られました。

サンプルコードについて

限られた時間の中でAIを作成してもらうために、サンプルコードは

  • サンプルコードを読んだだけでAPIが理解出来る
  • 拠点を評価順にソートするコードなど強いAIを作るための部品を揃えておく
  • サンプル自体は弱く、改良しがいがあるものにする

を意図して書きました...が、思った以上に強くなってしまいました。

サンプルを改良したつもりでももとのサンプルを超えられなかったという悲鳴を聞いたり、サンプルコードと提出されたコードを戦わせるとサンプルコードが上位に入ってしまった...など。

弱くなるように色々なパラメータをいじったはずが依然として、強かったというのは、そもそもサンプルで用意した、「自分の所有しているすべての拠点に対して、ロボットが一定数以上あれば、そこから最も近い拠点を攻撃する」という行動が理にかなっていたためでした。

ルール設計側がサンプルを書くと気付かずについついゲームの本質を突いてしまうので、そこを弱くする修正は念入りに行った方が良さそうです。

告知

  • さっきから何度か貼りましたが、JavaChallenge2012のウェブサイトが完成しました。結果や、ゲームのダウンロードが可能です。