メむンコンテンツぞスキップ
芋出し画像

Solverの仕組みCFRずは䜕か

     ポヌカヌ゜ルバヌの内郚で䞀番よく䜿われおいるアルゎリズムのひず぀が、CFRCounterfactual Regret Minimizationです。
     名前は難しく芋えたすが、「自己察戊を繰り返しながら、埌悔を枛らしおいくこずでナッシュ均衡に近づく仕組み」ず思っおおけばだいたい合っおいたす。

    ここでは、数匏は最小限にしお「䜕をしおいるアルゎリズムなのか」「プレむダヌ目線ではどう理解しおおけばいいのか」を敎理したす。

    ◆ 1CFRずは䜕をするアルゎリズムか

    ・CFRは䞀蚀でいえば
     「倚人数の順番ゲヌムポヌカヌのような朚構造ゲヌムで、ナッシュ均衡に近い戊略を芋぀ける自己察戊アルゎリズム」

    ・やっおいるこずの流れはシンプルで、

     1適圓な戊略からスタヌトしお自己察戊する

    画像

     2「本圓はあのアクションを遞んでおけばもっず埗だったのに」ずいう“埌悔”を、各スポット・各アクションごずに蚘録する
     3埌悔が倧きかったアクションほど、次の反埩で遞びやすく確率を䞊げる

    画像


     4これを䜕千・䜕䞇回ず繰り返すず、「どのアクションに぀いおも倧きな埌悔が残らない戊略」に近づいおいく
     → その平均戊略が、ナッシュ均衡戊略の近くに萜ち着く

    ・ポむントは、「䞀発で正解を解く」のではなく
     「自己察戊しながら少しず぀“埌悔”を枛らしおいく」ずいう足し算で均衡に寄せおいるこず。

    最終的には埌悔EV差dEVが 0 に近づくたで蚈算を回したすが、時間がかかりすぎるため、ある皋床のずころで打ち切る蚭定になっおいたす。ざっくり蚀えば「この戊略に察しお盞手が完党なベストレスポンスを打ったずきに奪えるEVの䞊限が、ポットの 0.25 以䞋になったら止める」ずいう意味です。詳しくは【知らないず恥ずかしいdEV──0.01bb差の意味】をご芧ください。

    ◆ 2「埌悔」ず「無埌悔戊略」

    ・ひず぀の「情報セット」を考えたす。
     情報セットずは「そのプレむダヌから芋える情報が同じになる状況」のこずです䟋自分のハンドずボヌドは芋えおいるが、盞手のハンドは芋えない、など。

    ・そこには「ベット」「チェック」「フォヌルド」のように耇数のアクションがありたす。

    ・反埩番号を (t) ずし、その反埩で実際に遞んだアクションを (a_t)、そのずきのEVを (v(a_t)) ずしたす。
     「もし代わりにアクション (a) を遞んでいたら」の仮想EVを (v(a)) ずするずき、アクション (a) に぀いおの“埌悔”は

    Rt(a)=v(a)−v(at)R_t(a) = v(a) - v(a_t)

    ・反埩を重ねるず、アクション (a) に぀いおの环積埌悔は

    RcumT(a)=∑t=1TRt(a)R^{\text{cum}}T(a) = \sum{t=1}^T R_t(a)

    ・Regret Matching ず呌ばれる曎新ルヌルでは、各情報セットごずに

     ・正の环積埌悔が倧きいアクションほど、次回以降の確率を高くする
     ・环積埌悔が負かれロのアクションには確率を割り振らないたたは極端に小さくする

    ずいう圢で戊略を曎新しおいきたす。

    ・ざっくり蚀えば、

    「過去に『あれをやっおおけばよかった 』ず埌悔した手ほど、次からは出番を増やす」

    ずいう、ずおも人間っぜいロゞックを数匏に萜ずしたものです。

    ◆ 3「Counterfactual条件付きの」ずいう郚分

    ・ポヌカヌでは、ある情報セットに到達する確率は
     盞手の戊略や、それたでのアクションの流れに匷く䟝存したす。

    ・CFRでは次のような“条件付きの䞖界”を考えたす。

    「自分がある戊略を䜿い、盞手は珟時点の戊略を䜿っおいるず仮定したずき、
     この情報セットに到達する確率はどれくらいか」

    ・この条件付き確率を重みずしお䜿い、

     ・その情報セットに到達したず仮定したずきのEV
     ・そのずきに別アクションを遞んでいた堎合のEV

    を蚈算しお、埌悔を曎新したす。
    これが Counterfactual Regret反実仮想の埌悔です。

    ・盎感的には、

    「たたたたこのスポットにあたり来なかったから埌悔が小さい」のではなく、
    「このスポットに来た“ず仮定した䞊で”、どのアクションがよかったか」

    だけに集䞭しお埌悔を枬っおいる、ずいうこずです。

    ◆ 4アルゎリズムのざっくり手順

    ・ポヌカヌ甚のCFRをかなり粗くたずめるず、1反埩あたりは次のような流れです。

     1珟圚の戊略プロファむル各プレむダヌの戊略でゲヌムツリヌを巡回する
     2各情報セットで、党アクションの counterfactual value条件付きEVを蚈算する
     3実際に遞んだアクションずの差から、その情報セット内の各アクションの「埌悔」を曎新する
     4各情報セットごずに
       ・正の环積埌悔に比䟋しおアクション確率を割り圓おる
       ・正芏化しお新しい戊略にする
     5反埩を重ねながら「その時点の戊略」ではなく「戊略の平均」をずっおいく
       この平均戊略がナッシュ均衡に収束する、ずいう理論結果がある

    ・実際の実装では、ゲヌムツリヌを党郚なめるのは重すぎるので、

     ・サンプリングCFRランダムに郚分ツリヌだけ蟿る
    ・CFR+、DCFR などの改良版

    が䜿われおいたすが、根本のアむデアは䞊の流れです。

    ◆ 5CFRがポヌカヌで嬉しい理由

    ・ポヌカヌは「ツリヌ構造のゲヌム」であり、状態数が途方もなく倚いので、1回で党䜓の最適解を蚈算するのは珟実的ではありたせん。

    CFRは
    ・各情報セットを局所的に芋お「埌悔を枛らす」䜜業をひたすら積み䞊げる
    ・その結果ずしお、党䜓ずしお「無埌悔戊略」に近づいおいく
    ・無埌悔戊略の平均が、ナッシュ均衡に収束するずいう定理がある

    ずいう構造を持っおいるので、

    「巚倧なゲヌムツリヌを、自己察戊しながら近䌌的にGTOぞ寄せおいく」

    ためのアルゎリズムずしお非垞に盞性が良い、ずいうわけです。

    実際のポヌカヌAIPluribus、DeepStack系などや各皮゜ルバヌは、
    このCFRファミリヌCFR+、DCFR、External Sampling CFR などを土台にしお、
    ・ツリヌを郚分的にサンプリングし぀぀
    ・Regretの曎新を高速化し
    ・珟実的な時間ずメモリで「ほがGTO」に近い戊略を生成しおいる、

    ずむメヌゞしおおけば倧きくは倖れたせん。

    ◆ 6プレむダヌ目線でのCFRの理解

    プレむダヌがCFRの内郚実装を完党に理解する必芁はありたせん。
    抌さえおおきたいのは、次の2点だけです。
    ①「自己察戊を繰り返しながら“埌悔”を枛らしおいく → 無埌悔戊略 → ナッシュ均衡付近」ずいう流れになっおいるこず。
    ②各スポットで「このアクションをしおおけばよかった」ずいう埌悔を蚘録し、その倧きさに比䟋しお次回の頻床を倉えおいるこず。

    ・このむメヌゞを持っおおくだけで、

    「゜ルバヌがなぜ“それっぜい”ミックスやサむズを出しおくるのか」

    を感芚的に玍埗しやすくなりたす。

    ・゜ルバヌは“神蚗”ではなく、CFRのようなアルゎリズムで

     ・自己察戊
     ・埌悔の蓄積
     ・戊略の曎新

    をひたすら繰り返した「結果ずしおの戊略」を芋せおくれおいるだけです。
    その意味で、「゜ルバヌの仕組みCFRの考え方」を䞀床敎理しおおくず、
    出力の芋え方や“ズラし方”の感芚がだいぶ倉わっおくるはずです。

    PioSolver最新版

    • Pioの䞭身は公匏には现かく公開されおないけど、

    • もずもず「CFRベヌスの゜ルバヌ」ずしお知られおいる

    • Pioの䜜者も昔から「CFRの改良版いろいろ最適化しおる」くらいの説明をしおいる

    • むメヌゞずしおは「CFRを土台にした独自改良版」 ず考えお問題ない。

    GTO+ / GTO+2

    • こちらも基本路線は CFRベヌスの反埩アルゎリズム。

    • GTO+偎はドキュメントでも「CFRregret minimizationを䜿っお解いおいる」系の説明をしおいお、GTO+2 でも「゚ンゞン匷化呚蟺機胜远加」っお感じで、アルゎリズムの系統がたったく別物に倉わった、ずいう話は出おいない。

    GTO Wizard

    公開されおいる範囲だず

    • プリフロップポストフロップの GTO 解はCFR 系゜ルバヌ自前゚ンゞンで事前に巚倧DBずしお解いおおいお、それをクラりドから匕っ匵っおきおいる、ずいう䜜り。

    • なので「GTO Wizard  その堎でCFRを回しおいるツヌル」ではなく
      『CFRで事前に解かれた゜リュヌションのビュヌア補助機胜AI』
      ずいうむメヌゞが近い。

    Simple 系゜ルバヌ

    Simple Postflop / Simple Preflop / Simple 3-way など

    • 公開情報・挙動・蚈算スタむルから芋お
      → CFR系サンプリング・改良版 をベヌスにしおいるタむプ。

    • Pio / GTO+ ず同じ「朚構造ゲヌムを自己察戊で均衡に寄せる」系統

    ICMIZER / HRC みたいな ICM・push/fold専甚ツヌル
    → 䞻圹は CFR ではなく、ICMモデル党探玢動的蚈画法線圢蚈画

     
     
    ポヌカヌを䞭心に、初心者から䞊玚者たで幅広く圹立぀情報を発信したす。 知識を知っお終わりにせず、実戊で䜿える技術に倉えるための「基瀎理解」ず「考え方」を敎理しおいきたす。 ポヌカヌを䞀生の趣味ずしお長く楜しむための、戊略理解の土台づくりをサポヌトしたす。

    あなたぞのおすすめ