General Game Playingの世界大会（IGGPC2014）の参加記録

ゲームAI

2014年のInternational General Game Playing Competition（IGGPC）の参加記録です．IGGPCは2005年から毎年開催されているGeneral Game Playingの世界大会です．

General Game Playingとはなにか

ゆるい概要についてはゲームAI研究について何も知らなくてもわかるGeneral Game Playingの概要をご参照ください．競技としてのGGPは，以下のような動作ができる「強い」ゲームAIプログラムを作るというものです．

  1. ゲームマネージャーと呼ばれるサーバーから以下のものを受信する
    • Game Description Languageで書かれたゲームルールと，そのゲームでの自分の役割（e.g. 先攻or後攻）
    • ゲーム開始前の思考時間（start clock）
    • ゲーム開始後の1ターン毎の思考時間（play clock）
  2. start clockを使ってゲームを分析する
  3. ゲームが始まり，以下をゲームが終わるまで繰り返す
    1. ゲームマネージャーから他のプログラムがどの手を選んだかを受信する
    2. play clockを使って現在の局面に対する手を選び，ゲームマネージャーに送信する

どんなゲームをプレイするかは事前には知らされません．強いAIを作るためには，限られた時間の中でゲームルールを読んで（もちろん人間が読んではいけない）ゲームを分析したり，自己対戦の結果から評価関数を学習したりすることが必要となります．

GGPのためにこれまでに使用されてきたゲームは，8パズルのような1人ゲームからオセロやチェスのような2人ゲーム，Chinese Checkersのような多人数ゲーム等，多岐に渡ります．ゲームの例はGamemasterやTiltyard GGP Serverで見ることができます．

これまでの優勝プログラム

2005 ClunePlayer
2006 Fluxplayer
2007-2008 Cadiaplayer
2009-2010 Ary
2011 TurboTurtle
2012 Cadiaplayer
2013 TurboTurtle

この中ではCadiaplayerのみソースコードが公開されています．2007年のCadiaplayer以降，優勝プログラムは全てモンテカルロ木探索を使用しています．モンテカルロ木探索はランダムシミュレーションを使った探索アルゴリズムで，囲碁での成功が有名ですが，その正確な評価関数を必要としないという性質からGGPにおいても支配的なアルゴリズムとなっています．

自分のプログラム

Knowerという名前のプログラムで参加しました．start clockの間に自己対戦からの強化学習によって評価関数を学習し，それをモンテカルロ木探索の中で利用するというAIになっています．ソースコードの全体は今のところ公開していませんが，Yet Another Prologを用いたゲームルールの推論部分だけ公開しています（https://github.com/muupan/ggpe）．

予選

7/3-21の間に6回予選があり，そのうち好きなものに参加することができ，いずれか1つの予選で日程で基準点を上回れば本戦に進むことができるという形式でした．

予選参加のためにはまず自分のプログラムを公式サイトで登録する必要があり，それから参加したい日程を選ぶということになるのですが，自分が予選期間の途中で確認した時点では48のプログラムが登録されていました．登録だけして結局参加しなかったプログラムや，自分が確認した後で登録したプログラムもあるかもしれないので，正確な予選参加者はわかりませんが，例年の数よりずっと多いことは確かです（2013年はたった16プログラムでした）．この参加者の増加にはCourseraでGGPの講義が行われたことの影響が大きいと思われます．

予選では1人ゲームと2人ゲーム，合わせて10のゲームをプレイしました．2人ゲームは運営側が用意したベンチマークプレイヤ（アルゴリズム不明）との勝負でした．1人ゲームが多く，強化学習とランダムシミュレーションが武器であるKnowerにとって少し厳しい物でした．例えば8パズルに「完成したら100点，しなかったら0点」というスコアが与えられている場合，いくらランダムシミュレーションを繰り返しても偶然完成してしまわない限りスコアは0点にしかならず，強化学習もモンテカルロ木探索も歯が立ちません．こういうゲームでは，ゲームルールを読んで分析する（例えば，8パズルのピースのうち何個が正解の位置にあるかを数えて評価に使うようにする）ということが求められます．Knowerは1度予選に落ちた後，1人ゲーム向けの改良を加えた後に再度挑戦し，無事に予選を通過出来ました．

予選では，8パズルの他に，Multiple Tic Tac Toeという，三目並べの盤面が9個並んでいるけど1個以外はダミーで勝敗に影響しない，という明らかにAIをいじめたいだけのゲーム（これもゲームルールの分析が求められます）などもありました．Connect FourやAlquerqueといったより複雑な実在するゲームも使用されました．

最終的に，Knower含め17のプログラムが予選を通過しました．

本戦

本戦は7/29-30の2日間に分けて行われました．1日目はみんなで同じ1人ゲームをプレイしたり，2人ゲームを互いにプレイしたりして，合計18ゲームがプレイされました．プログラムは18ゲームの合計スコアによってランク付けされ，これにより2日目に進むことができるプログラムが決められました．1日目の結果ををブログにまとめてくれている人がいます（Sancho GGP Player: Finals Day 1 round-up）．BreakthroughやPentagoといったゲームの他に，数独などもプレイされました．

2日目に進めるのは12プログラムのみで，2日目は上位4プログラムを勝者サイド，その下の8プログラムを敗者サイドとするダブルエリミネーション方式のトーナメントでした．Knowerは11位でギリギリ2日目に進むことができました．特筆すべきは，勝者サイドになった1日目の上位4プログラム全てが，去年までのIGGPCに参加していない新参者だということです．Courseraの講義で知名度が増えた結果，これまでGGPを研究してきた人たちを押しのけて新たな勢力が台頭してきたようです．

2日目は全て2人ゼロサムゲームで，その結果はhttp://challonge.com/iggpc2014で見ることができます．Knowerは残念ながら1回戦で敗退してしまいました．優勝したのはSanchoという，1日目を圧倒的なスコアで1位通過したプログラムでした．

Carbon vs. Silicon

IGGPC2014を優勝したSanchoは「Carbon vs. Silicon」（人間 vs. コンピュータ）と題したマッチを戦いました．Carbonを代表するのはIGGPCを運営するスタンフォード大の学生達です．プレイされたゲームはJoint Connect Fourと呼ばれるGGP向けに人工的に作られたゲームで，Connect Fourの盤面が2つ並んでおり，一方は普通のConnect Four，もう一方は勝敗が逆になっているConnect Four（4つ並べてしまったら負け）になっていて，2人のプレイヤが交互に別々の盤面に石を置く同時着手ゲームになっています．結果はSanchoの圧勝で，ケイ素生物の強さを見せつけました．

Sanchoの勝因

Sanchoの特徴としては，参加者用のチャットで聞いた限りでは

  • ゲームルールの分析にかなり力を入れている
    • 例えばJoint Connect Fourを2つのゲームに分解して別々に探索を行うことができる
  • ゲームに応じてアルゴリズムを選択できる
    • 8パズルにはA*を使っていた
  • ゲームルールの推論（局面から合法手を列挙したり，局面と手から次の局面を求めたりする処理）が高度に最適化されている
    • 参加したプログラムの中でおそらく最も高速なシミュレーションが行える

のようなことが挙げられます．Sanchoのソースコードは公開されており（https://github.com/SteveDraper/ggp-base），また使われている戦術についてもブログ（http://sanchoggp.blogspot.jp/）に書かれています．

2014/10/03追記：SanchoのソースコードのURLが間違っていたので修正