CFR

概要

反実仮想後悔最小化（CFR）は、2人ゼロサムゲームにおけるナッシュ均衡を解くためのアルゴリズムです。HartとMas-Colellによって提案され、後にZinkevichらによってゲーム理論のポーカー研究に導入されました。CFRはAIポーカーにおける画期的な手法であり、LibratusやPluribusなどのトップポーカーAIの中核技術の1つです。

基本原理

CFRは、各決定ノードでの「反実仮想的後悔」、つまりプレイヤーが実際のアクションではなく代替アクションを選択した場合に得られたであろう追加のペイオフを反復的に計算します。アルゴリズムは蓄積された後悔値に基づいてその後の戦略を調整し、徐々にナッシュ均衡に収束します。具体的なプロセスは以下の通りです。

• ゲームツリーのすべての情報集合を走査する。
• 各アクションの反実仮想値を計算する（プレイヤーがその情報集合に現在の戦略で到達すると仮定）。
• 蓄積された後悔値を更新し、それに応じて新しい戦略を生成する（通常は後悔マッチングを使用）。

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

テキサスホールデムは代表的な不完全情報ゲームであり、状態空間が膨大です。CFRとその改良版（例：CFR+、Deep CFR）は、抽象化手法（状態クラスタリング、アクショングルーピングなど）を通じて計算複雑性を削減し、大規模並列計算でトレーニングします。例えば、Libratusは修正されたCFRアルゴリズムを使用して、ノーリミットテキサスホールデムでトップ人間プレイヤーを打ち負かしました。

特徴

• 理論的保証：ゼロサムゲームでは、CFRは平均戦略がナッシュ均衡に収束することを保証します。
• 事前知識不要：一様ランダム戦略から開始し、自動的に最適戦略を学習します。
• 高い計算コスト：ノーリミットテキサスホールデムでは完全なゲームツリーの走査は不可能であり、抽象化とサンプリングが必要です。

限界

CFRは主に2人ゼロサムゲームに適しています。マルチプレイヤーゲームでは理論的に収束は保証されませんが、修正（例：前方探索を加えたCounterfactual Regret Minimization）により実用的に良好な結果が得られます。