![多?数不完全情報ゲームに対するア
プローチ
■ そもそも，多?数不完全情報ゲームにおける，最適な戦略（政策）とは??
■ 強化学习的な観点で考えると．．．
– 期待利得を最?化 : ?"[∑%&'
(
?%
?%]
– ??プレイヤ
■ 利得関数や状態遷移確率が固定の場合，期待利得は戦略のみに依存
– 多?数
■ 利得が相?のプレイヤの戦略にも依存
■ 相?が取ってくる戦略はわからないので，どうやって最適であることを
定義する??](https://image.slidesharecdn.com/rlarch20190820-190821031739/85/AI-7-320.jpg)
![[DL輪読会] マルチエージェント強化学习と心の理論](https://cdn.slidesharecdn.com/ss_thumbnails/0917imai-211210044729-thumbnail.jpg?width=560&fit=bounds)
![SSII2021 [TS2] 深層強化学习 ? 強化学习の基礎から応用まで ?](https://cdn.slidesharecdn.com/ss_thumbnails/ts2-01-210607042910-thumbnail.jpg?width=560&fit=bounds)
![SSII2021 [OS2-01] 転移学习の基礎：異なるタスクの知識を利用するための機械学习の方法](https://cdn.slidesharecdn.com/ss_thumbnails/os2-02final-210610091211-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (20)
More from Kenshi Abe (6)
多人数不完全情報ゲームにおけるAI ~ポーカーと麻雀を例として~
- 2. ??紹介 ■ 名前 – 阿部 拳之（あべ けんし） – @bakanaouji（ばかなおうじ） ■ 経歴 – 東京?業?学総合理?学研究科知能システム科学専攻（?2017年） ■ 強化学习×進化計算をメインに研究 – 株式会社ハル研究所（2017年?2018年） ■ ゲームプログラマー – 株式会社サイバーエージェント アドテク本部 AILab（2018年?） ■ 強化学习?機械学习×?雀AIについて研究
- 4. Summary 1. ポーカー础滨の実例 – ??零和不完全情報ゲームの攻略 – 三?以上のプレイヤが存在する不完全情報ゲームへの挑戦 2. ?雀础滨の実例 – 主流のアプローチの紹介 ※本?の発表は強化学习ではなく，ゲーム理論寄りのアプローチの話がほとんどに なります
- 5. ポーカー础滨の実例
- 7. 多?数不完全情報ゲームに対するア プローチ ■ そもそも，多?数不完全情報ゲームにおける，最適な戦略（政策）とは?? ■ 強化学习的な観点で考えると．．． – 期待利得を最?化 : ?"[∑%&' ( ?% ?%] – ??プレイヤ ■ 利得関数や状態遷移確率が固定の場合，期待利得は戦略のみに依存 – 多?数 ■ 利得が相?のプレイヤの戦略にも依存 ■ 相?が取ってくる戦略はわからないので，どうやって最適であることを 定義する??
- 8. ??零和不完全情報ゲームにおける 最適な戦略 ■ ナッシュ均衡 – どのプレイヤも?分の戦略を変更することによって，より?い利得を得るこ とができないような戦略の組み合わせ ■ 直感的には，それぞれのプレイヤが?分だけ戦略を変えることのメリッ トがない状況 – 各プレイヤ?の戦略を?.，利得を?.とすると，ナッシュ均衡戦略の組み合わせ ??は以下の式を満たす ??, ?. ?. ? , ?3. ? = max 89 :∈<9 ?.(?. > , ?3. ? ) ■ ??零和不完全情報ゲームでは，ナッシュ均衡戦略を最適戦略とすることが多い ?@ ?@ ? , ?A ? = max 8B :∈<B ?@(?@ > , ?A ? ) , ?A ?@ ? , ?A ? = max 8C :∈<C ?A(?@ ? , ?A > )
- 9. なんでナッシュ均衡戦略に従うこと が良い?? ■ 相?の戦略?Aがわかっている場合??? – ?Aに対する最適応答?? ?A に従えば，?分の利得をナッシュ均衡に従った場 合の利得以上にできる ?? ?A = argmax 8B :∈<B ?(?@ > , ?A) →ナッシュ均衡でなく最適応答に従ったほうが良いのでは??
- 10. なんでナッシュ均衡戦略に従うこと が良い?? ■ 相?の戦略?Aがわかっている場合??? – ?Aに対する最適応答?? ?A に従えば，?分の利得をナッシュ均衡に従った場 合の利得以上にできる ?? ?A = argmax 8B :∈<B ?(?@ > , ?A) →ナッシュ均衡でなく最適応答に従ったほうが良いのでは?? ■ しかし，実際には相?の戦略はわかっていないことが多い – 相?が実際には?Aに従ってこなかった場合，?分の利得が?@ ?@ ? , ?A ? より少な くなる可能性がある ■ ナッシュ均衡に従った場合??? – 相?の戦略に関係なく?分の利得を?@ ?@ ? , ?A ? 以上にすることができる →利得の損失を最?限に抑えられる →対称性があるゲームの場合は負けない戦略
- 11. ナッシュ均衡戦略の計算 ■ ゲームの状態数が?きい場合，厳密なナッシュ均衡戦略の計算は難しい．．． – ポーカーで?うと??? – Heads up Limit Texas Hold’em : 約10@I – Heads up No-limit Texas Hold’em : 約10@J' ■ できる限りナッシュ均衡戦略に近い戦略を求める – 代表的なアルゴリズム?Counterfactual Regret Minimization (CFR)
- 12. Counterfactual Regret Minimization ■ 基本的な流れ – 「この?を取ったほうが良かった」という後悔 (regret) を元に戦略を更新す ることで，（平均）戦略をナッシュ均衡へ近づけていく ■ Counterfactual Regret ?. % ?, ? = ?3. 8O ? (?. ?P→R % , ? ? ?. ?%, ? ) – 「現在の戦略?%を情報集合?において?動?を取るように変更したら，どれ だけ利得が増えるのか」を定式化 A B B B グー チョキ パー 情報集合? Regret Minimization in Games with Incomplete Information (2008) https://papers.nips.cc/paper/3306-regret-minimization-in-games-with-incomplete-information
- 13. Counterfactual Regret Minimization ■ 基本的な流れ – 「この?を取ったほうが良かった」という後悔 (regret) を元に戦略を更新す ることで，（平均）戦略をナッシュ均衡へ近づけていく ■ Counterfactual Regret ?. % ?, ? = ?3. 8O ? (?. ?P→R % , ? ? ?. ?%, ? ) – 「現在の戦略?%を情報集合?において?動?を取るように変更したら，どれ だけ利得が増えるのか」を定式化 A B B B グー チョキ パー グーを出すようにしたら， どれくらい得かな．．．
- 14. Counterfactual Regret Minimization ■ Cumulative Counterfactual Regret ?. ( ?, ? = T %&@ ( ?. % (?, ?) ■ Cumulative Counterfactual Regretに基づいて，戦略を更新 ?. (U@ ?, ? = max(?. ( ?, ? , 0) ∑R∈V(P) max(?. ( ?, ? , 0) , ?? T R∈V(P) max(?. ( ?, ? , 0) > 0 1 |? ? | , ????????? ■ ? = 1, ? , ?までの戦略?. % を平均化した戦略がナッシュ均衡戦略へと収束 – ただし，??零和不完全情報ゲームのみ保証 – 三?以上では収束性の証明はされていない
- 15. Counterfactual Regret Minimization ■ アルゴリズム概要 1. ある情報集合?に対して，以下の２つの価値を計算 今の戦略の期待利得? ?. ?%, ? ”?において?動?を取るように変えた戦略”の期待 利得??. ?P→R % , ? 2. ?. ?%, ? ， ?. ?P→R % , ? を元に，regretを計算 3. Regretを元に，戦略を更新 A B B B 今の戦略の期待利得 : ?. ?% , ? ? ? ?
- 16. Counterfactual Regret Minimization ■ アルゴリズム概要 1. ある情報集合?に対して，以下の２つの価値を計算 今の戦略の期待利得? ?. ?%, ? ”?において?動?を取るように変えた戦略”の期待 利得??. ?P→R % , ? 2. ?. ?%, ? ， ?. ?P→R % , ? を元に，regretを計算 3. Regretを元に，戦略を更新 A B B B 今の戦略の期待利得 : ?. ?% , ? ? ? ? ?. ( ?, ? = 2 ?. ( ?, ? = 0 ?. ( ?, ? = 1
- 17. Counterfactual Regret Minimization ■ アルゴリズム概要 1. ある情報集合?に対して，以下の２つの価値を計算 今の戦略の期待利得? ?. ?%, ? ”?において?動?を取るように変えた戦略”の期待 利得??. ?P→R % , ? 2. ?. ?%, ? ， ?. ?P→R % , ? を元に，regretを計算 3. Regretを元に，戦略を更新 A B B B 今の戦略の期待利得 : ?. ?% , ? ? ? ? ?. ( ?, ? = 2 ?. ( ?, ? = 0 ?. ( ?, ? = 1 ?. (U@ (?)を(2/3, 0, 1/3)に更新
- 18. Counterfactual Regret Minimization ■ さらに?速化したアルゴリズムCFR+によって，10@I 程度の情報集合数を持つ ゲームにおいて収束できるように ■ Heads up Limit Texas Hold’em（情報集合数?約10@I）はほぼ攻略?? ■ しかしHeads up No-limit Texas Hold’em（情報集合数?約10@J'）はまだまだ遠 い．．． →戦略ベクトルをPCに保持できるような容量ですらないので，そもそも戦略を 求めようとすることが現実的ではない →ゲームを抽象化 (abstraction) して，情報集合数を現実的なサイズまで減らす Solving Heads-up Limit Texas Hold’em (2015) https://poker.cs.ualberta.ca/publications/2015-ijcai-cfrplus.pdf
- 19. Abstraction ■ ゲームを抽象化することによって情報集合数を削減 ■ Domainに関する知識を使って設計するのが基本 ■ ポーカーにおけるabstractionの例 – ベッドできる?額を制限する（action abstraction） – 同じような強さの?札は同?のグループとして扱う（information abstraction） 1. Abstractionを?いてゲームを抽象化 2. CFRなどで抽象化したゲームのナッシュ均衡戦略を計算 3. 実際のプレイ時に抽象化ゲームのナッシュ均衡戦略を?いる というのが主流に
- 20. Abstraction ■ ただし，当然抽象化しすぎると元のゲームと剥離しすぎてしまう ■ 直感的には，抽象化をしないほど元のゲームにおけるナッシュ均衡戦略と近い 戦略が得られそう ■ ??で，抽象化しないと状態集合数を減らせない →どうする??
- 21. Libratus ■ Heads up No-limit Texas Hold’emにおいて初めてプロに圧勝し，話題となった ■ Abstractionによって抽象化したゲームにおける戦略を実際のプレイ中に改善 ■ 戦略改善の流れ 1. 予めAbstractionによって抽象化したゲームのナッシュ均衡戦略を計算して おく 2. 実際のプレイ中に抽象度を細かくしたSubgameにおける戦略を計算，その 戦略に従って?動 Superhuman AI for heads-up no-limit poker- Libratus beats top professionals (2018) https://science.sciencemag.org/content/359/6374/418.abstract
- 22. Subgame Solving ■ 完全情報ゲーム – 任意の意思決定点での最適な戦略を得るには，それ以下のSubgameのみを 解けば良い – 例?モンテカルロ?探索 – Subgameのみで解けるとゲーム?の状態数が少ない →状態数が少なくなるとAbstractionの必要がなくなるので，嬉しい →不完全情報ゲームでも同じことをしたい?? ■ 不完全情報ゲーム – ?分がどの意思決定点にいるのか，ということが不確定 – 最適な戦略が到達しなかった他のサブゲームの利得に依存することがある – Subgameを独?で解けば良いというものではない．．． →この問題を解決するのがSubgame solving A B B B 今このノードにいることが完全にわかっている場合， それ以降のSubgameを解けば良い
- 23. Subgame Solving ■ 完全情報ゲーム – 任意の意思決定点での最適な戦略を得るには，それ以下のSubgameのみを 解けば良い – 例?モンテカルロ?探索 – Subgameのみで解けるとゲーム?の状態数が少ない →状態数が少なくなるとAbstractionの必要がなくなるので，嬉しい →不完全情報ゲームでも同じことをしたい?? ■ 不完全情報ゲーム – ?分がどの意思決定点にいるのか，ということが不確定 – 最適な戦略が到達しなかった他のサブゲームの利得に依存することがある – Subgameを独?で解けば良いというものではない．．． →この問題を解決するのがSubgame solving A B B B どこにいるかわからない???
- 24. LibratusにおけるSubgame Solving ■ Subgame solvingによって得た戦略が元の戦略よりも改善することが保証 – 抽象化したゲームにおけるナッシュ均衡戦略よりも良い戦略が得られる ■ アルゴリズム – Subgameから”opt out”する?動を追加したaugmented subgameを?成 ■ “opt out”に対する利得はreach marginと呼ばれる値によって決定 – Augmented subgameにおけるナッシュ均衡戦略をCFRなどで計算
- 25. どのタイミングでSubgame solvingし なおすか?? ■ 3回?のベッティングラウンド到達時や，残りのゲームのサイズが?さ い意思決定点に到達時 – 抽象度を低くして，戦略を計算しなおす ■ 相?がabstractionの範囲外の?動を取ってきたとき – 例?抽象化したゲームではベッド額を$100または$200に制限して いたのに，相?が実際のプレイで$150ベッドしてきた – 従来のアプローチでは$100か$200として丸めこんだ値として扱う ことが主流 (action translation) – Libratusでは，範囲外の?動を相?が取ってくるたびに，その?動を 含むSubgameを?成，それを解いて戦略を計算しなおす Safe and Nested Subgame Solving for Imperfect-Information Games (2017) https://arxiv.org/abs/1705.02955
- 26. Libratusの結果 ■ プロ vs Libratus – プロ相?に?い勝率 -200 -100 0 100 200 300 400 0 30000 60000 mbb/game Games pl Cumulative mbb/g -100 -50 0 50 100 150 200 250 300 0 30000 60000 90000 120000 mbbx106 Games played Cumulative mbb Fig. 3. Libratus performance against top humans. Shown are the results of the 2017 Brains vs. Artificial Intelligence: U RESEARCH | RESEARCH ARTICLE
- 27. Libratusまとめ 1. 予めAbstractionによって抽象化したゲームのナッシュ均衡戦略を計算しておく 2. 実際のプレイ中に，今の意思決定点からSubgameを?成 3. Subgameの抽象度を低くしていくことで，より実際のゲームに対するナッシュ 均衡に近い戦略を計算
- 29. 三?以上の零和不完全情報ゲームの 難しさ ■ ??零和ゲーム – CFRにおける平均戦略がナッシュ均衡戦略に収束する保証がある – ナッシュ均衡戦略に従っていれば?分の損失を最?限に抑えることができ る ■ 三?以上の零和ゲーム – CFRにおける平均戦略がナッシュ均衡戦略に収束する保証がない – ナッシュ均衡戦略に従うことが良いことなのかすら怪しい
- 30. 三?以上の零和不完全情報ゲームの 難しさ < ?@@ ? , ?A@ ? > < ?@A ? , ?AA ? > < ?@@ ? , ?AA ? > ナッシュ均衡その1 ナッシュ均衡その2 これもナッシュ均衡 ■ ナッシュ均衡は戦略の組み合わせであり，その組み 合わせはいくつか存在 ■ ??零和ゲーム – 各プレイヤが独?にナッシュ均衡戦略を選択し たとしても，両プレイヤの戦略の組み合わせは ナッシュ均衡となる ■ 三?以上の零和ゲーム – 各プレイヤが独?にナッシュ均衡戦略を選択し た場合，全プレイヤの戦略の組み合わせはナッ シュ均衡ではない可能性がある – ナッシュ均衡戦略に従っているのに戦略を変え たほうがメリットがある可能性がある →ナッシュ均衡戦略でも負ける可能性が???
- 31. 三?以上の零和不完全情報ゲームの 難しさ ■ ナッシュ均衡は戦略の組み合わせであり，その組み 合わせはいくつか存在 ■ ??零和ゲーム – 各プレイヤが独?にナッシュ均衡戦略を選択し たとしても，両プレイヤの戦略の組み合わせは ナッシュ均衡となる ■ 三?以上の零和ゲーム – 各プレイヤが独?にナッシュ均衡戦略を選択し た場合，全プレイヤの戦略の組み合わせはナッ シュ均衡ではない可能性がある – ナッシュ均衡戦略に従っているのに戦略を変え たほうがメリットがある可能性がある →ナッシュ均衡戦略でも負ける可能性が??? < ?@@ ? , ?A@ ? , ?i@ ? > < ?@A ? , ?AA ? , ?iA ? > < ?@@ ? , ?AA ? , ?ii ? > ナッシュ均衡その1 ナッシュ均衡その2 < ?@i ? , ?Ai ? , ?ii ? > ナッシュ均衡その3 ナッシュ均衡??
- 32. 三?以上の零和不完全情報ゲームの 難しさ ■ 三?以上の零和ゲーム – CFRがナッシュ均衡に収束するかも保証されていない – そもそもナッシュ均衡戦略に従うのがいいのかすらも怪しい →では，どんな戦略に従うのが良いのか?? ■ 実?的には，三?以上の零和ゲーム（主にポーカー）にCFRを適?するだけで ある程度強い戦略はできるらしい – この実験的な事実を利?したのが2019年登場のPluribus
- 33. Pluribus ■ 6?プレイヤのHeads up No-limit Texas Hold’emでプロを超えた ■ 基本的な考え? – 最初にある程度の戦略をCFRによって計算しておき，それを実際のプレイ中 に改善していけばよいのでは? →やりたいことはLibratusとほぼ?緒 ■ やってることもLibratusと似ている 1. 予めCFRによってある程度の強さの戦略を計算しておく 2. 実際のプレイ中にSubgameに対してCFRを適?し，戦略を逐?計算 ■ Libratusとの主な差分 – プレイヤの数が増えて状態数も膨?な数になるので，実際のプレイ中に戦 略を計算することが厳しい – 深さ制限探索で探索するノード数を減少 Superhuman AI for multiplayer poker (2019) https://science.sciencemag.org/content/early/2019/07/10/science.aay2400
- 34. Depth Limited Search 1. ある深さのノード（葉ノード）に到達するまでは通常 と同様に探索 2. 葉ノードに到達したらノードのvalueを推定 – Monte Carlo Rolloutによって推定 – 予め計算しておいたk = 4個の戦略の中から戦略を 選択，葉ノード以降はその戦略に従って?動 ■ 単純なblueprint戦略 ■ 降りることに特化したblueprint戦略 ■ コールすることに特化したblueprint戦略 ■ レイズすることに特化したblueprint戦略 – ノードのvalueが戦略に依存したものであることを 近似的に表現 Fig. 4. Real-time search in Pluribus. The subgame sh nodes indicates that the player to act does not know w information subgame. Right: The transformed subga strategy. An initial chance node reaches each root nod reached in the previously-computed strategy profile (o time in the hand that real-time search is conducted). T which each player still in the hand chooses among k chooses. For simplicity, 2k = in the figure. In Pluribu selection of a continuation strategy for that player f terminal node (whose value is estimated by rolling continuation strategies the players chose). Fig. 4. Real-time search in Pluribus. The subgame shows just two players for simplicity. A dashed line between nodes indicates that the player to act does not know which of the two nodes she is in. Left: The original imperfect- information subgame. Right: The transformed subgame that is searched in real time to determine a player’s
- 35. Pluribusの結果 ■ 5?のプロ vs Pluribus – プロ相?に?い勝率?? – （実際には負けているケースもある）
- 36. ?雀础滨の実例
- 37. ?雀AIの研究 ■ ポーカーと違い，?本くらいでしか研究が?われていない – ?雀が世界的に?るとメジャーでなく，国ごとにルールが微妙に違 うのが原因?? ■ 主なアプローチ – 教師あり学习 – プレイ中のシミュレーションによる?の決定 – 最近では，MDPとして定式化してvalueが?い?を選択する?法も ■ 強化学习やゲーム理論によるアプローチはほとんど存在しない – POMDPかつマルチエージェントなので，学习が?常に難しい．．．
- 38. 教師あり学习×?雀AI ■ 捨て牌選択などを牌譜データから教師あり学习させるのが主流 ■ 最近では，CNNをモデルとして?いることによって上級者との捨 て牌の?致率が68%程度まで向上 ? この局?では何捨てる?? ? ポンする?しない?? ? チーする?しない?? Building a computer mahjong player based on monte carlo simulation and opponent models (2015) https://ieeexplore.ieee.org/document/7317929 Supervised Learning of Imperfect Information Data in the Game of Mahjong via Deep Convolutional Neural Networks (2018) https://ipsj.ixsq.nii.ac.jp/ej/index.php?active_action=repository_view_main_it em_detail&page_id=13&block_id=8&item_id=192052&item_no=1
- 39. 教師あり学习×?雀AI ■ 天鳳の上位陣の?を模倣するように学习 ■ 天鳳から牌譜データをスクレイピング →学习?データとして加?処理 →教師あり学习 牌譜データ 加? 学习?データ スクレイピング 学习
- 40. プレイ中のシミュレーションによる 捨て牌選択 ■ “Building a computer mahjong player based on monte carlo simulation and opponent models (2015)”にて提案 ■ 捨て牌選択における各?動に対する得点をモンテカルロシミュレーションに よって推定 – 各牌を捨てる?動 – 降りる?動（絶対放銃しないと仮定）TABLE VI. EVALUATION OF SCORE PREDICTION Player Mean square error Prediction model 0.37 -Revealed Melds 0.38 -Revealed fan value 0.38 Expert player 0.40 A. Game records for training D? ???? ??? s?????? ???? Fig. 1. Overview of Monte Carlo moves Building a computer mahjong player based on monte carlo simulation and opponent models (2015) https://ieeexplore.ieee.org/document/7317929
- 41. プレイ中のシミュレーションによる 捨て牌選択 ■ シミュレーション中の挙動 – ?分の?番 ■ 各牌を捨てた局?からシミュレーション ■ 降りる?動に対しての場合，?から牌を へらすだけで牌は捨てない – 相?の?番 ■ 具体的な?牌は持たずに学习済みのモデ ルに基づいて遷移を決定 – 聴牌状態へ移?する確率分布 – 降り状態へ移?する確率分布 – ツモ?ロン上がりする確率分布 ■ 捨て牌は?からのツモをそのまま捨てる ining a player has won in the game records, mple by using the score and creating ting the information available to the number of states is about 5.92 × 107 . g scores re of a hand basically increases ex- o the fan7 value of the hand. We regression model that predicts the actual score in the training data. es used in the model. Examples of the Fig. 1. Overview of Monte Carlo mov
- 42. プレイ中のシミュレーションによる 捨て牌選択 ■ シミュレーション中の挙動 – ?分の?番 ■ 各牌を捨てた局?からシミュレーション ■ 降りる?動に対しての場合，?から牌を へらすだけで牌は捨てない – 相?の?番 ■ 具体的な?牌は持たずに学习済みのモデ ルに基づいて遷移を決定 – 聴牌状態へ移?する確率分布 – 降り状態へ移?する確率分布 – ツモ?ロン上がりする確率分布 ■ 捨て牌は?からのツモをそのまま捨てる he game records, ore and creating available to the bout 5.92 × 107 . ly increases ex- the hand. We hat predicts the e training data. Examples of the d melds and the Fig. 1. Overview of Monte Carlo moves
- 43. MDPとしての定式化 ■ “Method for constructing artificial intelligence player with abstraction to markov decision processes in multiplayer game of mahjong (2019)”にて提案 ■ ?雀を抽象化したゲームをMDPとして定式化 – 降りる戦略や，聴牌に向かう戦略をプレイヤが取ったときのダイナミクス をそれぞれ定式化 – MDP内の状態遷移確率は実際のデータを元にlogistic regressionでモデル化 ■ MDPから導出した価値関数から，どの?動を取るべきかを決定 Method for constructing artificial intelligence player with abstraction to markov decision processes in multiplayer game of mahjong (2019) https://arxiv.org/abs/1904.07491
- 44. まとめ ■ 多?数不完全情報ゲームはかなりの速度で攻略されてきている ■ ゲーム理論を元にしたアプローチが現状では強い – しかしAbstractionなどでドメイン知識を多く使っている ■ 多?数不完全情報ゲームでは強化学习は??った成果がない – POMDPや相?の戦略の流動性をどう対処するかが鍵