Crushing or Crushed

主にShort-handed NLHEで自分が勉強したことについてまとめるブログです。

Poker AIからGTO学習パイプラインを知る

こんにちは。最近はポーカーそっちのけで理論の勉強ばかりしています。手段と目的が逆になってきている感がありますが、楽しいので良しとします。

今回はもうちょっとわかりやすい記事を。

 

昨今ディープラーニングや機械学習を用いたゲームAIが話題によく上がります。AIで倒すにはまだあと百年はかかるだろうといわれた囲碁でも去年、人類最強の囲碁プロAIにが完封されました。ポーカーシーンでもHeads-up No-limit Hold'emにおいてプロ相手に14.7bb/100handsという素晴らしい成績を残しています。 

                    f:id:alphanavis:20180625132253p:plain

 

今回はそのPoker AI "Libratus"の学習パイプラインを追って、私たちがGTOsolverをどのように解釈するべきなのかを学べたらと思います。

 

・参考文献

Superhuman AI for heads-up no-limit poker: Libratus beats top professionals
Science  17 Dec 2017:
eaao1733
DOI: 10.1126/science.aao1733

http://science.sciencemag.org/content/early/2017/12/15/science.aao1733.full

 

Libratusとは

2017年にカナダのカーネギーメロン大学が開発したポーカーAIです。LibratusとはLatin で”バランスのとれた”という意味らしいです。つまり、Libratusが目指すのは、完璧なバランスが取れた戦略---GTO---です。毎アクションごとにGTOsolverを回すのは時間の制約上困難であるため、彼らはそれを克服するようなモジュールを提案しています。

 

１．Libratus modulesの概要

f:id:alphanavis:20180625131321p:plain

Abstraction（抽象化）

まず初めにゲームの抽象化(Abstraction)を行います。ゲームの状態数があまりに膨大なので、似ているところはまとめてしまおうというコンセプトです。

抽象化は私たちが行っているGTOの体系化に少し似ています。

Eq. Finding（GTOの導出）

簡略したゲームに対してGTOSolverを用いて、ナッシュ均衡(Nash eq.)を求めます。

私たちで言うところのPioSolverやGTO+の計算と同じ。

Subgame Solver（部分ゲームに対するGTOを求める）

小さくしたゲーム空間でのナッシュ均衡と真のナッシュ均衡にはギャップがあります。より精度の良いNash eq.を求めるために、実際に行われているゲーム付近のゲーム木を再展開してNash eq.を求めなおします。

私たちで言うところの、気になったスポットをPIOにかけなおして、答えを確認する感じ。

Self-improver（強化学習）

抽象化したゲームにないような戦略をとられた場合、こちらはNash eq.を知らないので、相手にエクスプロイトされる可能性があります。なので、実際のゲームでとられた知らない戦略について、一日かけて計算しなおします。

私たちで言うところの、turnで200%のドンクを打たれたんだけど、どうすればよかったの？？？PIOに聞いてみよう。みたいな感じです。次からはそのような戦略に対する、反応を知っているので安心。

 

意外と人間と同じような考え方でmoduleが作られていますね。

 

２．ゲームの抽象化とGTOの導出

f:id:alphanavis:20180625133652p:plain

HU-NLHMではゲームの状態数（すべての場合の数）が ~10^{160}通りあるといわれています（定説ですが）。囲碁が ~10^{180} ですので、非常に大きいということがわかります。このすべての状態についてNash eq.を求めるのは非現実的です。なのでゲームを小さくしてあげることが必要になります。次に小さくしたゲーム空間のGTOを求めます。 \epsilon \mbox{ equilibrium}とは制約を緩くした状況下でのGTOのことです。PIOを使うときにも"Exploitable for 0.25% of the pot per hand (used pot size = 50)"といったように何%の誤差を許すかを指定すると思います。 \epsilonはその何％のところです。

\epsilon \mbox{ equilibrium}(Game Theory sub-Optimal)では実はプロに勝てませんでした。なので、turn以降のプレイをフルサイズのゲームツリーに展開して計算しなおします。 \epsilon \mbox{ equilibrium}が真のGTOに十分近いという仮定を利用すれば計算時間がいくつか削れるので、実際のプレイに使える時間内に計算を終わらせることができます。

以下に、実際に何が行われているのかと、私たちがブラックボックスとして使っているGTOsolverの計算が何を意味しているのかを簡単に説明します。

戦略集合の抽象化

f:id:alphanavis:20180625225500p:plain

実際のAの戦略はcheckから1$刻みで10000通りあります。しかし、400$と401$ベットの戦略に劇的な戦略の変化はあるでしょうか？計算コストを節約するためにこの誤差を許して500$刻みにするだけで10000通りあった戦略が20通りまで減ります。

PIOsolverでベットサイズを指定するのはこの作業をしているわけですね。使ったことがある方はわかると思いますが、ベットサイズを多く指定すればすれはするほど、計算時間がかなりかかります。私たちが導出しているGTOは部分ゲームのNash eq.だということを忘れないようにしましょう。

 

部分ゲーム(Subgame)

 ゲーム全体の中の一部のゲームのこと。実際のゲームではベットサイズ選択の幅がとても広いが、PIOに解かせているゲームはベットサイズが複数程度のもので、このゲームは全体のゲームの部分ゲームである。

 

状態集合の抽象化

f:id:alphanavis:20180625225517p:plain

上の図を見ていただくとAc5dとAs5dが同じグループに属しています。リバーのボードに対して、これらのカードの期待値と勝率はほとんど同じです（実は違うが説明のためにほとんど同じとする）。計算コストを削減するためにこれらのハンドを１グループにまとめています。

PIOで集合分析をする際のコンセプトと同じですね。体系化するために、A-high＋low-connectedボードや超ウェットなボードといったようにいくつフロップを指定して、OOPとIPのベット率、EVの分布を調べるといったことは大変有用です。しかし、カードの抽象化と同じように部分ゲームのNash eq.を導出しているということに気を付けましょう。

\epsilon \mbox{ Nash Eq.}

f:id:alphanavis:20180625225743p:plain

厳密なNash eq.を導出するには抽象化されたゲームに対しても状態数が多すぎて計算コストがかかってしまいます。なので制約を緩くしてGTOを求める必要があります。それが \epsilon \mbox{ Nash Eq.}です。

PIOを使うときにも"Exploitable for 0.25% of the pot per hand (used pot size = 50)"といったように何%の誤差を許すかを指定すると思います。 \epsilonはその何％のところです。私たちがPIOを使って求めているGTOはこの制約を緩くしているGTsO(Game Theory sub-Optimal)です。

GTOsolver algorithm

PIOの中身。Monte Carlo Counterfactual Regret Minimizationというアルゴリズムが使われています。アルゴリズムの説明は割愛。興味がある方はLibratusの論文に引用されている参考文献をチェックしてみてください。

Blueprint Strategy

f:id:alphanavis:20180625230015p:plain

さて、ゲームの抽象化、GTO導出アルゴリズムの選定が終わると実際にGTOを求めることになります。抽象化されたゲームに対するNash eq.の集合を、彼らはBlueprint Strategyと呼んでいます。Blueprintとは日本語で設計図という意味です。抽象化された部分ゲームのGTOなので”ラフ”(Rough)な戦略の集合です。実際このラフな戦略ではプロには勝てませんでした。。。

私たちがPIOで目指しているのはこのBlueprint strategyを組み立てる、ということになります。妥当性のあるフロップを選定することで、すきのないBlueprint Strategyを築いていきたいところですね。

 

３．Subgame SolverとSelf-improver

Blueprint Strategyでプロに勝てなかった原因は大きく2つあります。

  1. 完全な（もしくは十分な）戦略ではないため搾取可能。
  2. Blueprint Strategyにないような戦略をとられると、GTOが全く分からないので、めちゃくちゃな戦略をとってしまう。

１を解決するためには真のGTOに近いGTO戦略を導出する必要があります。そのために提案されたのがSafe Subgame Solvingです。

Safe Subgame SolvingとはBlueprint strategyが幾分かNash eq.に近いことを利用して，部分ゲームからゲーム木を再展開してNash eq.を解く方法です。ツリーの再展開にはAlphaGoでも用いられたMonte Carlo Tree Searchが採用されています。このアルゴリズムにより3bb/100handsのEVを改善しました。

 

２を解決するには、AIが持っている部分ゲームを拡張する必要があります。

f:id:alphanavis:20180626064914p:plain

人間側はBlueprintにないようなゲームを展開することで優位を築くことができます。水色の点線を実際にプレイされた手だとすると、AI側は一番近い、ノードに丸め込むしかありません。赤色が実際にAIがとる戦略です。赤色の戦略は水色のGTOではないので、人間側が正しくプレイするとAI側の-EVになります。

実際のゲームは20日間に渡って行われました。AIは自分が知らない戦略、相手がよくとった戦略を記憶しておきます。夜の間にその部分ゲームの均衡を計算して、Blueprintを強化していくことにより、相手に搾取されない戦略を築きました。

 

４．結果と考察

Libratusはプロ5人相手に戦い、誰一人としてプロは勝てませんでした。AIから観察された結果を考えることで、強いプレイヤーになるためにはどのような戦略をとればよいかがわかります。

Libratusの強みは

  1. 多くの異なったベットサイズの使い分け
  2. 正しいドンクベット
  3. ポット200%以上のベット

だそうです。弱みと言えば”相手の戦略から搾取しない”といったところでしょうか。しかしGTOでプレイすることで、プロ相手に14.7bb/100hands出しているので問題ないと思います。（レーキはなし）

 

５．おわりに

今回はAIのGTO学習パイプラインを追うことで、私たちが普段使っているGTOsolverでは何を解いているかということを理解しました。ブラックボックス的に使うのではなくある程度知っておかないと、GTOsolverを神格化してしまうので注意しましょう。