【CFR】不完全情報ゲームを学習するAIを実装してみる【KuhnPoker】

こんにちは、エンジニアの竹内です。
これまでの記事ではDQfD、PPOといった深層強化学習のアルゴリズムを紹介してきましたが、今回は少し趣向を変えて、ニューラルネットを使わずに不完全情報ゲームの戦略を求めるアルゴリズムを扱いたいと思います。

不完全情報ゲームのAI
KuhnPokerのルール
記号の定義と説明
- ナッシュ均衡
Counterfactual Regret Minimization
実装
- ゲームのルール部分
- CFRアルゴリズム
結果
まとめ
References

不完全情報ゲームのAI

不完全情報ゲームとは文字通り、プレイヤーが行動を決定する際に結果を左右する情報の一部が得られないようなゲームのことであり、ポーカーや麻雀、ガイスターなどが該当します。それに対して、ゲームに関する情報がすべて得られるものは完全情報ゲームと呼ばれ、将棋やチェス、囲碁やオセロなどが該当します。
トップレベルのAIの強さ、あるいは人間との対戦成績という観点では、戦略の解析がより簡単な完全情報ゲームの方がリードしている印象です。
一方で不完全情報ゲームの戦略を学習するAIについても発展が目覚ましく、StarCraftⅡでプロチームを破ったDeepMindのAlphaStarや、6人対戦のテキサスホールデムポーカーでプロのプレイヤーを上回る強さを発揮したFacebook AIのPluribusというAIなどが代表的です。

今回はそんな不完全情報ゲームを学習するアルゴリズムの中でも、特に重要なCounterfactual Regret Minimization(以下CFR)と呼ばれるものを解説、実装していきます。
CFRは先程紹介したポーカーAI、Pluribusの基礎となる部分に採用されている手法であり、簡単に説明すると「各行動を選択しなかった場合の後悔(regret)の値」を最小化していくように戦略を更新していく手法で、モンテカルロ法を用いてゲーム木の全探索を避けるMontecarlo CFRや、ニューラルネットと組み合わせたDeep CFRといった派生手法も数多く存在します。
そんなCFRを使って、今回はルールを簡略化したポーカーであるKuhnPokerと呼ばれるゲームの均衡戦略を求めていきたいと思います。
KuhnPokerはゲーム木のノード数が少なく均衡戦略の完全な解析が可能であるため、しばしばアルゴリズムの評価指標として用いられます。

KuhnPokerのルール

KuhnPokerは2人のプレイヤーで行われ、J, Q, K(今回は0, 1, 2とします)の3枚のカードのみを使用する非常に簡単なポーカーです。
まずはじめに、各プレイヤーが自分の手番で取ることのできる4種類の行動の意味を以下に説明しておきます。行動の役割は基本的に本格的なポーカーと同じとなっています。
bet → まだ誰も賭けていない状態で最初にお金を賭ける
check → まだ誰も賭けていない状態でパスを選択する
call → 相手と同額を賭ける
fold → ゲームを降りる

ゲームの進行

対戦する二人のプレイヤーをそれぞれ、プレイヤー0とプレイヤー1とします。
最初に、各プレイヤーに(0, 1, 2)の3枚からなる山札の中から1枚ずつが配られます。(お互いの手札が同じ数字になることはなく、相手の手札は非公開情報)
カードが配られた後、プレイヤー0はbetかcheckを選択します。
- プレイヤー0がbetした場合プレイヤー1はcallかfoldを選択し、ゲーム終了です。
- プレイヤー0がcheckした場合、プレイヤー1はcheckかbetを選択します。
  - プレイヤー1がcheckした場合、ゲーム終了です。
  - プレイヤー1がbetした場合、プレイヤー0はcallかfoldを選択し、ゲーム終了です。

f:id:morika-takeuchi:20200825122148p:plain — ゲームの進行のフローチャート(diagrams.netで作成)

利得の計算
ゲームの終了時、勝敗に応じてお互いに利得が与えられます。(ゼロ和ゲームのため、お互いの利得の和はゼロになります。)

相手のbetに対してfoldを選択した場合→数字の大きさに関わらず、betしたプレイヤーが+1、foldしたプレイヤーが-1の利得を得る
相手のbetに対してcallした場合→数字の大きいプレイヤーが+2、小さいプレイヤーが-2の利得を得る
相手のcheckに対してcheckを選択した場合→数字の大きいプレイヤーが+1、小さいプレイヤーが-1の利得を得る

KuhnPokerのゲーム木の一部を図にすると以下のようになります。(終端ノードの利得はプレイヤー0のものを表しています。)
以後、プレイヤー0に数字が0のカード、プレイヤー1に数字が1のカードが配られた状態を(0, 1)などと記述することにします。

f:id:morika-takeuchi:20200804144631p:plain — KuhnPokerのゲーム木(の一部)

記号の定義と説明

CFRの説明に入る前に、不完全情報ゲームをモデル化するために諸々の記号を定義していきます。定義だけだと少し分かりづらいと思うので、下に先程のKuhnPokerにおける例を書いておきます。

$N=\{1, 2, 3 \cdots, n\}$ : プレイヤー全体の集合

今回は実装の都合上、0, 1, 2, …をプレイヤーの集合とします。KuhnPokerの場合は $N=\{0, 1\}$ です。
また、ゲームの初めにカードを配布する場合など、ランダムにゲームを遷移させる際に「プレイヤー0でもプレイヤー1でもないプレイヤーが行動を選択した」とみなすために便宜的にチャンスプレイヤーと呼ばれるプレイヤーcを導入します。(ディーラーみたいなものです。)
実装においてはチャンスプレイヤーのインデックスは-1としてあります。

$H$ : 履歴(history)

ゲームで起こりうる、各プレイヤーが選択した行動の履歴全体の集合です。Hの要素をhで表します。履歴hは各プレイヤーの非公開情報も含めた、いわゆる神視点から見たゲームの進行状況となります。
例えばhの例として $[(0, 1), \rm{check}]$ や $[(1, 2), \rm{bet}, \rm{call}]$ 、 $[]$ (まだカードが配られていない)などが考えられます。

$Z \subseteq H$ : 終端履歴(terminal history)

$H$ の要素hのうち、ゲーム終了まで到達した履歴の集合です。
例えばZの要素として $[(2, 0), \rm{bet}, \rm{call}]$ 、 $[(0, 1), \rm{check}, \rm{check}]$ などが考えられます。

$A(h) = {a: (h, a) \in H}$ : 行動集合

終端履歴でない $h \in H$ で選択可能な行動の集合です。
例えばプレイヤー0がcheckをした後、プレイヤー1が取れる行動はcheckかbetですから、 $A([(1, 0), \rm{check}])=\{\rm{check}, \rm{bet}\}$ となります。

$I_i$ : 情報集合(information set)

不完全情報ゲームでは、プレイヤーiが行動を選択する際に「自分の手番までにゲームがどのような遷移をしてきたか」完全に把握することはできません。例えばP0がcheckで回してきたとしても、P1は今自分が居る履歴が[(0, 1), check]なのか[(2, 1), check]なのか(プレイヤー0に配られたカードが0なのか2なのか)区別することができません。情報集合はそういった区別できない幾つかの履歴をひとまとめにした集合であり、不完全情報ゲームを定義する上で肝となる概念です。全ての履歴はそれぞれのプレイヤーのいずれかの情報集合1つに属します。ポーカーでは相手に配られたカードはわからないので、相手が持ちうるハンドの種類数だけ情報集合の要素が存在します。
例えば
$I^0_0 = \{[(0, 1)], [(0, 2)]\}$ 、 $I^1_0 = \{[(0, 1), \rm{check}, \rm{bet}], [(0, 2), \rm{check}, \rm{bet}]\}$ 、 $I^0_1 = \{[(0, 2), \rm{check}], [(1, 2), \rm{check}]\}$
などが考えられます。(Iの右上の添字は異なる情報集合を区別するために便宜的につけてあり、数字に特に意味はないです。)
同じ情報集合に属する履歴において、プレイヤーが取れる行動の選択肢は以下のように必ず同じになります。

$A(I_i) = A(h) = A(h') ~ \rm{where} ~ h, h' \in I_i$

$\sigma_i(I_i)$ : 戦略

プレイヤーiが情報集合 $I_i$ でとる戦略です。戦略はその情報集合で選択可能な行動上の確率分布となります。
情報集合 $I_i$ に属する各履歴における戦略は全て $\sigma_i(I_i)$ に等しくなります。(プレイヤーはどの履歴にいるか区別出来ないので、履歴に合わせて行動を変えることは出来ません。)

$\sigma_i(h)=\sigma_i(h')= \sigma_i(I_i) ~ \rm{where} ~ h, h' \in I_i$

全てのプレイヤーの戦略の集合を戦略プロファイル $\sigma$ とします。
$\sigma_i(I, a)$ を、戦略 $\sigma_i(I)$ において行動 $a$ を選択する確率とします。

$\pi^\sigma(h)$ : 到達確率

全てのプレイヤーが戦略プロファイル $\sigma$ にしたがって行動したときに、履歴 $h$ に到達する確率です。 $h$ への到達確率は、 $h$ へ到達するような各プレイヤー(チャンスプレイヤー含む)の行動選択確率の積で計算されます。

$\pi^\sigma(h) = \prod_{i \in N \cup \{c\}}\pi^\sigma_i(h)$

また、情報集合 $I$ への到達確率は $I$ に属する全ての履歴 $h$ への到達確率の和として計算します。

$\pi^\sigma(I)=\sum_{h \in I}\pi^\sigma(h)$

ここで、 $\pi_i^\sigma(h)$ を $\pi^\sigma(h)$ のうちプレイヤーiの行動選択確率のみを取り出した積、 $\pi_{-i}^\sigma(h)$ をプレイヤーi以外(チャンスプレイヤー含む)の行動選択確率のみを取り出した積とします。

KuhnPokerで考えると、全てのプレイヤーが等確率で行動を選択するような戦略プロファイル $\sigma$ について、履歴 $h=[(2, 1), \rm{check}, \rm{bet} ]$ への到達確率 $\pi^\sigma(h)$ は

$\begin{eqnarray}\pi^\sigma(h) &=& P(2と1が配られる)\times P(P0が\rm{check})\times P(P1が\rm{bet}) \\ &=&\frac{1}{6} \times \frac{1}{2} \times \frac{1}{2} \\ &=& \frac{1}{24}\end{eqnarray}$

となります。

また、情報集合 $I_0 = \{[(2, 1), \rm{check}, \rm{bet}], [(2, 0), \rm{check}, \rm{bet}]\}$ への到達確率 $\pi^\sigma(I_0)$ は同様な計算により $\frac{1}{24} + \frac{1}{24} = \frac{1}{12}$ となります。

$u_i^\sigma(h)$ : 期待利得

全てのプレイヤーが戦略プロファイル $\sigma$ にしたがって行動したときに、プレイヤー $i$ が履歴 $h$ 以降得られる利得の期待値です。 $h$ が終端履歴の場合は、そこで得られる利得と一致します。また、 $u_i(\sigma)$ をゲーム開始時における期待利得、つまりゲーム全体を通して得られる期待利得とします。
例えば、全てのプレイヤーが等確率で行動を選択するような戦略プロファイル $\sigma$ と履歴 $h=[(2, 1), \rm{check}, \rm{bet} ]$ について、

$\begin{eqnarray} u_i^\sigma(h) &=& (-1) \times P(P0が\rm{fold}) + 2 \times P(P0が\rm{call}) \\ &=& (-1) \times \frac{1}{2} + 2 \times \frac{1}{2} \\ &=& \frac{1}{2}\end{eqnarray}$

と計算できます。

ナッシュ均衡

二人ゼロ和不完全情報ゲームにおいては、以下の条件を満たす戦略プロファイル $\sigma$ を求めることが目的となります。

$u_1(\sigma) \ge \underset{\sigma'_1 \in \sum_1}{\max}u_1(\sigma'_1, \sigma_2)$

$u_2(\sigma) \ge \underset{\sigma'_2 \in \sum_2}{\max}u_2(\sigma_1, \sigma'_2)$

つまり、どのプレイヤー目線でも「相手の戦略を固定したときに他のいかなる戦略をとっても期待利得をより大きくすることが出来ない」となっているような戦略の組み合わせであり、このような戦略プロファイルのことをナッシュ均衡と呼びます。
ナッシュ均衡の近似解として、以下の条件を満たす戦略プロファイルをε均衡と呼びます。

$u_1(\sigma) + \epsilon \ge \underset{\sigma'_1 \in \sum_1}{\max}u_1(\sigma'_1, \sigma_2)$

$u_2(\sigma) + \epsilon \ge \underset{\sigma'_2 \in \sum_2}{\max}u_2(\sigma_1, \sigma'_2)$

ε均衡は「相手の戦略を固定したときに他のいかなる戦略をとっても期待利得をεより大きく改善することができない」となっているような戦略プロファイルとなります。εが小さければ小さいほどナッシュ均衡に近く、0のときにナッシュ均衡と一致します。
CFRアルゴリズムによって求めるのはこのε均衡の方になります。

KuhnPokerのナッシュ均衡
KuhnPokerのナッシュ均衡戦略は、考案者であるハロルド・クーンによって求められており、クーン・ポーカー - Wikipediaによると、

任意の $\alpha \in [0, \frac{1}{3}]$ に対してプレイヤー0は
0を持っている場合には $\alpha$ の確率でbet
2を持っている場合には $3\alpha$ の確率でbet
1を持っている場合には常にcheck
プレイヤー1がそのcheckに対してbetした場合には $\alpha +\frac{1}{3}$ の確率でcall

プレイヤー1は
2を持っている場合には常にbetかcall
1を持っている場合には、可能ならcheckを、不可能であれば $\frac{1}{3}$ の確率でcall
0を持っている場合には常にcallせず、 $\frac{1}{3}$ の確率でbet

という行動を取るのが最適となります。*1

Counterfactual Regret Minimization

前置きが長くなりましたが、CFRアルゴリズムの説明に入っていきます。
CFRアルゴリズムでは1イテレーションごとに自己対戦を通して戦略プロファイルを更新していきます。戦略の更新の仕方をざっくりと説明すると、あるイテレーションtにおいて「あのとき別の手を選んでいたら、これだけ期待利得が改善できたのになあ」という後悔(regret)の値を累積し、次のイテレーションでは後悔の大きい行動の選択確率をより大きくする、というものです。
以下の(i)~(v)の手順で戦略を更新していきます。

(i) まず、ゲーム内の全ての履歴 $h$ について以下で定義されるcounterfactual value $v_i$ の値を計算します。

$v_i(\sigma, h) = \pi_{-i}^\sigma(h)u_i^\sigma(h)$

これは、ある履歴hにおける期待利得に、その履歴へのプレイヤーiを除く到達確率を掛けたものになります。

(ii) counterfactual valueをもとに、履歴 $h$ と情報集合 $I$ における以下のcounterfactual regret $r(h, a)$ , $r(I, a)$ の値を計算します。

$\displaystyle r(h, a) = v_i(\sigma_{I \rightarrow a}, h) - v_i(\sigma, h)$

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

counterfactual regretは、ある情報集合 $I$ で行動 $a$ を取っていた場合のcounterfactual valueと、その情報集合でのcounterfactual valueとの差、つまり $I$ で行動 $a$ を取っていた場合に改善できる利得の大きさを表しています。*2

(iii) イテレーション毎に今までのcounterfactual regretの累積値 $\displaystyle R_i^{T, +}(I, a)$ を計算します。ただし、累積値が負の値になった場合は0とします。

$\displaystyle R_i^{T, +}(I, a)=\max(\sum_{t=1}^T r_i^t(I, a), 0)$

となります。

(iv) 計算した累積値をもとに各行動の選択確率を重み付けし、累積値が0の場合は全ての行動を等確率で選ぶように戦略を更新します。

$\displaystyle{\sigma_i^{T+1}(I, a)=\begin{cases} \frac{R_i^{T, +}(I, a)}{\sum_{a \in A(I)}R_i^{T, +}(I, a)} & {if \sum_{a \in A(I)}R_i^{T, +}(I, a) > 0} \\ \frac{1}{|A(I)|} &{\rm{otherwise}} \end{cases}}$

(v) 最後に、イテレーション毎の戦略をそのイテレーションにおけるプレイヤーiの到達確率で重み付けした以下の平均戦略 $\overline{\sigma}_i^T$ を計算します。

$\displaystyle{\overline{\sigma}_i^T(I, a)=\frac{\sum_{t=1}^T\pi_i^{\sigma^t(I)}\sigma^t(I)(a)}{\sum_{t=1}^T\pi_i^{\sigma^t(I)}}}$

$T \rightarrow \infty$ のとき、この平均戦略はナッシュ均衡戦略に収束します。

実装

アルゴリズムの概要を押さえたところで、実際にPythonで実装していきます。
また、ブログ上のコードは説明のために簡略化して断片的に載せてあるため、全ソースコードについてはgithubを御覧ください。

ゲームのルール部分

アルゴリズムを実装する前に、学習環境となるKuhnPokerの部分を実装していきます。
単純にゲームのルールをつらつら書いていくと後で戦略を計算するときに苦労するので、予めゲームを木で定義し、それぞれのノードにアルゴリズムで必要となる情報を持っておくようにします。

ノード
ゲームの各手番における、プレイヤーや履歴、各行動を選んだ際の次のノードなどの情報をもつクラスです。1つの履歴に対して1つのノードが対応します。
expand_child_node()を呼ぶことで、自身の子ノードを展開することが出来ます。これを繰り返し呼ぶことでゲーム全体を図1のような木構造で定義することが出来ます。

class Node:
    def __init__(self, player: int, terminal: bool, eu=0.0: float):
        self.children = {}  # 行動をkey、子ノードをvalueとします。例えば{'check': 子ノード1, 'bet': 子ノード2}のような形になります。
        self.player = player  # このノードの手番プレイヤーです。チャンスノードの場合は-1とします。
        self.terminal = terminal  # 終端ノードの場合はTrueとなります。
        self.private_cards = []  # それぞれのプレイヤーのハンドです。
        self.history = []  # このノードと対応する履歴hです。ただしチャンスノードの行動、つまり手札の配り方はprivate_cardsで持つようにしてhistoryに含めないようにします。
        self.information = ()  # このノードの手番プレイヤーが知ることのできる情報、つまり自身のカードとお互いの行動履歴です。

        self.pi = 0  # 履歴の到達確率π(h)です。
        self.pi_mi = 0  # π(h)のうち手番プレイヤー以外の貢献π_{-i}(h)です。
        self.pi_i = 0  # π(h)のうち手番プレイヤーのみの貢献π_{i}(h)です。平均戦略の計算に使用します。
        self.eu = eu  # ノードの期待利得u(h)です。期待利得はプレイヤー0が得られる利得とします。(プレイヤー1の利得は符号を反転させたものになります。)
        self.cv = 0  # counterfactual valueの値です。
        self.cfr = {}  # 各行動aにおけるcounterfactual regretの累積値です。
        self.pi_i_sum = 0  # 平均戦略を計算する際の分母です。
        self.pi_sigma_sum = {}  # 平均戦略を計算する際の分子です。

    def expand_child_node(self, action: str, next_player: int, terminal: bool, utility: float=0, private_cards=None):
        """
        self.childrenにactionをキーとして子ノードを追加します。
        子ノードの履歴は親ノードの履歴にactionを追加したもの、子ノードの情報は次のプレイヤーの手札と履歴をあわせたものになります。
        """
        next_node = Node(next_player, terminal, utility)
        self.children[action] = next_node
        self.cfr[action] = 0
        self.pi_sigma_sum[action] = 0
        next_node.private_cards = self.private_cards if private_cards is None else private_cards  # 手札は最初に配られたとき以外は前のノードのものを引き継ぎます。
        next_node.history = self.history + [action] if self.player != -1 else self.history  # 前のノードがチャンスプレイヤー以外の場合はhistoryを更新します。
        next_node.information = (next_node.private_cards[next_player], tuple(next_node.history))
        return next_node

KuhnPoker
ゲームの固有の情報をもつクラスです。コンストラクタでKuhnPokerのゲーム木を構築します。*3

def add_list_to_dict(target_dict, key, value):
    # 同じ情報集合に属するノードをまとめるためのutility関数です。
    if key in target_dict.keys():
        target_dict[key].append(value)
    else:
        target_dict[key] = [value]

class KuhnPoker:
    def __init__(self):
        self.num_players = 2
        self.deck = [i for i in range(3)]
        self.information_sets = {player: {} for player in range(-1, self.num_players)}  # プレイヤー-1はチャンスプレイヤーを表します。
        self.root = self._build_game_tree()

    def _build_game_tree(self):
        stack = deque()  # stackを使って深さ優先探索を行います。
        next_player = -1
        root = Node(next_player, False)
        add_list_to_dict(self.information_sets[next_player], root.information, root)  # プレイヤー毎に同じ情報を持つノードをまとめておきます。
        for hand_0 in combinations(self.deck, 1):
            for hand_1 in combinations(self.deck, 1):
                if set(hand_0) & set(hand_1):  # 同じカードが配布されていた場合
                    continue
                private_cards = [hand_0, hand_1, ()]  # それぞれp0, p1, chance playerの情報です。
                next_player = 0
                node = root.expand_child_node(str(*hand_0) + ',' + str(*hand_1), next_player, False, private_cards=private_cards)  # 各行動についてノードを展開します。
                add_list_to_dict(self.information_sets[next_player], node.information, node)  # 新しく展開したノードを適切な情報集合に加えます。
                stack.append(node)
                for action in ["check", "bet"]:  # p0の取りうる行動
                    next_player = 1
                    node = node.expand_child_node(action, next_player, False)
                    add_list_to_dict(self.information_sets[next_player], node.information, node)
                    stack.append(node)
                    if action == "check":
                        for action in ["check", "bet"]:  # p1の取りうる行動
                            if action == "check":
                                utility = self._compute_utility(action, next_player, hand_0, hand_1)  # p1がcheckなら利得を計算してゲーム終了です。
                                next_player = -1  # 終端ノードのプレイヤーは-1とします。
                                node = node.expand_child_node(action, next_player, True, utility)
                                add_list_to_dict(self.information_sets[next_player], node.information, node)
                                node = stack.pop()
                            if action == "bet":
                                next_player = 0
                                node = node.expand_child_node(action, next_player, False)
                                add_list_to_dict(self.information_sets[next_player], node.information, node)
                                stack.append(node)
                                for action in ["fold", "call"]:  # player 0 actions
                                    utility = self._compute_utility(action, next_player, hand_0, hand_1)
                                    next_player = -1
                                    node = node.expand_child_node(action, next_player, True, utility)
                                    add_list_to_dict(self.information_sets[next_player], node.information, node)
                                    node = stack.pop()
                    if action == "bet":
                        stack.append(node)
                        for action in ["fold", "call"]:  # player 1 actions
                            utility = self._compute_utility(action, next_player, hand_0, hand_1)
                            next_player = -1
                            node = node.expand_child_node(action, next_player, True, utility)
                            add_list_to_dict(self.information_sets[next_player], node.information, node)
                            node = stack.pop()
        return root

    def _compute_utility(self, action, player, hand_0, hand_1):
        # ルールにしたがって利得を計算します。
        card_0, card_1 = hand_0[0], hand_1[0]
        is_win = card_0 > card_1
        if action == "fold":
            utility = 1 if player == 1 else -1
        elif action == "check":
            utility = 1 if is_win else -1
        elif action == "call":
            utility = 2 if is_win else -2
        else:
            utility = 0
        return utility

CFRアルゴリズム

アルゴリズムの実装部分です。1回のイテレーションの流れとしては、

現在の戦略に応じて各ノードへの到達確率を更新
戦略と到達確率をもとに各ノードのcounterfactual valueを更新
counterfactual valueをもとに戦略プロファイルを更新

という順で行っていきます。

def train():
    kuhn_poker = KuhnPoker()  # インスタンス生成時にゲーム木が作成されます。
    strategy_profile = get_initial_strategy(kuhn_poker.root, kuhn_poker.num_players)  # 最初の戦略プロファイル
    average_strategy_profile = deepcopy(strategy_profile)  # 平均戦略プロファイル

    for _ in tqdm(range(1000000)):
        update_pi(kuhn_poker.root, strategy_profile, [1.0 for _ in range(kuhn_poker.num_players + 1)], [1.0 for _ in range(kuhn_poker.num_players + 1)])  # 到達確率の更新
        update_node_values(kuhn_poker.root, strategy_profile)  # 各ノードの値の更新
        update_strategy(strategy_profile, average_strategy_profile, kuhn_poker.information_sets)  # 戦略の更新
    print(average_strategy_profile)

ゲームと戦略プロファイルの初期化

戦略プロファイルの初期値に関しては特に条件は無いので、全ての行動を等確率で選ぶような戦略を設定しておきます。
戦略プロファイルはネストした辞書型で定義し、[プレイヤー][情報][行動]の順でアクセスすることでプレイヤーがある情報集合の下で選択する行動の確率を得られるようにしておきます。

def get_initial_strategy(node: Node, num_players=None, strategy_profile=None):
    if node.terminal:
        return strategy_profile
    if strategy_profile is None:
        strategy_profile = {player: {} for player in range(-1, num_players)}  # chance nodeのために+1する
    if node.information not in strategy_profile[node.player]:
        strategy_profile[node.player][node.information] = {action: 1 / len(node.children) for action in node.children}
    for child in node.children.values():
        strategy_profile = get_initial_strategy(child, strategy_profile=strategy_profile)
    return strategy_profile

各ノードへの到達確率の更新

現在の戦略をもとに、各ノードへの到達確率を計算します。
現在のノードへの到達確率を更新するとともに自身の子ノードに対して関数update_piを再帰的に適用します。

def update_pi(node: Node, policy: dict, pi_mi: list, pi_i: list):
    node.pi = pi_mi[node.player] * pi_i[node.player]  # ノードへの到達確率
    node.pi_mi = pi_mi[node.player]  # ノードへの到達確率のうち「このノードのプレイヤー以外の戦略」を掛けたもの
    node.pi_i = pi_i[node.player]  # ノードへの到達確率のうち「このノードのプレイヤーのみの戦略」を掛けたもの
    if node.terminal:  # 終端ノードならば探索を終了
        return
    for action, child_node in node.children.items():  # このノードの子ノードに対して再帰的に関数を呼び、子ノードへの到達確率を更新する。
        next_pi_mi = copy(pi_mi)
        next_pi_i = copy(pi_i)
        for player in policy.keys():
            if player == node.player:
                next_pi_i[player] *= policy[node.player][node.information][action]
            else:
                next_pi_mi[player] *= policy[node.player][node.information][action]
        update_pi(child_node, policy, next_pi_mi, next_pi_i)

各ノード情報の更新

ノードへの到達確率をもとに、各ノードの期待利得、counterfactual value、平均戦略計算用の数値を更新します。
現在のノードの数値を更新するとともに、自身の子ノードに対して関数update_node_valuesを再帰的に適用します。

def update_node_values(node: Node, strategy_profile: dict):
    node_eu = 0  # ノードに到達した後得られる期待利得
    if node.terminal:
        return node.eu
    node.pi_i_sum += node.pi_i
    for action, child_node in node.children.items():
        p = strategy_profile[node.player][node.information][action]
        node.pi_sigma_sum[action] += node.pi_i * p
        node_eu += p * update_node_values(child_node, strategy_profile)
    node.eu = node_eu
    node.cv = node.pi_mi * node_eu
    for action, child_node in node.children.items():
        # 利得やcvの値は全てP0が得られる値として計算しているため、P1のcfrを計算するときは符号を反転させます。
        cfr = node.pi_mi * child_node.eu - node.cv if node.player == 0 else (-1) * (node.pi_mi * child_node.eu - node.cv)
        node.cfr[action] += cfr
    return node_eu

戦略プロファイルの更新

各ノードのcfrの値をもとに、戦略プロファイル及び平均戦略プロファイルを更新します。

def update_strategy(strategy_profile: dict, average_strategy_profile: dict, information_sets: dict):
    for player, information_policy in strategy_profile.items():
        if player == -1:  # チャンスノードでは戦略は更新しません
            continue
        for information, strategy in information_policy.items():
            cfr = {}
            for action in strategy.keys():
                cfr_in_info = 0
                average_strategy_denominator = 0
                average_strategy_numerator = 0
                for same_info_node in information_sets[player][information]:  # 同じ情報集合に属する各ノードのcfrの値を足します
                    cfr_in_info += same_info_node.cfr[action]
                    average_strategy_denominator += same_info_node.pi_i_sum
                    average_strategy_numerator += same_info_node.pi_sigma_sum[action]
                cfr[action] = max(cfr_in_info, 0)
                average_strategy_profile[player][information][action] = average_strategy_numerator / average_strategy_denominator
            cfr_sum = sum([cfr_values for cfr_values in cfr.values()])
            for action in strategy.keys():
                if cfr_sum > 0:
                    strategy[action] = cfr[action] / cfr_sum
                else:
                    strategy[action] = 1 / len(strategy)
    return

結果

100万イテレーション(手元のPCでだいたい2分ぐらい)計算した後に平均戦略プロファイルを見てみます。
$\alpha=0.2077473540513475$ としたときのKuhnPokerのナッシュ均衡がおおむね正しく求められていることがわかります。

# ハンド→履歴(初手の場合は'-')→行動: 選択確率の順で記述してあります。
0:
  '-':
    bet: 0.2077473540513475
    check: 0.7922526459486573
  bet:
    call: 5.0e-07
    fold: 0.9999995
  check:
    bet: 0.3326864064713018
    check: 0.6673135935287035
  check-bet:
    call: 3.1555590414045963e-07
    fold: 0.9999996844440958
1:
  '-':
    bet: 3.4583333333333334e-06
    check: 0.9999965416666667
  bet:
    call: 0.33413558683028116
    fold: 0.665864413169702
  check:
    bet: 3.772727272727273e-06
    check: 0.9999962272727273
  check-bet:
    call: 0.5416096460453012
    fold: 0.45839035395469413
2:
  '-':
    bet: 0.6246676468993436
    check: 0.37533235310066854
  bet:
    call: 0.9999995
    fold: 5.0e-07
  check:
    bet: 0.9999995
    check: 5.0e-07
  check-bet:
    call: 0.9999993339236601
    fold: 6.660763399017379e-07

まとめ

CFRを使ってKuhnPokerのナッシュ均衡を求めてみました。非常に簡略化されたポーカーでもそこそこ複雑な手順を踏まないと最適な戦略が計算できないという点からは、不完全情報ゲームを攻略する上での難しさが垣間見えるかと思います。(不完全情報ゲームに関してはなかなか「ディープでポン」というわけにはいかなそうです。)
もちろんテキサスホールデムを始めとしたいわゆる本物のポーカーの戦略に関してはこのままのアルゴリズムでは到底計算することはできず、行動や状態を手作業で抽象化した上で、現時点で自分が到達しているノードから先のみ詳細に計算する(subgame solving)などの手法が必要となります。
今後、こういった手法やCFRの派生アルゴリズムについても機会があればご紹介していけたらと思います。

References

・An Introduction to Counterfactual Regret Minimization
http://modelai.gettysburg.edu/2013/cfr/

・M. Zinkevich, M. Bowling, M. Johanson, C. Piccione.Regret Minimization in Games with Incomplete Information. NIPS 2007.
http://martin.zinkevich.org/publications/regretpoker.pdf

・クーン・ポーカー - wikipedia
https://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%BC%E3%83%B3%E3%83%BB%E3%83%9D%E3%83%BC%E3%82%AB%E3%83%BC

*1:手札が最弱でも必ず降りるというわけではなく、たまにbet(ブラフ)することで相手を降ろし、手札が最強でも必ずbetするのではなく、たまにcheckするのが最適な戦略というのはなかなか興味深いです。

*2:個人的に行動価値と状態価値の差分で考える部分がなんとなく強化学習のAdvantageの概念に近いなあと思っています。

*3:ルールの規則性を整理して再帰関数を使えばもっとスッキリ書けるかもしれません。