反実仮想後悔

概要

反実仮想後悔 (CFR) は、ゲーム理論と人工知能の分野における重要な概念です。2008年にMartin Zinkevichらによって提案され、不完全情報ゲームにおける戦略最適化問題を解決するために使用されます。テキサスホールデムのようなゲームでは、CFRは後悔最小化アルゴリズムの核心的な構成要素であり、LibratusやPluribusなどの高度なAIを構築するために広く使用されています。

原理

反実仮想後悔は、特定の情報集合（プレイヤーが現在知っているすべての情報）において、実際に行った行動ではなく別の行動を選択した場合に得られたであろう利得の差を測定します。具体的には、各情報集合と各可能な行動について、その行動の「反実仮想後悔値」を計算します。つまり、他のすべての決定点では現在の戦略に従い、このノードでのみ行動を変更したと仮定した場合、後悔値は新しい行動の期待利得から現在の戦略の期待利得を引いたものに等しくなります。

各ラウンドのプレイ後、実際の結果に基づいて各情報集合の行動の後悔値を更新します。反復回数が増えるにつれて、後悔が蓄積され、戦略の調整に使用されます：後悔が低い（つまり後悔の少ない）行動にはより高い確率が割り当てられます。最終的に、すべての情報集合における平均後悔がゼロに近づくと、戦略はナッシュ均衡に収束します。

テキサスホールデムへの応用

CFRは、隠された情報、ランダム性、多ラウンドの意思決定を含むテキサスホールデムのようなゲームに特に適しています。完全なゲームツリーは大きすぎるため、実際の応用では抽象化手法（状態クラスタリングや行動抽象化など）を使用して複雑さを軽減します。数兆回の自己プレイシミュレーションを通じて、CFRはほぼ最適な戦略を生成でき、ヘッズアップノーリミットテキサスホールデムでトップの人間プレイヤーを打ち負かしています。

関連用語との関係

• 後悔最小化 (RM): CFRはRMをマルチプレイヤーの不完全情報シナリオに拡張したもので、同じ核心的な考え方を共有します。
• ナッシュ均衡: CFRの目的は混合戦略ナッシュ均衡を見つけることであり、どのプレイヤーも一方的に戦略を変更することで利益を得ることができません。
• 戦略反復: CFRは繰り返し反復を通じて戦略を更新し、従来の価値反復や方策勾配法とは異なります。