目次と前回の記事
Python のバージョンとこれまでに作成したモジュール
本記事のプログラムは Python のバージョン 3.13 で実行しています。また、numpy のバージョンは 2.3.5 です。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| mbtest.py | テストに関する関数 |
| util.py | ユーティリティ関数の定義 |
| tree.py | ゲーム木に関する Node、Mbtree クラスなどの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
今回の記事の内容
前回の記事では、原始モンテカルロ法の読みの深さを単純に広げるというアプローチ（深さ $n$ の原始モンテカルロ法）について説明しました。このアプローチには、下記のように「組み合わせの爆発によって、勝率や最善手の精度が崩壊する」という致命的なジレンマが存在します。
- 深く読もうとする と 1 局面あたりのプレイアウト回数が激減し、勝率の精度が致命的に悪化する
- 勝率の精度を高くしようとする と 1 手先（深さ1）しか読めない
この「精度と深さ」のジレンマを解決するために考案された画期的なアルゴリズムが、今回の記事から解説するモンテカルロ木探索（Monte Carlo Tree Search（MCTS））です。
モンテカルロ木探索の考え方は、一言で言えば 重要な局面に対してプレイアウトを多く割り当てる（えこひいきをする） というものです。具体的には、すべての未来の局面を平等に調べるのをやめ、「勝敗を分ける重要な局面」や「筋の良さそうな強い手」だけをえり好みして、重点的にプレイアウトの回数を注ぎ込みます。その結果、限られた制限時間の中でも「勝率の精度を高く保ったまま、読みの深い探索を行う」ことができるようになります。
このアルゴリズムでは、大きく分けて以下の 2 つの問題を考える必要があります。
- 重要な局面とそうでない局面をどのように見分けるか
- どのように効率よく読みの深さを広げていくか
今回の記事では前者の「重要な局面の選別」に対するモンテカルロ木探索のアルゴリズムの考え方について説明します。
参考までに Wikipedia のモンテカルロ木探索のリンクを下記に紹介します。
「勝率」と「真の勝率」のおさらい
最初に今回の記事で多用する、「勝率」と「真の勝率」の用語についておさらいします。
前回の記事で説明したように、本記事ではこれらの用語を以下の意味で用います。
- 勝率：プレイアウトを何回か試すことで得られた、現時点での「状態価値の推定値」（実験データから計算した勝率）
- 真の勝率：プレイアウトを無限に繰り返すことで得られる、その局面の本来の「状態価値」（理論上の完璧な勝率）
前回の記事のサイコロの例えでは、「勝率」は実際にサイコロを振って求めた 1 の出目の割合であり、「真の勝率」は計算上の確率である 1/6（理論値）に対応すると説明しました。モンテカルロ木探索は、この限られたプレイアウトの回数で求めた「勝率」をいかに「真の勝率」に効率よく近づけるかという問題を扱っているとも言えます。
モンテカルロ木探索におけるプレイアウトの回数の割り当ての考え方
原始モンテカルロ法の最大の弱点は、「すべての局面に均等な回数のプレイアウトを割り当ててしまうこと」でした。
それに対してモンテカルロ木探索では、最善手の精度に大きな影響を与える、「真の勝率が高い局面」に対して、より多くのプレイアウトを割り当てる というアプローチを取ります。
このアプローチは、将棋やオセロなどのゲームに親しんでいる人にとっては、ごく当たり前の感覚であるかもしれません。ゲームをプレイするとき、複数の選択肢（合法手）があれば、無意識に以下のように考えているはずです。
- 勝率が高そうな「有望な手」 に対しては、積極的に先の展開を深く考える
- 勝率が低そうな「見込みのない手」 に対しては、最初から深く読まずに切り捨てる
モンテカルロ木探索が行なおうとしているのは、まさにこの人間の思考プロセスそのものです。今回の記事では、「真の勝率が高い局面にプレイアウトを多く割り当てること」が、なぜ最終的に計算される最善手の精度を高めるために有効なアプローチとなるかについて解説します。
今回の記事で扱う問題設定
先程説明したように、モンテカルロ木探索には、大きく分けて「プレイアウトをどう割り当てるか」と「どうやって読みの深さを広げるか」という 2 つのテーマがあります。
今回の記事ではアルゴリズムの本質をシンプルに説明するために、後者の「深さを広げる問題」はいったん脇に置き、原始モンテカルロ法と同じく、「1 手先（深さ 1）の局面だけに、限られたプレイアウトの総数をどう分配するか」という問題に絞って考えていきます。
おさらいとして、制限時間がある（深さが 1 の）原始モンテカルロ法は以下のようなアルゴリズムでした。
- すべての「1 手目の局面」に対して、実行可能なプレイアウトの総数（制限時間）1を 均等に割り振って プレイアウトを行い、「勝率」を求める
- 現在の局面の合法手の中から、着手後の局面の「勝率」が最大となる合法手を最善手として選択する
これに対してモンテカルロ木探索では、あらかじめ決められたプレイアウトの総数を「真の勝率が高そうな局面にえこひいきして割り当てる」ことで、最終的に計算される最善手の精度を高めます。つまり、モンテカルロ木探索が解くべき問題は下記のような問題です。
「限られたプレイアウトの総数を 1 手目の各局面にどのように割り当てれば、計算される最善手の精度を最大にできるか？」
この問題の目的が「何かを最大化（または最小化）するような最適な割り当てを探す」であることから、この問題が以前の記事で説明した数学における「最適化問題」であることがわかります。
そこで、この問題の性質を数学的に分析するために、この問題を「最適化問題」として定式化（数式に落とし込む作業）することにします。
記号の説明
最適化問題として数式を組み立てる前に、まずは今回の解説で登場する「記号のルール」を整理します。後で数式を見て記号の意味がわからなくなったらここを振り返ってください。
添字（右下の小さな文字）についての注意点
前回の記事では添字を「ステップ数（読みの深さ）」として使っていましたが、今回の記事では「1 手先の局面（深さ 1）がいくつ並んでいるか」だけを考えるため、添字の $1, 2, \dots, n$ は「1 手目の局面の番号」を表す 点に注意して下さい。
| 記号 | 意味 |
|---|---|
| $p$ | 1 手目の局面に割り当てる プレイアウトの回数の総数 |
| $n$ | 現在の局面の 合法手の総数（= 1 手目の局面の総数） |
| ${s_1, s_2, \dots , s_n}$ | 各合法手を着手した 1 手目の局面の集合 |
| ${p_1, p_2, \dots , p_n}$ | 局面 $s_i$ に割り当てた プレイアウトの回数 |
| ${\bar{r_1}, \bar{r_2}, \dots, \bar{r_n}}$ | 実際のプレイアウトから計算された 勝率（標本平均のデータ） |
| ${\bar{R_1}, \bar{R_2}, \dots, \bar{R_n}}$ | 局面の勝率を表す 確率変数（標本平均の確率変数） |
| ${\bar{μ_1}, \bar{μ_2}, \dots, \bar{μ_n}}$ | 局面の勝率の 期待値（標本平均の期待値） |
| ${\bar{σ_1}, \bar{σ_2}, \dots, \bar{σ_n}}$ | 局面の勝率の 標準偏差（標本平均の標準偏差） |
| ${μ_1, μ_2, \dots , μ_n}$ | 局面の 真の勝率（母平均） |
| ${σ_1, σ_2, \dots , σ_n}$ | 局面の 真の標準偏差（母標準偏差）2 |
多くの記号があるため混乱した人がいるかもしれませんが、上記の記号は統計学のルールに則って以下のように分類されています。
-
バー（記号の上の横棒「 $\bar{ }$ 」）がついている記号
これらは、すべて「有限回のプレイアウトによって得られた 標本」に関連する記号です。例えば、特定の局面 $s_{i}$ に対してプレイアウトを $p_{i}$ 回行った結果の「勝率」は、統計学における「母集団から無作為復元抽出を行って得られた標本」の 標本平均 そのものになります。以前の記事 で説明したように、標本に関する記号は、一般的に上にバーをつけた記号で表記します -
小文字 $r_i$ と大文字 $R_i$ の違い
小文字の $r_i$ は以前の記事で説明したように、プレイアウトによって実際に得られた「具体的な勝率の数値（実現値）」を表します。大文字の $R_i$ はプレイアウトを行う前の「ランダムに変動する勝率（確率変数）」そのものを表します。 - $μ$ と $σ$
$μ$ は平均を、$σ$ は標準偏差を表す際に一般的に用いられる記号です。なお、分散は $σ^2$ で表記します
最適化問題としての定式化
「プレイアウトの割り当て問題」の目標は、「最善手の精度（正解率）」という目的関数を最大化 することです。従って、この最適化問題の条件を整理すると下記のような表になります。なお、最適化問題の用語については以前の記事を参照して下さい。
| 最適化問題の用語 | 今回の問題での具体的な意味 | 数学的な記法・制約 |
|---|---|---|
| 目的関数 | 最善手を正しく選択する「精度」を表す関数 | $f(p_1, p_2, \dots, p_n)$ |
| 実行可能領域 | 各局面に割り当てる回数が取りうる値の範囲 | $\mathcal{X}$ |
| 制約 |
|
|
| 実行可能解 | ルール（実行可能領域と制約）を守った具体的な割り当て方 | $\{p_1, p_2, \dots , p_n\} \in \mathcal{X}$ |
| 最適解 | 最善手の精度が最大となる理想的な割り当て方 | $\{p_1^*, p_2^*, \dots , p_n^*\}$ |
このように整理すると、「プレイアウトの割り当て問題」が「制約（$p_i$ が 0 以上の整数で、合計が $p$）を満たす範囲のなかで、精度 $f$ を一番大きくしてくれる変数（$p_{1}, \dots, p_{n}$ の割り当て）の組み合わせを見つけること」であることがわかります。
これを、以前の記事で紹介した、最大化するパラメータを表す記号 $\mathrm{argmax}$ を用いて数式として表すと、下記のようになります。
$$\{p_1^*, p_2^*, \dots , p_n^*\} = \operatorname{argmax}_{\{p_1, p_2, \dots , p_n\} \in \mathcal{X}}f(p_1, p_2, \dots, p_n)$$
一見すると難しそうな数式ですが、言っていることは「ルール（$\mathcal{X}$）を守った割り当ての候補のなかで、精度（$f$）が最大となる割り当ての組み合わせを求めよ」というシンプルなものです。
目的関数の定式化
最適化問題を解くためには、目的関数 $f$（最善手の精度）を具体的な式で表す必要があるので、次はその定式化を行うことにします。
複数回のプレイアウトによって計算された「勝率」は「真の勝率の推定値」であるため、「勝率」が最大となる合法手が必ずしも本当に一番強い手である「真の最善手」に一致するとは限りません。ここでいう「真の最善手」とは、「無限にプレイアウトを繰り返したときの勝率（真の勝率 $\mu _{i}$）が最も高くなる合法手」のことです。
以前の記事で説明したように、標本平均の期待値は母平均（= 真の勝率）に一致するため、真の勝率は次のように「勝率の期待値」で表す ことができます。
$$μ_i = E[\bar{R_i}] = \bar{μ_i}$$
ここで、合法手の中で真の勝率が一番高い、「真の最善手の番号」を $max$ と表すことにします。
また、以後の説明では、わかりやすさを重視して以下のような表記を行うことにします。
- 真の最善手の局面 $s_{max}$ を「本命の局面」 と呼ぶ
- それ以外の局面を「ライバルの局面」 と呼ぶ
すると、すべてのプレイアウトが終わった後で、この「真の最善手」が選択されるためには、「すべてのライバルの局面の勝率が、本命の局面 $s_{max}$ に対して計算された勝率以下になる」という条件を満たす必要があります。このことを箇条書きで表すと以下のようになります。
- $\text{1 番の局面の勝率 } \bar{R_1} \le \text{真の最善手の局面の勝率 } \bar{R_{max}}$
- $\text{2 番の局面の勝率 } \bar{R_2} \le \text{真の最善手の局面の勝率 } \bar{R_{max}}$
- ...
- $\text{n 番の局面の勝率 } \bar{R_n} \le \text{真の最善手の局面の勝率 } \bar{R_{max}}$
これらが「すべて同時に成り立つ確率」が、最善手の精度を表す目的関数 $f$ の正体です。
上記のように 1 番から $n$ 番のすべてを箇条書きとして並べると、その中のどこかに「$\bar{R_{max}} \le \bar{R_{max}}$」という条件が必ず含まれるため、上記がすべて同時に成り立つことは「本命を含むすべての局面 の勝率が、本命の局面 $s_{max}$ に対して計算された勝率以下になる」という意味になります。
そのため、元の条件の「すべてのライバル局面」と異ってしまう点が気になる人がいるかもしれませんが、「$\bar{R_{max}} \le \bar{R_{max}}$」は「本命の局面の勝率が本命の局面の勝率以下になる」という 100 % 正しい当たり前の事を言っているにすぎません。従って、「$\bar{R_{max}} \le \bar{R_{max}}$」という条件が含まれていても問題はありません。
このことから、制約条件（プレイアウトの総数が $p$）を前提とした、目的関数 $f$ は、以下の 条件付き同時確率 の式で定義することができます。なお、式を簡潔にするため、すべての $p_i$ が 0 以上の整数であるという制約は省略しました。
$$f(p_1, p_2, \dots, p_n) = P(\bar{R_1} \le \bar{R_{max}}, \text{ }\bar{R_2} \le \bar{R_{max}}, \text{ }\dots\text{ }, \text{ }\bar{R_n} \le \bar{R_{max}} \mid \sum_{i=1}^{n}p_i = p)$$
一見すると複雑な数式と思えるかもしれませんが、「決められた総数 $p$ をみんなで分け合ったとき、本命が優勝する（すべてのライバルに負けない）確率」を計算しているだけです。
目的関数をうまく定式化することができましたが、実はこの同時確率の式をこのまま 厳密に（解析的に）解くことは極めて困難 です。そこで今回の記事では、「真の勝率が高い局面（有望な手）にプレイアウトを多く割り当てることが、なぜこの確率を高めることに繋がるのか」についての理由を、現実的な 「近似値」の考え方 を使ってわかりやすく説明することにします。
具体例での説明（3 つの合法手から最善手を選ぶ場合）
抽象的な数式のままだとイメージが湧きにくいので、ここでは下記の設定で、「合法手が 3 つ（$n=3$）ある具体的な局面 $s_1, s_2, s_3$」の場合について説明します。
- プレイアウトの総数 $p$： 1,000 回
- 3 つの局面の 真の勝率：それぞれ 0.3, 0.45, 0.6
- 各局面の 母標準偏差：説明をシンプルにするため、すべて $1$ と仮定する3
これを、さきほどの統計学の記号で書き表すと、次のようになります。
$$μ_1 = 0.3, μ_2 = 0.45, μ_3 = 0.6$$
$$σ_1 = σ_2 = σ_3 = 1$$
真の勝率の最大値は $μ_3= 0.6$ なので、この問題設定の「本命（真の最善手）の局面は $s_3$（$max = 3$）」、「ライバルの局面は $s_1$ と $s_2$」で決定します。従って $s_3$ が最善手として選択されれば「真の最善手」が選択されたことになります。
この設定を先程の目的関数に当てはめると下記のようになります。下記は本命の局面の勝率 $\bar{R_3}$ が、すべての局面の勝率以上になる確率を表します。
$$f(p_1, p_2, p_3) = P(\bar{R_1} \le \bar{R_3}, \text{ }\bar{R_2} \le \bar{R_3}, \text{ }\bar{R_3} \le \bar{R_3} \mid p_1 + p_2 + p_3 = 1,000)$$
ここで、式の一番右側にある $\bar{R_3} \le \bar{R_3}$ は「$s_{3}$ の勝率は、$s_{3}$ の勝率以下である」という 100 % いつでも成り立つ当たり前のことを表すためこの部分は省略しても構いません。そのため、上記の式を整理すると下記のようになります。
$$f(p_1, p_2, p_3) = P(\bar{R_1} \le \bar{R_3}, \text{ } \bar{R_2} \le \bar{R_3} \mid p_1 + p_2 + p_3 = 1,000)$$
ここから先の解説で毎回「後ろの条件（合計 1,000回）」を式の中に記述すると、式が長くなって非常にわかりづらくなります。そこで、ここからは 条件の部分を省略して下記のようにシンプルに表記 することにします。ただし、「合計が 1,000 回」という条件が無くなったわけではない 点に注意して下さい。
$$f(p_1, p_2, p_3) = P(\bar{R_1} \le \bar{R_3}, \text{ } \bar{R_2} \le \bar{R_3})$$
この目的関数は、ライバル（$s_1$ と $s_2$）の勝率がどちらも本命（$s_3$）の勝率を超えられない確率の事を表します。
目的関数の上限の考察
目的関数が定義されたので、この目的関数の $f$ の性質を深く掘り下げることにします。
確率の乗法定理 $P(A, B) = P(A)P(B \mid A) = P(B)P(A \mid B)$ を用いることで、目的関数を下記の 2 通りの形で表すことができます。
- $f(p_1, p_2, p_3) = P(\bar{R_1} \le \bar{R_3}) \times P(\bar{R_2} \le \bar{R_3} \mid \bar{R_1} \le \bar{R_3})$
- $f(p_1, p_2, p_3) = P(\bar{R_2} \le \bar{R_3}) \times P(\bar{R_1} \le \bar{R_3} \mid \bar{R_2} \le \bar{R_3})$
ここで、掛け算の後半にある条件付き確率に注目してください。どんなに複雑な確率であっても、確率は必ず「1 以下の値」になります。従って、上記の式はどちらも「1 以下の数を掛け算している」ため、元の数よりも大きくなることは絶対にありません。ここから、次の 2 つの不等式が導かれます。
- $f(p_1, p_2, p_3) \le P(\bar{R_1} \le \bar{R_3})$
- $f(p_1, p_2, p_3) \le P(\bar{R_2} \le \bar{R_3})$
この 2 つの式から、目的関数 には、下記の式の右辺で表される、決して超えることのできない「上限（天井）」があることがわかります。
$$f(p_1, p_2, p_3) \le \min(P(\bar{R_1} \le \bar{R_3}), \text{ }P(\bar{R_2} \le \bar{R_3}))$$
バランスの良い割り当ての重要性
上記の不等式から、最善手の精度を高める際に下記の「本命が個々のライバルに負けない確率」を 両方をバランスよく高める必要がある という、重要な事実が導かれます。
- $P(\bar{R_1} \le \bar{R_3})$：本命（$s_3$）が $s_1$ に負けない確率
- $P(\bar{R_2} \le \bar{R_3})$：本命（$s_3$）が $s_2$ に負けない確率
例えば、本命である $s_3$ が $s_1$ に負けないようにするためにどれだけ頑張って $P(\bar{R_1} \le \bar{R_3})$ を 0.999（99.9 %）まで高めても、もう片方の $s_2$ に対する $P(\bar{R_2} \le \bar{R_3})$ が 0.01（1 %）しかなければ、最善手の精度（目的関数 $f$）は絶対に 1 % 以下に抑え込まれてしまいます。
つまち、先程示した下記の式は、$P(\bar{R_1} \le \bar{R_3})$ と $P(\bar{R_2} \le \bar{R_3})$ の どちらか片方を頑張って高めても、もう片方の値が小さければ目的関数の最大値がもう片方の値以下になってしまう ことを表します。
$$f(p_1, p_2, p_3) \le \min(P(\bar{R_1} \le \bar{R_3}), \text{ }P(\bar{R_2} \le \bar{R_3}))$$
このことから、目的関数を最大化 するためには、特定の局面だけに注目して片方だけを無理に高めるのではなく、$P(\bar{R_1} \le \bar{R_3})$ と $P(\bar{R_2} \le \bar{R_3})$ の 両方をバランスよく大きくする ことが重要になります。
このことは、全勝しないと優勝できない大会で、ライバルを一人に絞ってどれだけ練習を行っても、他のライバルに対する練習を怠ってしまうと優勝できる確率が激減してしまうということに似ています。つまり、優勝するためには、ライバル全員にまんべんなく勝てるように練習時間を割り当てる必要があるということです。
上記で「バランスよく」という少し曖昧な表現を使ったのには、数学的な理由があります。それは、プレイアウトの総数（$p=1,000$）という 限られた回数を 3 つの局面で奪い合っているから です。
この制約を、2 番目の局面の回数 $p_{2}$ について解くと下記のようになります。
$$p_2 = 1,000 - p_1 - p_3$$
各局面のプレイアウトの回数は 0 以上の整数なので、例えば $s_{1}$ の勝率を正確に見極めようとして $p_1 = 990$ 回も使ってしまうと、$p_{2}$ には最大でも 10 回しか残されません。このように、$p_{1}$ を動かすと連動して $p_{2}$ の上限も変わってしまう（お互いに独立していない）ため、2 つの確率を完全に狙い通りの同じ値にコントロールできるとは限りません。だからこそ、「限られたプレイアウトの回数の中で、両方をうまく高めるというバランス感覚」が求められるのです。
確率の近似
先程の考察から、目的関数には以下のような上限があることがわかりました。
$$f(p_1, p_2, p_3) \le \min(P(\bar{R_1} \le \bar{R_3}), \text{ }P(\bar{R_2} \le \bar{R_3}))$$
この $P(\bar{R_1} \le \bar{R_3})$ という式を厳密に計算しようとすると、2 つの動く変数同士（確率変数）の引き算を考える必要があり、高校数学の範囲を超えてかなり複雑になってしまいます。そこで、本記事ではこの式を 近似（だいたいの値で考えること）することで、この式の性質を簡潔に分析できるようにします。
本命である $s_{3}$ の勝率（$={\bar{r_{3}}}$）は、プレイアウトによってランダムに計算されるため、真の勝率からのばらつきが生じます。しかし、ここでは「$s_{3}$ には十分な回数のプレイアウトを割り当てるため、ばらつき（分散）はほぼゼロであり、常に真の勝率である $\mu_3 = 0.6$ という固定値をとる」と仮定してみましょう。
このように仮定することで、先ほどの確率は以下のように一つの確率変数だけを用いたシンプルな形に近似できます。
$$P(\bar{R_1} \le \bar{R_3}) \approx P(\bar{R_1} \le μ_3)$$
$$P(\bar{R_2} \le \bar{R_3}) \approx P(\bar{R_2} \le μ_3)$$
このように「右側の確率変数を固定の数字」にすることで、この後で説明するように、正規分布の性質を使って、簡単に性質を調べることができるようになります。
厳密に考えるなら、新しい確率変数 $\bar{R} = \bar{R_1} - \bar{R_3}$ を定義し、この差が 0 以下になる確率 $P(\bar{R} \le 0)$ を計算することになります
この後で説明しますが、$\bar{R_1}$ も $\bar{R_3}$ も正規分布で近似することができ、その引き算で定義される $\bar{R}$ もまた正規分布に従うことが知られています。数学的には $\bar{R}$ を解くことも可能ですが、式がかなり複雑でわかりづらくなってしまうため、今回は直感的に理解しやすい「右側を固定する近似」を採用しました。
この近似の妥当性
「勝率のばらつきをゼロにするという勝手な仮定をして大丈夫なのか？」と思う人がいるかもしれません。
実際に、厳密にいえば $s_{3}$ の勝率は $μ_3$ からばらつきます。例えば、本命の $s_{3}$ の勝率 $\bar{r_3}$ が下振れして、真の勝率（0.6）よりも低い値（例えば 0.5 など）になると、ライバルである $s_1$ から見ればターゲットの勝率が下がるため、「ライバルの勝率 $\bar{r_1}$ が本命の勝率 $\bar{r_3}$ を逆転しやすくなる（＝ $s_{3}$ の勝率以下に収まる確率が低くなる）」ことになります。つまり、$s_{3}$ の勝率がばらつく分だけ、厳密な確率は先ほどの近似式 $P(\bar{R_1} \le \mu_3)$ よりも少しだけ厳しい（低い）値になります。
従って、$s_3$ の勝率のばらつきが大きければ大きいほど、この「近似値とのズレ」は開いてしまいます が、ここでモンテカルロ木探索の基本方針が「真の勝率が最も高い $s_{3}$ にプレイアウトの回数を最も多く割り当てるアルゴリズム」であることを思い出してください。
統計学の「大数の法則」により、プレイアウトの回数を増やせば増やすほど、その局面の勝率のばらつき（分散）は限りなくゼロに近づいていきます。つまり、モンテカルロ探索のアルゴリズムが正しく動いている前提であれば、$s_{3}$ のばらつきは実際にほぼゼロになるため、この近似を行っても実用上は問題はありません。
プレイアウトの総数 $p$ が例えば 10 回のように極端に少ない場合は、$s_3$ に割り当てることができるプレイアウトの回数も少なくなるため、$\bar{R_3}$ の分散は大きな値になってしまい、このような近似を行うことができなくなります。
しかし、そもそもプレイアウトの総数 $p$ が少なすぎる場合は、どのようなアルゴリズムを用いても最善手の精度を高めることは不可能です。そのため、この記事では「十分なプレイアウト総数があり、$s_{3}$ のばらつきを十分に小さくできている」という現実的な設定を前提としています。
正規分布の性質のおさらい
本命の $s_{3}$ の勝率を固定の数字 $μ_{3}$ に置き換えたことで、目的関数 $f$ の性質を検証するためには、以下の 2 つの式を検証すれば良いことになります。
- $P(\bar{R_1} \le \mu_3 = 0.6)$
- $P(\bar{R_2} \le \mu_3 = 0.6)$
以前の記事で説明したように、統計学の「中心極限定理」から、プレイアウト（無作為復元抽出）を繰り返して求めた各局面の勝率 $\bar{r_i}$（標本平均）は、回数が増えるほど「正規分布（左右対称な山型の分布）」に近づいていくという性質があります。
ここで、これからの考察で用いる「正規分布が持つ確率のルール」をおさらいしします。
平均から「標準偏差の何倍離れているか」の確率
以前の記事で説明したように、どのような平均 $μ$ と標準偏差 $σ$ を持つ正規分布であっても、平均を中心とした「標準偏差の倍数」の幅の中に、データが以下の確率で収まることが数学的に決まっています。
- $平均±標準偏差（σ）の範囲に収まる確率 \approx 約 68 \%$
- $平均±標準偏差の 2 倍（2σ）の範囲に収まる確率 \approx 約 95 \%$
- $平均±標準偏差の 3 倍（3σ）の範囲に収まる確率 \approx 約 99.7 \%$
上記を式で表すと下記のようになります。ただし、正規分布を表す確率変数を $X$ とします。
- $P(μ - σ \le X \le μ + σ) \approx 0.68$
- $P(μ - 2σ \le X \le μ + 2σ) \approx 0.95$
- $P(μ - 3σ \le X \le μ + 3σ) \approx 0.997$
下記は平均が $μ = 0$、標準偏差が $σ = 1$ の標準正規分布を表すグラフです。正規分布は連続型確率分布であり、連続型確率分布のグラフはグラフと x 軸の間の範囲の面積が確率を表します。従って、$P(0 - 1 \le X \le 0 + 1) \approx 0.68$ から、下記のグラフの平均から $\pm 1$ の範囲（赤色の面積）が全体の約 68% を占めます。
参考までに上記のグラフを描画するプログラムを下記に示します。プログラムの意味については以前の記事を参照して下さい。
import matplotlib.pyplot as plt
import numpy as np
from statistics import NormalDist
ndist = NormalDist(0, 1)
X = np.linspace(-4, 4, 400)
Y = [ndist.pdf(x) for x in X]
plt.plot(X, Y)
# x が -1 以上、および 1 以上となる最初のインデックスを求める
minx = np.argmax(X >= -1)
maxx = np.argmax(X >= 1)
# その範囲を赤色で塗りつぶす
plt.fill_between(X[minx:maxx], 0, Y[minx:maxx], color="r")
「片側の壁」を超えない確率
正規分布のグラフは平均を中心に「左右が完全に左右対称」となります。そのため、全体の半分（50 %）のデータは必ず平均以下に存在します。この性質と先程説明した性質を組み合わせると、「ある特定の壁（上限・下限）以下（以上）にデータが収まる確率」を以下のように導き出すことができます。
- $「平均 + 標準偏差（1σ）」以下になる確率 \approx 約 84.1 %$
- $「平均 - 標準偏差（1σ）」以上になる確率 \approx 約 84.1 %$
- $「平均 + 標準偏差の 2 倍（2σ）」以下になる確率 \approx 約 97.7 %$
- $「平均 - 標準偏差の 2 倍（2σ）」以上になる確率 \approx 約 97.7 %$
- $「平均 + 標準偏差の 3 倍（3σ）」以下になる確率 \approx 約 99.9 %$
- $「平均 - 標準偏差の 3 倍（3σ）」以上になる確率 \approx 約 99.9 %$
上記を式で表すと下記のようになります。
- $P(X \le μ + σ) \approx 0.841$
- $P(μ - σ \le X) \approx 0.841$
- $P(X \le μ + 2σ) \approx 0.977$
- $P(μ - 2σ \le X) \approx 0.977$
- $P(X \le μ + 3σ) \approx 0.999$
- $P(μ - 3σ \le X) \approx 0.999$
下記は標準正規分布の「平均 ＋ 標準偏差（$1σ$）」以下のすべての範囲を塗りつぶしたグラフで、赤色の範囲が全体の約 84.1 % の面積になります。
この性質を利用して $P(\bar{R_1} \le μ_3)$ と $P(\bar{R_2} \le μ_3)$ の性質について考察することにします。
参考までに上記のグラフを描画するプログラムを下記に示します。
X = np.linspace(-4, 4, 400)
Y = [ndist.pdf(x) for x in X]
plt.plot(X, Y)
minx = 0
maxx = np.argmax(X >= 1) # x が 1 以上となる最初のインデックスを求める
plt.fill_between(X[minx:maxx], 0, Y[minx:maxx], color="r")
各局面の勝率の「平均」と「ブレの幅（標準偏差）」
上記で説明した正規分布の性質を利用するために、プレイアウトによって得られる各局面の勝率 $\bar{R_i}$ の「平均（期待値）$\bar{μ_i}$」と「標準偏差 $\bar{σ_i}$」が具体的にどのような数式になるかを計算することにします。
以前の記事で説明したように、標本平均の期待値は、母平均（真の勝率）と完全に一致します。従って、今回の設定値を当てはめると下記のようになります。
$$E[\bar{R_1}] = μ_1 = 0.3, E[\bar{R_2}] = μ_2 = 0.45, E[\bar{R_3}] = μ_3 = 0.6$$
また、以前の記事で説明したように、標本平均の分散は「母分散を標本サイズ（回数）で割ったもの」になり、標準偏差はその平方根になります。従って、各局面に割り当てたプレイアウト回数 $p_{i}$ を用いた下記の式が成り立ちます。
- 分散：$V[\bar{R_i}] = \bar{σ_i^2} = \dfrac{σ_i^2}{p_i}$
- 標準偏差：$SD[\bar{R_i}] = \bar{σ_i} = \sqrt{V[R_i]} =\dfrac{σ_i}{\sqrt{p_i}}$
上記の式を言葉で説明すると以下のようになります。
- プレイアウトによって求められた勝率の平均値（期待値）$\bar{μ_i}$ は、真の勝率（母平均）$μ_i$ に一致する
- プレイアウトによって求められた勝率のばらつき（分散）$\bar{σ_i^2}$ は、プレイアウト回数 $p_{i}$ に反比例して小さくなる。
- プレイアウトによって求められた勝率のブレの幅（標準偏差）$\bar{σ_i}$ は、プレイアウト回数のルート（平方根） $\sqrt{p_{i}}$ に反比例して小さくなる。
上記を今回の具体的な設定である「すべての局面の母標準偏差が $\sigma_1 = \sigma_2 = \sigma_3 = 1$」を、先程の標準偏差の式に当てはめると、各局面の勝率のブレ（標準偏差 $\sigma _{i}$）は、下記のようにシンプルな式になります。
$$\bar{σ_i} = \frac{1}{\sqrt{p_i}}$$
この式は、プレイアウトによって計算される勝率の精度が以下のような性質を持つことを表します。
勝率のブレの幅（標準偏差）を半分（1/2）に抑え込んで正確な勝率を求めるためには、プレイアウトの回数は 2 倍ではなく、その 2 乗である「4 倍」も割り当てなければならない。
1 番の局面に割り当てるプレイアウトの回数の計算
考察に必要な準備が整ったので、ライバルの一つである 1 番の局面に焦点を当てて考察を行うことにします。具体的には 1 番の局面 $s_1$ の勝率 $\bar{R_1}$ が本命の勝率の壁（$μ_3$）を簡単に超えないようにするためには、プレイアウトの回数をどれくらい割り当てれば良いかについて考察します。
先程説明したように、局面 $s_1$ に対して割り当てるプレイアウトの回数を増やすと、$\bar{R_1}$ の確率分布は正規分布に近づいていきます。そこで、$R_1$ が正規分布で近似できると仮定すると、先程説明した下記の正規分布の性質（「片側の壁」を超えない確率）を当てはめることができるようになります。
- $「平均 + 標準偏差（1σ）」以下になる確率 \approx 約 84.1 %$
- $「平均 + 標準偏差の 2 倍（2σ）」以下になる確率 \approx 約 97.7 %$
- $「平均 + 標準偏差の 3 倍（3σ）」以下になる確率 \approx 約 99.9 %$
これを「ライバルの勝率が本命を超えない確率を表す $P(\bar{R_1} \le μ_3)$」に当てはめると、$\mu_{3}$ の値がちょうど $s_{1}$ の勝率の平均（= 真の勝率）と標準偏差を足した値である $\mu_1 + \bar{\sigma_1}$ に等しければ、$P(\bar{R_1} \le μ_3)$ は約 84.1 % になります。
これを一般化するために、「本命とライバルの真の勝率の差 $\mu_3 - \mu_1$ が、ライバルのブレ幅 $\bar{\sigma _{1}}$ の何倍離れているか」を表す倍数を $m$ 4と置くこと、下記の式のようになります。
$$\mu_{1}+m{\bar{\sigma _{1}}}=\mu _{3}$$
この $m$ という倍数は、ライバルの勝率の精度を決める役割 を持っています。$m$ の値を大きくするとライバルの勝率の精度が高まるため、ライバルの勝率が上振れしてが本命の勝率を超えづらくなります。そのため、先程説明した「片側の壁」を超えない確率のルールのように、$m$ の値を 1, 2, 3 と大きく設定すればするほど、ライバルが本命を逆転できなくなる確率 $P(\bar{R_1} \le \mu_3)$ を 100% に近づけることができるのです。
m とプレイアウトの回数の関係
上記で説明したように、$m$ は「ライバルが本命を超えない確率 $P(\bar{R_1} \le \mu_3)$」を決定するパラメータの役割を果たします。従って、プレイアウトの回数を表す $p_i$ を $m$ の式で表すことができれば、$P(\bar{R_1} \le \mu_3)$ とプレイアウトの回数 $p_i$ の関係がわかるようになります。
まず、先程の式を $s_{1}$ のブレ幅（標準偏差 $\bar{\sigma_{1}}$）について解くと、以下のようになります
$$\bar{σ_1} = \frac{μ_3 - μ_1}{m}$$
真の勝率である $μ_1$ と $μ_3$ はあらかじめ決まっている定数なので、「$m$ を大きくして本命がライバルに負けない確率を高めたいなら、それだけブレ幅（$={\bar{\sigma_{1}}}$）を小さく抑え込まなければいけない」という当たり前の事実を表します。
この式に先程求めた標準偏差の式 $\bar{σ_1} = \dfrac{σ_1}{\sqrt{p_1}}$ を代入すると下記のようになります。
$$\frac{σ_1}{\sqrt{p_1}} = \frac{μ_3 - μ_1}{m}$$
両辺の分母と分子をひっくり返して、ルートを消すために 2 乗すると、下記のようにライバル $s_{1}$ に割り当てるべきプレイアウトの回数 $p_{1}$ の数式を求めることができます。
$$p_1 = \frac{m^2σ_1^2}{(μ_3 - μ_1) ^2}$$
この式から、プレイアウトの回数 $p_1$ が以下のような重要な性質を持つことがわかります。
-
安全性を高めようとすると、プレイアウトの回数が「2 乗」で跳ね上がる
ライバルを完璧に返り討ちにするために $m$ を大きくしようとすると、必要なプレイアウト回数は $m$ の 2 乗に比例して爆発的に増えていく5 -
実力が近いライバルほど、プレイアウトの回数が跳ね上がる
分母にある、本命とライバルの真の勝率の差を表す $\mu_3 - \mu_1$ は、本命とライバルの実力差を表しています。従って、本命とライバルの実力差が小さければ小さいほど（＝実力が伯仲しているほど）、この値の 2 乗である分母が急速にゼロに近づくため、必要なプレイアウトの回数は 2 乗に反比例して急激に膨れ上がってしまいます。
これらの性質を現実の世界で例えると、下記のような誰もが直観的に理解している常識に相当します。つまり、先程の式は、下記のような常識を表す数式であると考えることができます。
- テストの点数を 30 点から 50 点に上げる場合はそれほど大変ではないが、90 点から 95 点、98 点から 99 点のように 100 点に近づけようとすればするほど急激に大変になっていく
- 実力が近い相手ほど、たくさん調べないといけない（多くの練習が必要になる）
具体例での考察
$m$ の値からプレイアウトの回数を求める式がわかったので、今回の設定値として（ライバルの真の勝率 $μ_1 = 0.3$、本命の真の勝率 $μ_3 = 0.6$、ライバルの母標準偏差 $σ_1 = 1$）を当てはめると下記の式になります。
$$p_1 = \frac{m^2\cdot1^2}{(0.6 - 0.3) ^2} = \frac{m^2}{0.09}$$
この式に $m = 1, 2, 3$ を代入してプレイアウトの回数を求め、本命がライバルを返り討ちにできる確率 $P(\bar{R_1} \le μ_3)$ をまとめると下記の表のようになります。なお、プレイアウトの回数は小数点以下第 2 桁で四捨五入しました。
| $m$ の値 | プレイアウトの回数 $p_1$ | ライバルを返り討ちにする確率 $P(\bar{R_1} \le μ_3)$ |
|---|---|---|
| 1 | 11.1 | 84.1 % |
| 2 | 44.4 | 97.7 % |
| 3 | 100.0 | 99.9 % |
この結果から、先程説明した以下の 2 つの重要な性質を確認することができます。
- プレイアウトの回数を増やせば増やすほど、ライバルを返り討ちにできる確率を確実に高めていくことができる
- ライバルを返り討ちにできる確率を高めようとして $m=1$ から $m=3$ へと 3 倍にすると、必要なプレイアウトの回数は $11.1$ から $100.0$ へと、$m$ の 2 乗（$3^2 ＝ 9$ 倍）のペースで一気に跳ね上がる
2 番の局面（もう一人のライバル）に割り当てるプレイアウトの回数の計算
もうひとつのライバルの局面（$s_2$）に割り当てるプレイアウトの回数は全く同じ方法で計算することができます。具体的には、先程の式の $p_1, σ_1, μ_1$ をすべて $s_2$ のものである $p_2, σ_2, μ_2$ に入れ替えた下記の式が成り立ちます。
$$p_2 = \frac{m^2σ_2^2}{(μ_3 - μ_2) ^2}$$
この式に、$s_2$ の設定値として（真の勝率 $μ_2 = 0.45$、本命の真の勝率 $μ_3 = 0.6$、母標準偏差 $σ_2 = 1$）を当てはめてみます。
$$p_2 = \frac{m^2\cdot1^2}{(0.6 - 0.45) ^2} = \frac{m^2}{0.0225}$$
同じように $m = 1, 2, 3$ を代入して必要なプレイアウトの回数 $p_2$ を求め、本命がライバルを返り討ちにできる確率 $P(\bar{R_2} \le μ_3)$ をまとめると下記の表のようになります。
| $m$ の値 | プレイアウトの回数 $p_2$ | ライバルを返り討ちにする確率 $P(\bar{R_2} \le μ_3)$ |
|---|---|---|
| 1 | 44.4 | 84.1 % |
| 2 | 100.0 | 97.7 % |
| 3 | 400.0 | 99.9 % |
この結果から、1 番の局面と全く同じ以下の 2 つの重要な性質を確認することができます。
- プレイアウトの回数を増やせば増やすほど、ライバルを返り討ちにできる確率を確実に高めていくことができる
- ライバルを返り討ちにできる確率を高めようとして $m=1$ から $m=3$ へと 3 倍にすると、必要なプレイアウトの回数は $44.4$ から $400.0$ へと、$m$ の 2 乗（$3^2 ＝ 9$ 倍）のペースで一気に跳ね上がる
2 つのライバルの比較
今回の記事の冒頭で説明したように、最善手の精度を高める（目的関数を最大化する）ためには、「すべてのライバルをバランスよく、同程度に返り討ちにする」 必要があります。
そこで、本命がライバルである $s_1$ と $s_2$ に同程度に負けないという「理想的な配分バランス」を並べて比較することにします。下記は先ほどの計算結果をまとめた表です。
| 本命がライバルを 返り討ちにする確率 |
$s_1$ のプレイアウトの回数 | $s_2$ のプレイアウトの回数 |
|---|---|---|
| 84.1 %（$m = 1$） | 11.1 | 44.4 |
| 97.7 %（$m = 2$） | 44.4 | 100.0 |
| 99.9 %（$m = 3$） | 100.0 | 400.0 |
この表から、本命がライバルを返り討ちにする確率を同じにしようとすると、実力が近い $s_2$ に対してより多くのプレイアウトを割り当てる必要があることが確認できます。さらに、どの確率を目指す場合であっても、$s_{2}$ に必要な回数は、常に $s_{1}$ の「ぴったり 4 倍」になることがわかります。
プレイアウトの回数が常に 4 倍になる理由
プレイアウトの回数が常に 4 倍になる理由は、さきほど導き出した下記の「プレイアウトの回数が、真の勝率の差の 2 乗に反比例する」という数学の法則によるものです。
$$p_1 = \frac{m^2σ_1^2}{(μ_3 - μ_1) ^2}$$
ふたつのライバルと、本命との「実力（= 真の勝率）の差」を計算すると下記のようになります。
- 本命とライバル $s_{1}$ の実力差：$0.6 - 0.3 = \mathbf{0.3}$
- 本命とライバル $s_{2}$ の実力差：$0.6 - 0.45 = \mathbf{0.15}$
実力の差を比べると、$s_{2}$ の方は $s_{1}$ よりも 「2 分の 1」の距離まで本命に肉薄している（実力が近い） ことが分かります。距離が $\frac{1}{2}$ に縮まったということは、プレイアウトの必要な回数は「2 乗に反比例」するため、$\left(\frac{1}{2}\right)^2 = \frac{1}{4}$ の逆数、つまり「4 倍」のプレイアウト が必要になります。
局面の数の一般化
ここまでは、局面の数が 3（ライバルの数が 2）の具体例で考えてきましたが、局面の数が 4 つ、5 つ…… あるいは 100 個に増えても、数学的な本質はまったく変わりません。
本命以外のすべてのライバルの局面 $s_{i}$ を同程度に返り討ちにする（バランスよく抑え込む）ために必要なプレイアウトの回数は、以下の式で一般化することができます。
$$p_i = \frac{m^2σ_i^2}{(μ_{max} - μ_i) ^2}$$
この数式こそが、モンテカルロ木探索の「探索の選択と集中」という考え方の正体です。「本命に実力が近い（真の勝率 $μ_i$ が高い）手ほど分母が小さくなるため、より多くのプレイアウトを注ぎ込んで『えこひいき』して調べなければならない というモンテカルロ木探索の思想が合理的であることが、この式から証明されます。
本命の局面に「最高のえこひいき」が必要となる理由
ここまでの説明では、話をシンプルにするために「本命 $s_{max}$ の勝率はばらつき（分散）が完全に 0（定数 $μ_{max}$）である」と仮定して、ライバルたちに必要なプレイアウトの回数を計算してきました。そのため、肝心の本命の局面に対して具体的にどれほどのプレイアウトの回数を割り当てるべきであるかについては説明しませんでした。そこで、本命の局面 $s_{max}$ に対して、ライバルたち以上に最も多くのプレイアウトを割り当てることの数学的なメリットについて説明します。
今度は逆に、「ライバルの中で 2 番目に強い強敵（勝率 $\mu_{2nd}$）のばらつき（分散）がほぼゼロである」と仮定して、本命側が勝つ確率 $P(\mu_{2nd} \le \bar{R_{max}})$ の視点から考えてみることにします。本命の勝率 $R_{max}$ が、2番手の実力 $\mu_{2nd}$ という壁を上回る（＝正しく本命が最善手として選ばれる）確率は、下記の正規分布の「片側の壁を超えないルール」から、まったく同じように計算することができます。
- $「平均 - 標準偏差（1σ）」以上になる確率 \approx 約 84.1 \%$
- $「平均 - 標準偏差の 2 倍（2σ）」以上になる確率 \approx 約 97.7 \%$
- $「平均 - 標準偏差の 3 倍（3σ）」以上になる確率 \approx 約 99.9 \%$
先程と同様に（本命の勝率の精度を決める役割を持つ）標準偏差の倍率を $m$ とすると、本命 $s_{max}$ に最低限割り当てる必要があるプレイアウトの回数 $p_{max}$ は、以下の式で求めることができます。
$$p_{max} = \frac{m^2σ_{max}^2}{(μ_{max} - μ_{2nd}) ^2}$$
この式の分母にあるのは「本命と、2 番手のライバルの実力差」です。つまり、本命の手であっても、2 番手のライバルと実力が僅差であればあるほど、分母が極端に小さくなるため、ライバルたちと同等かそれ以上のプレイアウトの回数（えこひいき）が必要になることがわかります。
未来の先読み（2 手目以降）での本命の精度の重要性
今回の記事では、話をシンプルにするために「1 手先（深さ 1）だけを評価する」という設定で考えてきましたが、モンテカルロ木探索は本来は 2 手、3 手 と読みの深さを広げていくアルゴリズムです。
実は、2 手目以降の深い読みを行うようになると、「本命の勝率の精度」が最終的に求められる最善手（目的関数）の精度を決める極めて重要な要素になります。
前回の記事で説明したように、深さが 2 以上の探索では以下のようにミニマックス法を使って、未来の勝率を現在へとさかのぼって伝えていきます6。
- 未来の $t$ 手目の局面に対してプレイアウトを行い、それぞれの勝率を求める
- 1 手手前の $t - 1$ 手目の局面の勝率を、そこから合法手を着手した局面の「勝率の最大値（= 本命の勝率）」とする
- この処理を繰り返すことで 1 手目までの局面の勝率を求め、最終的な 1 手目の最善手を求める
ここで、上記の手順 2 に注目すると、1 手前の局面の勝率として引き継がれるのは、常に「本命（最大値）の勝率」ただ一つ であり、ライバルたちの勝率は、その場で切り捨てられてその後は一切使用されません。
このとき、1 番強いはずの本命のプレイアウトの回数が足りず、その勝率データが大きな誤差を含んだ状態であると、ライバルたちにどれだけ多くのプレイアウトを割り当てたとしても、大きな誤差を含んだ勝率を用いて $t -1$ 手目以前の局面の勝率の計算が行われてしまうことになります。その結果、最終的に計算される最善手が「大きな誤差が含まれた勝率」を元に計算されることになり、結果として計算された最善手にも大きな誤差が含まれることになってしまいます。従って、本命の局面に対しては特に多くのプレイアウトの回数を割り当てて、計算される勝率の精度を高めることが極めて重要 になります。
以上から、「ライバルを抑え込むため」にも、「そして未来の読みの精度を正しく保つため」にも、「真の勝率が高い有望な手ほど、プレイアウトを多く割り当てなければならない」というモンテカルロ木探索の方針が合理的であることが示されました。
標準偏差に関する補足
これまでの解説では話をシンプルにするために、すべての局面の標準偏差を $\sigma_i = 1$ と固定して考えてきました。しかし、現実のゲームでは、局面によって勝率のブレ幅（母標準偏差）も当然異なります。また、先ほど示した下記の一般化の式の分子には、母標準偏差の 2 乗 $\sigma _{i}^{2}$ が存在するため、プレイアウトの回数には母標準偏差が影響します。
$$p_i = \frac{m^2σ_i^2}{(μ_{max} - μ_i) ^2}$$
この分子にある母標準偏差の 2 乗（$\sigma _{i}^{2}$）から、下記のような事実がわかります。
「たとえ真の勝率が少し低そうな手であっても、その局面の勝率のブレ幅（$\sigma _{i}$） が極端に大きい場合は、多めにプレイアウトを割り振る必要がある」
つまり、ゲームにおいて「標準偏差（ブレ幅）が大きい」とは、「まだよく分かっていない、大逆転のチャンス（あるいは大失敗の可能性）を秘めた、激しい展開が予想される局面」ということを表します。
実用上はすべての標準偏差を同じとみなして（= 1 と仮定して）計算しても大きな問題は起きませんが、厳密には「勝率が高い手（本命に近い手）」だけでなく、「ブレ幅が大きい手（よく分からない手）」もえこひいきの対象にする必要があります。詳細は今後の記事で説明しますが、実際にモンテカルロ木探索ではこのブレ幅も考慮に入れたプレイアウトの割り当てを行います。
今回の記事のまとめとモンテカルロ木探索の新たな課題
今回の記事では、「真の勝率が高い有望な手ほど、プレイアウトを多く割り当てなければならない」というモンテカルロ木探索の「えこひいき」の方針が数学的に合理的であることを証明しました。
ここまでの説明は、最初からそれぞれの局面の真の勝率（実力）がわかっているという前提 でプレイアウトの割り当てをどのように行うべきかについて説明しました。しかし、現実の強化学習では、まったく未知の状態から学習を始めるため、当然ですが、どの手がどれくらい強いのかということは事前には分かりません。また、仮にすべての局面の真の勝率があらかじめ計算できるのであれば、最初から真の勝率が最も高い合法手を選択すれば良いため、プレイアウトを行う必要がそもそもありません。
実力が分からないのに、実力が高い手をえこひいきしなければならないという、一見すると無理難題に見える課題をクリアするために、モンテカルロ木探索は下記の 「探索」と「活用」をリアルタイムに並行して行う というより困難な処理を行う必要があります。
- 探索（Exploration）：未知の局面の「本当の実力（真の勝率）」を正しく推測するために、いろんな手を幅広く試すこと
- 活用（Exploitation）：これまでに行った探索から「この手が強そうだ」と分かった有望な手に、プレイアウトを多く割り当てる（えこひいきする）こと
この問題の難しい所は、「探索」と「活用」のバランスです。「探索」と「活用」には下記のようなトレードオフがあるため、どのようなバランスで「探索」と「活用」を行うかによって、最終的に求められる最善手の精度が大きく変わってしまうからです。
-
「探索」を重視して、いろんな手をたくさん調べた場合
- 利点：各局面に対して多くのプレイアウトが割り当てられるため、すべての局面での勝率の精度が向上する（見落としが減る）
- 欠点：明らかに弱そうな手にまで貴重な時間（プレイアウト）を費やすことになるという 無駄が生じる ため、深くまで探索することができなくなる
-
「活用」を重視して、強そうな手ばかりをえこひいきした場合
- 利点：強そうな手にプレイアウトを集中できるため、__効率よく深くまで探索することができる __
- 欠点：探索の回数が少なくなるため、勝率の精度が悪化する。その結果、最初の方に「たまたま偶然うまくいっただけの手」に騙されやすく、他に眠っているかもしれない__「本当の最善手」を見落としてしまう__
「探索」と「活用」をどのようなバランスで行うかについては様々なアルゴリズムが考案されており、モンテカルロ木探索では「UCB1（UCT）」というアルゴリズムが採用されています。次回の記事ではそれらのアルゴリズムの性質を比較しながら詳しく解説する予定です。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
次回の記事
近日公開予定です。
-
前回の記事で説明したように、「制限時間を設定する」ということは、「AI が実行できるプレイアウトの総数を決める」ということと同じ意味をもちます ↩
-
真の勝率と同様に、プレイアウトを無限に繰り返すことで得られた値の標準偏差、すなわち母集団の標準偏差（母標準偏差）の事を表します ↩
-
この設定は説明をシンプルにするためのものです。一般的には母標準偏差はもっと小さな値になります。また、すべての局面の母標準偏差が完全に一致することはほとんどありません ↩
-
統計学ではよく $n$ という記号が用いられますが、既に合法手の総数を表す記号として $n$ を使っているため、ここでは $m$ を用いました ↩
-
プレイアウトの回数は $m$ の 2 乗に比例して増えますが、$P(\bar{R_1} \le μ_3)$ の値そのものが 2 乗のペースで増えるわけではない（確率の上限は 1 なのでだんだん緩やかになる）点に注意して下さい ↩
-
前回の記事ではこの手順 2 の処理を、$t-1$ 手目の手番によって「勝率の最大値」と「勝率の最小値」を分けて表記しましたが、説明を簡単にするために、勝率はすべて「その手番のプレイヤーから見た勝率」に統一されているものとします。 ↩