【勉強ノート】不完全情報ゲームのアルゴリズム２

前回はじゃんけんを例にして後悔の最小化アルゴリズムを試した。
今回は、クーンポーカーを例にして反事実的後悔（Counterfactual Regret（CFR））最小化アルゴリズムを試す。
※Counterfactual Regretに訳語を当てている日本語の論文は見つからなかったので、Google翻訳のままの訳語を使用している。

反事実的後悔（Counterfactual Regret）最小化

前回のじゃんけんの例では、2人が同時に手を出して1回で勝負がつくため、すぐに後悔を計算することができた。

一方、展開型ゲームでは、2人が交互に手を出して、ゲームの終端に達した際にはじめて勝敗が分かる。
それぞれのノードでの後悔は、すぐには計算できず、なんらかの方法でゲーム木を展開して計算する必要がある。

反事実的後悔（Counterfactual Regret）最小化アルゴリズムは、後悔最小化アルゴリズムを確率を用いて展開型ゲームにも適用可能としたアルゴリズムである。

以下、数式での説明になるため、はじめに記号の定義を行って、利得、後悔、累積後悔、戦略、それぞれの数式とその意味について解説する（数式は一見意味が分からないが、じっくり眺めていると意味が見えてくるものである）。

その後、クーンポーカーのサンプルコードの実装を確認する。

記号の定義

A(I)：情報セットIの合法アクションのセット
t, T：タイムステップ。情報セットへの訪問ごとに加算。
履歴h：ゲームのルートから始まる一連のアクション（偶然の結果を含む）
$\pi^\sigma(h)$ ：戦略 $\sigma$ を用いたときのゲーム履歴hへの到達確率
$\pi_{-i}^\sigma(h)$ ：ゲーム状態に達するまでにプレイヤーi用いた行動の確率を1とした場合の、戦略 $\sigma$ を用いたときのゲーム履歴hへの到達確率。つまり、プレイヤーiを除いたプレイヤーの行動による履歴hへの到達確率
$\sigma_{I \to a}$ ：情報セットIでアクションaをとる確率が1であることを示す
Z：すべての端末ゲーム履歴のセット
$h \sqsubset z$ ： $z \in Z$ において、hが非終端ゲーム履歴であることを示す
$u_i(z)$ ：端末履歴zにおけるプレイヤーiの利得

反事実値(counterfactual value)

履歴hでの反事実値(counterfactual value)（※利得に相当するもの）を、以下の通り定義する。
$\displaystyle v_i(\sigma, h) = \sum_{z \in Z, h \sqsubset z} \pi_{-i}^\sigma (h) \pi^\sigma (h, z) u_i(z) \tag{1}$

終端の利得 $u_i(z)$ に、履歴hから終端zでまでの確率 $\pi^\sigma (h, z)$ を掛けることで期待値を計算し、それにi以外のプレイヤーの行動によってルートから履歴hに到達する確率 $\pi_{-i}^\sigma (h)$ で重み付けしている。

ノードに到達する確率が低い場合は、たとえ負けても後悔も小さくなるというのは、直感的にも理解できる。

反事実後悔

履歴hでアクションaを実行しなかったという反事実後悔を、以下の通り定義する。
$\displaystyle r(h, a) = v_i(\sigma_{I \to a}, h) - v_i(\sigma, h) \tag{2}$

前回の後悔最小化アルゴリズムの利得を反事実値に置き換えている。

情報セットIでアクションaを実行しなかったという反事実後悔

$\displaystyle r(I, a) = \sum_{h \in I} r(h, a) \tag{3}$

ここで、 $r_i^t(I,a)$ を、プレーヤーiに属する情報セットIで、プレイヤーが $\sigma^t$ を使用するときの、アクションaを実行しなかったときの後悔とする。

情報セットは、観察可能な状態が一致するすべての状態を含むため（観測不能な相手の手札は複数の状態をとりうる）、情報セットIに到達するすべての履歴hの反事実後悔の和になる。

累積反事実後悔

累積反事実後悔は次のように定義される。
$\displaystyle R_i^T(I,a) = \sum_{t=1}^T r_i^t(I,a) \tag{4}$

戦略

非負の反事実後悔Rを後悔最小化アルゴリズムに適用して、以下の通り、戦略を取得する。
$R_i^{T,+}(I,a) = max(R_i^T(I,a), 0)$ とし、

$\displaystyle \sigma_i^{T+1}(I,a) = \left\{ \begin{array}{ll} \frac{R_i^{T,+}(I,a)}{\sum_{a \in A(I)}R_i^{T,+}(I,a)} & \mbox{if }\sum_{a \in A(I)} R_i^{T,+}(I,a) > 0 \\ \frac{1}{|A(I)|} & \mbox{otherwise} \\ \end{array} \right. \tag{5}$

混合戦略が、正の累積反事実後悔の比率になることを示している。
すべてのアクションで累積反事実後悔0になる場合があるため、その場合は等確率となる。

前回の後悔最小化アルゴリズムと異なるのは式(1)のみであり、それ以外は考え方は同じである。

クーンポーカーの例

クーンポーカーを例にして、反事実的後悔最小化アルゴリズムを試す。

講義のページでJavaで実装したサンプルコードが、提供されているので、それの実装の確認を行う。
http://cs.gettysburg.edu/~tneller/modelai/2013/cfr/KuhnTrainer.java

クーンポーカーについて

クーンポーカーは、ポーカーを単純化した不完全情報ゲームである。
カードは3枚のみで、2人のプレイヤーにランダムに1枚ずつ配られる（残り1枚は未使用）。
先手はパスかベットを行う。
その後、後手がパスかベットを行う。
後手がベットの場合、先手はパスかベットを行う。
勝敗は以下の通り決まる。
f:id:TadaoYamaoka:20200921125718p:plain

サンプルコードの実装

サンプルコードは、前回のじゃんけんのサンプルコードと骨格は同じである。

主に異なるのは、カードをランダムで配る部分、ノードごとに後悔累積を計算する点、アクションごとの利得を計算する部分である。
カードをランダムで配る部分は、本質ではないので省略する。

式(3)の情報セットの反事実後悔は、反復を繰り返すことで、異なる履歴hで同一のノードに到達するとこで近似的に求めている。

アクションごとの利得（反事実値(counterfactual value)）を計算する部分は、上記で解説した式(1)に該当する。
これは、再帰的に処理することで実装できる。

引数p0、p1が、履歴hへの到達確率 $\pi_{-i}^\sigma (h)$ になっており、相手プレイヤーのアクションの選択確率のみ計算されている。
また、相手の利得を自分の利得とする場合に符合を反転させている点に注意が必要である。

    private double cfr(int[] cards, String history, double p0, double p1) {
        int plays = history.length();
        int player = plays % 2;
        int opponent = 1 - player;
        if (plays > 1) {
            boolean terminalPass = history.charAt(plays - 1) == 'p';
            boolean doubleBet = history.substring(plays - 2, plays).equals("bb");
            boolean isPlayerCardHigher = cards[player] > cards[opponent];
            if (terminalPass)
                if (history.equals("pp"))
                    return isPlayerCardHigher ? 1 : -1;
                else
                    return 1;
            else if (doubleBet)
                return isPlayerCardHigher ? 2 : -2;
        }               

        String infoSet = cards[player] + history;
        Node node = nodeMap.get(infoSet);
        if (node == null) {
            node = new Node();
            node.infoSet = infoSet;
            nodeMap.put(infoSet, node);
        }

        double[] strategy = node.getStrategy(player == 0 ? p0 : p1);
        double[] util = new double[NUM_ACTIONS];
        double nodeUtil = 0;
        for (int a = 0; a < NUM_ACTIONS; a++) {
            String nextHistory = history + (a == 0 ? "p" : "b");
            util[a] = player == 0 
                ? - cfr(cards, nextHistory, p0 * strategy[a], p1)
                : - cfr(cards, nextHistory, p0, p1 * strategy[a]);
            nodeUtil += strategy[a] * util[a];
        }

        for (int a = 0; a < NUM_ACTIONS; a++) {
            double regret = util[a] - nodeUtil;
            node.regretSum[a] += (player == 0 ? p1 : p0) * regret;
        }

        return nodeUtil;
    }

実行結果

実行すると以下のように表示される。

Average game value: -0.05496601204878785
   1: [0.849753597014784, 0.15024640298521594]
  1b: [0.9999985021329627, 1.4978670373388295E-6]
  1p: [0.6644684285945989, 0.33553157140540113]
   2: [0.9999775448613657, 2.245513863439736E-5]
  2b: [0.6616830625007863, 0.3383169374992136]
  2p: [0.9999834630233202, 1.6536976679856157E-5]
 2pb: [0.5159302151546348, 0.48406978484536534]
   3: [0.5475228231479871, 0.4524771768520129]
  3b: [1.4987829882135705E-6, 0.9999985012170118]
  3p: [1.4987829882135705E-6, 0.9999985012170118]
 3pb: [1.3706996079562322E-6, 0.9999986293003921]

各履歴での、各アクション（パスとベット）それぞれの利得（反事実値(counterfactual value)）が表示されている。
ルートでの平均利得は、-0.0549となっており、お互いナッシュ均衡でプレイした場合、先手が不利になることを示している。

Wikipediaの解説によると、理論値は-1/18（=0.0555）なので、近い値になっている。

まとめ

不完全情報ゲームの代表的なアルゴリズムであるCFRについて解説を行った。
CFRは⼆⼈零和不完全情報ゲームの場合にナッシュ均衡に収束すること証明されているが、この記事では証明については触れなかった（証明に興味のある方は論文を参照してほしい）。

TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。