汎用ゲームプレイ

汎用ゲームプレイ（はんようゲームプレイ、General game playing、GGP）は、複数のゲームを上手くプレイできる人工知能プログラムの設計である^[1][2][3]。チェスのような多くのゲームでは、コンピュータは専用に設計されたアルゴリズムを用いてゲームをプレイするようにプログラムされており、そのアルゴリズムを他の文脈に転移することはできない。例えば、チェスをプレイするコンピュータプログラムはチェッカーをプレイすることはできない。汎用ゲームプレイは、汎用人工知能への道における必要なマイルストーンであると考えられている^[4]。

汎用ビデオゲームプレイ（General video game playing、GVGP）は、汎用ゲームプレイの概念をコンピュータゲームをプレイする目的に適応させたものである。ビデオゲームの場合、ゲームルールはTDギャモンのようなエージェントによって複数回の反復を通じて学習されるか^[5]、あるいは従来の汎用ゲームプレイのようにドメイン固有言語で手動で事前定義され、エージェントに事前に送信される^[6][7]。2013年以降、深層強化学習のアプローチに続いて大きな進歩が見られ、Atari 2600のゲームを学習できるプログラム^{[8][5][9][10][11]}や、Nintendo Entertainment Systemのゲームを学習できるプログラム^[12][13][14]の開発などが含まれる。

汎用ゲームプレイ技術の最初の商用利用は、1998年のZillions of Gamesであった。汎用ゲームプレイは、2003年以降、サプライチェーン・マネジメントにおける取引エージェント向けにも提案されており、そこではオンラインオークションでの価格交渉が行われる^{[15][16][17][18]}。

歴史

1992年、バーニー・ペルはメタゲームプレイの概念を定義し、「MetaGame」システムを開発した。これはチェスライクゲームのルールを自動的に生成する最初のプログラムであり、ゲームの自動生成を使用した最も初期のプログラムの1つであった。ペルはその後、システム「Metagamer」を開発した^[19]。このシステムは、ゲーム記述言語（GDL）と呼ばれる特殊な言語でゲームルールの定義が与えられると、ゲームが生成された後は人間の介入なしに、数多くのチェスライクゲームをプレイすることができた^[20]。

1998年、商用システムZillions of GamesがJeff MallettとMark Leflerによって開発された。このシステムは、ゲームルールを定義するためにLISPライクな言語を使用した。Zillions of Gamesは、駒の可動性、盤面の構造、ゲームの目標に基づいて、ゲームルールから評価関数を自動的に導出した。また、コンピュータチェスシステムに見られる通常のアルゴリズム、すなわち、指し手順序付けを伴うアルファ・ベータ法やトランスポジションテーブルなども採用していた^[21]。このパッケージは2007年に、完全なForthベースのプログラミング言語を組み込んだ代替のメタゲームエンジンであるAxiomプラグインの追加によって拡張された。

1998年、z-Treeがウルス・フィッシュバッハーによって開発された^[22]。z-Treeは、実験経済学のソフトウェアツールとして最初のものであり、最も引用されている。z-Treeは、人間を被験者とするゲーム理論実験のために、z-Tree言語でゲームルールを定義することができる。また、人間の被験者とのプレイに参加するコンピュータプレイヤーを定義することもできる^[23]。

2005年、スタンフォードプロジェクト「General Game Playing」が設立された^[3]。

2012年、PyVGDLの開発が始まった^[24]。

汎用ゲームプレイの実装

スタンフォードプロジェクト

「General Game Playing」は、カリフォルニア州のスタンフォード大学のスタンフォード論理学グループによるプロジェクトであり、汎用ゲームプレイのためのプラットフォームを作成することを目的としている。これはGGP AIの標準化における最もよく知られた取り組みであり、一般的にGGPシステムの標準と見なされている。ゲームは、ゲーム記述言語で表現された一連のルールによって定義される。ゲームをプレイするために、プレイヤーはゲームホスティングサーバー^[25][26]と対話し、このサーバーが指し手の合法性を監視し、プレイヤーに状態の変化を通知する。

2005年以来、アメリカ人工知能学会（AAAI）カンファレンスで毎年、汎用ゲームプレイコンペティションが開催されている。このコンペティションでは、出場するAIの様々なゲームをプレイする能力を、個々のゲームでのパフォーマンスを記録することによって評価する。コンペティションの第1段階では、出場者は合法手を実行し、優位に立ち、より速くゲームを完了する能力について評価される。続く決勝ラウンドでは、AIは次第に複雑になるゲームで互いに対戦する。この段階で最も多くのゲームに勝利したAIがコンペティションの優勝者となり、2013年まではその製作者に10,000ドルの賞金が授与された^[19]。これまでの優勝プログラムは以下の通りである^[27]。

年	名前	開発者	所属機関	出典
2005	Cluneplayer	Jim Clune	UCLA
2006	Fluxplayer	Stephan Schiffel and Michael Thielscher	ドレスデン工科大学	[28]
2007	Cadiaplayer	Yngvi Björnsson and Hilmar Finnsson	レイキャヴィーク大学	[29]
2008	Cadiaplayer	Yngvi Björnsson, Hilmar Finnsson and Gylfi Þór Guðmundsson	レイキャヴィーク大学
2009	Ary	Jean Méhat	パリ第8大学
2010	Ary	Jean Méhat	パリ第8大学
2011	TurboTurtle	Sam Schreiber
2012	Cadiaplayer	Hilmar Finnsson and Yngvi Björnsson	レイキャヴィーク大学
2013	TurboTurtle	Sam Schreiber
2014	Sancho	Steve Draper and Andrew Rose		[30]
2015	Galvanise	Richard Emslie
2016	WoodStock	Eric Piette	アルトワ大学

その他のアプローチ

独自の言語を用いてゲームルールを定義する他の汎用ゲームプレイソフトウェアには、以下のようなものがある。

システム	年	説明
FRAMASI	2009	Rustam Tagiewによって汎用ゲームプレイと経済実験のために開発された[31][32]。
AiAi	2015-2017	Stephen Tavener（元Zillions開発者）によって開発された[33][34][35]。
PolyGamo Player	2017	David M. Bennettによって2017年9月にUnityゲームエンジンをベースにリリースされた[36]。
Regular Boardgames	2019	Jakub Kowalski、Marek Szykuła、およびヴロツワフ大学の彼らのチームによって開発された[37][38]。
Ludii	2020	Cameron Browneとマーストリヒト大学の彼のチームによって、ERC資金提供のDigital Ludeme Projectの一環としてリリースされた[39][40][41]。

GVGPの実装

強化学習

GVGPは、実際のビデオゲームAIを自動的に作成したり、「手続き型コンテンツ生成を用いて自動的に作成されたものを含むゲーム環境をテストし、人間のプレイヤーが悪用しうるゲームプレイの潜在的な抜け穴を見つける」ために使用される可能性がある^[7]。GVGPはまた、ゲームルールの生成や、良いAIと悪いAIの間でゲームが許容するスキルの差別化を比較する相対的アルゴリズムパフォーマンスプロファイル（RAPP）に基づいてゲームの品質を評価するためにも使用されている^[42]。

ビデオゲーム記述言語

汎用ビデオゲームAIコンペティション（General Video Game AI Competition、GVGAI）は2014年から開催されている。このコンペティションでは、GGPコンペティションで使用されるボードゲームの代わりに、1980年代のアーケードゲームやコンソールゲームに似た（時にはそれらに基づく）2次元ビデオゲームが使用される。これは、研究者や実践者が最高の汎用ビデオゲームプレイアルゴリズムをテストし、比較する方法を提供してきた。このコンペティションには、ビデオゲーム記述言語（VGDL）で書かれた多数のゲームを含む関連ソフトウェアフレームワークがある。VGDLをGDLと混同してはならない。VGDLは簡単に解析できる単純なセマンティクスとコマンドを使用するコーディング言語である。VGDLの一例として、2013年に開発されたPyVGDLがある^[6][24]。GVGPで使用されるゲームは、今のところ、最も単純で定量化しやすいため、しばしば2次元アーケードゲームである^[43]。ビデオゲームを解釈できるAIを作成するプロセスを簡略化するため、この目的のためのゲームは手動でVGDLで記述される^[要説明]。VGDLは、解集合プログラミング（ASP）と進化型アルゴリズム（EA）を使用して、レベルのプロシージャル生成のためにゲームを記述するために使用できる。その後、GVGPを使用して、プロシージャルレベルの妥当性や、エージェントのパフォーマンスに基づいてレベルの難易度や品質をテストすることができる^[44]。

アルゴリズム

GGP AIは複数のゲームをプレイするように設計されなければならないため、その設計は特定のゲームのために特別に作られたアルゴリズムに依存することはできない。代わりに、AIは、その手法が広範囲のゲームに適用できるアルゴリズムを使用して設計されなければならない。Regular Boardgames（RBG）やLudiiなどの最近のGGPシステムは、推論効率を最適化し、より多様なゲームをサポートするために、代替のルール表現を探求している。AIはまた、過去の状態の出力ではなく、現在の状態に適応できる継続的なプロセスでなければならない。このため、オープンループ技術がしばしば最も効果的である^[45]。

GGP AIを開発するための一般的な手法は、モンテカルロ木探索（MCTS）アルゴリズムである^[46]。UCT法（Upper Confidence Bound applied to Trees）と組み合わせて使用されることが多く、特定のゲームをよりうまくプレイするため、またビデオゲームプレイとの互換性を持たせるために、MCTSの変種が提案されている^[47][48][49]。使用される木探索アルゴリズムの別の変種として、有向幅優先探索（DBS）がある^[50]。この手法では、利用可能な各アクションに対して現在の状態の子ノードが作成され、最も高い平均報酬の順に各子を訪問し、ゲームが終了するか時間がなくなるまで続けられる^[51]。各木探索手法において、AIは潜在的なアクションをシミュレートし、獲得ポイントの観点から各パスの平均最高報酬に基づいてそれぞれをランク付けする^[46][51]。

前提条件

ゲームと対話するために、アルゴリズムはすべてのゲームが共通の特性を共有しているという前提の下で動作しなければならない。書籍『Half-Real: Video Games Between Real Worlds and Fictional Worlds』の中で、Jesper Juulはゲームを次のように定義している：

• ゲームはルールに基づいており、可変的な結果を持ち、異なる結果は異なる価値を与え、プレイヤーの努力が結果に影響を与え、プレイヤーは結果に愛着を持ち、ゲームは交渉可能な結果を持つ^[52]。

これらの前提を用いて、プレイヤーの入力を定量化し、ゲームの結果と様々なルールがどのように適用されるかを定量化し、アルゴリズムを使用して最も有利な経路を計算することによって、ゲームプレイAIを作成することができる^[43]。