PHPを使ったり4000円課金したりしてCEDEC AI CHALLENGE 準優勝に至るまでの軌跡

by @dekokun on 2014/09/08 00:07

Tagged as: PHP, contest.

概要

日本で最大のゲーム開発者向けカンファレンスであるところのCEDECにて、AIのプログラミングコンテストが開かれました。

その名もCEDEC AI CHELLENGE。

そこで、PHPを使って参戦したら見事準優勝したので何を行ったかを書きます

なお、この大会はオンラインで行われる予選と、実際にCEDECの会場で行われる本選の2段階で行われました。 上記「見事準優勝」等と言っておりますが、予選はともかく本選の方はほとんど運によって全てが支配されていたため、準優勝ってなんぼのもんなのかと言われると、「最低限瞬殺されないくらいの強さ」というくらいの話でしかないです。はい。

参加者は、去年は11人だったようですが今年は5倍以上の60人。来年はもっと増えるんですかね。来年も参加したいですね。

なお、タイトルに「PHP」と付けたのは、日々disられがちなPHP使いへのエールを込めてです(去年のISUCONブログでも同じ事を書いたよね ISUCON予選にPHP実装で参加して3位になりましたーやったことなどまとめ)

簡単なルール

  • 詳細はこちら Game Rules
  • 一回の対戦は4人で行われます。8人のバーチャルな女の子がいて、平日は5回、休日は2回、それぞれ誰かとデートをします
  • 平日に誰が誰とデートをしたかの情報は開示されるのですが、休日は、どの女の子がデートをしたかだけが開示され、誰とデートしかかは不明です
  • それらの情報を元により多くの女の子の好感度をあげよう！
  • 女の子には一人ひとりに情熱度が付与され公開されていて、情熱度が高い女の子の好感度を上げるほど勝利は近いぞ！
  • さて、他の人の情報が中途半端にわかっている状態で君は誰とデートする？！
  • みたいなざっくりとしたルールはそんな感じです
  • 使用言語は、C, C++, Java, C#, Scala, Ruby, Python, Perl, PHP, Haskell, JavaScriptです
    • 今回私はPHPを使いました。最近disられがちなPHPの復権を望んでそんなことをしましたが、動的言語が遅いのはわかりきった話ではあるので、次はScalaで戦います
    • 多分、今回本選に参加したメンバーの中でPHP使ってたの私だけだろうなぁ
    • 別のところでGoが使わせてもらえるのならGoで書く

戦略概要

  • ルールベースAIとモンテカルロなAIの組み合わせ
  • 最初は「ただのルールベースAIで行くぞ」と思ってルールベースの土台を作ったが、結局「基本ははモンテカルロ法ルール。前半と後半でちょっとパラメータを変化させるためにルールベースAIを使った」という感じだったため、ルールベースAIを導入した意味はほとんどなかった
  • どのようにモンテカルロ法を使ったか
    • 自分の取りうる全ての手に対して、その後自分と相手がランダムに全ての手を打ったと仮定した際に誰が勝つかを計算し、その中で自分の勝率が最も良かった手を打つ
    • 情報の不完全性を最大限利用して頭のいいAIに情報を与えないためにために、前半は休日の際は1ターンの中では2日とも同じ相手に点を入れるようにしてある
    • 上記を前半だけにしたのは、前半に混乱させれば後々それが効いてくるだろうというのと、後半はお互いの今後の可能性が減りより精緻なよみができるようになるのでその中でちゃんと最善の手を打たせたかったから

なぜモンテカルロ？

意思決定の流れを時系列順に

  • 「このAI,モンテカルロが向いているんちゃいますか？」という後輩の進言によってモンテカルロ法のAIについて調べる
  • 調べたところ「どのような手を打っても確実にゲームは終了する」というゲームの特徴がモンテカルロ法にぴったりだった
  • 唯一の懸念点は、PHPを選択していることで「Scala等のコンパイル型の言語を選んだ参加者と比べて計算量が圧倒的に少なく試行回数が稼げない」ところ
  • 以下『工夫したところ』『反省点』にあるように、今回の問題はモンテカルロ法を選択した際に収束を早める工夫が色々できそうだったのでまぁ、他の参加者を出し抜くことも可能だろう
  • モンテカルロに決定
  • 私はこの時まで、モンテカルロに対して「なんか確率的な手法なんでしょーよく知らんけど」みたいな感じだったため、後輩がいなかったら「AIにモンテカルロ法を使用する」という発想が出てくることは絶対になかったと思われる。後輩に感謝

AIで工夫したところ

  • 自分が取りうる手は状況によって変わらないためプログラム内に自分の打ち得る手を最初に列挙しておいたところ
    • こちら、実は手打ちでやっており、やばかった。700超通りの配列を延々手打ちで作成したのはものすごくプログラマとしてダメなことしてるなと思いながら延々手打ちをした
  • 過去のデート回数については、1ターン毎の各ヒロインのデート回数を、そのターンでの全デート回数で割った数を、自分以外の各プレイヤが取得した好感度として計算 <- この考えを入れることで明らかに勝率が上がった
  • 今回、「敵がランダムに行動する」という仮定をとった際、自分がとった手は全く相手の手に影響を与えないため（例えば囲碁の場合、自分が打った場所には敵は打てないが、今回はそのような制約はない）、ランダムな、全プレイヤーが取りうる手の中で、自分がとる手を入れ替えていくことで計算量を減らすという戦略をとった
  • このゲームでは、「敵がランダムに行動する」という仮定をとった際、「ある手を打つことが決まっているのであれば、それがどのタイミングだとしても最終結果は変わらない」ため、あるプレイヤーが今後取りうる手を計算する際に、「全45ポイントをどのヒロインに割り振るか」だけを計算することで、収束を早めることができた
    • これによって、一人のプレイヤーが取りうる手の組み合わせ結果が 8^45(ものすごくたくさん) から 52C8(752538150) まで減った(と思う。計算が間違っていなければ)
    • ただ、この方法での敵のポイント分布は実際にランダムに敵が行動した場合のポイント分布と異なるという欠点はあるが収束を早めるためにやってよかったと思っている

AIの中身以外で良かった点

  • Jenkinsを構築しGithubにコードがPUSHされたタイミングで、過去の自分と300回ほど対戦して極端に勝率が低くなっていないかを確認するCIを回していた
    • これを実現するためにはCPUぶんまわしの並列実行バリバリできるサーバが必要であり、AWSのc3.8xlargeというかなり最強に近いインスタンスを使用し、2日で4000円ほどが吹き飛んだ
    • 勝率のグラフ化、plotプラグインが便利だった
    • 提出直前は、「ある施策を打つ」「JenkinsのCIで極端に勝率が落ちる」「revertする」の繰り返しで、弱いAIを提出しちゃわなかったという点で圧倒的に役に立った
  • ライバルと一緒に参加したこと
    • まぁ、ライバルというか会社の後輩なんだけど、二人で励まし合ったり情報交換したりして頑張れた
    • なお、彼は予選の「最後に提出したAIが採用される」というルールを把握しておらずそんなに強くないAIで戦い死んだ
  • 予選終了後にライバルとの反省会
    • 予選が終わった後すぐにお互いがどのような戦略をとっていたのかをまじえつつ反省会を行った
    • その結果は決勝のAIにフィードバックされております
  • プロファイラでボトルネックを測定した
    • PHPには、最強のプロファイリングツールであるxhprofがありまして、こいつのお陰でボトルネックらくらく特定でしたね

行おうとしたけどしなかった施策達

邪悪なものから、普通に実現できなかったものまで

並列実行

  • そもそもPHPでは並列実行周り非常に弱いのだが、新しいプロセスを起動し自分自身を実行して標準出力でデータを受け渡すなどしてなんとかすれば並列実行できるしそちら頑張ってみようかなと思った
    • そもそもコア数が1だったら意味が無いので計測した。具体的には、 予選サーバの/proc/cpuinfoファイルの中身をAI実行ファイルから覗き見た
    • 結果、コア数が1だとわかったため並列実行は断念
    • 後で運営の方に確認したところ、DigitalOceanの一番安いインスタンスを使用していたとのことだった
    • 事前にインスタンス情報も与えられていなかったし計測するのは本当に大切なことだ！

外部のサーバに頑張らせる

  • 外部の超いいインスタンスを用意し、そのAPIを叩くことで高性能な外部のサーバに計算させることを考えた
    • が、PHPから外部のサーバを叩こうとしたらエラーだったため「さすがに運営が止めているか。そりゃそうだよな」とすぐに諦めた
    • 運営によると「外部への通信は制限していなかったはず」と言っていたので何か間違えたかも

事前に計算結果を持っておく

  • 今回PHPを使ったわけだが最大の弱点として「遅い」という問題があるため、それを事前計算で解決しようとした
  • 具体的には、試行回数を増やしたモンテカルロ法で、事前にあらゆる手に対しての最善手を計算してファイルに格納しておき、実際の戦いでは現状から答えを読み取るだけで済むようにする
  • ファイルアップロードの容量制限があるのは知っていたため、前半の手だけでも格納できないかなと考えていた
  • 実装時間がたりなさすぎてできなかった

複数AIの協調動作(邪悪)

  • 複数アカウントを作成し、序盤はそれぞれのAIがある法則にしたがって自分の手を打ち他のAIにメッセージを投げる
  • それぞれのAIが、序盤のメッセージを受け戦いの中に味方がいることを察すると、後はそれぞれが事前に決められたあるAIを勝たせるために協調動作する
    • 具体的には、勝たせるAIが狙っている女の子に対しては自分は一位の好感度を得ないようにし、他のAIが勝ちそうな女の子の好感度を上げて他のAIにポイントをとらせないみたいな
  • この方法は予選突破にしか使えず、そもそも実装がかなり複雑になるため予選突破するためなら普通に頑張ったほうが早いと思ってやめた。そもそも発想が邪悪すぎる

感想

  • アイデアをくれた後輩に感謝
  • モンテカルロ法、実行結果をみても正しく動いているかがよくわからないためデバッグが著しく困難
    • その反省を活かして決勝にJenkinsを導入したのはとてもよかった
  • PHPの「division by zero エラーでもプログラムが止まらない」という特性を知った
    • 予選では上記エラーが出まくるプログラムを提出していました。動いていたから気付かなかった。恐ろしいですね
  • 懇親会の中華、おいしかったです

最後に

  • 運営の方が、この対戦に使用される絵(スクリーンショット)を描いていただける絵師さんを募集しているそうです
  • コードはこちら https://github.com/dekokun/CEDECAI
  • このブログ、めちゃ長いな
comments powered by Disqus