基礎原理から出発したモンテカルロ・グラフ探索

 (github.com/lightvector)
3 ポイント 投稿者 GN⁺ 2024-03-11 | 1件のコメント | WhatsAppで共有
  • Monte-Carlo Graph Search(MCGS) は、複数の手順が同じ状態へ遷移するゲームにおいて、MCTSをツリーではなく有向グラフに適用し、重複探索を共有しようとするアプローチである
  • 既存のMCTSの 訪問回数 N と 平均価値 Q をそのままDAGに移すと、共有子の訪問回数が親の方策・価値推定と食い違い、アルゴリズムが不健全になる可能性がある
  • MCTSを 正則化された方策最適化 として見ると、PUCTが作るアクションごとの訪問分布は事後方策であり、Qはその方策の期待効用として解釈できる
  • 正しいMCGSでは、子ノード訪問回数とは別に エッジ訪問回数 N(n,a) を追跡し、Qを U(n) と子Qの加重和から再計算することで、グラフ上でも方策と価値の意味を維持する
  • 実際の実装には、stale Q、増分更新、遷移先の子からplayoutを継続するか、ハッシュ衝突やゲーム内サイクルの扱いといった選択肢が残っており、KataGoは現在 冪等更新 を使用している

ツリー探索が見落とす遷移状態

  • ゲーム木探索では、異なる手順が同じ状態へ 遷移(transposition) することがある
    • チェスでは 1. d4 d5 2. Nf3 と 1. Nf3 d5 2. d4 は同じ局面に到達する
  • 遷移が可能なゲームでは、探索深度が深くなるほど重複状態が指数的に増えうるため、同じ状態の計算を共有するほうが望ましい
  • 一般的な MCTS 実装はゲームを分岐ツリーとして扱うため、同じ局面の複数インスタンスを再探索する
    • 反復局面に対するニューラルネットワーク評価のキャッシュのような低レベル最適化はコストを下げられる
    • しかし、あるインスタンスで重要な戦術を発見して評価が修正されても、他のインスタンスに伝播しない問題は残る
  • 状態空間を 有向非巡回グラフ(DAG) としてモデル化すれば、複数の経路が同じ状態に到達する際、その状態を1つのノードで表現できる
  • 実際にサイクルがあるゲームの処理は大半を除外し、DAGでMCTSがどう動作すべきかに焦点を当てる

標準MCTS: 実行統計を蓄積するツリー

  • 標準MCTSは、探索したゲームの一部をメモリ上の ノードツリー として保存する
  • 各ノードは通常、次の値を追跡する
    • N: これまでにこのノードを通過した、またはこのノードで終了した playout の数
    • Q: それらの playout がサンプルした効用値の実行平均
  • 1回の playout は次の順序で進む
    • ルートから始め、探索式に従って次のアクションを選びながら下る
    • まだ探索していない状態に到達したら新しいノードを追加する
    • 新しい状態の効用 U を得る。例ではニューラルネットワークの value head への問い合わせである
    • ツリーをさかのぼりながら各ノードの N を増加させ、Q の平均を更新する
  • AlphaZeroスタイルのMCTSでは、アクション選択に PUCT 公式を使う
    • N(a): アクション a が試された回数であり、ツリーではそのアクションが指す子ノードの N と等しい
    • Q(a): アクション a の平均効用であり、子ノードの Q と等しい
    • PlayerToMove: 現在のプレイヤーが最大化側か最小化側かを反映する
    • P(a): ニューラルネットワークの方策予測のような事前確率
    • c_PUCT: 調整可能な定数
  • “PUCT” は予測事前分布を用いる Predictor UCT/UCB 系から来ており、AlphaZero変種は元の形とは関数形が異なる
  • 現代のMCTSはニューラルネットワーク評価を用いると決定論的になりうるが、名称中の “Monte-Carlo” は、過去にランダム rollout を最後まで実行して効用を推定していた方式に由来する
  • 手番の計算予算が尽きるまで playout を繰り返した後、ルートでは Q ではなく 訪問回数 N が最も大きい子 を最終アクションとして選ぶ
    • Q が高く N が低い子は、浅い探索でノイズにより高く見えただけの誤りかもしれない
  • ルートの訪問分布 N(a) / ΣN(b) は、AlphaZeroの学習ループで方策学習目標として使える

DAGに素朴に適用すると生じる問題

  • ツリーMCTSのコードをほぼそのままにして、新しいゲーム状態がすでに nodes_by_hash にあれば既存ノードを指すようにできる
  • この方式では、子ノード訪問回数 が親で選ばれたアクション訪問回数と等しいというツリーの仮定を維持できない
  • 例の状況
    • ノードAはノードCへ行くアクションを好み、Aの Q は主としてCを探索した約30回の playout によって決まっている
    • Cは他の遷移経路からも約40回訪問されている
    • その後、Cが他の遷移経路からさらに多く訪問され、深い場所の戦術が見つかってCの効用推定が 0.39 → 0.51 に上昇する
  • Cを更新した playout はAを通っていないため、Aの Q はCの新しい評価を反映できない
  • その後Aが再び playout を受けても、PUCTは訪問回数の多いCではなく訪問回数の少ない別のアクションを探索する可能性がある
    • Cが「すでに十分探索された」ように見えるためである
    • その結果、Aの Q がかえって低下することがある
  • 素朴なグラフ拡張では、遷移経路が上位の好手を多く訪問するほど親が他の手をより探索するようになり、playout 平均に人為的なバイアスを生むことがある
  • 無限探索でも最善手へ収束するか明確でないほどの 不健全なアルゴリズム になってしまう

すべての親を更新しても解決しない

  • あるノードが特定の playout で更新される際、その playout が実際に通った親だけでなく すべての親と祖先 に反映される方式も考えられる
  • この方式は、先のA-Cの例ではAの効用も一緒に更新できる
  • しかし別の例では、親Dが自分では好まない遷移子Fの大量の訪問によって汚染される
    • Dの最善の子Eは Q = 0.56 で、Dの Q = 0.55 はこれと整合している
    • DはFを1回しか探索していないが、Fは他の経路ですでに9回訪問されており、合計10回訪問の状態である
    • その後Fが他の経路からさらに100回訪問され、低い効用を維持すると、全親更新方式はDの Q を 0.35 まで引き下げうる
  • Dの立場では、Fにそれほど多くの playout を割り当てたいわけではなかったため、全親更新も 方策の意味を壊す方式 である

MCTSを方策最適化として見る

πが最大化する値:
Σ π(a) Q(a) - λ_N D_KL(P || π)
  • 構成要素の意味
    • Σ π(a) Q(a): 方策 π に従うときの推定期待効用
    • D_KL(P || π): 事前方策 P と事後方策 π の差を測る逆方向KLダイバージェンス
    • λ_N: KL項の強さを決める係数であり、訪問回数が増えるほど減少する
  • 訪問分布は、ニューラルネットワークの事前方策 P を出発点とし、より多くの訪問によってアクション効用の根拠が蓄積されるほど改善される 事後方策 と見なせる
  • したがってMCTSは、ツリーの各ノードで小さな オンライン方策学習 を同時に行うアルゴリズムとして解釈される
  • この見方は、訪問分布が強いエージェントの方策のように見え、AlphaZeroで方策学習目標として使われる理由を説明する
  • 最適化問題の厳密解を計算して方策として使う方法も可能だが、実際には訪問が少なく偶然 Q が高く見える手に大きな重みを与えてしまうことがある
    • 訪問分布を事後方策として使えば、ある手が高い重みを得るには実際に多く探索される必要があるため、より頑健である

Qの再解釈: playout 平均から方策期待値へ

  • 標準定義では、ノード n の Q(n) は n を訪問した playout の効用平均である
Q(n) = (1 / N(n)) Σ U(p)
  • これを子基準で書き直すと次のようになる
Q(n) = (1 / N(n)) ( U(n) + Σ N(c) Q(c) )
  • ここで U(n) はノード n 自体の生のニューラルネットワーク効用推定であり、N(c) Q(c) は子ごとの訪問回数で重み付けした子価値である
  • したがって Q は、子Qたちの 訪問分布による加重平均 と解釈できる
  • 訪問分布がMCTSの最適化する事後方策であるなら、Q(n) はその事後方策に従ったときの正則化された期待効用である
  • この解釈では、各ノードが子たちの報告する Q を最大化するように方策を継続的に最適化し、自身の Q をその方策で達成可能な期待効用の最新推定値として更新する
  • 子ノードの Q がゲーム理論的最適値に収束すれば、親の方策と Q も再帰的に最適値へ収束する

正しいMCGS: エッジ訪問と子訪問の分離

  • グラフで生じる問題は、親の子訪問がその親を通してのみ発生すると仮定しているために起こる
  • 遷移経路があると、子ノード訪問回数がPUCTがその親で割り当てようとした訪問回数と任意にずれる可能性がある
  • 解決策は、PUCTが特定ノードで選んだアクションの累積回数 を別途追跡することである
  • 各ノード n は次の値を追跡する
    • N(n): このノードが訪問された総回数
    • N(n,a): ノード n でPUCTがアクション a を選んだ回数、つまりエッジ訪問回数
    • Q(n) = (1 / N(n)) ( U(n) + Σ N(n,a) Q(n,a) )
  • ここで Q(n,a) は、アクション a を打って到達した子ノード c の Q(c) と等しい
  • PUCT計算でも、子訪問回数ではなく エッジ訪問回数 を使う
argmax_a PlayerToMove(n) * Q(n,a)
       + c_PUCT P(n,a) sqrt(Σ N(n,b)) / (1 + N(n,a))
  • 基本アルゴリズムは、playout 経路のアクションを選択し、遷移先状態がすでにあれば既存ノードを接続し、戻りながらエッジ訪問回数を増やした後、N と Q を子の値の関数として再計算する
  • この方式は、Czech, Korus, Kersting の Monte-Carlo Graph Search for AlphaZero と高レベルでは類似しているが、実行統計ではなく方策最適化の観点から導かれている

実装の選択肢: stale Q と更新方式

  • 提示された疑似コードは、playout が実際に通った経路上のノードだけを更新する
  • このため、通過しなかった経路上のノード Q は stale Q になる可能性がある
  • それでも理論的には健全である
    • PUCTのような標準的探索式は、極限ではすべてのアクションを無限に試す
    • ノードが再訪されれば、その時点の子 Q とエッジ訪問回数を使って正しい Q を直接計算する
    • DAGでは極限的にゲーム理論的最適値へ収束しうる
  • stale Q は探索効率を下げうる
    • 即時の親ポインタを保持して親Qも更新できる
    • すべての祖先をトポロジカルソート順で更新して stale 状態をなくせる
    • playout 経路だけ更新しつつ、別の並列スレッドが stale ノードを見つけて更新させることもできる
  • 疑似コードは 冪等更新 を使う
    • 以前にどのような中間更新があっても、ノードを1回訪問すれば子の現在値に対して N と Q が正しくなる
  • 増分更新も可能だが、グラフでは同等または極限的に同等なものにするのがより難しい
  • Czech らは実行統計の観点からアプローチしたため、より増分的な公式を使う
    • エッジ訪問回数だけでなくエッジのQも保存する
    • stale Q が最新値に漸進的に追いつくメカニズムと誤差許容ハイパーパラメータを持つ
  • 提示された疑似コードは、新たな誤差許容パラメータやエッジQの保存がなくてもMCGSを動作させられることを示している
  • KataGoは現在 冪等公式 を使用している

遷移先の子から playout を継続するか

  • ツリーMCTSでは、エッジ訪問の増加と子訪問の増加は同じ出来事である
  • グラフでは遷移のため、子ノードがそのエッジよりすでに多く訪問されていることがある
  • このとき、子ノードはすでに十分訪問されたと見なして playout を中断し、エッジ訪問だけを増やしてから親と祖先を更新できる
  • 中断を好む理由
    • エッジ訪問が少なく子訪問が多いなら、その子への追加訪問がもたらす限界情報量は小さい可能性がある
  • 継続を好む理由
    • 子訪問がエッジ訪問より大きいノードは、複数の親から遷移してくるノードである可能性が高く、より多くの親に影響するため正確な評価が重要かもしれない
  • この選択は実験領域として残っている
    • 子訪問回数がエッジ訪問回数より十分に大きいときだけ中断する閾値方式も可能である
  • KataGoはデフォルトで playout を中断するが、継続する、あるいは確率的に一部だけ中断する設定オプションも提供する
  • 疑似コードは playout を中断せず、必要であれば child.N <= edge_visits 条件で1行のチェックを追加できる

ハッシュ、終端ノード、実際のゲームサイクル

  • ゲーム終端ノードは疑似コード上で、訪問回数に関係なく N = 1, U = Q = ゲーム結果効用 として再計算される
    • 親の該当エッジ訪問回数は通常どおり増加するため、この方式でも可能である
    • ゲーム結果が確率的で期待効用を直接計算できないなら、終端ノード訪問ごとに N を増やし、サンプル結果を平均する方式が重要になる場合がある
  • ゲーム終端効用をより広く扱い、証明可能な値をグラフ上へより速く伝播させることも可能である
    • 一般のMCTS/MCGSには確定効用値を認識する仕組みがないため、終端状態が重要なときでも alpha-beta のような古典探索ほど安価には最適値へ収束しない
  • 遷移を見つけるために、ゲーム状態の 一意ハッシュ を仮定する
    • 複雑なゲーム状態に対して真に衝突のないハッシュを作るのは難しく、コストが高いことがある
    • 128ビットまたは192ビットの十分大きな Zobrist hash は、敵対的に作られた状態でない限り、実務上は衝突を事実上防ぐのに通常十分である
    • ハッシュ衝突でサイクルが生じた場合に無限再帰を避けるには、サイクル検出を追加できる
  • 囲碁の superko、チェスの三fold repetition のように実際のゲーム規則で生じるサイクル処理は詳しく扱わない
  • 2024-03-10 付録は、反復とサイクル処理に関するより粗い考えをまとめた Google Docs リンクを提供しており、ゲームごとのヒューリスティック実験が必要かもしれない
  • KataGoの囲碁処理では、特定の手の後に元の局面へ戻るには少なくとも S + E - 1 手が必要だという囲碁特有の定理を活用し、サイクル関連状況でノード共有を安定的に制限している

関連記事

1件のコメント

 
GN⁺ 2024-03-11
Hacker News のコメント

  • こうしたグラフ探索こそが、AI の推論を発展させるために必要だと思う。単純な LLM だけでは失敗する可能性が高い
    リンク先には、ゲーム盤面向けの Zobrist ハッシュ https://en.wikipedia.org/wiki/Zobrist_hashing を含め、良い参考資料が多い
    グラフ探索の計算量が爆発しないように、言語ベースの状態記述に合った良いハッシュを見つける必要がある
    木探索に関しては、Thinking Fast and Slow: https://arxiv.org/abs/1705.08439 や、MCTS アプローチを現在の他の強化学習戦略と比較した Teaching Large Language Models to Reason with Reinforcement Learning: https://arxiv.org/abs/2403.04642 も読む価値がある

    • これはかなり低レイヤーに見える
      一歩進めるなら、状態表現と探索アルゴリズムを一緒に学習する方式になり得る。探索アルゴリズムが、コストを得られるニューラルネットワークの状態表現上を探索するような形だ
      https://sites.google.com/view/genie-2024/
      DeepMind の Genie は、離散状態をモデル化する良い例だ。ニューラルネットワークが、衝突判定や行動を含む非常に複雑な表現を学習する。その状態をピクセルにデコードする代わりに、おそらくその状態上で直接探索できるはずだ
      もちろん、この構造は実際にはかなり異なるものになるかもしれない
    • かなり単純化しているが、探ってみる価値のあるアプローチはこうだと思う
      論理的な論証の集合を置き、それぞれの論証にハッシュを与える方法を見つけ、その論証ハッシュを第一原理に従って重ねた Merkle ツリーとして表現する
      ある論証がうまく反論されると、その論証のハッシュが変わり、下位の論証のハッシュも無効になる
    • どうにかして両方を組み合わせることはできないのだろうかと思う。脳があらゆることに単一の手法だけを使っているとは考えにくく、複数の道具と、その上でどの道具をいつ使うかを選ぶセレクターがある可能性が高そうだ

  • HN の URL で著者を見て、すぐに KataGo を作った天才だと分かった: https://github.com/lightvector/KataGo
    https://www.reddit.com/r/cbaduk/ に投稿している内容も、ずっと素晴らしい

    • URL が文字どおり KataGo のリポジトリ内にある

  • チェスの経験が非常に多いわけではないが、探索木の中で同じポジションが重要なほど頻繁に重複するという主張には懐疑的だ。Leela Zero で実測値を見てみたい
    三回同一局面と 50 手ルールまで状態に含めれば、反復の可能性はずっと低くなるはずだが、その点を考慮していない状態でもそう思う

    • 囲碁ではコウが非常によくある。盤面をそのまま繰り返す手は打てないが、木探索がコウの局面を正しく評価できないと、AI に悪手を打たせる状況を簡単に作れてしまう

  • 「Monte-Carlo Tree Search」という名前に反して、上のアルゴリズムにはモンテカルロがまったくなく、完全に決定的だというくだりが不思議だ。一般に実装される MCTS が決定的だとは。サンプリングにはランダム性があると思っていた

    • もともとの MCTS にはランダム性があった。記事でも触れているようだが、最後に局面を評価するためにプレイアウトを行う形だった
      現在の似たプロジェクトでは、これがより高品質なニューラルネットワーク評価に置き換えられている。ランダムに手を打って誰が勝つかを見る方式はあまり良くないが、当時知られていた最善の戦略だった
      結局、モンテカルロ部分は、今でも MCTS と呼ばれているものの本質的要素ではなく、むしろ次善策だった。だから名前が少し不幸なものになっている
    • 厳密には、同じ “monte carlo” という名前の下にある別のアルゴリズムだ
      興味深いのは、ほとんどのモンテカルロ法は真の乱数生成器ではなく疑似乱数生成器に依存しているため、同じシードと入力が与えられれば常に同じ結果になる決定的な方式だという点だ
      このアルゴリズムは、一般的な疑似乱数生成器と別個のヒューリスティックを使う代わりに、ニューラルネットワークに問い合わせる。ニューラルネットワークは巨大な探索空間上のヒューリスティックなので、学習によって特定の結果の方へ強く偏った非常に悪い疑似乱数生成器のように動作し、結果としてヒューリスティックが適用された疑似乱数生成器のように見える
      重要なのは、これは MCTS の特殊化であり、技術的にはすべてのユースケースに合うわけではないということだ
    • ランダム性があるなら、収束するのか、そしてどの程度のリソース・時間が必要なのかが気になる。CPU、RAM、GPU、TPU、QPU の観点でも変わり得る

  • MCTS を調べていたとき、記事で言及されている論文は完全にレーダーの外にあった。次の機会にこの修正方式を自分で動かしてみると、かなり面白そうだ

  • 簡単な紹介があるといい

    • ゲームプレイ AI を作るとき、広くたとえればすべての AI がそうだが、最も有望な手法の一つが木探索だ。後続の手をもとに現在の手を順位付けする方式だ
      同じ状態に複数の経路で到達できるゲームでは、異なる枝に同じ状態ノードを繰り返し記録するため、多くのメモリを無駄にすることがある
      この記事は、グラフ探索というアプローチをよく検討している。本質的には、ゲーム状態をハッシュ化する追加計算を行って、すでに訪問したノードかどうかを確認し、その代わりにメモリを節約する方式だ
      すでに見たノードを再度記録しなくてよいため、循環のない木が有向非巡回グラフに変わる
      このため、正しい結果を得るには木探索を少し手直しする必要がある。特に最適化の単位を頂点、つまり状態ではなく、辺、つまり行動や手により合わせる必要がある
      主題をよく理解した人が書いた、リテラートプログラミング風の、よく書かれた技術エッセイだ