モンテカルロ木探索を開墾する
会社で開墾会という論文などで見かけた手法を勉強して共有する会をしています。 この記事は開墾会の資料で、モンテカルロ法とモンテカルロ木探索を具体例を交えながらまとめています。
問題設定
上の図は道にコインが落ちているマップである。2人のプレイヤーはスタート地点からコマを交互に移動させていき、多くコインを集めたほうが勝ちというゲームをする場合を考える。 ただし、
- 一回通った地点は通れないものとする。
- これから通る道にコインが何枚あるかは事前にわからないものとする。
この問題を題材にして、モンテカルロ法とモンテカルロ木探索を用いて先手のプレイヤーが取るべき手を学習していく。
ゲーム木
モンテカルロ法などの説明に入る前にこの問題のゲーム木を書いておきたいと思う。 ゲーム木とは、ゲームの盤面をノード、盤面に対して打てる手をエッジとしたグラフのことである。 今回の場合は、木の終端ノードがゴールまでの経路（解）、その他のノードがゴールまでの経路の一部を切り出した経路（部分解）となる。以下に、今回の問題のゲーム木を示す。
上のゲーム木において、赤の線が先手のプレイヤーが選択した道、青線が後手のプレイヤーが選択した道となる。 終端ノードに付いている数字は、報酬であり、先手が勝ちの場合は1、引き分けの場合は0、負けの場合は−1としている。
モンテカルロ法
モンテカルロ法は、ランダムに何らかの報酬が得られるまで行動して、得られた報酬をそれまでに辿ってきた状態に分配していき、平均報酬Qを求める方法です。 実行手順は以下のようになります。
- 終端ノードにたどり着くまでランダムに手を選ぶ
- 得られた報酬をこれまで通ってきた状態に伝搬する
- このとき、選択された回数Nと平均報酬Qを記録しておく
- 1.2.を任意の回数繰り返す
モンテカルロ法を実行することにより、全ノードに対して平均報酬Qを求めることができ、平均報酬Qが大きい手を選ぶことで、最善手を導くことができる。
適用例
先程定義した問題に対して適用してみる。 まず、ランダムに手を選択していって、以下の図のように終端ノードにたどり着いたとする。
たどり着いた終端ノードの報酬は1なので、この報酬を辿ってきたノードに伝搬させる。このとき、Nをカウントアップ、Qを計算する。
次に、以下の図のように終端ノードにたどり着いたとする。
たどり着いた終端ノードの報酬は0なので、この報酬を辿ってきたノードに伝搬させる。このとき、 となる。
このような操作を繰り返すことで、全ノードの平均報酬を更新していく。
問題点
モンテカルロ法は、手の選択が完全にランダムなので、相手にとっての最良の手も平等に探索してしまい、探索に無駄が生じる。 例えば、先程のゲーム木の根ノードの左側は、引き分けか負けしかないため、探索するだけ無駄になってしまう。 また、これにより、Qが過大評価されることがある。 例えば、先程のゲーム木の根ノードの左側は、引き分けか負けしかないため、評価は−1にして絶対に左側を選択しないようにしたい。
これを回避するためには、ノードの選択ををランダムではなく平均報酬で決めていく方法も考えられるが、勝てるパターンもあるのに最初に探索したパターンが負けのパターンだった場合に、勝ちパターンを探索しなくなってしまう。 平均報酬が高いノードを積極的に探索して効率よく探索したい、でも平均報酬の見積もりが十分でないノードの見積もりもやりたい。 この平均報酬の活用と見積もりのバランスを取りながら探索を行うのがモンテカルロ木探索である。
モンテカルロ木探索
モンテカルロ木探索は、上記したように、平均報酬の活用と見積もりのバランスを取りながら探索を行う方法である。 モンテカルロ木探索では、一般的にゲーム木は膨大な大きさになるため（囲碁や将棋などの場合）、木を深さごとに展開しながら探索を行う。 モンテカルロ木探索は以下の3つの操作を任意の回数繰り返すことで行われる。
- Tree policy
- Default policy
- Backup
それぞれについて説明する。
Tree policy
このステップでは、木の展開済みの範囲におけるノードをUpper Confidencial Bound for Trees(UCT)に基づいて選択することを繰り返し、木の展開済みの範囲における終端ノードを求める。
ここで、はノードiの平均報酬、Nは全探索数、
はノードiの探索数、Cは重み（任意に決定）である。
この式は、基本的には第一項で平均報酬Qが高いノードを探索しようとするが（活用）、第二項によりノードそれぞれの探索数を考慮して、探索数が少ないノードであっても積極的に探索しようとする（探索）。 重みCは活用と探索のバランスを取るために設定する。探索の優先度を高くしたい場合はCを大きくする。 例えば、探索数が0のノードがあった場合は、第二項が無限となりUTCも大きくなるので、そのノードを探索しようとする。
Default policy
このステップでは、Tree policyによって選ばれた展開済みの範囲における終端ノードから、木全体の終端ノードにたどり着くまでランダムにノードを選び、終端ノードの報酬を求める。
Backup
このステップでは、Default policyによって得られた報酬を辿ってきたノードに伝搬し、平均報酬Qとノードの探索数Nを更新する。
適用例
先程定義した問題に対して適用してみる。 まず、Tree policyで展開済みの範囲の木のノードをUCTに基づいて選ぶ。まだ一度も探索が行われておらずUCTは比較できないため、どちらかをランダムに選ぶ。今回は以下の図のように選ばれたとする。
次に、Default policyでランダムにノードを選択し、以下の図のように終端ノードにたどり着き、報酬が得られる。
得られた報酬は1。次に、得られた報酬をBackupで辿ってきたノードに伝搬する。また、このとき、ルートノードの右側のノードは一度探索されたので、そのノードの子のノードは展開済みとなる。
次に、Tree policyによりルートノードの左側が選ばれ、同様にDefault policyとBackupを行い、以下のような状態になったとする。
この状態から、次の探索でTree policyを適用する場合、UCTの式が効いてくる。 UCTの式に当てはめると、木の右側はUCT=1.776、左側はUCT＝0.776となる（C=1で計算）。 そのため、Qが大きい右側が選ばれる。これは、これまでに得られたQを活用することで、勝ちパターンが多いであろう方向に積極的に探索が行われていることを意味する。 また、右側のノードの先も同様にUCTで計算するが、まだ探索されておらず比較できないので、ランダムに選ぶ。以下のように選択されたとする。
Tree policyで選ばれたノードは、木全体において終端ノードであるため、Default policyはそのノードの報酬を返し、Backupで報酬が伝搬される。
このように、平均報酬Qが大きい、つまり良い解があるであろうノードを優先的に探索を行い、Qを更新していく。 しかし、UCTの式の第二項により、ノードの探索回数も考慮されるため、Qが大きいノードばかりを探索せずにどこかのタイミングで、Qが小さい方も探索される。このパターンは、具体例を示すまでに何回か繰り返さないといけないので割愛する。（UCTにおけるCのを大きくすることでQが小さいノードの探索頻度が向上する）
特徴まとめ
- 途中過程の良し悪しはわからなくても、勝ち負けがはっきりしているゲームに有効
- モンテカルロ木探索では、途中の状態の良し悪しを判断せずに、最終的に行き着く結果の状態の良し悪しだけ分かればいいため
- また、組合せ最適化論において解の良し悪しは判断できるが、途中過程（部分解）での評価が難しい場合に有効と思う
- 木の探索をモンテカルロ法に比べて、無駄なく行える
- 木の規模が大きくなるとモンテカルロ法では現実的な探索ができずに学習が上手く進まない
- モンテカルロ木探索は細く長い勝ちの手順が苦手
- 細く長い勝ちの手順とは、最前手が一手のみでその他は負けのような状況が複数回あるような状況。一歩間違えれば負けの連続。
- これは勝ちのパターンに探索でたどり着くのが難しくなる
- 例えば、細く長い勝ち手順の先の報酬だけ異様に高い2000点みたいになると困りそう
