Probabilistic State Translation in Extensive Games with Large Actions Sets

不完全情報ゲームの代表例と言えるポーカーで初めてプロに勝った人工知能 Libratus*1の論文を理解するために, 最近, 大規模な展開形ゲームのナッシュ均衡を求めるための手法に関する論文を読んでいます. それの一環として, タイトルにもあるProbabilistic State Translation in Extensive Games with Large Actions Setsを読んだのでそれをまとめます.

この論文を選んだ理由としては, 定式化が非常にしっかりしていたからです. Libratusの論文Safe and Nested Subgame Solving for Imperfect-Information Gamesも数学的に書かれているので, それを読み解くには, 記号に慣れる必要があり, 良い訓練になると考えました.

この記事は, 論文の流れに添いつつも, 自分の考えや調べたことなどが含まれています.

Introduction

複数のエージェントが存在する複雑な問題の多くは, ゲーム理論の展開形ゲームと呼ばれる木の構造を持つ形式で定式化することができます. しかし, 木のサイズが大きくなると, 実際にナッシュ均衡と呼ばれるゲームにおける解を計算することが, 事実上不可能になります. そこで, 抽象化(abstraction)と呼ばれる方法を使います. 本来解きたいゲーム(real game)を抽象化(具体的には, 取りうる行動を減らすなど)して, 木のサイズを計算できるレベルまで小さくする. そして, 抽象化したゲーム(abstraction game)を解くことで, real gameの解の近似解を得る方法です.

この方法には, ２つの問題があります. １つ目は, 抽象化によってreal gameに持っていた情報を失うことです. 抽象化によって, abstration gameのナッシュ均衡は, real gameのナッシュ均衡と大きく乖離してしまう場合があります.

２つ目は, 抽象化によって取りうる行動や起きうる状態が減ることです. 抽象化したからといって, real gameにおいて, その行動や状態が起こらないとは限りません. もし仮に, abstradtion gameでは起きない行動や状態が起きた場合, abstraction gameのナッシュ均衡の戦略は使うことができなくなってしまいます. そのため, real gameの状態からabstraction gameの状態を変換するマッピングが必要になります.

この論文では, real gameにおける状態とabstract gameにおける状態のマッピングであるstate translationを数学的にきちんと定式化します. またより柔軟にエージェントを作り出すため, 抽象化とtranslationを分けて考えることができることを示します. また既存のtranslationの方法もきちんと定式化しています. 新しい提案手法と比較実験を行い, 抽象化の特性を利用してプレイしてくるエージェントに対して, exploitability*2が減ることを示しました.

この記事では, 実際にポーカーに適用した部分や実験結果は紹介していません. 基本的に定式化の部分のみの紹介になります.

Background

Extensive Game

展開形ゲーム(Extensive Game)は, プレイヤー(player)とチャンス(chance)*3が取り得る行動の組み合わせによって構築されます. 例えば, 将棋であればプレイヤーの行動は, どの駒を動かすかなどです. チャンスとは, プレイヤーとは独立した存在で, プレイヤーに及ばない部分の行動を表現する際に使われます. 将棋であれば先行後攻を決めるのは, プレイヤーではなく振り駒によって確率的に決まります. この先行後攻を決める部分も行動とみなすためにチャンスと呼ばれる特別なプレイヤーを導入します.

将棋や囲碁のように全ての行動がどのプレイヤーにも観察可能なゲームもあれば, ポーカーのように相手のカードが見えないといったある行動が観測可能でないゲームも存在します. そのようなすべての行動が観測可能とは限らないゲームのことを不完全情報ゲーム(imperfect information game)と呼びます. どの行動が観察できないのかを定式化するには, 情報分割(information partition)といった概念を考える必要があります. 情報分割は履歴(history)*4の集合をプレイヤーにとっては判別できない履歴は同じ集合に属するように分割した集合の集合です.

まずこういった概念を数式で定式化するために, まず展開形ゲームを定義します.

不完全情報ゲームの有限展開形ゲーム不完全情報ゲームにおける有限な展開形ゲームは $\Gamma = (N, H, A, P, f_c, \{\mathbf{I}_i\}_i, \{u_i\}_i, \{\sigma_i\}_i)$ で表される.

$\Gamma$ の要素を１つ１つ見ていきます.

$N$ : プレイヤーの有限集合. ５人のポーカーなら $N = \{1,2,3,4,5\}$ . またチャンス $c$ を含めて, 全プレイヤーを $N \cup \{c\}$ と表す.
$H$ : 履歴(history)の集合. 末端の履歴*5のことを, $Z$ で表す.
$A(h) = \{a: (h,a) \in H \}$ : 末端でない履歴 $h \in H/Z$ において取り得る行動の集合
$P: H/Z \rightarrow N \cup \{c\}$ : プレイヤー関数(player function). その履歴において, 次行動をとるプレイヤーを出力する関数
$f_c$ : チャンスの行動の確率分布
$\mathbf{I}_i$ : プレイヤー $i \in N$ の情報分割. $P(h) = i$ となる履歴, つまり, プレイヤー $i$ が次に行動する履歴の集合を $H_i$ とおけば, 情報分割は, $H_i$ の分割になる. 情報分割の要素を情報集合(information set)と呼ぶ. 同じ情報集合にいる履歴は, そのプレイヤーからはどっちの履歴なのか判断がつかないことを表す. 区別がつかないので, 取り得る行動は同じでなければならないので

\begin{align} A(h) = A(h') \quad \forall h, h' \in I_i \in \mathbf{I}_i \end{align}

が必要になる.

$u_i$ : プレイヤー $i$ の効用関数. 末端の履歴から実数(効用)を返す.
$\sigma_i$ :プレイヤー $i$ の戦略.

数式でドバッとゲームを表現されるとわかりづらいと思うので, 以下の図のようなゲームを使って具体的に, 上の要素を書き下してみます.

まずプレイヤーの集合を考えると, 図からプレイヤーは二人なので, $N=\{1, 2\}$ となります. そして, 次に履歴の集合です. まず最初の何も行動が起きていない状態は, 空集合で表します. なので, $\phi$ は履歴の集合の要素です. 次に, プレイヤー１が最初に行動をします. 可能な行動は, $L, R, U, D$ なので, それらも履歴の集合になります. 次に, もしプレイヤー１が $L, R$ をとった場合, プレイヤー２は, $a, b$ のどちらかの行動を取ることができます. またプレイヤー１が $U$ を取った時, プレイヤー２は $\alpha, \beta, \gamma$ のどれかの行動をとることができます. またプレイヤー１が $D$ を取った時, プレイヤー２は $r, l$ のどれかの行動をとることができます. したがって, 履歴の集合 $H$ は,

\begin{align} H = \{L, C, R, O, (L, a), (L, b), (R,a), (R,b), (U, \alpha), (U, \beta), (U, \gamma), (D, l), (D, r)\}. \end{align}

次に $A(h)$ について考えてみると, ゲームの最初はプレイヤー１が $L, R, U, D$ のどれかを取るので, $A(\phi) = \{L, R, U, D\}$ となります.

次に, プレイヤー１が $L, R$ をとった場合は, プレイヤー２の手番で, $a, b$ のどちらかの行動をとることができるので, $A(L) = A(C) = A(R) = A(O) = \{a,b\}$ となる. もし, プレイヤー１が $U$ をとった場合, プレイヤー２の手番で, $\alpha, \beta, \gamma$ のどれかの行動をとることができるので, $A(U) = \{\alpha, \beta, \gamma\}$ となります. 同じように, プレイヤー１が $D$ を取った場合, プレイヤー２の手番で, $r, l$ のどれかの行動をとることができるので, $A(D) = \{l, r\}$ となります.

$P(h)$ について考えてみると, ゲームの最初は, プレイヤー１が行動するので, $P(\phi) = 1$ . そのあとはプレイヤー１がどの行動を取ろうとも, プレイヤー２が行動するので, $P(L) = P(R) = P(U) = P(D) = 2$ . そのあとは, 末端に行くので, $P(h)$ は考えない.

$f_c$ は, 今回はチャンスを考えていないので無視する.

抽象化を考える上で一番重要になる情報分割について考えてみます. 上の図をみると, 青い丸で囲まれたところは, 情報集合を表していて, プレイヤー２は青い丸のどのノード*6にいるかわからない状態を表しています. まずプレイヤー２が次に行動する履歴の集合 $H_2$ は, $H_2 = \{L, R, U, D\}$ である. 青い丸の履歴の部分は, プレイヤー２にとって区別できないので, プレイヤー２の情報分割は, $\mathbf{I}_2 = \{\{L, R\}, \{U\}, \{D\}\}$ となる. プレイヤー１の情報分割は, トリビアルな例なので, 省略します(全ての情報集合の要素が１).

効用関数と戦略の部分も基礎的なものなので, 具体例は省略.

これで展開形ゲームの基礎的な内容は終わりで, 次に本題である抽象化についてです.

Game Abstraction

抽象化には以下の２つのテクニックがあります.

チャンスの行動をいくつかのバケットにするテクニック

例えば, ポーカーであればチャンスは最初のカードの手にあたります. テキサスホールデムというポーカーのゲームでは, 最初２枚のカードが配られます. 通常であれば, $52 \times 51$ の組み合わせがありますが, これでは大きすぎます. 手の強さを計算して, ある程度同じ強さのものはひとまとめにして同じ手とみなすような抽象化はこれにあたります.

プレイヤーがとることのできる行動を制限するテクニック

ポーカーであれば, 掛け金の上限を設定するといった抽象化はこのテクニックにあたります.

こういった抽象化を数学的に定義します.

Abstraction プレイヤー $i \in N$ の抽象化とは, $\alpha_i = \langle \alpha_i^{\mathbf{I}}, \alpha_i^{A}\rangle$ である. ここで,
$\alpha_i^{\mathbf{I}}$ は $H_i$ の抽象化したゲームの情報分割で, 元のゲームの情報集合よりcoarse*7である.
$\alpha_i^{A}$ は, 抽象化行動集合(abstract action set)と呼び, 履歴から行動を返す関数で, $\alpha_i^{A}(h) \subset A(h)$ であり, 抽象化したゲームの同じ情報集合に属する履歴 $h, h'$ に対して, $\alpha_i^{A}(h) = \alpha_i^{A}(h')$ を満たす.

プレイヤー全体の抽象化を, $\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_n)$ で表します. この $\alpha$ を使ったabstract gameを $\Gamma^{\alpha}$ で表します.

実際に抽象化の影響については[Waugh et al., 2009]が研究していて, 抽象化の度合いとabstract gameのナッシュ均衡とreal gameのナッシュ均衡の乖離は関係がないことを証明しています. 直感的には, 抽象度が上がれば, 情報は失われていくので, abstract gameのナッシュ均衡はreal gameのナッシュ均衡から乖離すると思われるが, 実際はそうでないということです.

さて, 理解を深めるためにこの定義を使って, ゲームの抽象化をしてみます.

再び, 先ほどの図を用いて考えてみましょう.

上の図は, プレイヤー１の行動 $D$ は $U$ とみなすという抽象化をしているということを表しています.

これを上で定義した抽象化 $\alpha$ で表してみます.

まずプレイヤー１の抽象化について. プレイヤー１の情報分割は, 変わらないのでそのまま $\alpha_1^{\mathbf{I}} = \mathbf{I}_1$ .

次に, 抽象行動集合は, $\alpha_1^{A}(\phi) = \{L, R, U\}$ となります. $D$ という行動は抽象化されたからです.

次にプレイヤー２の抽象化を考えます.

プレイヤー２の抽象したゲームの情報分割は, $\alpha_2^{\mathbf{I}} = \{\{L, R\}, \{ U, D\}\}$ . 抽象化する前は, $\{U\}$ と $\{D\}$ が別れていたが, 抽象化によって $U$ は $D$ とみなしたので, 区別がつかなくなったことを表しています.

次に抽象行動集合は, $\alpha_2^{A}(L) = \alpha_2^{A}(R) = \{a, b\}$ となります. 次に, $D$ は抽象化されて, $U$ とみなすので, $\alpha_2^{A}(U) = \alpha_2^{A}(D) = \{\alpha, \beta, \gamma \}$ となります.

ある程度, 抽象化のイメージがついたところで, 抽象化の問題を解決するためのtranslationについて話を進めます. 実際の論文では, 抽象化について別の定義(Loose abstraction)を用いています. 具体的な情報分割を明示しなくても抽象化できるような工夫がされています. 詳しくは本論文を読んでみるといいと思います.

Translation Method

Introductionでも述べたように, abstract gameの解を使うためには, real gameの行動や状態をabstract gameに変換するマッピングが必要になります. それが, translationと呼ばれるものです. translationの方法は色々ありますが, real gameにおける行動をabstract gameにおいて有効な行動に逐一変換する方法が簡単です.

Hard translation

この論文が出る前の既存のtranslationの手法は, [Gilpin et al., 2008]が提案したもので, hard translationと呼びます. これはreal gameの履歴をabstract gameの履歴に変換するものです. 数式で定式化すると, 以下のようになります.

hard translation function hard translation $T(h)$ とは, real gameの履歴からabstract gameの履歴の関数である. つまり, $T: H \rightarrow H'$ である.

これは履歴に対する関数なので, 行動を変換する関数は別で定義する必要がある. これをhard translation in-step functionと呼ぶ.

hard translation in-step function hard translation in-step functionとは, $h \in H$ , $a \in A(h)$ に対して, $t_{in}(h, a) \in A'(T(h))$ となる関数である.

$'$ がついているのは, abstract gameを表します. 言葉で説明すると, hard translation in-step functionとは, real gameの履歴 $h \in H$ とその時の行動 $a \in A(h)$ から, abstract gameで有効な行動に変換する関数です. real gameの行動を即時にabstract gameの行動に変換する関数です.

逆に, abstract gameからreal gameに変換するtranslationも定義できて, それをhard translation out-step functionと呼ぶ.

hard translation out-step function hard translation out-step functionとは, $h \in H$ , $a' \in A'(T(h))$ から $t_{in}(h, a') \in A(h)$ となる関数である

言葉で説明すると, abstract gameの行動をreal gameの行動に変換してくれる関数です. out-step functionは, abstract gameの解に従っている場合でも, real gameの行動をしたいときに使うことができます.

さて, 数学的にtranslationを定義しましたが, translationを具体的に定義することでabstract gameが構築されます. 実際に上で見た例がその実例となります( $D$ を $U$ とみなすことを $T(D) = U$ とかける).

実際に適当に抽象化するだけではreal gameに近いabstract gameを作ることができません. ここで, $T$ を実際に作る方法を考えます. まずtranslation in-step functionを用いて $T$ を再帰的に書けることを利用します.

\begin{align} T( (h,a) ) = (T(h), t_{in}(h, a)) \end{align}

これは, 履歴 $(h, a)$ をabstract gameに変換した履歴は, 一個前の履歴 $h$ をabstract gameの履歴に変換したものとreal gameでの行動 $a$ をabstract gameの行動に変換したものを付け加えたものということです. これは直感的に正しそうです. これを用いれば, $t_in$ が既知ならば, $T$ は決まります.

そうすると, 続く問題は $t_in$ の決め方になります. このin-step functionを決めるために行動の類似度を測るための概念を導入します. これをsimilarity metricsと呼ぶ.

$S(h, a, a')$ と書いて, 履歴 $h$ の時点でのreal gameの行動 $a$ とabstract gameの行動 $a'$ の類似度を表します. これを使って, hard translation in-step functionを定義します. 単純に一番real gameの行動に近いabstract gameの行動に変換するだけです. 数式で表すと, 以下のようになります.

\begin{align} t_{in}(h, a) = \operatorname{\rm arg~max} S(h, a, a') \end{align}

out-step functionの役割もありますが, この記事では省略します.

この論文では新しいtranslationの方法を提案していますが, hard translationには何が問題になるのでしょうか. それは, 相手が抽象化していることを知られていて, なおかつ, どうやって抽象化しているのか知られている時, それを利用されてしまう可能性が高くなることです. ポーカーでいえば, ベット額を$1から$10は$1とみなすような抽象化をした時, 相手は自分の手札が強い時は$10ベットして, 弱い時は, $1ベットすれば, どちらも$1と見なされるので, 自分の情報はバレずに勝った時の利得を上げて, 負けた時のリスクを下げることができてしまう. よって, 抽象化のやり方がバレないようにする必要があるのですが, hard translationだと抽象化は決定的なので, 何回かゲームをすることで, 抽象化の仕方を推定される可能性がある. そこで, この論文では, translationを確率的にしたsoft translationというものを提案しました.

Soft translation

いきなりですが, soft translationを数学的に定義します.

soft translation function soft translation function $T^p(h)$ とは, $T^p(h) \subset \mathbb{R} \times H'$ となる関数である.

soft translation functionは, １つの履歴を出力するのではなく, 履歴に実数の値がついたペアとなる要素の集合を返すことです. この実数はその行動のとる確率と結びついています*8. よって, hard translation functionと違って, soft translationはどの履歴にtranslateされるかは確率的に変動するような仕組みを提供してくれます.

同じようにin-step functionも定義しましょう.

soft translation in-step function soft translation in-step functionとは, $h \in H$ , $a \in A(h)$ に対して, $t_{in}(h, a) \in \mathbb{R} \times A'(T(h))$ となる関数である.

これによって, 行動の変換が確率的になるので, 先ほど指摘した抽象化の方法がばれるという問題は緩和します.

ただこのやり方だとhard translationと違って, translationの結果が履歴と実数のペアの集合であるため, real gameを毎回, translationすると, その履歴の数は指数関数的に増加してしまう. そのため, translationするごとに集合をそのまま保持するのではなく, その集合から一つの履歴をサンプリングすることで指数的な増加を抑える.

実際の論文では, このsoft translationとhard translationを使ったエージェントを様々な敵と戦わせた結果を解析していますのでそちらを知りたい方はぜひ論文を読んでみてください.

最後になりますが, もし間違いなどあればぜひコメントくれると嬉しいです.