可搾取量(exploitability)で不完全情報ゲームの戦略を評価する

こんにちは、エンジニアの竹内です。
以前のブログ記事【CFR】不完全情報ゲームを学習するAIを実装してみる【KuhnPoker】 - Morikatron Engineer Blogにて二人不完全情報ゲームのナッシュ均衡を計算的に求めるCounterfactual Regret Minimizationというアルゴリズムを紹介しました。
その際、最終的に得られた戦略プロファイルが解析的に計算されたナッシュ均衡と近い値をとっているかを確認することでアルゴリズムの正当性を示していました。
しかし、この方法では「戦略の更新を繰り返すたびにナッシュ均衡に近づいているのか」がわからないだけでなく、そもそも解析的にナッシュ均衡を計算できないゲームについては最終的に得られた戦略プロファイルを評価することができません。

そこで今回は、二人不完全情報ゲームにおける戦略プロファイルを評価する際に有効な「可搾取量(exploitability)」という指標を紹介し、前回Pythonで実装したCFRアルゴリズムに組み込んでいきたいと思います。

可搾取量とは
- 可搾取量の定義
  - 定義
- 可搾取量の具体的なイメージ
実装
まとめ
Reference

可搾取量とは

じゃんけんやポーカーのような不完全情報ゲームにおいては囲碁や将棋のような完全情報ゲームとは異なり、どの相手にも勝ち越すことのできる絶対的に強い戦略(≒必勝法)というものは基本的には存在しません。多くの場合、ある戦略は特定の戦略に対しては強い一方で別の戦略に対しては弱い、といった周期的な性質をもっています。この戦略の周期性が「読み合い」や「駆け引き」を生じさせ不完全情報ゲームを奥深く、面白いものにしています。
このような性質がある中で、不完全情報ゲームにおける戦略の優劣はどの様に判断すれば良いでしょうか？

一つのアイデアとして「自分の戦略に対して最も強い戦略を想定した際に、どれぐらい負けを抑え、搾取されないようにできるか」という観点で評価するという考え方があります。これが今回紹介する「可搾取量(exploitability)」と呼ばれるものです。

イメージしやすいように、勝った方が負けた方から賞金1円を受け取れる（あいこの場合は何も起きない）「賭けじゃんけん」を例に考えてみることにします。この賭けじゃんけんをA君とB君の二人で行うものとします。
今、A君が「60%の確率でグー、10％の確率でチョキ、30%の確率でパーをを出す」という戦略を取っているとします。そこでもし仮にB君にその戦略がバレてしまった場合、B君はできる限りA君から受け取れる金額が高くなるような戦略を取ろうとするでしょう。このような「相手の戦略に対して最も期待利得が高くなるような戦略」を「最適反応戦略（または最適反応）」と呼びます。
今のA君の戦略に対するB君の最適反応戦略は「パーを100%の確率で出す」であることはすぐに分かります。（基本的に最適反応戦略は特定の行動を確率1で選択する純粋戦略となります。）このときB君がA君から受け取れる金額の期待値は0.5円となり、A君側から見ると0.5円もB君に搾取されてしまうことになります。

そこで今度はA君が「50%の確率でグー、20％の確率でチョキ、30%の確率でパーを出す」という戦略をとった場合はどうでしょうか。この場合もB君の最適反応戦略は「パーを100%の確率で出す」となりますが、今度はA君がB君から搾取される金額の期待値は0.3円となり、A君にとっては先程よりも搾取されづらい戦略となります。
この様に「相手に自分の戦略がバレてしまい、相手が自分に対して最も不利な戦略をとってきた場合に最悪どれぐらい搾取されてしまうか」を表した量を可搾取量と言います。不完全情報ゲームにおいて、お互いのプレイヤーの戦略プロファイルがナッシュ均衡に近づいていくと、この可搾取量も0に近づいていきます。したがって二人不完全情報ゲームにおいてこの可搾取量という値は「現在の戦略プロファイルがナッシュ均衡にどれだけ近いか」を表す指標となります。

可搾取量の定義

上で説明した可搾取量を二人不完全情報ゲームのモデルに基づいて数式で定義していきます。各記号については最低限の定義のみを書いているため、具体例などを含めた詳しい説明については前回の記事をご参照ください。

定義

二人不完全情報ゲームにおいて、 $i=1, 2$ に対し、プレイヤー $i$ の戦略を $\sigma_i$ 、 $i$ 以外のプレイヤーの戦略を $\sigma_{-i}$ 、戦略プロファイル $\sigma = (\sigma_1 \cup \sigma_2)$ におけるプレイヤー $i$ の期待利得を $u_i(\sigma) = u_i(\sigma_1, \sigma_2)$ 、そしてナッシュ均衡を $\sigma*$ とします。
このとき $\sigma_i$ に対する可搾取量 $\epsilon_i$ は、ナッシュ均衡のもとで得られる期待利得と、相手が最適反応戦略をとった場合の期待利得との差

$\epsilon_i(\sigma_i) = u_i(\sigma^*)-u_i(\sigma_i, b_{-i}(\sigma_i))$

で定義されます。
ただし最適反応戦略 $b_{-i}(\sigma_i)$ を

$b_{-i}(\sigma_i) = \underset{\sigma'_{-i}}{\rm{argmax}}~u_{-i}(\sigma_i, \sigma'_{-i})$

とします。

今回は片方のプレイヤーの戦略だけではなく両方のプレイヤーの戦略をまとめて評価するため、それぞれプレイヤーについて可搾取量の和をとった、以下の戦略プロファイル $\sigma$ の可搾取量を*1求めればよいことになります。

$\epsilon(\sigma)= \sum_{i \in \{1, 2\}}u_i(\sigma^*)-u_i(\sigma_i, b_{-i}(\sigma_i))$

一般的にナッシュ均衡のもとで得られる期待利得 $u_i(\sigma^*)$ を計算することはKuhn Pokerのような規模の小さいゲームを除いて困難ですが、二人ゼロサム・ゲームの場合 $u_i(\sigma^*) = - u_{-i}(\sigma^*)$ が成り立つため、嬉しいことに戦略プロファイルの可搾取量を計算する際は各々のプレイヤーの戦略について合算する過程で以下の様に $u_i(\sigma^*)$ の項がキャンセルされます。

$\begin{eqnarray}\epsilon(\sigma) &=& \sum_{i \in {1, 2}}u_i(\sigma^*)-u_i(\sigma_i, b_{-i}(\sigma_i)) \\&=& u_1(\sigma^*) -u_1(\sigma_1, b_2(\sigma_1)) + u_2(\sigma^*) - u_2(b_1(\sigma_2), \sigma_2) \\&=& u_1(\sigma^*) +u_2(\sigma_1, b_2(\sigma_1)) - u_1(\sigma^*) + u_1(b_1(\sigma_2), \sigma_2) \\&=& u_2(\sigma_1, b_2(\sigma_1)) + u_1(b_1(\sigma_2), \sigma_2)\end{eqnarray}$

したがって戦略プロファイル $\sigma$ に対する可搾取量 $\epsilon$ はそれぞれのプレイヤーの戦略における可搾取量の総和

$\epsilon(\sigma) = u_2(\sigma_1, b_2(\sigma_1)) + u_1(b_1(\sigma_2), \sigma_2)$

と表されます。

またナッシュ均衡における可搾取量は以下の様に0となります。

$b_2(\sigma^*_1) = \sigma^*_2, ~b_1(\sigma^*_2) = \sigma^*_1$

より

$\begin{eqnarray}\epsilon(\sigma^*) &=& u_2(\sigma^*_1, \sigma^*_2) + u_1(\sigma^*_1, \sigma^*_2) \\&=& u_2(\sigma^*_1, \sigma^*_2) - u_2(\sigma^*_1, \sigma^*_2) \\&=& 0\end{eqnarray}$

可搾取量の具体的なイメージ

数式だけだと分かりづらいので、先程の賭けじゃんけんの例を上の可搾取量の定義に当てはめて考えてみます。
まず、じゃんけんのナッシュ均衡においては当然 $u_i(\sigma^*)= 0$ となります。

次に、プレイヤー1の戦略 $\sigma_1$ 、つまり出す手の確率がそれぞれ{グー: 0.6, チョキ: 0.1, パー: 0.3}であったとします。このとき $\sigma_1$ に対するプレイヤー2の最適反応戦略 $b_2(\sigma_1)$ は{グー: 0, チョキ: 0, パー: 1.0}となりプレイヤー1の期待利得は

$(-1) \times 0.6 \times 1.0 + (+1) \times 0.1 \times 1.0 = - 0.5$

となります。また、プレイヤー１の戦略に対する可搾取量は

$\begin{eqnarray}\epsilon_1(\sigma_1) &=&u_1(\sigma^*)-u_1(\sigma_1, b_2(\sigma_1)) \\&=&0 - (-0.5) \\&=& 0.5\end{eqnarray}$

と計算されます。
同じようにしてプレイヤー1とプレイヤー2の戦略がそれぞれ
プレイヤー1: {グー: 0.6, チョキ: 0.1, パー: 0.3}
プレイヤー2: {グー: 0.2, チョキ: 0.2, パー: 0.6}
であった場合の戦略プロファイルに対する可搾取量 $\epsilon(\sigma)$ は

$\begin{eqnarray}\epsilon(\sigma) &=& u_2(\sigma_1, b_2(\sigma_1)) + u_1(b_1(\sigma_2), \sigma_2) \\&=&0.5 + 0.4 \\&=&0.9\end{eqnarray}$

と計算されます。

実装

ここからはPythonで実際に可搾取量を求めるアルゴリズムを実装していきます。
検証する環境には前回の記事で実装したKuhn Pokerを使用していますが、特にゲーム固有の仕組みは使用していないため、他の不完全情報ゲームにも利用が可能です。Kuhn Pokerの詳しいルールについては前回の記事をご参照ください。
また、記事内のコードは断片的に載せているため、コード全体をご覧になりたい方はgithubをご参照ください。

大枠

定義通り各プレイヤーについて現在の戦略に対する相手の最適反応戦略及び可搾取量を求め、その和を取っていきます。
ただし、各ノードに記録されている期待利得はプレイヤー1のものであるため、プレイヤー2が得られる期待利得についてはプレイヤー1が得られる期待利得の符号を反転させたものとなることに注意します。また、コード上では各プレイヤーは0-indexで実装してあるのでその点にも注意です。

def get_exploitability(game, average_strategy_profile):
    """
    game: ゲームの木や情報集合等の情報を持ったゲームクラス
    average_strategy_profile: 可搾取量の計算対象となる戦略プロファイル（ナッシュ均衡に収束している最中の平均戦略）
    """
    exploitability = 0
    for player in range(game.num_players):  # 二人ゲーム限定
        if player == 0:
            exploitability += compute_exploitability(game.root, game.information_sets, average_strategy_profile, player)
        else:
            exploitability += (-1) * compute_exploitability(game.root, game.information_sets, average_strategy_profile, player)  # プレイヤー2の期待利得はプレイヤー1の期待利得の符号を反転させたもの
    return exploitability

最適反応戦略と可搾取量の計算

今回の実装のメインとなる、特定の戦略に対する最適反応戦略と可搾取量を求める部分に入っていきます。
先程の賭けじゃんけんの例では手番が同時で一回きりでしたが、Kuhn Pokerのような展開型のゲームでは最適反応戦略を計算する際に各状態への到達確率を考慮する必要があります。
これについてわかりやすいようにKuhn Pokerを使った具体的な例で考えてみます。
プレイヤー1の戦略を既知として、プレイヤー2がそれに対する最適反応戦略を選ぶケースを想定します。例えば今プレイヤー2にクイーンのカードが配られ、プレイヤー1がベットを選択したとして、プレイヤー2目線でコールかベットのうち最適な行動、即ち期待利得を最大化する行動を取るにはどうすればよいでしょうか。
極端な例として、もしプレイヤー1の戦略が「ジャックが配られた時は99%の確率でベットし、キングが配られた時は1%の確率でベットする」であった場合、プレイヤー1はジャックを持っている確率が高く、プレイヤー2は明らかにコールを選択する方が良さそうです。しかし逆に「ジャックが配られた際は1%の確率でベットし、キングが配られた際は99%の確率でベットする」であった場合、今度はおそらくプレイヤー1はキングを持っている確率が高く、プレイヤー2はフォールドを選択して降りる方が良さそうです。
この様に、どちらの行動を優先すべきかを決めるためには、相手の手札として考えられるすべての候補に対して、それぞれ現在の状態へと至る確率と、その状態で特定の行動を選択した際に得られる期待利得を考慮する必要があります。

以上を踏まえて最適反応戦略及び可搾取量を求める関数を実装していきます。

def compute_exploitability(node, information_sets, average_strategy_profile, opponent_player):
    """
    一方のプレイヤーの戦略に対する最適反応戦略および可搾取量を計算します。
    この関数を再帰的に呼び出すことでゲームの木に対して深さ優先探索を行い、最も終端ノードに近いノードからさかのぼって計算していきます。
    node: 現在のゲームのノード
    information_sets: ゲーム全体の情報集合
    average_strategy_profile: 最適反応戦略を計算する対象となる戦略
    opponent_player: 最適反応戦略を選択する側のプレイヤー
    """
    if node.terminal:  # 終端ノードの場合は単純にお互いの利得を出力
        return node.eu
    if node.player == opponent_player:  # opponent playerは最適反応戦略をとる
        best_response_value = None  # 最適反応をとったときの期待利得
        best_weighted_expected_utility = -float("inf") if opponent_player == 0 else float("inf")  # 到達確率で重み付けした期待利得の最大
        for action, _ in node.children.items():  # それぞれの行動のうちどれが一番（ノードへの到達確率）×（その行動を取ったときの期待利得）が大きくなるかを計算する
            current_weighted_expected_utility = 0  # （ノードへの到達確率）×（その行動を取ったときの期待利得）
            current_node_expected_utility = 0  
            for same_info_node in information_sets[node.player][node.information]:  # 同じ状況のノード(すべての相手の手札のパターン)を列挙
                expected_utility = compute_exploitability(same_info_node.children[action], information_sets, average_strategy_profile, opponent_player)  # この先のノードでも最適反応戦略をとった時の期待利得
                if node == same_info_node:  # 実際に現在いるノードについては期待利得を記録しておく
                    current_node_expected_utility = expected_utility
                current_weighted_expected_utility += same_info_node.true_pi_mi * expected_utility  # 同じ状況のノード全てについて、選択した行動の重み付き期待利得の和を取る
            if opponent_player == 0:  # 到達確率で重み付けした期待利得が最も大きくなる行動を選択
                if best_weighted_expected_utility < current_weighted_expected_utility:
                    best_weighted_expected_utility = current_weighted_expected_utility
                    best_response_value = current_node_expected_utility
            else:  # プレイヤー2の場合は重み付けした期待利得に-1を掛けた値が最も大きくなる行動を選択
                if best_weighted_expected_utility > current_weighted_expected_utility: 
                    best_weighted_expected_utility = current_weighted_expected_utility
                    best_response_value = current_node_expected_utility
        return best_response_value

    else:  # 最適戦略を計算する必要の無い方のプレイヤーについては現在の戦略に従って行動を選択
        expected_utility = 0
        for action, child_node in node.children.items():
            p = average_strategy_profile[node.player][node.information][action]
            expected_utility += p * compute_exploitability(child_node, information_sets, average_strategy_profile, opponent_player)
    return expected_utility

正しく実装できているかチェック

上で実装した関数によって正しく可搾取量が求められているかチェックしてみます。
Kuhn Pokerの場合にはナッシュ均衡の例がwikipediaに記載されていますから、その通りの戦略プロファイルを一つ用意し、それに対して可搾取量を計算する関数から0が返って来れば正しく計算できているということになります。Kuhn Pokerクラスの方にナッシュ均衡戦略を取得するメソッドを実装しておきます。*2

def check_exploitability():
    game = KuhnPoker()
    nash_equilibrium = game.get_nash_equilibrium(game.root)
    update_pi(game.root, nash_equilibrium, nash_equilibrium, [1.0 for _ in range(game.num_players + 1)],
              [1.0 for _ in range(game.num_players + 1)], [1.0 for _ in range(game.num_players + 1)])
    exploitability = get_exploitability(game, nash_equilibrium)
    print(exploitability)  # 0に近い値が出力される

上の関数を実行してみると実際に0に近い値（桁落ちで若干ズレますが）が出力されます。
ナッシュ均衡以外にも「全ての行動を等しい確率で選択するような戦略プロファイル」や「特定の行動を確率1で選択するような純粋戦略」といった手計算しやすいケースで試してみて期待通りの結果が得られるかチェックすると良いです。*3

CFRアルゴリズムのパフォーマンス

さて、正しく実装できていることを確認した上で、今度は実際に以前紹介したCFRアルゴリズムをKuhn Pokerに適用した場合で戦略を更新しながら可搾取量の推移を確認してみます。
可搾取量の計算は現在の戦略に従ってノードへの到達確率を更新した後、戦略を新しく更新する前に計算します*4。その他の大枠の部分は基本的には前回の記事とほぼ同じです。
可搾取量のログについてですが、1000万ステップの更新のたびに可搾取量を計算してログを残すのは大変ですし、可搾取量は後半になるにつれて減少量が小さくなっていくため、対数スケールでプロットするようにスケジューリングしておきます。

def main():
    logger.configure("./logs")
    num_updates = int(5e7)
    average_strategy_profile = train(num_updates, lambda x: (10 ** (len(str(x)) - 1)))  # 対数スケールでプロット
    export_strategy_profile_to_yaml(average_strategy_profile)  # 得られた戦略はyamlで出力しておく


def train(num_iter, log_schedule):
    game = KuhnPoker()
    strategy_profile = get_initial_strategy_profile(game.root, game.num_players)
    average_strategy_profile = deepcopy(strategy_profile)
    for t in tqdm(range(num_iter)):
        update_pi(game.root, strategy_profile, average_strategy_profile, [1.0 for _ in range(game.num_players + 1)], [1.0 for _ in range(game.num_players + 1)], [1.0 for _ in range(game.num_players + 1)])
        update_node_values(game.root, strategy_profile)
        exploitability = get_exploitability(game, average_strategy_profile)  # 戦略を更新する前に可搾取量を計算しておく
        update_strategy(strategy_profile, average_strategy_profile, game.information_sets)
        if t % log_schedule(t) == 0:
            logger.logkv("t", t)
            logger.logkv("exploitability", exploitability)
            logger.dumpkvs()
    return average_strategy_profile

1000万回戦略の更新を行った結果、可搾取量の推移を見やすいように両対数グラフにしてプロットすると単調に減少していっているのがわかるかと思います。

f:id:morika-takeuchi:20201023152041p:plain — KuhnPoker+CFRで可搾取量を計算した結果

上のグラフから、CFRアルゴリズムを使って戦略の更新を繰り返すことで、戦略プロファイルが徐々にナッシュ均衡に近づいていくことがわかります。

まとめ

二人不完全情報ゲームにおける戦略を評価するための指標、可搾取量を紹介しました。
可搾取量は不完全情報ゲームの戦略を求めるアルゴリズムを提案する論文などでは、既存のアルゴリズムと比較するためによく用いられる評価指標であり、可搾取量が0へと収束する速度によって複数のアルゴリズムのパフォーマンスを定量的に比較することができます。
しかしながら、ゲームの木を全探索する必要があるため本格的なポーカーのような探索空間が膨大なゲームについては計算が困難な場合があります。これについては強化学習と探索を組み合わせて近似的に最適反応戦略を求めることで解決するというアプローチがDeepMindの論文[2004.09677] Approximate exploitability: Learning a best response in large gamesの中で提案されています。

今後はCFR以外のアルゴリズムやKuhnPoker以外の簡単な不完全情報ゲームについても、ぼちぼち実装していきながら可搾取量の推移を比較する、みたいな記事を書いていけたらなと思っています。

Reference

Accelerating Best Response Calculation in Large Extensive Games
Michael Johanson, Kevin Waugh, Michael H. Bowling, Martin Zinkevich, 2011
https://openreview.net/forum?id=rkVq1QfdbS

Safe and Nested Subgame Solving for Imperfect-Information Games
Noam Brown, Tuomas Sandholm, 2017
https://arxiv.org/abs/1705.02955

Building a Poker AI Part 7: Exploitability, Multiplayer CFR and 3-player Kuhn Poker
Thomas Trenner
https://medium.com/ai-in-plain-english/building-a-poker-ai-part-7-exploitability-multiplayer-cfr-and-3-player-kuhn-poker-25f313bf83cf

*1:戦略プロファイルに対する可搾取量の定義として和をとっているものと平均をとっているものの2つがありましたが、今回は和を取る方を採用しています。

*2:あまりにもベタ書きなのでブログには載せられません。githubをご参照ください。

*3:私も実際今回の実装にあたっていくつかのパターンについて手計算の結果と合っているか地道にチェックしました。

*4:新しく戦略を更新した後だとノードの到達確率と噛み合わず、微妙に正しい計算結果が得られなくなります。これで私はだいぶ時間を溶かしました。