Pythonで〇×ゲームのAIを一から作成する その243 原始モンテカルロ法の定式化とアルゴリズムの性質

目次と前回の記事

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 の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

今回の記事の内容

以前の記事では強化学習が下記の式で定式化できることを示しました¹。

強化学習の目的は、環境によって下記が定義された場合に、エージェントと環境の相互作用によって得られた経験を元に、目的関数 $V_Π(s_0)$ を最大化する、下記の式で定式化される最適方策 $Π^*$ を見つけることである。

$$Π^* = \operatorname{argmax}_{Π} V_Π(s_0)$$

• 状態の集合（状態空間）を表す $\mathcal{S}$
• 行動の集合（行動空間）を表す $\mathcal{A}$
• 「任意の状態 $s \in \mathcal{S}$」と「その状態 $s$ で取りうる任意の行動 $a \in \mathcal{A}(s)$」のすべての組み合わせに対する「状態遷移関数 $f(s, a)$」と「報酬関数 $r(s, a)$」
• エピソードの開始時の初期状態を表す $s_0$
• エピソードの終了条件（特定の状態への遷移、一定時間の経過など）

上記は状態遷移と報酬関数が 〇× ゲームのように決定論的な場合の定式化です。それらが確率的な場合については今後の記事で紹介する予定です。

今回の記事では、強化学習の手法の一つである「原始モンテカルロ法の定式化」について説明します。

強化学習の数式を厳密に解こうとすると膨大な計算量が必要になりますが、以前の記事で説明した下記の原始モンテカルロ法は「ランダムにシミュレーションを繰り返す（プレイアウトする）」ことで、大数の法則を利用して目的関数の近似値を効率よく計算するというアプローチを取ります。今回の記事では、下記の原始モンテカルロ法のアルゴリズムが、上記で定式化した数式を解くための具体的な手順（解法）になっていることを詳しく説明します。

1. 現在の局面から合法手を着手したすべての局面に対して下記の計算を行う
   1. ゲームの決着がつくまで乱数を利用してランダムな着手を行い続け、その結果を記録する。この作業を プレイアウト と呼ぶ
   2. あらかじめ決めておいた回数または、あらかじめ決めておいた時間になるまでプレイアウトを繰り返し、その勝率を計算する
2. 最も高い勝率が計算された局面になる合法手を最善手とする

なお、以前の記事で説明したように、モンテカルロ法を利用したアルゴリズムでは引き分けを一般的に 0.5 勝として扱うので、本記事でも引き分けをそのように扱うことにします。

原始モンテカルロ法の定式化

強化学習の用語や記号については以前の記事と以前の記事を参照して下さい。また、それらの強化学習の用語と原始モンテカルロ法の関係の関係については以前の記事で説明したので、忘れた方は復習して下さい。

環境の設定

最初に 〇× ゲームの強化学習を行う環境において、下記がどのように定義されるかについて説明します。

• 状態空間 $\mathcal{S}$
• 行動空間 $\mathcal{A}$
• 状態遷移関数 $f(s, a)$ と 報酬関数 $r(s, a)$
• エピソードの初期状態 を表す $s_0$
• エピソードの終了条件

状態は 〇× ゲームの局面に対応するので、状態空間 $\mathcal{S}$ は 〇× ゲームで現れる可能性があるすべての局面の集合を意味します。

行動は 〇× ゲームの着手に対応するので、着手を行うマスの座標を (x, y) で表すことにすると、行動空間 は下記のように 9 つのマスの座標の集合として定義されます。

$$\mathcal{A} = \{(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)\}$$

なお、〇× ゲームはすでにマークが置かれているマスには着手を行うことができないため、局面によって打てる合法手が異なります。そこで、以前の記事で説明したように、局面 $s$ でとれる行動の集合を $\mathcal{A}(s)$ と表記して区別することにします。

〇× ゲームでは、同じ局面に対して同じ着手を行うと次の局面は必ず一つに決まるため、状態遷移と得られる即時報酬は決定論的です。そのため、すべての状態（局面）と行動（合法手の着手）の組み合わせに対する 状態遷移関数 $f(s, a)$ と 報酬関数 $f(s, a)$ は環境によって具体的な値が定義されます。

エピソードの 初期状態 $s_0$ は「最善手を求めたい 現在の局面」を指します²。

エピソードの 終了条件 は、ゲームの決着が付いた局面を表す状態に遷移することです。

これらはすべて 〇× ゲームのルールを元に環境によって定義されており、後から変更されることはありません。また、状態遷移、即時報酬、（この後で説明する）方策はいずれも過去の履歴に影響されず、現在の状態（局面）だけで決まるというマルコフ性を満たすため、原始モンテカルロ法の 1 エピソードで得られる履歴は前回の記事で説明した「マルコフ決定過程」という数学的なモデルにあてはまります。

方策の性質

現在の局面から終局までを表す原始モンテカルロ法の 1 エピソードでは、ステップ 0³の現在の局面 $s_0$ に対して着手を行い、次の局面 $s_1$ からは決着が付くまでランダムな着手を行い続けるという「プレイアウト」を行います。

つまり、原始モンテカルロ法では「ステップ 0 で選択する行動」と「ステップ 1 以降のプレイアウトで選択する行動」では、行動の選び方（方策）が全く異なります。そこで、ステップ $t$ における方策関数を $π_t$ と表記して区別すると、全体の方策 $Π$ はステップ 0 の方策 $π_0$ と、ステップ 1 以降の方策 $π_{t \ge 1}$ の集合として下記のように表すことができます。

$$Π = \{π_0, π_{t \ge 1}\}$$

プレイアウト（ステップ 1 以降）では、その局面でのすべての合法手の中から均等な確率（等確率）でランダムに着手を選択します。従って、ステップ 1 以降の方策関数 $π_{t \ge 1}$ は、その時の状態 $s_t$ を用いて下記のような確率の式⁴で表されます。

$$π_{t \ge 1}(a \mid s_t) = \begin{cases}
\dfrac{1}{|\mathcal{A}(s_t)|} & a \in \mathcal{A}(s_t)\\
0 & \text{それ以外の場合}
\end{cases}$$

最適方策の性質

下記は、最適方策 $Π^*$ をステップ 0 での最適方策 $π_0^*$ とステップ 1 以降の最適方策 $π_{t \ge 1}^*$ の集合として表した式です。

$$Π^* = \{π_0^*, π_{t \ge 1}^*\}$$

目的関数 $V_Π(s_0)$ を最大化する最適方策 $Π^*$ においても、ステップ 1 以降では「ランダムに指す」という原始モンテカルロ法のルールが適用されるという点は変わりません。そのため、最適方策においても $\pi_{t \ge 1}^* = \pi_{t \ge 1}$（＝常に等確率でランダムに指す）が成り立ちます。

このことから、原始モンテカルロ法において最適方策 $Π^*$ を求める式は、ステップ $t$ 以降の方策について悩む必要はなく「ステップ 0（目の前の局面の一手）の行動方針 $π_0$ だけをどのように選択するか」という下記の式で表されるシンプルな問題に簡略化できることがわかります。

$$Π^* = \operatorname{argmax}_{Π}V_Π(s_0) = \operatorname{argmax}_{π_0} V_Π(s_0)$$

一般的な強化学習では、ゲーム中に現れる「すべての局面（未来のすべてのステップ）」での最適な方策（着手の選び方）を同時に求めようとするため、計算が非常に複雑になります。一方、原始モンテカルロ法では「いま直面している初期状態 $s_0$ の行動だけを最適化すればよい」という割り切った性質を持っています。原始モンテカルロ法が一般的な強化学習に 比べて著しく計算が簡単 であるというメリットは、この性質によって得られたものです。

最適方策の求め方

原始モンテカルロ法における目的、すなわち目的関数 $V_Π(s_0)$ を最大化する「ステップ 0 の最適方策 $π_0^*$」を求めるためには、この目的関数をステップ 0 の方策関数 $π_0$ を用いた式へと具体的に変形する必要があります。

そこで、その変形に必要な2つの道具である「状態価値関数」と「行動価値関数」の役割について簡単におさらいします。

状態価値関数と行動価値関数のおさらい

以前の記事で説明したように、強化学習では方策に従って行動を行った場合に得られる「累積報酬（または収益）の期待値」のことを価値（value）と呼び、以下の 2 種類があります。

• 状態価値：ある状態 $s$ から方策 $Π$ に従って最後まで行動を選択し続けた場合に得られる累積報酬（または収益）の期待値⁵
• 行動価値：ある状態 $s$ で 具体的な行動 $a$ を取り、その後方策 $Π$ に従って最後まで行動を選択し続けた場合に得られる累積報酬（または収益）の期待値

それぞれの価値を表す関数は下記のように記述します。

• 状態価値関数：$V_Π(s)$
• 行動価値関数：$Q_Π(s, a)$

なお、〇× ゲームでは対局の途中で点数が入ることはなく、最後に勝敗が決まったときだけ報酬（勝ち＝1、引き分け＝0.5、負け＝0）が得られます。このような問題では将来に得られる即時報酬を割り引く「収益（割引累積報酬）」ではなく、単純に即時報酬の合計を表す「累積報酬」を価値として扱うのが一般的なので、以下の説明でも累積報酬をベースに進めていきます。

目的関数を最大化する最適方策の求め方

方策 $π(a \mid s)$ は状態 $s$ で 行動 $a$ を選択する確率を表します。従って、状態 $s_t$ における状態価値 $V_Π(s_t)$ は、方策関数と行動価値関数を用いた下記の式に変形することができます。

$$V_Π(s_t) = \sum_{a_t \in \mathcal{A}(s_t)}π(a_t \mid s_t)Q_Π(s_t, a_t)$$

この $\sum$ の式は、高校数学で習う「期待値（平均値）」の計算そのものです。「その行動を選ぶ確率 $π$」に「その行動を選んだときの価値（累積報酬の期待値）$Q$」を掛け算し、すべての合法手について足し合わせることで、その局面全体の「累積報酬の期待値（状態価値）」を計算しています。

従って、ステップ 0 の初期状態 $s_0$（目の前の局面）における目的関数 $V_Π(s_0)$ は上記の式に $t=0$ を当てはめた下記の式で表されます。

$$V_Π(s_0) = \sum_{a_0 \in \mathcal{A}(s_0)}π_0(a_0 \mid s_0)Q_Π(s_0, a_0)$$

この式を踏まえると、原始モンテカルロ法の最適方策 $π_0^*$ を求める問題は、下記の式で定式化されます。

$$π_0^* = \operatorname{argmax}_{π_0}V_Π(s_0) = \operatorname{argmax}_{π_0}\sum_{a_0 \in \mathcal{A}(s_0)}π_0(a_0 \mid s_0)Q_Π(s_0, a_0)$$

ここで、方策 $π(a_0 \mid s_0)$ は確率なので、当然ながら下記の 2 つの制約があります。

• $\text{すべての } a_0 \in \mathcal{A}(s_0) \text{ に対して }、0 \le π(a_0 \mid s_0) \le 1$ （確率は 0% から 100% の間）

• $\sum_{a_0 \in \mathcal{A(s_0)}}π(a_0 \mid s_0) = 1$ （すべての行動の確率を足すと 100% になる）

この制約の元で全体の期待値（平均）である $V_Π(s_0)$ を最大にするためには、シンプルに「一番高い行動価値 $Q_Π(s_0, a_0)$ が得られる行動を 100 % 選択する」という方策がベストになります。

従って、ステップ 0 の最適方策 $\pi _{0}^{*}$ は下記のように定式化することができます。

$$π_0^*(a_0 \mid s_0) = \begin{cases}
1 & a_0 = \operatorname{argmax}_{a_0 \in \mathcal{A}(s_0)}Q_Π(s_0, a_0)\\
0 & \text{それ以外の場合}
\end{cases}$$

ただし、この「一番良い行動を 100% 選べば全体の期待値が最大になる」という考え方（ロジック）が成り立つためには、「確率 $π_0(a_0 \mid s_0)$ をどう変化させても、行動価値 $Q_Π(s_0, a_0)$ が変化しない（互いに独立している）」必要があります。そこで、次にこの 2 つが独立していることの数学的な証明を行います。

選択（方策 $\pi_{0}$）と価値（$Q_{\Pi }$）が独立していない場合に、「一番高いものを選べば良い」と言えなくなってしまう理由について、身近な例を挙げて説明します。

A さん、B さん、C さんの 3 人がいて、これまでのテストの平均点がそれぞれ 30点、50点、70点 であることがわかっています。この状況で「3 人の中から 1 人を指名し、その人が次のテストで取った点数をそのまま自分のポイントとして貰えるゲーム」に挑戦するとします。

• 選択と実力が「独立している」場合：
  誰を指名しようが、3 人の実力やテストの点数には一切影響を与えない（独立している）場合は、自分のポイントを最大にするための戦略は簡単です。明らかに一番平均点が高い Cさんを 100 %の確率で指名するのが最も賢い選択になります

• 選択と実力が「独立していない」場合（連動している場合）：もし、3 人が「自分を信じて指名してくれたら嬉しくて猛勉強し、実力以上の力を発揮するタイプ」であればどうなるでしょうか。例えば、普段は 30 点の A さんが指名されたときだけは死に物狂いで頑張って 90 点 を取れるとすると事態は大きく変わります。事前に分かっている平均点（30 点、50 点、70 点）だけを見て「一番高いのは C さんだから C さんを指名する」のように安易に決めることはできません。指名した瞬間に A さんの価値が 90 点へと跳ね上がるため、「本当に C さんを選ぶのがベストなのか？（実は A さんを選んだ方が高いポイントを貰えるのではないか？）」を疑わなくてはならなくなります

このように、「自分が何を選ぶかによって、選んだ対象の価値（点数）が変動してしまう状況」では、先ほどのシンプルな定式化が使えなくなってしまいます。このことから、原始モンテカルロ法において「今の着手の行動価値 $Q_Π$ が一番高い手を選ぶ」というアルゴリズムが 100 %正しいと言い切るためには、「行動を選択する確率 $π_{0}$ をどう変えても、それぞれの着手の行動価値 $Q_Π$ が勝手に変動したりせず独立している」ということを、数学的に証明しておく必要があります。

上記は $Q_Π(s_0, a_0)$ を最大化する行動（最善手）が 1 つだけ存在する場合の式です。もし行動価値が最大となる行動が複数存在する場合は、「それらの最善手を選択する確率の合計が 1（100 %）」にであれば、どのように確率を振り分けても $V_Π(s_0)$ は同じ最大値になります。

別の言葉で説明すると「最善手が複数あるなら、どれを選んでも、あるいはそれらをどんな割合でランダムに選んでも結果（行動価値）は変わらない」ということです。

例えば、$x$, $y$ という 2 つの行動がどちらも最高の行動価値を持つ場合は、以下のどれを選んでもすべて「最適方策」となります。

• $π(x \mid s_0) = 1, π(y \mid s_0) = 0$ （行動 $x$ を絶対選ぶ）

• $π(x \mid s_0) = 0, π(y \mid s_0) = 1$ （行動 $y$ を絶対選ぶ）

• $π(x \mid s_0) = 0.5, π(y \mid s_0) = 0.5$ （半分ずつの確率でランダムに選ぶ）

• $π(x \mid s_0) = 0.1, π(y \mid s_0) = 0.9$ （1割と9割の確率で選ぶ）

なお、一般的な AI には、以下のいずれかを最適方策とします。

• 決定論的な方策にする：最善手の中から 1 つを機械的に選択し⁶、その行動を取る確率を 1、それ以外の行動を取る確率を 0 とする
• 確率的な方策にする：最善手を選択する確率を均等に割り振る

ステップ 0 の方策と行動価値の独立性の証明

以前の記事で説明したように、行動価値関数はその定義から即時報酬を表す報酬関数 $r$、状態遷移関数 $f$、状態価値関数 $V_Π$ を用いた下記の式で表されます。

$$Q_Π(s, a) = r(s, a) + V_Π(f(s, a))$$

ここで $s$ と $a$ を「ステップ $t$ の状態 $s_t$ と行動 $a_t$」と考え、式を簡潔にするために次のステップの状態を $s_{t+1} = f(s_t, a_t)$ と表記すると、上記の式は下記のように書き直すことができます。

$$Q_Π(s_t, a_t) = r(s_t, a_t) + V_Π(s_{t+1})$$

従って、独立性を証明しようとしている「ステップ 0 の状態 $s_0$ で、特定の行動 $a_0$ を選択した場合」の行動価値 $Q_Π(s_0, a_0)$ は下記の 式 (1) で表されます。

$$Q_Π(s_0, a_0) = r(s_0, a_0) + V_Π(s_1) \quad \text{--- (1)}$$

ここから先ほどの「選択と価値が独立しているか」の証明に入ります。

式 (1) の右辺にある 2 つの「$r(s_0, a_0)$」と「$V_Π(s_1)$」がどちらも $π_0$ と独立していれば、それらを足し合わせた $Q_Π(s_0, a_0)$ も $π_0$ と独立していることが証明されたことになります。そこで、それぞれが $π_0$ と独立していることを順番に証明します。

報酬関数 と方策の独立性

報酬関数 $r(s_0, a_0)$ は環境によってあらかじめ定義されているものです。そのため「この局面でここに着手した時に得られる即時報酬」は、どんな作戦（$π_0$）で着手を行うかに関係なく、局面 $s_0$ と着手 $a_0$ が決まれば、常に同じ値になります。従って、$r(s_0, a_0)$ と $π_0$ は独立しています。

ステップ 1 の状態価値とステップ 0 の方策の独立性

ステップ 1 の状態価値 $V_Π(s_1)$ は、その局面から得られる収益（累積報酬）の期待値なので、下記のように表されます。ただし、$G$ は収益を表す確率変数です。

$$V_Π(s_1) = E[G \mid s_1, Π]$$

なお、ここで登場する $E[G \mid s_1, Π]$ は、「1 手進んだステップ 1 の状態 $s_1$ ⁷からスタートして、最後まで方策 $Π$ に従ってランダムに着手を選択し続けたときに、各ステップ $i$ で得られる収益 $G$ の期待値」を意味します。

原始モンテカルロ法における収益は「単純な即時報酬の合計」のことなので、ステップ $t$ で得られる即時報酬の確率変数を $R_t$ とすると、ステップ 1 以降の収益 $G$ は下記の式で表されます。ただし、エピソードのステップ数を $n$ とします。

$$G = \sum_{i=1}^{n-1}R_i$$

この式を先ほどの $V_Π(s_1)$ の式に当てはめると下記のように変形できます。なお、下記の変形は以前の記事で説明した期待値の和の公式 $E[X+Y] = E[X] + E[Y]$ を用いました。

$$V_Π(s_1) = E[\sum_{i=1}^{n-1}R_{i} \mid s_1, Π]$$

$$ = \sum_{i=1}^{n-1}E[R_i \mid s_1, Π]$$

従って、原始モンテカルロ法のステップ 1 から始まる未来の履歴（下記のマルコフ決定過程⁸）において、すべての $R_i$ が「どんな確率で発生するか（確率質量関数）」さえわかれば、期待値の公式を使ってすべての $E[R_i \mid s_1, Π]$ を計算できることになります。

$$S_1=s_1, A_1, R_1,S_2, A_2, R_2,\dots , ,S_{n-1}, A_{n-1}, R_{n-1},S_n$$

「ステップ 0 の方策 $π_0$ がこの未来の履歴に影響を与えない」ことを、このマルコフ決定過程に登場する確率変数（状態、行動、報酬）の確率質量関数を時系列に沿って順番に求めることで証明します。

ステップ 1 の確率質量関数

最初に、ステップ 1 の 確率変数 $S_1, A_1, R_1$ の確率質量関数を求め、それらが $π_0$ と独立することを示します。

ステップ 1 の状態の率質量関数

ステップ 1 での状態は、すでに $s_1$ と決まっています。従って $S_1$ がある状態 $s$になる確率は、次のようなシンプルな式で表せます。なお、マルコフ決定過程に登場するすべての確率変数は「初期状態が $s_1$、方策が $Π$」であるという条件があるため、そのことを明確にするために条件付き確率で表すことにします。

$$P(S_1=s \mid s_1, Π) = \begin{cases}
1 & s = s_1\\
0 & s ≠ s_1
\end{cases}$$

この式が表しているのは、「状態 $s$ が、いま直面している局面 $s_1$ そのものである確率は 100%（= 1）であり、それ以外の局面である確率は 0%（= 0）である」という当たり前の事実です。

この式には、ステップ 0 の方策 $π_0$ を表す要素はどこにも登場しません。従って、$S_1$ の確率質量関数は明らかに $π_0$ と独立しています。

「ステップ 1 の状態は $s_1$ で決まっていることから、最初から $P(S_1 = s_1 \mid s_1, Π)$ のように書けばいいのではないか」と思った人がいるかもしれません。しかし、確率質量「関数」として定義するためには、「任意の値を自由に入れられる引数」が必要ですが、最初から特定の固定された値である $s_1$ を入れてしまうと、関数としての形が作れなくなってしまいます。そのため、ここではあえて「何が入るか分からない自由な変数」として別の文字 $s$ を用意し、$P(S_1 = s \mid s_1, Π)$ という関数の形にした上で、「中身が $s_1$ のときだけ確率 1 になる」という書き方をしています。

なお、これ以降に登場する $A_1$ や $R_1$ などの他の確率変数については、まだ値が固定されていないため、$P(A_1 = a_1 \mid s_1, Π)$ のようにそのまま対応する文字（小文字）を実現値として使って表現することにします。

ステップ 1 の行動の確率質量関数

先程説明したように、原始モンテカルロ法ではステップ 1 以降の方策 $π_{t \ge 1}$ は常に下記のような「等確率でランダムに選ぶ」関数で表されます。

$$π_{t \ge 1}(a_t \mid s_t) = \begin{cases}
\dfrac{1}{|\mathcal{A}(s_t)|} & a_t \in \mathcal{A}(s_t)\\
0 & \text{それ以外の場合}
\end{cases}$$

従って、ステップ 1 の行動を表す確率変数 $A_1$ の確率質量関数は上の式に $t=1$ を当てはめた下記のシンプルな式で表せます。

$$P(A_1=a_1 \mid s_1, Π) = \begin{cases}
\dfrac{1}{|\mathcal{A}(s_1)|} & a_1 \in \mathcal{A}(s_1)\\
0 & \text{それ以外の場合}
\end{cases}$$

この数式の中にもステップ 0 の方策 $π_0$ を表す要素はどこにも登場しません。つまり、「1 手進んだ先の局面 $s_1$ でどの着手を選択するか」は、ステップ 0 で自分がどんな作戦（方策）$π_0$ を考えて着手を選択していたかには一切影響されないということです。

従って、$A_1$ の確率質量関数は明らかに $π_0$ と独立しています。

ステップ 1 の即時報酬の確率質量関数

ある状態 $s$ で行動 $a$ を取った時に得られる即時報酬は、環境（ゲームのルール）によって定義された報酬関数 $r(s, a)$ によって求めることができます。

ステップ 1 の状態が $s_1$ で決まっていることから、ステップ 1 の行動で得られる即時報酬 $r_1$ の一覧は、その局面でとることができるそれぞれの合法手 $a_1 \in \mathcal{A}(s_1)$ に対して $r_1= r(s_1, a_1)$ を計算することで求めることができます。

具体例として $\mathcal{A}(s_1) = {(0, 0), (1, 0), (2, 0), (0, 1), (1, 1)}$ の 5 つで、それぞれの報酬が以下のように設定されている場合を考えてみましょう。

行動 $a_1$	即時報酬 $r_1 = r(s_1, a_1)$
(0, 0)	0
(1, 0)	1
(2, 0)	0
(0, 1)	1
(1, 1)	1

この場合にステップ 1 で得られる即時報酬 は 0 か 1 のいずれかとなります。

ここで、得られる即時報酬が 0 となるのは (0, 0) または (2, 0) という着手を選択した場合です。ステップ 1 では等確率に着手を選ぶ（方策関数 $π_{1}$ に従う）ため、即時報酬が 0 になる確率 $P(R_1=0 \mid s_1, Π)$ は、それぞれの確率を足し算した以下の式で計算できます。

$$P(R_1=0 \mid s_1, Π) = π_1((0, 0) \mid s_1) + π_1((2, 0) \mid s_1)$$

同様に得られる即時報酬が 1 となる確率は、残りの 3 つの着手を選択する確率を足し算した下記の式で計算できます。

$$P(R_1=1 \mid s_1, Π) = π_1((1, 0) \mid s_1) + π_1((0, 1) \mid s_1) + π_1((1, 1) \mid s_1)$$

上記のように、得られる即時報酬ごとに異なる式で計算を行うのは大変です。上記の場合は、以前の記事で説明した、特定の条件が満たされた場合に 1 を、そうでない場合に 0 を計算するという、「指示関数」を用いてこの 2 つの式を綺麗に 1 つにまとめることができるので、その考え方について説明します。

まず、先ほどの $P(R_1=0 \mid s_1, Π)$ の式を、あえて「すべての行動（5 つの着手）を並べた足し算」の形で書き直してみます。すると、下記のように「報酬が 0 になる手には 1 を、報酬が 0 にならない手には 0 を掛け算して合計したもの」と言い換えることができます。

$$P(R_1=0 \mid s_1, Π) = 1 \times π_1((0, 0) \mid s_1) + 0 \times π_1((1, 0) \mid s_1) + 1 \times π_1((2, 0) \mid s_1) + 0 \times π_1((0, 1) \mid s_1) + 1 \times π_1((1, 1) \mid s_1)$$

指示関数は、「条件を満たすときは 1（ON）、そうでないときは 0（OFF）」というスイッチのような役割を果たしてくれる関数で、「$r(s_1, a_1) = 0$（即時報酬が 0）になる着手だけを 1（ON）とするスイッチ」は、指示関数 $\mathbf{1}$ を使って下記のように記述できます。

$$\mathbf{1}_{{r(s_1, a_1)=0}}$$

この仕組み（指示関数）を使えば、即時報酬が（0 でも 1 でも）任意の値 $r_{1}$ の場合の確率 $P(R_1 = r_1 \mid s_1, Π)$ を、合計を計算する $\sum$ を用いて次のような 1 つの式に綺麗にまとめることができます。

$$P(R_1=r_1 \mid s_1, Π) = \sum_{a_1 \in \mathcal{A}(s_1)} \mathbf{1}_{{r(s_1, a_1)=r_1}}π_1(a_1 \mid s_1)$$

原始モンテカルロ法のステップ 1 以降の方策は「常に等確率でランダムに指す」というルールなので、$a_1 \in \mathcal{A}(s_1)$ である確率は常に $π_1(a_1 \mid s_1) = \frac{1}{|\mathcal{A}(s_1)|}$ となります。これを上の式に代入すると下記の式に変形できます。

$$P(R_1=r_1 \mid s_1, Π) = \sum_{a_1 \in \mathcal{A}(s_1)} \dfrac{\mathbf{1}_{{r(s_1, a_1)=r_1}}}{|\mathcal{A}(s_1)|}$$

ここで、分母の ${|\mathcal{A}(s_1)|}$ は「局面 $s_{1}$ の合法手（行動）の総数」を表します。この値は、ステップ 1 で行動を選択する前から決まっている値であるため、ステップ 1 で選択した行動とは独立した値です。従って、下記のように $\sum$ の外側に移動することができます。

$$P(R_1=r_1 \mid s_1, Π) = \dfrac{\sum_{a_1 \in \mathcal{A}(s_1)}\mathbf{1}_{{r(s_1, a_1)=r_1}}}{|\mathcal{A}(s_1)|}$$

分子の ${\sum_{a_1 \in \mathcal{A}(s_1)}\mathbf{1}_{{r(s_1, a_1)=r_1}}}$ は、$r(s_1, a_1)=r_1$ という条件を満たしたときだけ 1 が足されるので、結果的に「即時報酬 $r_1$ が貰える合法手の個数」をカウントするという意味になります。

このことから、一見するとかなり複雑そうに見えるこの数式は、「局面 $s_{1}$ において、報酬 $r_{1}$ が得られる行動が全体の中に占める割合」を計算しているだけという、非常に単純な計算を行う式であることがわかります。ランダムに手を指し続けるプレイアウトだからこそ、この「合法手の割合」がそのまま「その即時報酬が得られる確率」に直結するのです。

局面 $s_{1}$における報酬関数 $r(s_1, a_1)$ の中身と、打てる手の総数 $|\mathcal{A}(s_1)|$ は、ゲームのルール（環境）として最初からすべて定義されています。そのため、この式を使えば具体的な確率の値を計算することができます。そして何より重要なのは、この確率を導く式の中に、ステップ 0 の方策 $π_{0}$ を表す要素がどこにも出現しないということです。従って、$R_1$ の確率質量関数も、ステップ 0 の方策 $π_0$ と完全に独立していることが示されました。

ステップ 1 のまとめ

以上の検証により、1 手進んだ先の未来であるステップ 1 のすべての確率変数（状態 $S_{1}$、行動 $A_{1}$、即時報酬 $R_{1}$）の確率質量関数は、すべて具体的な数値として計算可能であり、なおかつ「ステップ 0 の方策 $π_{0}$ には一切影響を受けずに独立している」ということが証明されました。

ステップ 2 以降の確率質量関数

前回の記事で説明したように、確率過程のステップ 2 以降の確率質量関数は、以下の手順を繰り返すことで機械的に求めることができます。

1. 次に計算を行うステップ数を表す $t$ を 2 とする
2. これまでに計算した「ステップ $t-1$ までの確率質量関数」と、「ステップ $t$ への遷移を表す状態遷移関数」を用いて、ステップ $t$ のすべての状態 $x_t$ に対する確率質量関数 $P(X_t=x_t)$ 計算する
3. $t$ が最後のステップである $n$ の場合は処理を終了し、そうでない場合は $t$ に 1 を加えて手順 2 に戻る

ただし、前回の記事で説明したように、状態・行動・即時報酬が交互に現れるマルコフ決定過程をそのまま扱うと、マルコフ連鎖のルールから少し外れてしまうという問題があります。そのため、各ステップにおける「状態」「行動」「即時報酬」を一つの集合として扱い、それを新しいステップの状態 $X_t = \{S_t, A_t, R_t\}$ として再定義した $X_t$ に対して上記の手順の計算を行います。

ここから、この未来のステップ 2 以降の確率変数全体がステップ 0 の方策 $π_{0}$ と独立していることの証明に入ります。ここで使うのは、高校数学でお馴染みの、ドミノ倒しのように証明を行う下記の「数学的帰納法」です。

• ドミノの先頭（ステップ 1）： 先ほどの証明により、ステップ 1 の $X_1 = {S_1, A_1, R_1}$ の確率質量関数は、$π_{0}$ と独立していることが証明済である
• ドミノ倒しの連鎖（ステップ t）：数学的帰納法では、「ステップ $t-1$ の確率質量関数が $\pi_{0}$ と独立している」と仮定したときに、上の計算手順によって導かれる「ステップ $t$ の確率質量関数も $\pi_{0}$ と独立している」ということが示されれば、ステップ 1 が独立だからステップ 2 も独立、ステップ 2 が独立だからステップ 3 も独立・・・というドミノ倒しの連鎖ように「すべてのステップ $t \ge 1$ の確率質量関数が $\pi_{0}$ と独立している」ことが再帰的に証明されたことになる

ステップ t の状態の確率質量関数

最初にステップ $t$ の状態を表す $S_t$ の確率質量関数 $P(S_t=s_t \mid s_1, Π)$ を求め、これが $π_0$ と独立していることを示します。

なお、ここからの計算式では、式をシンプルして流れを追いやすくするために、結論が出るまでの途中の計算式において、条件付き確率の前提である「$s_1, \Pi$」の表記を省略し、単に $P(S_t = s_t)$ のように記述することにします。

ステップ $t$ の状態が特定の局面 $s_t$ となる条件は「1 つ前のステップ $t-1$ での状態が $s_{t-1}$、行動が $a_{t-1}$」であり、なおかつ「その組み合わせによる状態遷移の結果が $f(s_{t-1}, a_{t-1}) = s_t$ となる場合」です。

そのため $P(S_t=s_t)$ を高校の数学で習う公式を使って、次の手順で計算することができます。

1. ステップ $t-1$ で起こりうるすべての状態 $s_{t-1}$ に対して、「ステップ ${t-1}$ の状態が $s_{t-1}$ で、次の状態が $s_t$ になる」という同時確率 $P(S_{t-1}=s_{t-1}, S_t=s_t)$ を計算する（確率の乗法定理）
2. これらをすべて足し合わせることで、最終的にステップ $t$ の状態が $s_{t}$ になる確率を網羅する（周辺化）

上記の手順 1 の同時確率は、「ステップ $t-1$ の状態が $s_{t-1}$ になる確率」と「ステップ $t-1$ の状態が $s_{t-1}$ であるという条件のもとで次の状態が $s_t$ に遷移する条件付き確率」を乗算した下記の式で求められます。

$$P(S_{t-1}=s_{t-1}, S_t=s_t) = P(S_{t-1}=s_{t-1})P(S_t=s_t \mid S_{t-1}=s_{t-1})$$

ここで、ステップ $t-1$ の状態が $s_{t-1}$ の場合次の状態が $s_t$ に遷移する条件は、状態遷移関数 $f(s, a)$ を用いた下記の式で表されます。

$$f(s_{t-1}, a_{t-1}) = s_t$$

従って、条件付き確率 $P(S_t=s_t \mid S_{t-1}=s_{t-1})$ は、先程 $R_1$ の確率質量関数を求めた時と同じ理由（ロジック）で、指示関数と方策関数を用いた下記の式で表すことができます。

$$P(S_t=s_t \mid S_{t-1}=s_{t-1}) =\sum_{a_{t-1} \in \mathcal{A}(s_{t-1})} \mathbf{1}_{{f(s_{t-1}, a_{t-1})=s_t}}π(a_{t-1} \mid s_{t-1}) $$

$$ = \frac{\sum_{a_{t-1} \in \mathcal{A}(s_{t-1})} \mathbf{1}_{{f(s_{t-1}, a_{t-1})=s_t}}}{|\mathcal{A}(s_{t-1})|} $$

これらを組み合わせると手順 1 で求める同時確率は下記のようになります。

$$P(S_{t-1}=s_{t-1}, S_t=s_t) = \frac{P(S_{t-1}=s_{t-1})\sum_{a_{t-1} \in \mathcal{A}(s_{t-1})} \mathbf{1}_{{f(s_{t-1}, a_{t-1})=s_t}}}{|\mathcal{A}(s_{t-1})|}$$

従って $P(S_t = s_t)$ は下記のように、手順 2 に従ってステップ $t-1$ で起こりうるすべての状態 $s_{t-1} \in \mathcal{S}$ について、この同時確率の合計を計算することで求めることができます。

$$P(S_t=s_t) = \sum_{s_{t-1} \in \mathcal{S}}P(S_{t-1}=s_{t-1}, S_t=s_t)$$

$$ = \sum_{s_{t-1} \in \mathcal{S}}\frac{P(S_{t-1}=s_{t-1})\sum_{a_{t-1} \in \mathcal{A}(s_{t-1})} \mathbf{1}_{{f(s_{t-1}, a_{t-1})=s_t}}}{|\mathcal{A}(s_{t-1})|}$$

一つ前のステップ $t-1$ の　$P(S_{t-1}=s_{t-1})$ は既に計算済で、状態遷移関数 $f(s_{t-1}, a_{t-1})$ と状態 $s_{t-1}$ での合法手の $\mathcal{A}(s_{t-1})$ は環境によって具体的な値が定義されているため、この $P(S_t=s_t)$ は具体的に計算することができます。

次に、導き出したこの数式から $P(S_t=s_t)$ が $π_0$ と独立していることを証明します。

• 数学的帰納法の仮定 から、一つ前のステップ $t-1$ での $P(S_{t-1}=s_{t-1})$ は、ステップ 0 の方策 $π_0$ と独立してることが仮定されている
• 環境の定義 から、状態遷移関数 $f(s_{t-1}, a_{t-1})$ と状態 $s_{t-1}$ での合法手の総数 $|\mathcal{A}(s_{t-1})|$ はあらかじめ定義された定数と考えることができるため、これらはいずれも $π_0$ と独立してる

この数式の右辺を構成するすべてのパーツが $\pi _{0}$ と独立しており、数式の中に $\pi _{0}$ を表す要素はどこにも出現しません。従って、ステップ $t$ の状態価値の確率質量関数 $P(S_t = s_t)$ も、ステップ 0 の方策 $\pi _{0}$ と完全に独立していることが示されました。

以上から、数学的帰納法により、任意の（未来のすべての）ステップ $t \ge 1$ における $P(S_t = s_t)$、すなわち $P(S_t = s_t \mid s_1, \Pi)$ は、ステップ 0 の方策 $\pi _{0}$ と独立していることが証明されました。

ステップ t の行動の確率質量関数

次に、ステップ $t$ の行動を表す確率変数 $A_{t}$ の確率質量関数を求めることにします。ここでも、途中の式では見た目をシンプルにするために「$s_1, \Pi$」の表記を省略して記述します。

ステップ $t$ でどのような行動 $a_{t}$ を選択するかは、そのときの状態（局面）が何であるかによって変わります。従って、$P(A_t = a_t)$ は先ほどの状態 $S_{t}$ のときと同じように、起こりうるすべての状態 $s_t \in \mathcal{S}$ について $P(A_{t}=a_{t}\mid S_{t}=s_{t})P(S_{t}=s_{t})$ を足し合わせることで、次のように計算できます。

$$P(A_{t}=a_{t})=\sum_{s_{t}\in \mathcal{S}}P(A_{t}=a_{t}\mid S_{t}=s_{t})P(S_{t}=s_{t})$$

ここで、特定の状態 $s_{t}$ のもとで行動 $a_{t}$ を選ぶ確率 $P(A_t = a_t \mid S_t = s_t)$ は、まさに下記のステップ 1 以降の方策関数 $\pi_{t \ge 1}(a_t \mid s_t)$ そのものです。

$$π_{t \ge 1}(a_t \mid s_t) = \begin{cases}
\dfrac{1}{|\mathcal{A}(s_t)|} & a_t \in \mathcal{A}(s_t)\\
0 & \text{それ以外の場合}
\end{cases}$$

これを $P(A_{t}=a_{t})$ の式に代入すると以下のようになります。

$$P(A_{t}=a_{t})=\sum _{s_{t}\in \mathcal{S}}π_{t \ge 1}(a_t \mid s_t)P(S_{t}=s_{t})$$

この数式の右辺の方策関数 $\pi_{t\ge 1}$ はいつでも一律で「等確率にランダム」と決まっているルールなので、当然 $\pi_{0}$ とは独立しています。

状態の確率 $P(S_t = s_t)$ は、先程数学的帰納法によって任意のステップ $t \ge 1$ において「$\pi _{0}$ と完全に独立している」ことが証明されています。

このように、右辺に $π_0$ を用いた式は存在しないため、すべてのステップ $t \ge 1$ において、$P(A_{t}=a_{t} \mid s_1, \Pi)$ が $π_0$ から完全に独立していることが証明されました。

ステップ t の即時報酬の確率質量関数

次に、ステップ $t$ で得られる即時報酬を表す確率変数 $R_{t}$ の確率質量関数を求めることにします。ここでも、途中の式では見た目をシンプルにするために「$s_1, \Pi$」の表記を省略して記述します。

ステップ $t$ で得られる即時報酬が $r_t$ となる条件は「ステップ $t$ での状態が $s_t$、行動が $a_t$」であり、なおかつ「その組み合わせによって得られる即時報酬が $r(s_t, a_t) = r_t$ となる場合」です。

この条件は、先程 $S_t$ の確率質量関数を求めた際に説明した下記の条件の「ステップを表す $t-1$ を $t$」に、「状態遷移関数を報酬関数」に入れ替えたものと同じになります。

『ステップ $t$ の状態が特定の局面 $s_t$ となる条件は「1 つ前のステップ $t-1$ での状態が $s_{t-1}$、行動が $a_{t-1}$」であり、なおかつ「その組み合わせによる状態遷移の結果が「$f(s_{t-1}, a_{t-1}) = s_t$」 となる場合』

従って、ステップ $t$ で得られる即時報酬 $R_t$ の確率質量関数 $P(R_t=r_t)$ は、状態 $S_t$ のときと全く同じ足し合わせ（周辺化）の考え方を用いた下記の式で求めることができます。

$$P(R_t=r_t) = \sum_{s_t \in \mathcal{S}} \frac{P(S_t=s_t)\sum_{a_t \in \mathcal{A}(s_t)}\mathbf{1}_{{r(s_t, a_t)=r_t}}}{|\mathcal{A}(s_t)|}$$

$P(S_t=s)$ は先ほどの説明で計算済であり、報酬関数 $r(s_t, a_t)$ と合法手の総数 $|\mathcal{A}(s_t)|$ は環境によって定義されているため、この式を用いて具体的な $P(R_{t}=r_{t})$ の値を計算することができます。

次に、導き出したこの数式から $P(R_t=r_t)$ がステップ 0 の方策 $π_0$ と独立していることを証明します。

• 右辺の分子の左側にある $P(S_t=s_t)$ は、先ほど「任意のステップ $t \ge 1$ においてステップ 0 の方策 $π_0$ と独立している」ことが数学的帰納法によって証明されている
• 右辺の分子の右側にある報酬関数 $r(s_{t}, a_{t})$ と、分母にある状態 $s_{t}$ の局面での合法手の総数 $|\mathcal{A}(s_{t})|$ は、ゲームのルール（環境）としてあらかじめ定義された定数と考えることができるため、これらはいずれも $π_0$ と独立してる

右辺を構成するすべてのパーツが $π_0$ と独立していており、数式の中に $π_0$ を表す要素はどこにも出現しません。従って、任意の（未来のすべての）ステップ $t \ge 1$ における報酬の確率質量関数 $P(R_t = r_t \mid s_1, \Pi)$ も、ステップ 0 の方策 $\pi _{0}$ と独立していることが証明されました。

上記の式は、ステップ 1 の $R_1$ の確率質量関数を表す式としてもそのまま利用できます。その理由について説明します。

先程計算したように、ステップ 1 での状態は $s_1$ であると最初から決まっているため下記が成り立ちます。

$$P(S_1=s \mid s_1, \Pi) = \begin{cases}
1 & s = s_1\\
0 & s ≠ s_1
\end{cases}$$

この式を、先程求めた一般式に $t=1$ を代入して当てはめてみます。すると、$s = s_1$ 以外のとき（確率 0 のとき）の足し算はすべて消えてなくなるため、次のように、前に個別で計算した $P(R_1 = r_1 \mid s_1, \Pi)$ の式と完全に一致します。

$$P(R_1=r_1 \mid s_1, \Pi) = \sum_{s \in \mathcal{S}} \frac{P(S_1=s)\sum_{a_1 \in \mathcal{A}(s)}\mathbf{1}_{{r(s, a_1)=r_1}}}{|\mathcal{A}(s)|}$$

$$= \sum_{a_1 \in \mathcal{A}(s_1)} \frac{\mathbf{1}_{{r(s_1, a_1)=r_1}}}{|\mathcal{A}(s_1)|}$$

まとめ

これまでの数学的帰納法により、1 手進んだ先の未来である任意のステップ $t \ge 1$ における状態 $S_t$、行動 $A_t$、即時報酬 $R_t$ の確率質量関数はすべて具体的に計算可能であり、ステップ 0 の方策 $\pi_{0}$ から完全に独立している（影響を受けない） ことが証明さされました。

この事実をもとに、下記のステップ 0 での行動価値を表す式 (1) に立ち戻ってみます。

$$Q_Π(s_0, a_0) = r(s_0, a_0) + V_Π(s_1) \quad \text{--- (1)}$$

この式 (1) の右辺を構成するパーツをおさらいすると、次のようになります。

• 報酬関数 $r(s_0, a_0)$ は、ゲームのルール（環境）として定義されているため、当然 $\pi _{0}$ から独立している
• 未来の収益の見込み（期待値）である $V_\Pi(s_1)$ も、次の理由から $\pi _{0}$ から完全に独立している
  • 状態価値の定義から $V_Π(s_1) = \sum_{i=1}^{n-1}E[R_i \mid s_1, Π]$ である
  • 先ほどの数学的帰納法により、未来の各ステップ $i$ における報酬 $R_{i}$ の確率質量関数はすべて $\pi _{0}$ から独立している
  • 各ステップの期待値 $E[R_i \mid s_1, \Pi]$ は、そのステップ $i$ の確率質量関数だけから求められるため、それらをすべて足し合わせた合計である $V_\Pi(s_1)$ も、当然 $\pi _{0}$ から独立している

$Q_Π(s_0, a_0)$ の右辺のパーツがいずれも $\pi_{0}$ から独立しているため、その合計である行動価値関数 $Q_\Pi(s_0, a_0)$ も、ステップ 0 の方策 $\pi _{0}$ と完全に独立していることが証明されました。

ステップ 0 での方策 $π_0$ とステップ 0 での行動価値 $Q_Π(s_0, a_0)$ が連動して勝手に値が変わってしまう心配（独立性の懸念）が完全に消え去ったため、目的関数を最大化するために選ぶべきステップ 0 の最適方策 $\pi_{0}^{*}$ は、「行動価値（勝率の期待値） $Q_\Pi(s_0, a_0)$ が最大となる行動を 100% の確率で選択すればよい」という下記のシンプルな式で求めることができるということが確認できました。

$$π_0^*(a_0 \mid s_0) = \operatorname{argmax}_{π_0}V_Π(s_0) = \operatorname{argmax}_{π_0}\sum_{a_0 \in \mathcal{A}(s_0)}π_0(a_0 \mid s_0)Q_Π(s_0, a_0)$$

$$= \begin{cases}
1 & a_0 = \operatorname{argmax}_{a_0 \in \mathcal{A}(s_0)}Q_Π(s_0, a_0)\\
0 & \text{それ以外の場合}
\end{cases}$$

原始モンテカルロ法のアルゴリズムの妥当性

上記の式から、最適方策である $π_0^*$ を求めるためには、現在の局面（ステップ0）で打てるすべての行動 $a_0$ に対する 行動価値 $Q_Π(s_0, a_0)$ を実際に計算して比べる 必要があることがわかりました。

この行動価値 $Q_Π(s_0, a_0)$ を求めるために必要となる「次の局面の価値 $V_Π(s_1)$」は、これまでに説明してきた確率の式を厳密に解いていけば、理論上の具体的な値を求めることができます。

実際に、以前の記事では 〇× ゲームのすべての局面（状態）に対する状態価値⁹を実際にコンピュータで力任せにすべて計算しましたが、その際に行っていたのは、まさに今回の記事で説明した数式とまったく同じ計算です¹⁰。そして計算した状態価値のデータをもとに、ゲーム木を Mbtree_GUI クラスを用いて下図のように視覚化しました。

しかし、ここに強化学習ならではの大きな課題があります。

一般的な強化学習のルール（設定）では、ゲームの規則である「状態遷移関数」や「報酬関数」の中身は、学習を行う AI（エージェント）にとっては「未知のブラックボックス（秘密のルール）」 とされています。つまり、AI は数式を直接解いて正しい $Q_\Pi(s_0, a_0)$ をあらかじめ計算しておくことができないのです。

また、仮にルールが最初から分かっていたとしても、将棋や囲碁のようにゲームの規模が莫大な場合は、盤面のパターン（状態の数）が多すぎて、すべての価値を厳密に計算することはスーパーコンピュータを使っても不可能です。

数式が隠されていて正確な確率が計算できない時に便利なのが「モンテカルロ法」です。モンテカルロ法とは、「確率の計算式が分からないなら、実際に何度もサイコロを振って実験データを集め（無作為復元抽出）、その実験結果の平均値（標本平均）を使って、本当の期待値の代わりとする」というアプローチで、サイコロを何度も振ったり、〇× ゲームのプレイアウトを何度も行うような、無作為復元抽出を何度も簡単に行うことができる場合に大活躍します。

このモンテカルロ法には、以前の記事でも紹介した「大数の法則」という強力な数学的裏付けがあります。実験の回数を増やせば増やすほど、シミュレーションから求めた平均値は、本当の理論上の確率へと無限に近づいていくという性質です。

この仕組みをゲームの AI に当てはめたのが「原始モンテカルロ法のアルゴリズム」です。「いま目の前にある局面から次の手を試しに打ち、そこからゲームの決着がつくまでランダムに手を指し続けるシミュレーション（プレイアウト）を繰り返して勝率を計算する」という具体的な手順は、数学的には「大数の法則を利用して、厳密な値を求めることが困難な行動価値 $Q_\Pi(s_0, a_0)$ の近似値を力技で求めていた」ということを意味します。

以前の記事 のシミュレーションで、「プレイアウトの回数を増やせば増やすほど、ランダムな着手を行う AI に対する勝率がどんどん高くなって強くなっていった」という現象が起きたのも、この大数の法則によって $Q_\Pi(s_0, a_0)$ の近似値の精度がどんどん高くなり、数式上の理想的な最適方策へと近づいていったことが原因であると、数学的に説明がつきます。

このように原始モンテカルロ法を厳密に定式化したことには他にも大きな利点があります。それは、将棋、囲碁、オセロなどの、〇× ゲームと同様の性質を持つあらゆるゲームに対して、「まったく同じ数学的な裏付けによって、まったく同じアプローチで最適解を求めることができる」という点です。今回の記事で複雑な数式を用いた厳密な数学的な証明を行ったのは、強化学習のアルゴリズムに数学的な裏付けという強力な保証を得るためです。

実は、原始モンテカルロ法に限らず、多くの強化学習のアルゴリズムは「目の前の具体的な問題と、それを解く手順を、数式を使ってあらかじめ抽象化しておく」という設計思想を持っています。その理由は、数学の言葉で抽象化しておくことで、ゲームの種類が変わっても、あるいはゲーム以外の複雑な現実世界の問題であっても、「全く同じアルゴリズムをそのまま使い回して解くことができる」という汎用性を手に入れることができるからです。

具体例としては DeepMind 社が開発した「DQN（Deep Q-Network）」という有名な強化学習のアルゴリズムがあります。この手法を用いて実装された AI は、ゲームのルール（中身）を一切教えられていないにもかかわらず、全く同じアルゴリズムのままで、ブロック崩し（Breakout）や卓球ゲーム（Pong）といったアタリ社のさまざまなレトロゲーム（ビデオゲーム）をプレイし、人間を超える高得点を叩き出すという驚異的な成果を上げました。現在では、これらを含むさまざまな強化学習の実験用のゲーム環境（題材）を集めた「Gymnasium（ジムナジウム）」という世界標準のライブラリ（開発サイト）が公開されています。参考までに下記にそのリンクを示しますので、興味がある方覗いてみてください。

今回の記事のまとめ

今回の記事では、原始モンテカルロ法を定式化し、原始モンテカルロ法が「大数の法則」という数学に裏付けられたアルゴリズムであることを示しました。

ただし、「原始モンテカルロ法」には実戦で使う上では致命的な弱点があります。それは、「2 手目以降のシミュレーション（プレイアウト）が、すべて完全なランダムで行われる」という点にあります。どれだけ 1 手目を必死に考えようとしても、その先の未来が「お互いにデタラメに指し続ける」という前提の勝率であるため、戦術や読みが重要になる将棋やオセロなどの本格的なゲームでは、残念ながら「本当に強い AI」を作ることはできません。

この原始モンテカルロ法の弱点を克服し、より強力な AI へと改良するためには、「最善手をじっくり計算する範囲を、現在の局面（1 手目）だけでなく、その先の未来の局面（2 手目、3 手目……）へと広げていく」という工夫が必要になります。そのようなアイデアから生まれ、現代の最強の将棋や囲碁の AI などの基盤にもなった有名アルゴリズムが、原始モンテカルロ法を発展させた「モンテカルロ木探索（MCTS）」です。次回の記事からは、その「モンテカルロ木探索」の説明を行う予定です。

本記事で入力したプログラム

今回の記事で入力したプログラムはありません。

次回の記事

近日公開予定です。

1. 今回の記事から読みやすさを重視して、式を中央に表記することにしました ↩

2. 初期状態という名前からゲーム開始時の局面を想像する人がいるかもしれませんが、初期状態はゲーム開始時の局面とは限らない点に注意して下さい ↩

3. エピソードのステップは、現在の局面から行った行動（着手）の数に相当します。従って、まだ行動を行っていない現在の局面は「ステップ 0」となります ↩

4. 分母の $|\mathcal{A}(s_t)|$ は、局面 $s_{t}$ における合法手の「総数」を表します。例えば合法手が 3 つの場合は、それぞれの合法手が選択される確率は $\frac{1}{3}$ になります ↩

5. 目的関数 $V_Π(s_0)$ は、まさに「初期状態 $s_0$ における状態価値」そのものです ↩

6. 例えば最初に見つかった最善手を選択するという方法や、複数の最善手の中からランダムに 1 つを選ぶ方法などが考えられます ↩

7. ステップ 0 の状態 $s_0$ ではない点に注意して下さい ↩

8. ステップ 1 の状態が特定の状態 $s_1$ であることを明確にするために、$S_1=s_1$ としました ↩

9. 状態価値という概念を説明する前の以前の記事では「評価値の理論値」と表現しました ↩

10. 〇× ゲームでは即時報酬はゲームの決着が付いた場合のみで得られるため、今回の記事で紹介した計算式と比べてその分だけ簡略化されています ↩