Introduction for Monte Carlo Tree Search
Monte Carlo Tree Search(モンテカルロ木探索)は,囲碁などの対戦ゲームの攻略と戦略の研究に多く使用されています。巨大ゲーム空間を保有する囲碁(盤面は19x19)は長い期間に渡ってAIによる戦略手法を構築しづらいものでありましたが、Aplha Goの次世代対戦プログラムであるAlphaGo Zeroが輝かしい戦績を残したことでその手法がどの様なものであるのか話題になった次第です。AlphaGo ZEROは、Monte Carlo Tree Searchをベースにして構築されてできたプログラムです。AlphaGo Zeroとそのバックグラウンドについての説明は、Googleなど検索エンジンを使用することで数多くweb pageの中より散見することが可能です.
さてA Survey of Monte Carlo Tree Search Methods(以下MCTSと使います)ではMCTSについて細かく説明されているので、ここでは簡単に内容を紹介します。MCTSは以外と奥が深く様々な手法と比較されていることから、自分自身の理解を深めるためにも数回に分けて記述を行いたいと考えています。
論文のAbstructでも表記されている様に、MCTSは非常に単純で理解しやすいTree構造のプログラムで、緻密なTree探索方法をと乱数によるランダムサンプリングを融合した開発された手法です。特にAlphaZero Leeなど従来の対戦プログラムはSupervisedモデル(つまり教師つきモデル)を踏襲し過去の戦績・対戦Pathを学習したのちにプログラムが思考を開始指定たのに対して、人の関与を必要としない、かつ人間の対戦による教師データをも使用しないself-playを確立した画期的な手法です。
Gaming Theory
まず、一般的なゲーミング理論の数式は、下記の様に表示されます。
\begin{align}
&S: 状態 \\
&S_T \subseteq S : 終端の状態 \\
&n \in N : プレイヤーの数\\
&A: 行動のセット\\
&f: S \times A \rightarrow S : 状態の移行関数 \\
&R: S \rightarrow R^k : ユーティリティ関数 \\
&\rho : S \rightarrow \bigl(0, 1, .... , n \bigr): 各々の状態におけるプレイヤーの行動
\end{align}
人は行動から得られる利得を最大限にするため状態移行に関する行動の推定値(確率)を決定する戦略があります。一方で、ゲーム理論で有名なナッシュ均衡は、他人の戦略が変更されることで利得を得られることができないならば、お互い戦略を変更することなく現在得られる戦略をそのまま保持することになります。囲碁などのインタラクティブなリアルゲームの世界ではお互いその戦略は常に計算されている必要があり、誰かがゲームの支配者となって戦略を変更しないということはないでしょう。
さて、ここでゲームは下記の様に分類さます。
| ゲームタイプ | 説明 |
|---|---|
| ZeroSum | 全プレイヤーの総報酬がゼロ |
| Information | ゲーム状況が完全もしくは部分的にプレイヤーによってコントロール |
| Determinism | 報酬決定については未知 |
| Sequential | プレイヤーの行動は連続的もしくは完全一致 |
| Discrete | プレイヤーの行動はリアルタイムで独自的に決定される |
囲碁、チェス、三目並べなどのボード対戦ゲームは上記全ての要素を含んでいるので複合ゲームと呼ばれ、単純かつシンプルなプレイで進行できるが、その対戦戦略は非常に奥深く研究されてきてきました。
UCB1について
UCB1の適用でよく説明されているのはmulti-armed bandit programです。コイン配当の異なる複数台のSlot machineが存在する中で最も報酬を高く設定する場合、どの様なアプローチで期待報酬を高く設定できるでしょうか？
掛金を全てをslot machineに投じてレバーを引いてどのslot macinieの利益率が良いか一つ一つ確認することから始めるでしょう。
UCB1 = \bar{X_j} + \sqrt{ \frac{ 2 ln \bigl( n \bigr) }{ n_j }} \\
\bar{X_j} : arm_j からの平均報酬 \\
n_j : arm \: j のプレイ数 \\
n : 全体ゲームプレイ数\\
この公式では、右辺第一項$\bar{X_j}$がSlot Machineそれぞれの平均報酬すなわち期待値です。右辺第二項$\sqrt{ \frac{ 2 ln \bigl(n\bigr) }{ n_j }}$はBias項となりますのでプレイ数を増加させれば、UCB1はSlot Machineの期待値$\bar{X_j}$＋プレイしていないSlot MachineのBiasが高く設定される様になっています。つまり${n_j}$の大きさにより決定されるUCB1はより少なくプレイしたMachineからの探索をするようにプログラムされていきます。この様に探索と収穫のジレンマを解決すべく導き出されたモデル式です。
MCTSアルゴリズムについて
はじめに紹介されている、一般的なMCTSのメインアルゴリズムはA Survey of Monte Carlo Tree Search Methodsより抜粋した下記の図の様になります。
\begin{align}
&\Delta = 報酬\bigl(reward\bigr) 終端ノードから生成される。\\
&例えば、自分の手で先行して攻めて勝利すれば+10、\\
&負ければ-10という具合に価値をつけていく。
\end{align}
MCTSアルゴリズムの解説
上記の図についてより具体的に説明をしてきます。
ここでcomputational budgetとは設定された値になるまで下記のロジックをStep by Stepループしながら行うことです。最終的にノードで計算された利得(バックプロパゲーションで計算された)のBest Valueを得ることでどの戦略が良いのか決定することが可能になります。
| STEP | 内容 |
|---|---|
| ルートノードの選択から子ノードへ | ルートノードから子ノードへ展開する。子ノードは終端ノードに到達するまで展開できる。 |
| 子ノードの拡張 | 展開される子ノードは再帰的に展開されツリーに追加される。行動が制限されていなければ(例えば囲碁やオセロなどの盤面に駒を置けるスペースがあれば)子ノードは拡張できる。ただし拡張はランダムに選択される |
| シミュレーション | Default Policyで行われるシミュレーションは終端ノードまで行動させ新しい状態が作成される、もしくは勝敗が決定すればその時点でシミュレーションを打ち切る。シミュレーションが終了した時点で報酬を計算させる。(つまり可能な限り打ち手をシミュレーションしていく) |
| バックプロパゲーション | シミュレーション終了時点で得た報酬はルートノードまで遡って加算を行う。その際、Visitedフラグを立てることでUCB1計算に必要な情報とする |
次回は、Tree Policy、Default Policy、UCBなどを具体的に解説していきたいです。
参考文献および参照Web
AlphaGo Zero - How and Why it Works
ALPHA ZERO CHEAT SHEET
Mastering the Game of Go without Human Knowledge
ALPHA ZERO CHEAT SHEETは作者がMCTSについての画像を添付しているので俯瞰的に理解しやすくなっている。