モンテカルロ法

試行を多数回くり返し、その割合から計算しにくい量を見積もる

モンテカルロ法は、乱数を使った試行を多数回くり返し、その結果の割合や平均から、厳密に計算するのが難しい量を近似的に求める方法です。ニコラス・メトロポリス(Nicholas Metropolis)とS・ウラム(S. Ulam)は、1949年の論文 The Monte Carlo Method でこの方法の動機と考え方を説明しました。論文の冒頭では、この方法を、数理物理の微分方程式や積分微分方程式を扱う問題への統計的な取り組み方だと述べています。

この方法が役に立つのは、式をそのまま解くことも、すべての場合を数え上げることも現実的でない場面です。論文は、そうした場面の例として次の2つを挙げています。

ソリティアの成功率を、遊んだ結果から見積もる

1つ目の例は、1人で遊ぶトランプのソリティアです。ここで考えるのは、腕前が結果に関係しない種類のソリティアに限ります。

成功する確率を組み合わせの計算で厳密に求めることは、まったく手に負えない作業だと論文は述べています。そこで論文が勧めるのは、実際にゲームを多数回行い、そのうち成功した回数の割合を調べることです。この割合が、成功する確率の見積もりになります。

論文は、ソリティアをこの種の組み合わせの問題全体を示す例として挙げています。

20次元の図形の体積を、無作為に選んだ点で見積もる

2つ目の例は、20次元の空間にある図形の体積を求める問題です。図形は20個の不等式で決まる範囲で、1辺の長さが1の立方体(単位立方体)の中にあるとします。

体積の定義どおりに計算しようとして、各座標を10等分して格子の点を作ると、調べる点は 10^20 個になります。これをすべて数えることは明らかに不可能です。

論文が示すやり方は、単位立方体の中から、たとえば 10^4 個の点を無作為に選び、そのうち不等式をすべて満たす点がいくつあるかを数えることです。満たした点の割合が、単位立方体に対する図形の体積の割合の見積もりになります。論文は、この見積もりが高い確率で数パーセント以内の誤差に収まると述べています。10^20 個の点を調べる代わりに 10^4 個で済ませている点に、この方法の考え方が表れています。

見積もりの確かさは確率でしか言えない

モンテカルロ法の答えは、試行の結果から作った見積もりです。メトロポリスとウラムは、ソリティアの例について、見積もりが決められた範囲に確実に収まることはなく、試行の回数が多ければ高い確率で収まる、という形でしか言えないと述べています。

つまり、試行の回数を増やせば見積もりはより信頼できるようになりますが、ある回数で必ず正しい値が得られるという保証にはなりません。答えを使うときは、どれだけの回数を試したかと合わせて読む必要があります。

ゲームでは、ランダムに打ち進めた結果の平均で局面を評価する

モンテカルロ法は、囲碁のようなゲームで次の一手を選ぶ探索にも使われています。この使い方を理解するには、まず従来のやり方を知っておく必要があります。

2人が交互に手を指すゲームのプログラムでは、先の局面を枝分かれする木の形に広げて読みます。自分は評価の値が大きくなる手を、相手は小さくなる手を選ぶと仮定して値を決めていく木を、min-max の木と呼びます。木の末端にある局面の有利さは、評価関数という、局面を1つの数に直す関数で表します。レミ・クーロン(Rémi Coulom)は2006年の論文で、この評価関数をそのゲームの専門知識で作り、アルファ・ベータ探索と組み合わせるのが伝統的なやり方であり、チェスやオセロなどでは大きな成功を収めたと述べています。

一方で、クーロンによると、このやり方は囲碁ではうまくいきませんでした。囲碁では、局面の有利さを正確に数で表す評価関数を作ることが難しいからです。

そこで使われるのが、モンテカルロ法による評価です。クーロンの論文の要旨は、これを次のように説明しています。ある局面の価値を、その局面からランダムに続けた対局をいくつも行い、その結果を平均して見積もる。この見積もりは、min-max の木の末端で評価関数の代わりに使える。偶然の要素が無いゲームでも、終局までランダムに手を選び続ければこの評価ができます。

モンテカルロ木探索は、ランダムな対局を重ねながら木を育てる

クーロンの2006年の論文は、題名に Monte-Carlo Tree Search(モンテカルロ木探索)という語を使い、モンテカルロ法による評価と木の探索を組み合わせる方法を示しました。

この方法では、現在の局面を根として、そこからランダムな対局を何度もくり返します。くり返した対局は1本の木としてメモリに記録され、木の各ノードには、そのノードを通った対局の数と、それらの対局の値の合計が数えられます。ノードごとの値の平均は、合計を対局の数で割れば求まります。

木は最初から全部を作るのではなく、少しずつ広げます。最初は根のノードだけがあり、すでに1回通ったノードをランダムな対局がもう一度通ったときに、その次の手のノードを新しく作ります。十分な回数通ったノードでは、値が高い手ほど多く選ばれるようになります。こうして、有望に見える手の先ほど深く調べられるように木が育ちます。

この方法では、1回の対局が終わるたびに、その結果がすぐに根まで反映されます。そのため、いつ計算を止めても、その時点までの結果で手を選べます。クーロンはこの方法を9路盤の囲碁のプログラム Crazy Stone に実装し、このプログラムは第10回 KGS コンピュータ囲碁大会で優勝しました。

UCT は、どの手を試すかの配分を多腕バンディット問題として考える

木を育てるとき、どの手をどれだけ試すかの決め方で、探索の効率は大きく変わります。すべての手を同じ確率で試す素朴なやり方では、明らかに悪い手にも同じだけ時間を使ってしまいます。

一方で、はじめに悪く見えた手をすぐに切り捨てるのも危険です。クーロンは、ランダムな対局の結果が最初は悪く見えても、深く調べると強い次の一手が見つかり、評価が上がる場合があると指摘しています。

レヴェンテ・コチシュ(Levente Kocsis)とチャバ・セペシュヴァーリ(Csaba Szepesvári)は、2006年の論文 Bandit based Monte-Carlo Planning で、この問題に取り組む UCT という方法を示しました。2人は、次の2つの要求が互いにぶつかると整理しています。

• いま最もよく見える手をくり返し試して、その値を正確に見積もりたい
• いまはよくなさそうに見える手も試して、はじめの見積もりの誤りのせいでよい手を見逃さないようにしたい

前者を活用、後者を探索と呼び、この2つのバランスをどう取るかという問題を、探索と活用のジレンマと呼びます。論文は、このジレンマの最も基本的な形が多腕バンディット問題に現れると述べています。多腕バンディット問題は、当たりの出方が分からない複数のスロットマシンの腕から、どれを引くかを1回ずつ選び続ける問題です。

UCT は UCB applied to Trees の略で、多腕バンディット問題のための UCB1 という方法を、木の各ノードで次に試す手を選ぶのに使います。UCB1 の UCB は Upper Confidence Bounds(信頼上限)の略です。UCB1 は、腕ごとにこれまでの報酬の平均を記録しておき、平均に見積もりの不確かさを加えた上限が最も高い腕を選びます。試した回数が少ない腕ほど不確かさが大きく見積もられるので、まだ十分に試していない手にも順番が回ってきます。

コチシュとセペシュヴァーリは、UCT が十分な時間をかければ最善の行動に行き着くことを理論的に示し、人工的なゲームなどの実験で、比べた方法よりも効率がよかったと報告しています。

ランダムに試す回数と見積もりの確かさの関係は、ゲームでも同じ

ゲームの探索で使う場合も、モンテカルロ法の性質は変わりません。局面の評価はランダムな対局の結果から作った見積もりであり、対局の回数を増やすほど信頼できるようになりますが、確実な値ではありません。モンテカルロ木探索や UCT は、限られた回数の試行を、有望な手と見逃したくない手にどう振り分けるかを工夫した方法だと言えます。