ゲームAIコンテストに興味はあるんだけどなー、って方向けの記事です。
（Competitive Programming （その2） Advent Calendar 2015 15日目の記事として書いたものです。）
はじめに
僕はCODE FESTIVAL2014でのAI ChallengeをきっかけにAI系のコンテストにハマり始めました。
で、周りの競プロerにも勧めるんですが、よく「ハードルが高そう」という声を耳にするわけですね。
今日はそんな幻想をぶち壊した上で、少しでも参加したい気にさせてみせます！
ゲームAIコンテストって？
ゲームAIコンテストはいわゆるマラソン系のプログラミングコンテストになります。
コンテストが始まるとお題となるゲームとそのルールが発表されるので、参加者はそのゲームで動作するAIを1週間～2ヶ月ぐらいの期間で作成し提出します。
予選等での順位付けの方法は、参加者のAI同士で対戦を重ねた後のレーティングであったり、各AIがそのゲームで獲得したスコアであったりと様々です。
オンサイトでの決勝戦では決勝進出者のAIが戦っている様子をみんなでやんややんや言いながら眺めます。楽しいです。
ゲームAIコンテストの魅力
皆さんはゲームはお好きですか？…………ですよね、わかります。僕も大好きです。
後輩とぷよぷよの腕を競ったり、迫り来る敵たちを追い払い自身のハイスコアに挑戦したり。旅行先の宿でみんなでUNOなんてのも良いですね。ゲームは人生に潤いを与えてくれます。
また、皆さんはプログラミングはお好きですね？
ゲームAIコンテストでは、そんな皆さんが大好きなプログラミングを駆使して、皆さんが大好きなゲームを遊ぶことができます！一石二鳥！
真面目に、他のプロコンには無い魅力についても述べておきましょう。
AIプログラムは他のコンテストで作成するプログラムと違って、動いている様子をリアルタイムで眺めることができます。
なので作ってるうちに愛着が湧いてきます。かわいいです。手をかけてあげればあげるほど、どんどん強くなっていくところも素敵です。
そして、リアルタイムに眺めることができるので、AI作成者から観戦する側の人たちに至るまで、個性豊かなAIが躍動する様を胸を躍らせながら見ることができるのです。
プログラミングができない人でも楽しめるプロコン、すごくないですか？
AI作成のハードルは本当に高い？
本題です。ゲームAIのハードルの高さについて。
まず、AI作成をプログラミング初心者にもオススメできるかというと、さすがにちょっと厳しいです。そういう意味ではAtCoderやSRM等のコンテストと比べるとハードルは高くなります。
ですが、SRM青色 AtCoder 茶色コーダー以上の人たちの言う「ハードルが高そう」は、絶対に何か勘違いをしていると言い切れます。何故か。
それは、簡単な"深さ優先探索"と簡単な"幅優先探索"、この2つが書けるなら、最低限～それなりの動きをするAIを組めてしまうことが多いからです。（ゲームによってはダイクストラ法も書けなきゃという意見もありますが、まぁその程度です。）
takaptさんの記事と若干被っちゃったけどマラソンマッチの一種だし仕方ないね。
…果たしてこれでもまだハードルが高そうと言えるでしょうか。
これだけだと上位は狙えないという意見はもっともですが、上位を狙うハードルが高いのは他のコンテストも同じです。
簡単な探索だけで戦える？ ～実践編～
ここで、簡単な探索だけでどこまで戦えるのか、実際にAIを作ってみて試してみます。
挑戦するお題はCodinGameというサイト内のTron Battleという複数人対戦ゲームです。
こちらは下記リンク先のGAMES→BOT PROGRAMMINGタグよりいつでも遊ぶことができます。
ルールの概要は以下のとおりです。
- 縦20マス*横30マスのフィールドで2～4人のプレイヤーが戦う。
- 各プレイヤーは交互に1マスずつ移動する。その場にとどまることはできない。
- 各プレイヤーが通ったセルは通行不可となる。
- フィールド外や通行不可のセルへ移動したプレイヤーは脱落し、そのプレイヤーが通った跡のセルは再び通行可能となる
- 最後まで脱落しなかった人の勝ち。
1.ひとまず動くAIを
まずは"とりあえず動く"AIを作ってみましょう。
基本的にAIは (1)ゲームの状況を入力から受け取る (2)行動を出力する を繰り返すことになります。
このゲームでは、各ターンそれぞれのプレイヤーの初期座標、現在座標が入力されるので、それらをもとに次に移動する方向を出力します。
以下はこの問題において与えられるサンプルコードです。（一部省略しています。）
このコードは、入力される情報は一切無視して左へ突き進むAIですが、このままではすぐに画面外に飛び出し脱落してしまいます。
というわけで、以下のように手を加えてみました。
フィールド外と通行不可のセルには移動しないようにしました。これで提出してみましょう。
CodinGameではAIを提出すると1000戦ほど試合を組んでくれて、5分程で今の自分の順位を算出してくれます。
このTron Battleでは提出者が2563人いるみたいですが、なんとこのAI、749位を取ることができました。
このあたりで「ん、ハードル…高くないかも…？」的なことを感じ始めてもらえてるのではないでしょうか。
2.敗けた試合を観察しよう
先ほどのコードを改良して徐々に強くしていこうと思うのですが、はてさてどこを改良すれば良いでしょうか。
そのヒントは敗けた試合の中にあります。ビリになってた試合を数試合見てみた結果、以下のような明らかによろしくない脱落が見受けられました。
これを防ぐために、隣接する4セルについてその先にいくつ移動可能なセルがあるか数え上げ、その数が一番大きいセルへ移動するようにしてみます。
この数え上げは幅優先探索でペロッとしてあげると簡単にできちゃいますね。競プロerなら朝飯前なことでしょう。
これで提出してみると430位。良い感じ良い感じ。着実に強くなってくれています。
この後、脱落したプレイヤーの移動跡を通行可能にする処理と、移動方向の優先順位を←↓→↑の順から少しだけ工夫することで何と170位まで登りつめることができました。*1
こんなAIでも上位10%に入れちゃったりするのです。もうハードルが高いなんて言わせない！
まとめ
- ゲームAIコンテストは楽しい。
- ゲームAIコンテストのハードルは高くない。
- AIを組む際はひとまず動くものを作ってみる。
開催中・今後開催予定のコンテスト等
最後に、現在開催中/開催予定のAIコンテストや、AIを作って遊べるウェブサイトを紹介しておきます。
【SamurAI Coding 2015-16】
予選：?/?～2/8(月) 決勝：3/11(金)
URL：http://samuraicoding.info/index-jp.html
情報処理学会主催のAIコンテストです。どなたでも参加することができます。
学生の場合は、予選に参加するだけで情報処理学会の全国大会を無料で聴講できたりします。
今年のお題はざっくり言うと「ターン制スプラトゥーン」。
11月応募受付開始だったけどまだ始まらない、大丈夫かな…。
【ハル研プロコン2015】
受付期間：12/10(木)～1/7(木)
URL：http://www.hallab.co.jp/progcon/2015/
スマブラ等でおなじみのHAL研究所主催の学生向けコンテストです。
上位に入賞できなくても、チャレンジスコアを満たせば抽選で記念品が貰えたりします。
今年のお題は荷物配送問題。
【CODE VS】
URL：https://codevs.jp/
チームラボ・リクルート主催のAIコンテストです。前回大会から社会人も決勝に進めるようになりました。
"見ているだけで楽しめる"という部分にすごく力を入れられていて、盛り上がり方が他のAIコンテストの比じゃないです。
今まで4回(+1回)開催されており、うち直近2回のゲームは実際に遊んでみることも可能です。
次回は来年3月頃の予定らしいです。
【CodinGame】
URL：https://www.codingame.com/
上記の例でも紹介した、プログラムを組んでいろいろ遊べるウェブサイトです。
3ヶ月に1度ぐらいのペースでコンテストも開催されています。
かなり豊富な種類の言語が使えるので、初めて使う言語の練習なんかにも最適な気がします。
他に良さ気なものがあれば教えて下さい。
おしまい
*1:追記：数え上げも少し弄ったのを忘れてました。敵の周囲4マスは通行不可なものとして評価するようにしたりしてます。
