ゲームにおけるNon-transitivityについて
こんにちは、機械学習エンジニアの藤野です。
今日はゲームの戦略におけるTransitivity（推移性、推移律）について書かれたいくつかの論文を紹介したいと思います。なお、今回の内容は自分が以前他の勉強会で発表したスライドと被る部分があるのでそのリンクを示しておきます。
概念・定義
まずはじめに推移律の概念について簡単に説明します。
推移律は集合の2要素間で成り立つ関係で、例えば果物に対する選好（好き嫌い）であれば、りんごよりみかんが好き、みかんよりバナナが好きである場合に、りんごよりバナナが好きという関係が（すべての果物について）成り立つことを言います。
これをゲームの戦略の強さの文脈で考えてみると、任意の戦略A、B、Cに対して、AよりBが強くBよりCが強い場合にAがCよりも強い、となります。ただ、この関係がすべてのゲームにおいて成り立つわけではありません。
成り立たないゲームのわかり易い例がじゃんけんです。もう少し複雑な例でいうと、オンラインゲームとして有名なStarCraftもそうらしいです（自分はPlayしたことがないため詳しくはわかりません）。
[Balduzzi et al., 2019]ではこの性質をNon-transitivityと呼んでいます。そしてその極端なケースをCyclicityと呼び、2人ゼロサムゲーム（2人の利得の合計がゼロになるゲーム）の文脈において次のように定義しています。
$$
\int_W \phi(\mathbf{v}, \mathbf{w})\cdot d\mathbf{w} = 0 \,\,\, \text{for all} \,\,\, \mathbf{v} \in W
$$
ここで$${\mathbf{v}}$$、$${\mathbf{w}}$$はそれぞれ自分、相手の戦略を表し、$${\phi}$$は2人の戦略を入力として自分の勝敗を返す関数です。$${\phi (\mathbf{v}, \mathbf{w})}$$が正となるとき、自分（$${\mathbf{v}}$$）が勝つことを意味します。$${W}$$は戦略全体の集合です。つまり、戦略空間のすべての戦略について、それぞれの戦略の勝敗が総合的に見れば引き分けになるようなゲームをCyclicなゲームと定義しています。
Cyclicなゲームの例として、[Balduzzi et al., 2019]ではDiscゲームというものを挙げています。
Discゲームでは2人のプレイヤーが$${xy}$$平面上における半径$${k}$$の円周上及び円内部からそれぞれ1点を同時に選びます。自分から見て反時計回り側の半円にある点に対しては勝ちとなり、時計回り側の半円にある点に対しては負けとなります（図左）。Discゲームの特殊なケースの1つがじゃんけんです（図右）。
現実のゲームは、Transitiveな面とNon-transitive（Cyclic）な面の両方を持っていると考えられます。
Non-transitiveなゲームにおける学習
Non-transitiveな性質が強いゲームにおける学習方法は、Transitiveなゲームにおけるそれとは異なります。
例えばTransitiveなゲームにおいて有効であるSelf-playでは、1ステップ前の自分に対しての学習を繰り返します。
oracleは相手$${\mathbf{v}_t}$$に対する最適反応（期待利得を最大化する戦略）を返す関数です。Self-playでは戦略のTransitivityを仮定している（$${\mathbf{v}_{t+1}}$$が$${\mathbf{v}_t}$$に勝てるということは、$${\mathbf{v}_{t+1}}$$は過去全ての$${\mathbf{v}_{t-1}}$$、$${\mathbf{v}_{t-2}}$$、…、$${\mathbf{v}_1}$$に勝てるということ）ため、（Self-playに限らず）個別の相手に対しての学習を繰り返すだけでは、Non-transitiveな性質が強いゲームにおいては戦略の強さのサイクルをぐるぐる回ってしまうだけで、Transitiveな観点での向上は見込めません。
戦略のサイクルに陥らないためには、単体の戦略に対してではなく、確率的な戦略（混合戦略）や戦略の集合に対する学習が必要になってきます。手法の例として、過去の戦略の平均に対しての学習を繰り返すFicticious self-play [Heinrich et al., 2015]、過去の戦略のNash均衡における最適反応に対しての学習を繰り返すPolicy Space Response Oracle-Nash（PSRO-Nash）[Balduzzi et al., 2019]、グラフを用いてそれらを一般化したアプローチであるInteraction Graph [Garnelo et al., 2021]などがあります。
また、Non-transitiveな性質をもつゲームではすべての戦略に勝るような単一の戦略というものは一般的に存在しません。そのため、単一の戦略を学習するのではなく、複数の戦略からなる集合を学習していくことも重要になってきます。前述のPSRO-Nash、Interaction Graphはこのカテゴリーにも入ります。また、戦略の集合を単一のニューラルネットで表現し、戦略間のパラメータを共有することでマルチタスク学習のような効果を生み出すNeural Population Learning [Liu et al., 2022]という手法もあります。これらの集合を学習していくアプローチは、そのままPopulation Learning、Population-based Learningなどと呼ばれたりします。（集合を学習した後、評価時に具体的にどの戦略を選ぶかについては未だopen questionのようです（参考：ICLRでの著者とレビュアーのやり取り））
またNon-transitiveなゲームにおける学習を抽象的な視点から考察した論文として[Czrnecki et al., 2020]があります。この論文では、Non-transitiveなゲームにおける戦略の集合を複数の排他的な部分集合（論文ではNash clusterと読んでいます）に分割し、そのCluster間の強さを（後述のRPPを用いて）比較することで、Non-transitiveなゲームもTransitiveな軸に落とし込めることを理論的に証明しています。
戦略の集合同士の強さの比較にはRelative Population Performance（RPP）[Balduzzi et al., 2019]と呼ばれる評価軸が使われることが多いです。求め方は単純で、2つの戦略の集合のNash均衡における期待利得がそのままRPPとなります。例えばじゃんけんで{チョキ、パー}と{グー}の場合では、Nash均衡は(パー、グー)となるので、RPPは正の値をとり（具体的な値は利得行列の設計による）ます。相手の集合内の要素に勝てる要素を持つ集合だとRPPは高くなります。
可視化
[Czarnecki et al., 2020]では、様々なゲームにおけるTransitivity・Non-Transitivityの可視化を行っています。
それぞれのゲームについてモンテカルロ木探索により約1000の戦略をサンプリングし、そのすべての戦略間での利得行列を計算しています。下の図の縦軸は各戦略のTransitiveな強さ（勝率）、横軸はそれぞれの勝率におけるNon-transitiveなサイクル（前述のCluster）の大きさを示しています。上段の3つは人間が実世界で娯楽として楽しむゲーム（OXゲーム、3x3の囲碁、StarCraft）、下段は主に研究目的で作成されたゲームです。
人間が娯楽として楽しむゲームでは、勝率が上がっていくにつれてサイクルが徐々に大きくなり、ある点をすぎると小さくなっていくというある程度共通した形状をとっています。論文ではこの形状を独楽の断面図に似ていることからSpinning Top（英語でこまに対応する単語）、もしくはGame of Skillと呼び、実世界のゲームで共通して見られる構造であると述べています。少し抽象的なものにはなりますが、下がGame of Skillの図（戦略の分布）です。
縦方向の軸はTransitiveな強さを表し、水平方向はNon-transitiveなサイクルの強さ（Nash clusterの大きさ）に対応します。ゲームにおいてプレイヤーが目指すのはTransitiveな観点での強さを高めていくことです。上の図で言えば、より上方の戦略を獲得していくことに当たります。Non-transitiveなゲームでは、特定の相手に勝てるようになったとしても、それはTransitiveな点で進歩しているとは限りません。上の図で言えば同じ高さでぐるぐるしているだけかもしれません。Non-transitiveなサイクルにはまることなくTransitiveな観点での強さを向上させていくためには、前述の集合を元にした考え方が重要になってきます。
また論文では、Transitiveな面とNon-transitiveな面は、人間がゲームを楽しむ上で、ともに大事な性質であるとも述べています。ゲームにおいて上達の喜びを得るためにはTransitiveな性質が必要であり、また同時にゲームが単調にならず多様性を持つためにはNon-transitiveな性質が重要と述べています。前者については確かにその通りであると思います。後者においても、例えば囲碁や将棋で、Transitiveには同じような強さである場合でも初手や戦略は人それぞれですし、逆にその辺りのパターンが少ないと、指す側にとっても見る側にとっても面白みに欠ける気はします。研究目的で作られたゲーム（図下段）の構造は（特にDisc GameとElo Gameについて）Game of Skillとは異なり、かなり極端なものとなっています。
終わりに
Non-transitiveな性質をもつゲームを扱っている論文をいくつか紹介しました。自分でもまだ理解しきれていない部分は多いのですが、Non-transitivityは重要な視点だと思うので、今後も追っていきたいと思っております。ちなみに今回挙げた論文のほとんどは（意図せずですが）著者の所属がDeepMindとなっておりました。
さいごに、Ideinではいろいろなエンジニアを募集しています！！
参考文献
J. Heinrich et al., Ficticious Self-Play in Extensive-Form Games. ICML, 2015. URL.
D. Balduzzi et al., Open-ended Learning in Symmetric Zero-sum Games. ICML, 2019. URL.
W. M. Czarnecki et al., Real World Games Look Like Spinning Tops. NeurIPS, 2020. URL.
M. Garnelo et al., Pick Your Battles: Interaction Graphs as Population-Level Objectives for Strategic Diversity. arXiv, 2021. URL.
S. Liu et al., NeuPL: Neural Population Learning. ICLR, 2022. URL.