仮想プレイ

ゲーム理論において、仮想プレイ（かそうプレイ、英: : FP）は、戦略の相互作用を繰り返す中でプレイヤーがいかに学習していくかを記述する学習規則である。仮想プレイにおいて、各プレイヤーは相手が定常な戦略（多くは混合戦略）を使用していると仮定し、相手の過去の行動の経験分布に対して最も有効な行動を取る。具体的には、各ラウンドにおいて、プレイヤーは前のラウンドまでに相手がプレイした各戦略の経験的頻度を計算し、それらの頻度に対する自身の最適応答を選択する。

このアプローチは、プレイヤーが繰り返される観察を通じて自身の戦略的環境について徐々に学習していくという、限定合理性の単純なモデルを提供する。仮想プレイは、ゼロサムゲーム、ポテンシャルゲーム、支配戦略を持つゲームなど、いくつかの重要なゲームのクラスにおいてナッシュ均衡に収束する。しかし、相手が非定常的な戦略や適応的な戦略を採用している場合、この手法には顕著な限界がある。例えば、相手が仮想プレイヤーの最近の動きを条件としてプレイしたり、最適応答パターンの予測可能な性質を意図的に利用したりする場合、仮想プレイのアプローチでは収束しないか、あるいは搾取される可能性がある。

この概念は、1951年に数学者のジョージ・W・ブラウンによって初めて導入された。

 歴史 
ブラウンは当初、ナッシュ均衡のプレイを説明するものとして仮想プレイを導入した。彼は、プレイヤーが自分の頭の中でゲームのプレイを「シミュレーション」し、そのシミュレーションに基づいて将来のプレイを更新すると想定した。そのため、「仮想（fictitious）」プレイという名前が付けられた。現在の用法からすれば、ゲームの各プレイは実際に現実に行われるため、この名称はやや不適切である。プレイは正確にはフィクションのものではない。

FPは戦略型ゲームに限定されたものであったが、大規模なゲームに展開型ゲームを戦略型ゲームに置き換えて分析しようとすると、組み合わせ爆発を起こすという問題があった。これを解決するために、2015年にUCLのヨハネス・ハインリヒ、DeepMindのマーク・ランクトット、デイビッド・シルバーは全幅展開型仮想プレイ（full-width eXtensive-form Fictitious Play: XFP）を導入した。XFPの特徴は、ある戦略に従った際の情報集合への到達確率を重みづけとみなして、戦略を更新していくことである。

XFPは更新毎に全ての情報集合を捜査する必要があり、大規模なゲームへの適用が困難であった。これに対し、同論文でハインリヒらは仮想自己対戦（Fictitious Self-Play: FSP）を提案している。FSPは、XFPを機械学習化したものであり、相手の戦略に対する最適応答の学習に強化学習を、自身の平均戦略の計算に教師あり学習を利用している。

ハインリヒとシルバーは2016年に共著でFSPを深層学習化したニューラル仮想自己対戦（Neural Fictitious Self-Play: NFSP） を提案している。NFSPでは、強化学習用のネットワークと教師あり学習用のネットワークを独立に用意し、この二つのニューラルネットワークの学習を行っている。強化学習用ネットワークはDQNライクな手法で最適応答を取るよう学習され、教師あり学習用ネットワークは自身の過去の最適応答を模倣するように学習される。生成される混合戦略は、ハイパーパラメータのηによって制御され、直感的にはηの確率で最適応答を選択し、1-ηの確率でこれまでの自身の最適応答の平均戦略を選択する。これには、決定的な行動を取ることによる相手からの搾取や、学習時の自己対戦における対戦相手としての戦略の不安定化を防ぐ目的がある。

 収束特性 
仮想プレイにおいて、厳密なナッシュ均衡は吸収状である。すなわち、ある時点で全プレイヤーがナッシュ均衡でプレイした場合、それ以降のすべてのラウンドでも同じナッシュ均衡でプレイすることになる（Fudenberg and Levine 1998, Proposition 2.1）。加えて、仮想プレイがいかなる分布に収束したとしても、それらの確率はもとのゲームのナッシュ均衡に対応する（Proposition 2.2）。

一般化じゃんけん A B C a (0, 0) (2, 1) (1, 2) b (1, 2) (0, 0) (2, 1) c (2, 1) (1, 2) (0, 0)
したがって、興味深い問いは、どのような状況下で仮想プレイが収束するかということである。2人ゲームの場合、以下の条件で収束する。
 両プレイヤーが有限の戦略のみを持ち、ゲームがゼロサムである場合（Robinson 1951）
 厳密に支配される戦略の逐次消去によってゲームが解ける場合（Nachbar 1990）
 ゲームがポテンシャルゲームである場合（Monderer and Shapley 1996-a, 1996-b）
 ゲームが一般的な利得を持ち、2 × N ゲームである場合（Berger 2005）

しかし、仮想プレイは常に収束するとは限らない。シャープレイ（1964）は、右図のゲーム（じゃんけんの非ゼロ和バージョン）において、プレイヤーが (a, B) を選択することから始めると、プレイが、無限に循環することを証明した。

 用語 
ベルガー（2007）は、「現代のゲーム理論家が『仮想プレイ』として記述しているものは、ジョージ・W・ブラウンが1951年の論文で定義した学習プロセスではない」と述べている。ブラウンの「オリジナル版は微妙な詳細において異なっており……」、現代の用法ではプレイヤーが「同時に」信念を更新するのに対し、ブラウンはプレイヤーが「交互に」更新するものとして記述した。その後ベルガーは、ブラウンのオリジナルの形式を用いて、2人非退化順序ポテンシャルゲームの場合の収束に関する単純で直感的な証明を提示している。

「仮想的（fictitious）」という用語は、それ以前にゲーム理論で別の意味を与えられていた。フォン・ノイマンとモルゲンシュテルン [1944] は、戦略を一つしか持たないプレイヤーを「仮想プレイヤー（fictitious player）」と定義し、n 人ゲームを (n + 1) 人ゼロ和ゲームに変換するために追加した。

 参考文献 

Berger, U. (2005) "Fictitious Play in 2xN Games", Journal of Economic Theory 120, 139–154.
Berger, U. (2007) "Brown's original fictitious play", Journal of Economic Theory 135:572–578
Brown, G.W. (1951) "Iterative Solutions of Games by Fictitious Play" In Activity Analysis of Production and Allocation, T. C. Koopmans (Ed.),  New York: Wiley.
 Fudenberg, D. and D.K. Levine (1998) The Theory of Learning in Games Cambridge: MIT Press.
 Monderer, D., and Shapley, L.S. (1996-a) "Potential Games", Games and Economic Behavior 14, 124-143.
 Monderer, D., and Shapley, L.S. (1996-b) "Fictitious Play Property for Games with Identical Interests ", Journal of Economic Theory 68, 258–265.
 Nachbar, J. (1990) "Evolutionary Selection Dynamics in Games: Convergence and Limit Properties", International Journal of Game Theory 19, 59–89.
 von Neumann and Morgenstern (1944), Theory of Games and Economic Behavior, Princeton and Woodstock: Princeton University Press. 
 Robinson, J. (1951) "An Iterative Method of Solving a Game", Annals of Mathematics 54, 296–301.
 Shapley L. (1964) "Some Topics in Two-Person Games" In Advances in Game Theory M. Dresher, L.S. Shapley, and A.W. Tucker (Eds.), Princeton: Princeton University Press.

 外部リンク 
Game-Theoretic Solution to Poker Using Fictitious Play

Category:ゲーム理論