モンテカルロ木探索についてのまとめ (データ構造とアルゴリズム Advent Calendar 2020)

この記事は「データ構造とアルゴリズム Advent Calendar 2020」20日目の記事です。

19日目は@takilogさん; グラフ上の合流に関する問題とアルゴリズム ,
21日目は@tmaeharaさんです。

概要
木探索と強化学習
- バンディット問題
- モデルベース強化学習
アルゴリズム
評価関数
その他の応用
最後に
References

概要

モンテカルロ木探索 (MCTS) は、木探索にモンテカルロ (ランダム) 要素を加味した評価関数を用いることで、効率よく探索を行うことのできるアルゴリズムです¹。特に囲碁など2プレイヤーの完全情報ゼロサムゲームで使用されており、プロ囲碁棋士を破ったAlphaGO, AlphaZeroや、Atariゲーム、将棋、チェスなどでも圧倒的スコアを出したMuZero²もこの方法を用いてます。別のタスクでは、バンディット問題やモデルベース強化学習においての探索にも使われたりします。ポーカーのような不完全情報ゲームでもMCTSを拡張した方法もあります³。

データ構造としては木構造になるので、初心者の方は実装するのが少し難しいかもしれませんが、幅優先探索や深さ優先探索を理解しているならば組み込むのは難しくありません。また、幅優先探索に評価関数を組み込んだ最良優先探索の考え方も用います。有名なアルゴリズムはA*アルゴリズムなどです。なお、一番難しい箇所は最適な評価関数を設計するところです。効率よく並列計算をしようとすると難しいです⁴。

様々な人がMCTSを解説していると思いますが、私も記事を書いてみようと思います。ボードゲームに限らず、探索が必要な場面では使える技術ですので、覚えておいて損はないと思います（計算コストは非常に大きいですが・・・）。

木探索と強化学習

木探索は、下図のように、望む最終結果を得るために最適なノードを選択しながらルートを探索していきます。通常の幅優先探索や深さ優先探索では、組み合わせ数が多すぎて探索しきれません。

引用元 DL2AI：ビームサーチの例

評価関数値に基づきノードを選択し、次のノードをさらに選択するという方法の幅優先探索です。貪欲法では、評価関数の中で最も良い値を選び続けていきます。この図は、最終的な文字列を探索していることを表しており、ビームサーチと呼ばれる方法で、ビーム幅２（評価値TOP2のノードを選択する）で探索をしています。

例えば、ユーザーが望む文章を生成したいとき、木探索とRNNによる評価値を組み合わせることで文章生成ができます。

評価関数は通常、最終結果をもとに更新されることが多いです。基本的にはこの枠組みで問題を解いていくことになります。

バンディット問題

MCTSを適用する例題としてバンディット問題を考えてみます。これは以前、強化学習入門：多腕バンディット問題という記事を書いています。要点は、K個のスロットマシンにあたりのある台が１つあり、多数の試行を通してどのスロットの腕を選んだらよいかを探索する問題です。こちらも木探索を使ってスロットのアームを選択しており、最終結果に基づき評価関数値を更新するという方法になっています。

モデルベース強化学習

ここで、強化学習は機械学習手法の1つであり、「環境」からの「状態」「報酬」を受け取り、それをもとにエージェント（モデル）が「行動」を行う方策を学習していきます。モデルベースでは状態遷移が既知、すなわち上図での枝が分かっている状態、マルコフ決定過程（MDP）で表現されるものです。しっかりした理論に基づいて体系化されていますが、ここでは省略します。評価関数・報酬の設計に関わるところで強化学習の考え方を使っていくことになります。

アルゴリズム

MCTSは4つのステップからなります。Wikipediaから図を引用します。

Monte Carlo tree search - Wikipedia

Selection: ルートから始めて、子ノードを選択していきます。選択基準には複数あります。
Expansion: 選択したノードから、次のノードをどれにするか選択します。シミュレーション後の結果をもとに展開します。
Simulation:　一様分布などランダムにノードを選択していきリーフノードまで計算を行います。このSimulation何度も繰り返します。rolloutと呼ばれます。
Backup: シミュレーションで得られた最終結果をもとに評価値を更新していきます。この図では(勝った回数) / (試行回数)となっており、最終的に勝つことができたノードほど選択されやすくなります。

この操作を繰り返していくことで、木を拡大していきます。十分なシミュレーション回数を行うと、よりよい探索を行うことができるようになります。

評価関数

探索と活用（Exploration and Exploitation）のバランスがうまく取れた評価関数を使っていきます。バンディット問題やベイズ最適化といった場面でも出てくる話です。「次の試行（実験）点をどこから選べばよいのか」というプラニングの問題では、この探索と活用というジレンマに悩まされることになります。機械学習モデルは、基本的に学習データ範囲内（内装領域）でしかモデル精度を保証できません。学習データ外に素晴らしい候補点があった場合は、探索を行ってその点を見つけていくことになります。そのための方法が複数提案されています。

UCB

代表的なものはUpper Confidence Bound (UCB)です。

$$ \begin{align} a_i = \arg \max_i (\frac{w_i}{n_i} + c \sqrt{\frac{logN}{n_i}}) \end{align} $$

$w_i$ が勝った回数、 $n_i$ がノードを選択した回数、$N_i$が全シミュレーション回数、$c$探索のパラメータで、この値が大きいほどランダムなノードが選ばれやすくなります。通常は$\sqrt2$です。第1項は活用を表します。あるノードを選んだときにどれだけ勝っているかの確率で、この手だけを選んでいけば、ある種の貪欲法になります。第2項は探索を表します。選ばれた回数が多いほど、この値は小さくなるので、少ない手が選ばれやすくなります。

Crazy Stone

Crazy Stoneという囲碁のプログラムがありますが、この選択基準は次の式になります。

$$ \mu_i = \exp \left(-2.4 \frac{\mu_0 - \mu_i}{\sqrt{2 ( σ_{0}^{2} + σ_{i}^{2} ) }} \right) + \varepsilon_i \ $$

この式はガウス分布を仮定して得られるものの近似です(2.4が正規分布と一致するように選ばれている)。これは、ｎ腕バンディットで用いられるボルツマン分布と類似したものです。εは0にならないようにする定数で、下式で定義されています。

$$ \begin{align} \varepsilon_i = \frac{0.1 + 2^{-1}+a_i}{N} \end{align} $$

ここでa_iはあたりなら１、その他は０という囲碁のルールに基づいた値で、ドメイン知識で決定されています。また、バリアンスは下式で計算します。

\begin{align} σ^{2} = \frac{Σ_{2} - S \mu^{2} + 4P^{2}}{S+1} \end{align}

ここで、Pが盤面の点数。Σ_{2} はノードのsum of squaredです。Sはシミュレーション回数です。不確定要素を考慮するためにこの式が得られています。かなり工夫がされています。

AlphaZero

arxiv.org

AlpahZeroは評価関数をニューラルネットワークで決定しています。ゲームのルールのみ教えています。個人だとまず学習できないレベルのマシンスペックによって計算されています。

MCTS疑似コード

以下のコードを見るとAlphaZeroで何をやっているのか概要が分かるかと思います。基本的にはMCTSを実行していますが、どのノード（手）を選択するかでニューラルネットワークで決定されたスコアをもとに決定されているのが分かるかと思います。

def run_mcts(config: AlphaZeroConfig, game: Game, network: Network):
  root = Node(0)
  evaluate(root, game, network) // ニューラルネットワークで値を取得して方策を予測
  add_exploration_noise(config, root)

  for _ in range(config.num_simulations):
    node = root
    scratch_game = game.clone()
    search_path = [node]

    while node.expanded():
      action, node = select_child(config, node)  // UCBスコアに基づいてノードの選択
      scratch_game.apply(action)
      search_path.append(node)

    value = evaluate(node, scratch_game, network)
    backpropagate(search_path, value, scratch_game.to_play())
  return select_action(config, game, root), root

Selection: UCB score

\begin{align} score &= Q(s, a) + C(s)P(a|s) \frac{\sqrt{N(s)}}{1+N(s, a)} \\ C(s) &= \log \frac{1+N(s) + c_{base}}{c_{base}} + c_{init} \end{align}

Q(s,a): 状態 s で行為 a を行った際の平均報酬, P(a|s)は方策です。すなわち、状態 s で行為 a を選択する確率で、ニューラルネットワークの出力となっています。 Nは訪問回数です。実際の疑似コードでは下のようになります。

# The score for a node is based on its value, plus an exploration bonus based on
# the prior.
def ucb_score(config: AlphaZeroConfig, parent: Node, child: Node):
  pb_c = math.log((parent.visit_count + config.pb_c_base + 1) /
                  config.pb_c_base) + config.pb_c_init
  pb_c *= math.sqrt(parent.visit_count) / (child.visit_count + 1)

  prior_score = pb_c * child.prior
  value_score = child.value()
  return prior_score + value_score

Backupにて更新されていく値になっています。詳細はブログ記事や論文を参照ください。

↓ブログ記事

deepmind.com

MuZero

MuZeroもAlphaZeroと同様に評価関数をニューラルネットワークで決定しています。AlpahZeroとの違いはAtraiやゲームルールすら教えずゼロから学習している点が違います。

Selection

探索木のノードごとに内部状態sがあり、sからの行動aはエッジ(s, a)で保存されています。 $\{N(s, a), Q(s, a), P(s, a), R(s, a), S(s, a)\}$は、それぞれ訪問回数N, 報酬の平均Q, 方策P, 報酬Rと状態遷移 Sを表しています。完全に強化学習の枠組みで得られる値です。

f:id:udnp:20201219211529p:plain

c1, c2は、よく訪問されるノードのQ(s, a)値に関連するP(s, a)の影響をコントロールするために用いられる定数です。

Expansion

最終ステップ$l$で、葉ノードに到達したとき、報酬と状態が別の関数gにて計算され、同時にテーブルに保存されます。また、方策とQ値は予測関数fで計算され、新しいノードが探索木に追加されることになります。そして, $N(s^{l}, a)=0, Q(s^{l}, a)=0, P(s^{l}, a)=p^{l}$で初期化されます。

Backup

累積報酬に関しては、時間割引率$\gamma$を考慮した推定値です。 f:id:udnp:20201220102234p:plain

$(s^ {k -1}, a^ k)$に対するQ, Nに関しては、次のように更新しています。

f:id:udnp:20201220101513p:plain

その他の応用

MCTSを使うとき、ゲームでは勝ったか負けたかのゼロサムですが、最終スコアが連続値でも問題なくつかうことができます。例えば、最終スコアが10になるように手を選択したり、特定の文字となるように探索したりなどです。前者の場合では最終結果がどれだけ10に近いかで評価関数を更新してきます。後者でも、文字列を何らかの関数でスカラーにすれば同じプロセスとなります。Chemoinfomaticsの分野では、分子構造を表す文字列生成 → ChemTSといった方法もあります。

最後に

MCTSの考え方は非常にシンプルなのですが、selection, expansionでどのようにノードを選択し拡大していくかという評価関数を作りこんでいくところが非常に難しいです。backupのところでも、単純に訪問回数に+1をするだけでなく行動価値の値を更新する際など、かなりの工夫が必要になっていきます。AlphaZeroやMuZeroに関する処理を実装することでさらに理解を深めていきたいです。

References

Remi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In International conference on computers and games, pages 72–83. Springer, 2006.↩
Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model, https://arxiv.org/abs/1712.01815 ↩
Combining Prediction of Human Decisions with ISMCTS in Imperfect Information Games, AAMAS ‘18: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent SystemsJuly pages 1874–1876, 2018.↩
On Effective Parallelization of Monte Carlo Tree Search, arXiv:2006.08785↩

グラフ機械学習と強化学習について

主にグラフ機械学習や強化学習手法を記載します。