概要
| 仮想プレイ | |
| 英名 | Fictitious Play |
| 別名 | FP |
仮想プレイとは、ナッシュ均衡を求めるゲーム理論のアルゴリズムの一種。これ自体が強化学習ではないが、後続の手法であるNFSPは強化学習手法を取り入れている。
基本的に自己対戦を前提としている。
相手がこれまでに取ってきた戦略の経験分布（平均戦略)を相手の戦略とみなし、それに対する最適応答を自分は返す、ということを繰り返すことでナッシュ均衡を求める。
最終的な出力（混合分布）はこれまでに出力してきた自分の最適応答の経験分布であって、最終ステップでの最適応答の純粋戦略ではない点に注意。
2つの更新方法
FPには、同時更新型（Simultaneous Fictitious Play:SFP）と交互更新型 (AFP: Alternating Fictitious Play）があり、歴史的には交互更新型のほうが先に提案された。
今日の教科書で紹介されるのは、SFPであることのほうが多い。
同時更新型では、お互いがtターン目の行動を選択し終わったあとに、両者とも相手のtまでの経験分布をみて最適応答を決定する。じゃんけんを連想すればよい。
一方で、交互更新型では、相手が行った戦略は即座に経験分布に反映される。戦略決定は常に相手の行動を受ける形で行われる。将棋を連想すればよい。
SFPとAFPは収束するゲームが異なっていることで知られている。
参考になる文献
- Iterative solution of games by fictitious play
- 1951年に発表された、最古の仮想プレイの論文。交互更新型が提案された。
- An Iterative Method of Solving a Game
- 1951年。2人プレイゼロサムゲームかつ両プレイヤーの戦略数が有限の場合にナッシュ均衡に収束することが示されている。
- Brown's Original Fictitious Play
