[DL輪読会]実世界のゲームにおける推移性と非推移性

DEEP LEARNING JP [DL Papers] 実世界のゲームにおける推移性と非推移性 Toru Fujino, UTokyo, SCSLab http://deeplearning.jp/ 1

• http://deeplearning.jp/

概要 • 実世界のゲームは推移性と非推移性の2つの軸から成 り立っている (という仮説). • 推移的なゲームを攻略するのは比較的簡単. • 非推移的なゲームを攻略するには, 少し工夫が必要. • 何らかの方法で推移的なゲームにcastする必要がある. • 実世界のゲームの戦略の分布を可視化してみると, 推 移性と非推移性に関して共通の構造（右図）がある ことがわかった。

書誌情報 • メインで読んだ論文 • W. M. Czarnecki et al. Real World Games Look Like Spinning Tops. arXiv. 2020 (DeepMind) • 補助的に読んだ論文 • D. Balduzzi et al. Open-ended Learning in Symmetric Zero-sum Games. ICML. 2019. (DeepMind) • 今回読めなかったけど, 関連しそうな論文 (両方DeepMind) • D. Balduzzi et al. Re-evaluating Evaluation. NeurIPS. 2018 • S. Omidshafiei et al. Navigating the Landscape of Games. arXiv. 2020.

目次 • ゲームにおける推移性と非推移性 • 推移的なゲームと非推移的なゲームにおける最適化アルゴリズム • 色々なゲームの推移性と非推移性の可視化 • ゲームの推移性と非推移性がゲームの面白さに与える影響 • まとめ

推移性 (律) とは • 定義 For all 𝑎, 𝑏, 𝑐 ∈ 𝑋, if 𝑎 𝑅 𝑏 and 𝑏 𝑅 𝑐, then 𝑎 𝑅 𝑐 • 例 • 選好における推移律 • りんごがみかんより好き, みかんがレモンより好き -> りんごがレモンより好き • ゲームの戦略の強さにおける推移律 • 戦略Aが戦略Bよりも強い, 戦略Bが戦略Cよりも強い -> 戦略Aが戦略Cよりも強い

ゲームにおける推移性 • 実世界のゲームでは, 戦略の強さにおいて必ずしも推移律が成り立つわけではな い. • 非推移性 • 完全に非推移的なゲーム • じゃんけん • はさみは紙に勝つ, 紙は石に勝つ, でもはさみは石に勝てない. • 実際のゲームは, 完全に推移的なゲームと完全に非推移的なゲームの間にある. • チェス • 碁 • StarCraft

関数形によるゲームの定式化 [Balduzzi et al. 2019] • プレイヤー数が2人のゼロサム・ゲームは, 両プレイヤーの戦略を入力として受 け取り勝敗結果を出力とする関数とみなすことができる. • Functional-form games (FFGs) によるゲームの定式化 • v, wはニューラルネットのパラメータなど.

関数形による推移的なゲームの定式化 [Balduzzi et al. 2019] • ゲームが推移的であるとき, 戦略の強さを表すrating関数f が存在し, その引き算 によりゲームの勝敗を求めることができる. • 推移的なゲームを一般化したものは単調な (monotonic) ゲームと呼ばれる. • σは何らかの単調増加関数.

関数形による非推移的なゲームの定式化 [Balduzzi et al. 2019] • 非推移的 (non-transitive) なゲームでは, すべての戦略vに対してかならず対抗 戦略が存在し, その積分はゼロとなる. • つまり, どんな戦略も総合的に見れば引き分け.

非推移的なゲームの例: Discゲーム [Balduzzi et al. 2019] • 半径kの円の円周及び内部の一つの点を選ぶゲーム. • どの点を選んでも平均的にはドローになる. • Discゲームの特殊なケースがじゃんけん.

目次 • ゲームにおける推移性と非推移性 • 推移的なゲームと非推移的なゲームにおける最適化アルゴリズム • 色々なゲームの推移性と非推移性の可視化 • ゲームの推移性と非推移性がゲームの面白さに与える影響 • まとめ

完全に推移的なゲームは単一の相手に対して最適化することで解ける • 推移的なゲームの定義 (再掲) • 勝敗を決めるφを最大化すればよい. • φを最大化するにはf(v)を最大化すれば良い. • 相手wは何でも良い.

単調なゲームで単一の相手に最適化すると勾配が消失してしまう • 単調 (monotonic) なゲームの定義 (再掲) • 単調なゲームの例: Elo • 戦略の強さの差が大きなときに勾配が消失して学習が進まなくなる.

単調なゲームではSelf-playが有効 • だんだんと強い相手に対して最適化する必要がある. • Self-play • 過去の自分に対して勝てるように最適化していく. • AlphaZero [Silver et al. 2018] が用いた手法.

非推移的なゲームでは (単純な) self-playがうまく機能しない • Self-playはゲームの推移性を仮定している. • が に勝てるということは, るということ. は過去全ての • しかし非推移的なゲームではこれが成り立たない. • なので, ナイーブなself-playはうまく機能しない. に勝て

実際のゲームは推移性と非推移性の2つの軸を持つ [Czarnecki et al. 2020] • Games of Skill仮説. • ゲームの戦略の分布を可視化すると右図の 様になる, という仮説. • 縦軸が推移性, 横軸が非推移性を表す. • 下の方の層では, 強い非推移性が見られる. • 同じくらいの強さの多様な戦略が存在する. • わざと負ける戦略も一番下に存在する. • 層が上がっていくにつれて非推移性の程度 は弱くなっていく.

非推移性を持つゲームで勝つために考えるべきこと • プレイヤーが目指すものは推移的な強さを高めて いくこと. • 右の図で言えばより上にある戦略を獲得していくこ と. • 特定の相手に勝てるようになったとしても, それ は推移的な観点からは進歩していない可能性があ る. • 右の図で言えば同じ高さでぐるぐるしているだけか もしれない. • 非推移性のサイクルにはまることなく, 推移的な 強さを向上させていく必要がある.

k-layered finite Game of Skill [Czarnecki et al. 2020] • まずは単純化したケースを考えてみる. • 戦略の集合がk個の層に分解でき, それぞれの相 関では推移性が成り立つ場合. • 同じ層の中では非推移性が成り立つ. • 推移性の観点では同じ強さだが, それぞれ相性 の善し悪しがある.

Population-basedの最適化 [Czarnecki et al. 2020] • 単一の相手ではなく, 戦略の集合に対して最適化を繰り返す方法. • 最初の戦略の集合のサイズを 層のサイズよりも 大きく設定することで, 非推移的な戦略の集合を包含することがで きる. • こうすることで, 新しく生成されていく戦略が「ある層のすべての戦 略に勝る戦略である」ことが保証される.

Nash clusteringの導入 [Czarnecki et al. 2020] • 実際のゲームはk-layered Games of Skillのようにきれいな層に分けることはで きない. • 層間に戦略の非推移性が存在する. • Nash clustering • 戦略の集合から, エントロピーが最大となるNash均衡を構成する戦略のクラスター ( 集合) を順に取り出していく. • 取り出したクラスターを順に並べたとき, このクラスター (集合) 間では推移的な関 係が成り立っている (理由は後述). • (C1, C2, ..., CN)

Population-baseの評価 [Balduzzi et al. 2019] • クラスター (集合) 間での強さの比較をするために, 集合baseの評価尺度を導入 する. • Relative population performance (RPP) • Aは2つの戦略の集合間の利得行列. • 2つの戦略の集合間のNash均衡における利得値.

RPPの計算例: じゃんけん • じゃんけんの利得行列 • RPP({石, はさみ}, {石}) の場合, RPPはゼロ. • RPP({石, はさみ, 紙}, {石}) の場合, RPPはε^2 • 相手の集合内の要素に勝てる要素をもつ集合だとRPPは高くなる. • 集合のサイズが大きくなるほどRPPは高くなる.

RPPを用いたNash clusteringの推移的な強さの比較 • Nash clusteringでは, 先に抽出されたクラスター (集合) ほどRPPの観点では強 い集合となっている.

Population-baseの最適化により, Nash clusteringの観点で推移的な進歩 が保証される [Czarnecki et al. 2020] • 各iterationのpopulationに少なくともNash clusterが一つ含まれていれば, 次の iterationでより強いclusterの戦略が追加される. • つまり各iterationでclusterが包含されるくらいの大きなpopulationで学習させれば, 推移的な観点から強くなっていくことができる (たぶん). • 証明はよくわからず. • AlphaStar [Vinyals et al. 2019] でも (非明示的に) 同様のアイデアが使用され ている.

目次 • ゲームにおける推移性と非推移性 • 推移的なゲームと非推移的なゲームにおける最適化アルゴリズム • 色々なゲームの推移性と非推移性の可視化 • ゲームの推移性と非推移性がゲームの面白さに与える影響 • まとめ

サンプリングによるGames of Skillの検証 • 実際のゲームがGames of Skillのような形状を持つのかを検証する. • OXゲーム, 囲碁 (3x3, 4x4), StarCraft, Discゲーム, etc. • それぞれのゲームにおいて, 推移的な強さの異なる戦略をモンテカルロ木探索に よりサンプリング. • そしてそれぞれの戦略に対してランダムシードを変えることにより多様な戦略を 複製. • そしてすべての戦略間の利得行列を作成し, Nash clustering等を求める.

実世界のゲームはGames of Skillに似た形状を持つ • 縦軸は勝率, 横軸はNash clusterの大きさ • Games of Skill仮説に沿った形の戦略の分布が見られる. • 推移的な強さが向上するにつれて非推移性が弱くなっている.

人工的なゲームはGames of Skillの形をしていない • Disc Game: 非推移的なゲーム • Elo Game: 単調 (Monotonic) なゲーム • Blotto: 非推移的な資源配分ゲーム • 2人のプレイヤーが一定量の資源を決められた数の区画に自由に割り当てる. • それぞれの区画において資源を多く配分したプレイヤーがその区画を獲得する. • 獲得した区画の数が多い方のプレイヤーの勝ち.

Populationサイズが学習に与える影響 • 様々なPopulationサイズに対して最適化をかけたときの, 推移的な強さの変遷. • Populationサイズが小さいときは強くならず, populationサイズをある程度大きくす ることによりで推移的な進歩が見られるようになる.

目次 • ゲームにおける推移性と非推移性 • 推移的なゲームと非推移的なゲームにおける最適化アルゴリズム • 色々なゲームの推移性と非推移性の可視化 • ゲームの推移性と非推移性がゲームの面白さに与える影響 • まとめ

ゲームにおける推移性は成長の喜びを与えてくれる • プレイヤーは練習を積むことでスキルが向上し, 今まで倒せなかった強いプレイ ヤーを倒すことができるようになる. • プレイヤーは成長を感じることができる. • 成長を感じられるからこそ, 人間はゲームにはまっていく. • 逆にいくら練習しても進歩が感じられないゲームには, 人間ははまれない.

ゲームにおける非推移性は戦略の多様性をもたらす • 推移的な観点では同じくらいの強さでも, それぞれの強さ・弱さを持った多様な スタイルが存在する. • チェスや囲碁では, 序盤に様々なパターンの手が打たれる. • それぞれに強み・弱みがある. • ただ総合的に見れば, どれが一番良いと言うことはできない. • 逆に皆が同じようにプレイするゲームはあまり面白くない.

目次 • ゲームにおける推移性と非推移性 • 推移的なゲームと非推移的なゲームにおける最適化アルゴリズム • 色々なゲームの推移性と非推移性の可視化 • ゲームの推移性と非推移性がゲームの面白さに与える影響 • まとめ

まとめ • 実世界のゲームは推移性・非推移性両方の性質をもつ. • ゲームの推移性・非推移性を知ることは, うまく動くアルゴリズムの構築に役立 つ. • 推移的なゲームは比較的シンプルなアルゴリズムで解ける. • 非推移性を持つゲームは何らかの方法で推移的なゲームにcastしてから最適化してい く必要がある. • ゲームが面白くあるためには推移性・非推移性両方の性質が必要. • 推移性があるからスキルが向上する. • 非推移性があるから多様なプレイスタイルが生まれる.

参考文献 • [Silver et al. 2018] A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science. 2018. • [Vinyals et al. 2019] Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature. 2019. • [Balduzzi et al. 2019] Open-ended Learning in Symmetric Zero-sum Games. ICML. 2019. • [Czarnecki et al. 2020] Real World Games Look Like Spinning Tops. arXiv. 2020.