Pythonで〇×ゲームのAIを一から作成する　その244　原始モンテカルロ法の単純な拡張とその問題点

Last updated at 2026-09-08Posted at 2026-09-06

目次と前回の記事

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

今回の記事の内容

前回の記事では、原始モンテカルロ法には、以下のような実戦で使う上では致命的な弱点があることを説明しました。

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

この問題を解決するためには、「最善手をじっくり計算する範囲を、現在の局面（1 手目）だけでなく、その先の未来の局面（2 手目、3 手目……）へと広げていく」という工夫が必要になりますが、単純に範囲を広げるというアプローチにはいくつかの問題があります。

そこで今回の記事では、この「単純に先読みを広げるアプローチ」が抱える問題点を整理し、この問題を解決するために考案されたモンテカルロ木探索（Monte Carlo Tree Search（MCTS））への導入の説明を行います。

原始モンテカルロ法の環境の修正

以下の説明では 現在の局面から $n$ 回の着手 を行った局面を「$n$ 手目の局面」と表記します。従って、スタート地点での現在の局面は $0$ 手目の局面になります。

ここで、一般的なのゲーム用語における「手数」の数え方と、強化学習にける行動が行われた「ステップ数」の数え方に以下のようなずれが生じる点に注意して下さい。

一般的なゲーム用語では、手数をゲームが開始してから行った着手の回数で表現する。従って、最初に行う着手は「1 手目」である
強化学習における行動は、行動を行った状態のステップ数で表現する。従って、初期状態がステップ 0 の状態であることから、最初の行動は「ステップ 0 の行動」となる

このように、ボードゲームの「1 手目（最初の着手）」は、強化学習では「ステップ 0 の行動」になるため、数え方に 1 つのずれ が生じます。

なお、強化学習の用語や記号については以前の記事と以前の記事を参照して下さい。

原始モンテカルロ法における「勝率」の2つの意味

原始モンテカルロ法は、以下の手順で「現在の局面（0 手目）」における最善手を求めるというアルゴリズムでした。ただし、勝率は「〇の勝利を 1 勝」、「引き分けを 0.5 勝」、「〇の敗北を 0 勝」として計算します。

すべての「1 手目の局面」に対して均等な回数のプレイアウトを行い、その勝率から各局面の「状態価値の推定値¹」を求める
現在の局面（0 手目）の合法手の中で、着手した先の局面の勝率（= 行動価値の推定値）が最大となる合法手を最善手として選択する

上記の「勝率」という用語には 「状態価値」の推定値 と、「行動価値」の推定値 という 2 つの異なる意味が混ざり合っている点が複雑です。実は、環境（ゲームのルール）側を少しだけ修正することで、この 2 つの価値を全く同じものとして扱えるようになります。そこで、この後の説明をよりシンプルにわかりやすくするために、この 2 つの意味（勝率が表す中身）を 1 つにまとめるという工夫を行なうことにします。

勝率の意味が異なる理由

2 つの「勝率」が上記のように異なる意味を持つ理由は、以前の記事で説明した行動価値関数 $Q_Π(s, a)$ の定義にあります。決定論的な環境では、行動価値関数は以下のように「即時報酬 $r(s, a)$」と「次の状態の状態価値 $V_Π(s')$」の和で計算されます²。

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

もし、すべてのゲームで「行動価値 $Q_\Pi(s, a)$」が、遷移先の「状態価値 $V_\Pi(s')$」と全く同じになるのであれば、2 つの勝率はどちらも単に「状態価値の推定値」³と呼ぶことができます。

しかし、一般的な強化学習の課題では「同じ状態に辿り着いたとしても、どこ（直前の状態）からどうやって来たか（行動）によって、その場で 得られる即時報酬 $r(s, a)$ が変わる」というケースが良くあります。具体例としては、次のような「C 地点という同じ状態に遷移するケース」があります。

A 地点から C 地点へ移動する。このルートには途中に得点アイテムが落ちているため、即時報酬 $r(s, a) = 100$ が得られる
B 地点から C 地点へ移動する。このルートには何も落ちていないため、即時報酬は得られず $r(s, a) = 0$ となる

このように、辿り着いた先が同じ C 地点（状態）であっても、道中で手に入る即時報酬 $r(s, a)$ が異なる可能性があるため、強化学習では「状態価値」と「行動価値」を厳密に区別する必要があるのです。

環境の工夫による勝率の意味の統一

原始モンテカルロ法が題材とする〇× ゲームや将棋のようなゲームは、「ゲームの決着がついたときたけ、勝敗結果に応じた即時報酬（〇の勝利 = 1、引き分け = 0.5、〇の敗北 = 0）が得られる」という性質を持っています。

このような性質を持つゲームでは、環境の定義に少し工夫を加えることで、行動価値を「遷移後の状態価値」そのもの へと一致させることができます。そのことを数式で表すと、下記のように行動価値関数定義から 即時報酬を取り除いたシンプルな形 になります。

$$Q_Π(s, a) = V_Π(s')$$

即時報酬をどのようにして取り除くかについては、この後で詳しく説明します。

当然ですが、途中でスコア（即時報酬）が加算されるような一般的な強化学習の環境では、この式は成り立たない点に注意してください。

添字の表記ルールについて

ここから先の説明を明確にするために、状態や行動といった記号に付ける「添字（右下の小さな文字）」のルールを以下のように定めます。後で記号の意味がわからなくなったら、ここを振り返ってみてください。

添字のパターン	例	意味
数値	$s_0$	エピソードの具体的なステップ数を表す
1 文字のアルファベット	$s_t$	ステップ数を表す変数を意味する
2 文字以上の小文字	$s_{pl}$	そのアルファベットが表す性質を持つ変数を意味する例：pl ＝決着がついていないプレイ中（playing）の局面
2 文字以上の大文字	$s_{FIN}$	変数ではなく、具体的な 1 つの状態（定数）を表す例：FIN ＝ゲームが完全に終了（finish）した状態
右肩に $'$（プライム）	$s'$, $s_{pl}'$	その記号の「次のステップの値」であることを表す

現状の環境における行動価値

環境に対してどのような工夫を行う必要があるかを明確にするために、最初に「今のままの環境」で 行動価値の数式がどのようになるか を確認することにします。

〇× ゲームや将棋のように、ゲームの決着がついた瞬間だけ即時報酬が得られる環境は、着手した先の状態 $s' = f(s, a)$ が「対局中」か「決着がついている」かの 2 つのパターンによって 行動価値の計算式が変わります。

そこで、ここからは以下の 2 つの記号を使ってこの 2 つのパターンの行動価値について考えていくことにします。

$s_{pl}$：ゲームの決着がついていない、プレイ中の状態（playing）
$s_{end}$：ゲームの決着がついている、終了した状態（end game）

遷移した状態が「決着がついていない」場合

遷移した状態が決着がついていない場合は、その場での即時報酬は得られないため $r(s, a) = 0$ となります。従って、行動価値は以下のようになります。

$$Q_Π(s, a) = r(s, a) + V_Π(s_{pl}') = V_Π(s_{pl}')$$

この式から、ゲームの決着がつかない場合の行動価値は、遷移後の状態価値に等しくなる ことがわかります。

遷移した状態が「決着がついている」場合

遷移した状態が決着がついている場合は、そこでエピソード（対局）が終了するため、それより先の未来はありません。状態価値とは「その状態以降の未来 に得られる累積報酬の期待値」のことなので、未来が存在しない以上、決着がついた局面の状態価値は必ず $V_Π(s_{end}') = 0$ とります。従って、行動価値は以下のようになります。

$$Q_Π(s, a) = r(s, a) + V_Π(s_{end}') = r(s, a)$$

この式から、ゲームが決着する場合の行動価値は、そのときに得られる即時報酬（勝敗結果）そのものになる ことがわかります。

求めたい最善手を変えないための「環境の修正条件」

ここまでの確認から、「ゲームが決着する場合でも、行動価値が遷移後の状態価値に等しくなる」ように環境（ルールの定義）をうまく修正すれば良いことがわかりました。

ただし、その際に環境を好き勝手に修正してゲームの本質的なルールまで変わってしまっては本末転倒です。環境を修正した結果、AI が計算する「最善手」が、修正前と全く同じにならなければ意味がありません。

そのことから、「原始モンテカルロ法によって計算される 最善手が変わらないように環境を修正する必要がある」ことがわかります。

環境の修正に課される「3 つの条件」

前回の記事で説明したように、原始モンテカルロ法における最善手は、現在の局面（ステップ 0）に対する最適方策 $π_0^*$ に基づいて以下のように選択されます⁴。

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

この式の意味は、ステップ 0 の行動価値 $Q_Π(s_0, a)$ が一番高い行動を最善手として選択する というシンプルなものです。

従って、どれだけ環境の定義を修正しても「最初の 1 手目（ステップ 0）におけるすべての行動価値 $Q_Π(s_0, a)$ の値」さえ変化しなければ、計算される最善手は変化しない ということになります。

上記をまとめると、常に $Q_\Pi(s, a) = V_\Pi(s')$ という式を成り立たせるためには、以下の 3 つの条件をすべて同時に満たす ように環境を修正すれば良いことがわかりました。

環境を修正しても、遷移した状態が決着がついていない場合に $Q_Π(s, a) = V_Π(s_{pl}')$ が引き続き成り立つこと
環境を修正することで、遷移した状態が決着がついた場合に $Q_Π(s, a) = V_Π(s_{end}')$ 成り立つようになること
環境を修正しても、ステップ 0 のすべての行動価値 $Q_Π(s_0, a)$ の値が変化しないこと

具体的な環境の修正方法

上記の 3つの条件をクリアするための具体的な環境の修正方法を解説します。なお、新しく導入する記号は変数ではなく「具体的な1つの定数」であるため、前節のルール通り添字が大文字の $s_{FIN}$ と $a_{FIN}$ で表記します。

具体的な修正手順は以下の通りです。

新しい状態の追加：エピソードの本当の最後（finsh）を表す特別な状態 $s_{FIN}$ を定義し、状態空間 $\mathcal{S}$ に加える
新しい行動の追加：$s_{FIN}$ へと移行するための、専用の特別な行動 $a_{FIN}$ を定義し、行動空間 $\mathcal{A}$ に加える
終了条件の変更：エピソードの終了条件を「ゲームの決着がついた状態 $s_{end}$ に遷移する」から、「最終状態 $s_{FIN}$ に遷移する」に変更する
決着がついた状態と最終状態の行動の設定：
- 最終状態 $s_{FIN}$ に達した後はもう何も行動できないため、取れる行動の集合 $\mathcal{A}(s_{FIN})$ は空集合（要素がゼロ）とする
- ゲームの決着がついた状態 $s_{end}$ で取れる行動は、エピソードを終わらせるための $a_{FIN}$ のみとする
即時報酬が得られるタイミングの変更：
- ゲームの決着がついた状態へ遷移した際に得られる即時報酬を 0 にリセットする
- その代わりに、ゲームの決着がついた状態 $s_{end}$ から終了行動 $a_{FIN}$ を選択して最終状態 $s_{FIN}$ に遷移した際に、その局面の勝敗結果に応じた即時報酬⁵が得られる ように変更する

注意点として、$s_{FIN}$ は 対局が完全に終わった ことを表す特別な状態にすぎないため、他の状態と異なり具体的なゲームの局面（盤面）を表しません。同様に $a_{FIN}$ も「対局を完全に終了させる」という特別な行動なので、他の行動と異なり具体的な着手を表すものではありません。また、ゲームの決着がついていない局面では $a_{FIN}$ を選択することはできません。

上記の修正は、一見すると新しい状態と行動が増えてややこしくなったように見えるかもしれませんが、要約すると下記の 2 点の単純な変更を行っただけにすぎません。

エピソードの終了条件を「ゲームの決着がつく」から、「ゲームの決着がついた後でゲームを終了させるための行動 $a_{FIN}$ を取る」に変更する
即時報酬をもらえるタイミングを 「決着がつく着手を行った瞬間」から「決着後に終了行動 $a_{FIN}$ を取った瞬間」 へ、1 ステップ後ろにずらした

上記の修正をテレビゲームで例えると、「ゲームオーバーになった際にスコアが表示されていたゲーム」を、「ゲームオーバーになった後で、ボタンを 1 回押すとスコアが表示されるゲーム」に修正したことにに相当します。

表示されるスコア（報酬）も、ゲームオーバーになったという事実（勝敗）も全く変わらず、ただ終了行動 $a_{FIN}$ に相当する「ボタンを押す」というステップが 1 つ挟まっただけです。このような修正であれば、ゲームそのもののルールや、プレイヤーが目指すべき戦略（最善手）が何も変わらないことが直感的に納得できるのではないでしょうか。

プログラムの実装や厳密な数式モデルに興味がある方向けに、この修正を「状態空間、行動空間、状態遷移関数、報酬関数、初期状態、終了条件」の変更点として数学的に整理しておきます。なお、$\leftarrow$ は左辺の集合を右辺の集合で更新することを表します。また、$\cup$ は集合の和を表す記号です。

状態空間の更新：$\mathcal{S} \leftarrow \mathcal{S} \cup {s_{FIN}}$
行動空間の更新：$\mathcal{A} \leftarrow \mathcal{A} \cup {a_{FIN}}$
合法手の集合の更新：
- すべての $s_{end}$ に対して、$\mathcal{A}(s_{end}) = \{a_{FIN}\}$
- 最終状態に対して、$\mathcal{A}(s_{FIN}) = \{\}$ （空集合）
状態遷移関数 $f(s, a)$ の更新：すべての $s_{end}$ からの状態遷移において、 $f(s_{end}, a_{FIN}) = s_{FIN}$
報酬関数 $r(s, a)$ の更新：
- すべての $s_{end}$ へ遷移する任意の行動において $r(s, a) = 0$
- すべての $s_{end}$ に対して $r(s_{end}, a_{FIN}) =$ その局面の勝敗に応じた報酬値
終了条件の更新：$s_{FIN}$ への状態遷移をもってエピソードの終了とする
不変の要素：上記以外の状態遷移関数や報酬関数の変更は行わず、エピソードの初期状態 $s_{0}$ も変更しない

環境の修正方法の妥当性の証明

次に、先ほど説明した環境の修正が、下記の「3 つの条件」をすべて満たしていることを順番に証明します。

環境を修正しても、遷移した状態が決着がついていない場合に $Q_Π(s, a) = V_Π(s_{pl}')$ が引き続き成り立つこと
環境を修正することで、遷移した状態が決着がついた場合に $Q_Π(s, a) = V_Π(s_{end}')$ 成り立つようになること
環境を修正しても、ステップ 0 のすべての行動価値 $Q_Π(s_0, a)$ の値が変化しないこと

行動価値が状態遷移後の状態価値と常に等しくなることの証明

環境の修正を行っても「ゲームの決着がついていない局面」に遷移したときに得られる即時報酬は $r(s, a) = 0$ のまま変更していません。従って、修正前と同様に以下の式がそのまま成り立ちます。

$$Q_Π(s, a) = r(s, a) + V_Π(s_{pl}') = V_Π(s_{pl}')$$

環境を修正したことで、即時報酬が得られるタイミングが 1 つ後ろへずれたため、ゲームが決着する局面へ遷移した瞬間に得られる即時報酬が $r(s, a) = 0$ に変化しました。これにより、これまでは即時報酬そのものになっていた計算式が、以下のように変化します。

$$Q_{\Pi}(s,a)=\underbrace{r(s,a)}_{0\text{ に修正}}+V_{\Pi }(s_{end}^{\prime })=V_{\Pi }(s_{end}^{\prime})$$

このように、即時報酬 $r(s, a)$ が消えた結果、ゲームが決着する場合であっても $Q_\Pi(s, a) = V_\Pi(s_{end}')$ 成り立つようになります。

以上から、状態遷移後の状態 $s'$ の局面が決着がついているかどうかに関わらず、常に下記の式が成り立つことが証明されました。

$$Q_Π(s, a) = V_Π(s')$$

すべての行動価値が変化しないことの証明

残る条件は「最初の 1 手目（ステップ0）の行動価値 $Q_Π(s_0, a_0)$」が変化しないことです。

実際には、ステップ 0 に限らず「すべての状態と行動 に対する行動価値 $Q_Π(s, a)$ の値そのものが、この環境の修正によって全く変化しない」ことが成り立ちます。

このことを遷移後の状態が「ゲームの決着がついていない場合」と、「決着がついている場合」の 2 つに分けて証明します。

ゲームの決着がついていない局面に状態遷移する場合

遷移した先がゲームの決着がついていない局面 $s_{pl}^{\prime }$ である場合は、修正前と修正後のどちらの環境でも以下の共通の式が成り立ちます。

$$Q_Π(s, a) = V_Π(s_{pl}')$$

従って、環境の修正によって、任意の $s_{pl}$ の状態価値を表す $V_Π(s_{pl})$ の値が変化しないことを証明すれば良いことがわかります。

以前の記事で説明したように、ある状態における状態価値とは、その状態から未来に向かって方策 $\Pi$ に従って行動を選択し続けたときに得られる「累積報酬 $G$ の期待値」のことで、下記の式で表されます。

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

今回の環境の修正によって、即時報酬が手に入るタイミングが以下のように変化しまが、その際に得られる即時報酬の値はゲームの勝敗に応じた値である点は変わりません。

修正前の環境：ゲームの決着がつく着手を行った時
修正後の環境：ゲームの決着がついた状態 $s_{end}$ に遷移した後で、次のステップで行動 $a_{FIN}$ を取って状態 $s_{FIN}$ に状態遷移した時

修正後の環境では、決着がついた $s_{end}$ で選べる行動は、先程の「ゲームを終了させるボタンを押す」という例えに相当する $a_{FIN}$ のただ 1 つだけに制限されています。選択肢が 1 つしかないということは、エージェントがどんな方策 $Π$ を取るかに関係なく、100 % の確率で $a_{FIN}$ が選択され、その時に修正前にゲームの決着がついた瞬間に得られていたものとまったく同じ即時報酬が得られます。

このことを、時系列を並べてみると以下のようになります。

$\text{修正前：対局中} \xrightarrow{a} s_{end} \text{ 決着（即事報酬を入手）（ここで終了）}$
$\text{修正後：対局中} \xrightarrow{a} s_{end} \text{ 決着（即事報酬なし）} \xrightarrow{\text{100 % で }a_{FIN}} \text{終了状態（即事報酬を入手）}$

上記から即時報酬が得られるタイミングが 1 ステップだけ後ろにずれますが、エピソード全体を通して手に入る累積報酬（即事報酬の合計）が、修正前と修正後で完全に一致することがわかります。

未来の累積報酬が全く同じであれば、その期待値として計算される状態価値 $V_\Pi(s_{pl})$ の値も、修正前と修正後で完全に一致します。以上のことから、環境の修正を行っても「ゲームの決着がつかない場合の行動価値 $Q_\Pi(s, a)$ の値が変化しない」ことが証明されました。

ゲームの決着がついた局面に状態遷移する場合

ゲームの決着がついた局面に状態遷移する場合は、修正する前の環境と、修正後の環境で行動価値を表す式が下記のように異なります。

修正前の環境：$Q_Π(s, a) = r(s, a)$（その場で得られる勝敗報酬）
修正後の環境：$Q_Π(s, a) = V_Π(s_{end}')$（決着した局面の状態価値）

先程説明したように、修正後の環境では $s_{end}$ の次のステップで 100 % の確率で修正前に得られていた即時報酬 $r(s, a)$ と同じ即時報酬が得られ、そこでエピソードが終了します。従って、修正後の環境では、$s_{end}$ の未来で得られる累積報酬の期待値を表す $Q_Π(s, a) = V_Π(s_{end}')$ の値は、修正前の環境の $Q_Π(s, a) = r(s, a)$ と等しくなります。

以上のことから、環境の修正を行っても「ゲームの決着がつかない場合の行動価値 $Q_Π(s, a)$ の値が変化しない」ことが証明されました。

まとめ

上記から、遷移後の状態が決着がついていない $s_{pl}^{\prime }$ か決着済み $s_{end}^{\prime }$ かに関わらず、すべての状態と行動に対する行動価値 $Q_Π(s, a)$ は、環境の修正によって変化しないこと が証明されたました。当然ですが、本当に証明したかった ステップ 0 の行動価値 $Q_Π(s_0, a_0)$ も環境の修正によって変化しません。

従って、この環境の修正によって最初に掲げた下記の「3つの条件」のすべてが満たされることが証明されました。

環境を修正しても、遷移した状態が決着がついていない場合に $Q_Π(s, a) = V_Π(s_{pl}')$ が引き続き成り立つこと
環境を修正することで、遷移した状態が決着がついた場合に $Q_Π(s, a) = V_Π(s_{end}')$ 成り立つようになること
環境を修正しても、ステップ 0 のすべての行動価値 $Q_Π(s_0, a)$ の値が変化しないこと

環境の修正後の原始モンテカルロ法

環境の少し修正したことで、複雑だった「勝率」という言葉の意味が 常に「状態価値」だけを表す ようになり、アルゴリズムが以下のようにシンプルになります。

すべての 1 手目の局面に対して均等な回数のプレイアウトを行い、その勝率からその局面の 「状態価値の推定値」 を求める
現在の局面（0 手目）の合法手の中で、着手した先の局面における 「状態価値の推定値」（= 勝率） が最大となる合法手を最善手として選択する

以後の説明では、この修正した環境をベースに話を進めていくことにします。

勝率と真の勝率の区別

この後の解説を直感的に分かりやすくするために、勝率という言葉の定義を以下のように整理することにします。

勝率：プレイアウトを何回か試すことで得られた、現時点での「状態価値の推定値」（実験データから計算した勝率）
真の勝率：プレイアウトを無限に繰り返すことで得られる、その局面の本来の「状態価値」（理論上の完璧な勝率）

高校数学の確率統計で例えるなら、「勝率」は実際にサイコロを振って求めた 1 の出目の割合であり、「真の勝率」は計算上の確率（$1/6$ など）に対応します。

上記の定義を用いることで、原始モンテカルロ法のアルゴリズムを下記のように簡潔に表現することができます。

すべての 1 手目の局面に対して、均等な回数のプレイアウトを行い「勝率」を求める
現在の局面の合法手の中で、着手後の局面の「勝率」が最大となる合法手を最善手とする

原始モンテカルロ法の単純な拡張とその問題点

今回の記事の冒頭で説明した、「最善手をじっくり計算する範囲を、現在の局面（1 手目）だけでなく、その先の未来の局面（2 手目、3 手目……）へと広げていく」という工夫とその問題点について説明します。

深さが 2 の原始モンテカルロ法

プレイアウトを行う局面を、これまでの 1 手目から 2 手目に単純に拡張した原始モンテカルロ法のアルゴリズムは以下のようになります。ただし、当然ですが、決着がついている局面に対してプレイアウトを行うことはできないので、その局面の勝率はその勝敗結果から直接求めます。

2 手先（ステップ 2）の評価：すべての「2 手目の局面」に対して均等な回数のプレイアウトを行い、それぞれの勝率を求める
1 手先（ステップ 1）の勝率の決定：「1 手目のすべての局面」に対して、そこから合法手を着手した「2 手目の局面（ステップ 2）」の勝率の 最小値 を求め、それをその 1 手目の局面の勝率とする
現在の局目（ステップ 0）の最善手の決定：現在の局面の合法手の中で、着手後の「1 手目の局面（ステップ 1）」の勝率が最大となる合法手を最善手として選択する

このアルゴリズムの正式な名称を文献等で探してみましたが、一般的に定着した名称がみつけられませんでした⁶。そこで、本記事ではこれまでの 1 手先でプレイアウトを行うアルゴリズムを単に「原始モンテカルロ法」と表記し、この拡張版のアルゴリズムを「深さ 2 の原始モンテカルロ法」と呼ぶことにします⁷。

「深さ 2 の原始モンテカルロ法」は、下記の前提で最善手を求めるアルゴリズムです。

3 手目以降の未来の局面では、これまで通りにランダムに着手し続ける
1 手目の局面（相手の手番）では、相手は「〇の勝率が最小になるような、一番嫌な手」を正確に選んで打ってくるはずだと仮定する

「次の自分の 1 手だけ」を独りよがりに深く検討していた従来の原始モンテカルロ法と比べると、深さ 2 の原始モンテカルロ法は「自分がこう打ったら、相手は返してくるだろう」という、お互いの行動を 1 手ずつ考慮した「2 手先までの未来」を深く検討するという改良が行われます。

深さが 3 以上の原始モンテカルロ法への一般化

この「先読みの範囲を広げる」という考え方をさらに一般化し、$n$ 手先までの行動を深く検討する「深さ $n$ の原始モンテカルロ法」 のアルゴリズムは以下のようになります。なお、決着がついている局面に対する勝率は先ほどと同様にその勝敗結果から求めます。

$n$ 手先（ステップ $n$）の評価：すべての「$n$ 手目の局面」に対して均等な回数のプレイアウトを行い、それぞれの勝率を求める
$1$ ~ $n-1$ 手先（ステップ $1$ ~ $n - 1$）の評価：
変数 $i$ の値を $n-1$ から一つずつ減らしてしていき、$i = 0$ になるまで以下の計算を繰り返す
1. $i$ が偶数の場合（自分の手番の局面）：そこから合法手を着手した次の局面（ステップ $i + 1$）の勝率の 最大値 を求め、それをその局面の勝率とする
2. $i$ が奇数の場合（相手の手番の局面）：そこから合法手を着手した次の局面（ステップ $i + 1$）の勝率の 最小値 を求め、それをその局面の勝率とする
現在の局目（ステップ 0）の最善手の決定：手順 2 によってすべての「1 手目の局面（ステップ 1）の勝率」が計算されるので、現在の局面の合法手の中で、着手後の局面の勝率が最大となる合法手を最善手として選択する

この深さ $n$ の原始モンテカルロ法は、「$n$ 手目まではお互いが最善を尽くし、$n+1$ 手目以降の未来は完全ランダムに着手（プレイアウト）する」という前提に立って、$n$ 手先までの行動を考慮 した最善手を計算するアルゴリズムです。

深さが n の原始モンテカルロ法の正体

この「互いが自分にとって最も有利な（相手にとっては最も不利な）選択肢を選び続ける」という前提で最善手を求めるアルゴリズムは、実は以前の記事で紹介した ミニマックス法 そのものです。

つまり、深さを 2 以上に拡張した原始モンテカルロ法は、以下の設定を施した 「深さ制限ミニマックス法」と完全に同じアルゴリズム であることがわかります。

探索する深さの上限を $n$ に制限する
本来なら局面の形勢を判断する静的評価関数を用いて計算する「深さ $n$ の局面の評価値」として、プレイアウトによって計算された「勝率」をそのまま流用する

従って、深さが 2 以上の原始モンテカルロ法は、深さ制限探索の性質を解説した以前の記事で説明した、以下の「ミニマックス法」とまったく同じ性質を引き継ぐことになります。

深さが $n$ で得られる勝率（評価値）の精度が高いほど、最終的に選択される最善手の精度も高くなる
深さの上限 $n$ を増やせば増やすほど、最終的に選択される最善手の精度が高くなる

このように、「先を読む範囲を広げる」という直感的なアプローチは、ゲームの AI の世界で広く使われる「深さ制限ミニマックス法」そのものに直結することがわかりました。

なお、一般的なミニマックス法の「評価値」は、原始モンテカルロ法の「勝率」のように「0 以上 1 以下の範囲」に収まるとは限りません。しかし「値が大きいほど自分（先手）が有利で、小さい程相手（後手）が有利である」という性質は完全に一致しています。2 つの用語が混ざると読者が混乱するのではないかと思いましたので、本記事ではこれ以降も「勝率」という表現で統一して解説を進めることにします。

深さが 2 以上の原始モンテカルロ法の問題点

深さ制限ミニマックス法は、一般的には先読みの深さ（上限）を増やせば増やすほど、より正確で強力な最善手を見つけられるようになることが期待できます。しかし、残念ながら原始モンテカルロ法の深さを先程説明したアルゴリズムによって単純に増やした場合は、AI の強さが改善されるどころか、逆に著しく悪化してしまうという不都合な現象が頻発します⁸。そこで、深く読もうとすればするほど AI が弱くなってしまうという、一見するとおかしな現象が起きてしまう理由について説明します。

「ルールベースの評価関数」と「原始モンテカルロ法」の違い

以前の記事で実装した ai14s のように、盤面の状況（マークの並び方など）をその場でチェックして形勢判断を行う AI（静的評価関数）の場合は、先読みの深さを数手増やしたところで「その局面がどれくらい有利か」を計算する難しさ（計算量）自体はそこまで大きく変わりません⁹。そのため、こうしたルールベースの AI であれば、純粋に「深さの上限を増やすメリット」だけを享受して、より精度の高い最善手を計算することができます¹⁰。

一方、ランダムなプレイアウトで勝率を求める「原始モンテカルロ法」では、深さを少し増やすだけで、同じ精度を保つために必要な計算量が指数関数的に膨れ上がります。制限時間がある中で深さを増やすと、1 局面あたりのプレイアウト回数を大幅に減らさざるを得ず、大数の法則が働かずに 勝率の精度が著しく低下します。その結果、深さを増やすメリットが精度低下のデメリットに相殺され、AIの精度が悪化してしまいます。

計算される勝率の精度が悪化する理由

言葉の説明だけではわかりづらいと思いますので、深さを少し増やすだけで、現実的な時間内で計算される勝率の精度が急激に落ちる理由を具体例を挙げて説明します。

指数関数的な局面数の増加（組み合わせの爆発）

深さが $n$ の原始モンテカルロ法では、「$n$ 手目のすべての局面に対してそれぞれ均等な回数」だけプレイアウトを行う必要があります。しかし、〇× ゲームに限らず、ほぼすべてのゲームでは「読みの深さ（手数）を増やすと、そこに存在する局面の総数は指数関数的に爆発する」という性質があります。

具体例として、〇×ゲームのゲーム開始時の局面から、深さ 1 〜 5 のそれぞれの局面の総数を計算してみることにします¹¹。〇×ゲームは、最初はマスの数と同じ 9 つの合法手があり、1 手進むごとに選べるマスが 1 つずつ減っていきます。そのため、各手番に存在する局面の総数は以下の表のようになります¹²。

読みの深さ（手数）	局面の総数の計算式	局面の総数
1	9	9
2	9 × 8	72
3	9 × 8 × 7	504
4	9 × 8 × 7 × 6	3,024
5	9 × 8 × 7 × 6 × 5	15,120

この表から、深さを増やすごとにプレイアウトによって勝率を計算する局面の総数がものすごい勢いで膨れ上がることがわかります。

例えば、各局面での勝率を計算する際のプレイアウトの回数を 1,000 回とした場合は、従来の「深さ 1」であれば、9 局面に対してそれぞれ 1,000 回の合計 9,000 回のプレイアウトを行います。しかし、たった 5 手先までじっくり読もうとして「深さを 5」に設定すると、15,120 局面に対してそれぞれ 1,000回、つまり合計 1,512 万回ものプレイアウトを行う必要が生じてしまいます。

数学的な「組み合わせの爆発」

この「手数を増やすと局面が爆発する」という現象を、高校数学の知識を使って厳密に確認することにします。

〇× ゲームや囲碁のように、着手を行うたびに原則として合法手の数が 1 つずつ減るゲームは¹³、最初の合法手を $n$ 種類とすると、$i$ 手目の局面の総数は、高校数学の「場合の数（順列）」でおなじみの以下の式（階乗）で計算できます。

$$_{n}\mathrm{P}_{i} = \frac{n!}{(n-i)!}$$

数学の世界には「スターリングの近似公式¹⁴」というものがあり、$n$ が大きくなると $n!$（階乗）は $n$ の指数関数のように猛烈な勢いで増加することが証明されています。つまり、選択肢が減るゲームであっても、その総数は指数関数的に増加します。

さらに、将棋やチェスのように「駒を動かしても次の選択肢（合法手）が単純には減らない（むしろ増えることもある）」ゲームでは、この組み合わせの爆発はより顕著になります。具体的にはゲーム中の合法手の平均 $x$ とすると、$n$ 手先の局面の総数はシンプルに「$x^{n}$」という指数関数で表されます。

時間制限がある場合のプレイアウトの回数

無限の時間をかけて計算を行えるなら、どれだけ先読みの深さを増やしても、末端のすべての局面に対して無限回のプレイアウトを行い、真の勝率を求めることができます。しかし、現実の世界では AI の思考時間には制限（例：1 手 3 秒など）を設けるのが一般的です。

ここで、制限時間とプレイアウトの回数の関係を調べるために、深さが $n$ の原始モンテカルロ法の処理の内訳を考えてみることにします。深さ $n$ のミニマックス法において、各局面の「最大値」や「最小値」を計算する処理は、一瞬で終わる非常に単純なものです。それに対して「プレイアウト」の処理は、ゲームが終了するまで「ランダムに着手を選ぶ」、「盤面を更新する」、「勝敗判定を行う」という複雑な処理を何回も繰り返します。つまり、原始モンテカルロ法の 処理時間のほぼ 100% をプレイアウトの処理が占めている と言えます。

このことから、「制限時間（秒数）を設定する」ということは、「AI が実行できるプレイアウトの総数を決める」ということと同じ意味をもつことがわかります。

そこで、具体例として、「プレイアウトの総数が最大 10,000 回」という制限時間を設定した場合に、深さ 1 〜 5 の原始モンテカルロ法によって、1 局面あたりのプレイアウトの回数がどのように変化するかを計算してみることにします。

1 局面あたりのプレイアウトの回数は、「プレイアウトの総数 ÷ プレイアウトを実施する局面の総数」で計算できるので、〇× ゲームでは下記のようになります。なお、一局面当たりのプレイアウトの回数は小数点以下第 2 桁で四捨五入しました。

読みの深さ（手数）	局面の総数	一局面あたりのプレイアウトの回数
1	9	1,111.1
2	72	138.9
3	504	19.8
4	3,024	3.3
5	15,120	0.7

上記の表から、〇× ゲームでは原始モンテカルロ法の深さを増やすと、1 つの局面に対して行われるプレイアウトの回数が実際に 急激に減少する ことが確認できます。

上記の表のように、計算上のプレイアウトの回数に「小数点（端数）」が出る場合は、大きく分けて以下の 2 つのアプローチが考えられます。なお、下記は読みの深さが 1 の場合のアプローチです。

端数を切り捨てる：9 種類の局面に対して 1,111 回ずつ、計 9,999 回のプレイアウトを行い、余った回数（1 回分）のプレイアウトは実施しない
余った回数を均等に分配する：基本は 1,111 回ずつとし、余った 1 回分を特定の 1 局面（またはランダムに選んだ局面）に割り当てることで 10,000 回のプレイアウトをすべて使い切る。この例の場合は 1 種類の局面に対して 1,112 回、残りの 8 種類の局面に対して 1,111 回ずつ、計 10,000 回のプレイアウトを行う

以後は、後者のアプローチを行った場合の説明を行います。

プレイアウトの回数と勝率の精度の関係

プレイアウトによって求められる局面の勝率の精度は、大数の法則によりプレイアウトの回数が少ないほど低く（= 誤差が大きく）なります。そのため、一局面あたりのプレイアウトの回数が少なければ少ないほど、計算された勝率の精度は低く（＝誤差が大きく）なってしまいます。

具体的に、先程の「プレイアウトの総数を 10,000 回」とした〇× ゲームで比較してみることにします。従来の原始モンテカルロ法のように「深さが 1」であれば、1 つの局面に対して 1,000 回以上のプレイアウト割り当てる ことができたのに対し、「深さを 4」まで広げると、各局面には わずか 3 回または 4 回 しかプレイアウトを割り当てることができません。このように、読みをほんの 3 つ深く読もうとしただけで、勝率データの信頼性が著しく低下してしまうのです。

この精度の低下は、「サイコロの出目の期待値を推測する実験」をイメージすれば一発で納得できるはずです。サイコロを 1,000 回振った結果の平均値は、本来の期待値である「3.5」に十分に高い精度で近づきますが、サイコロを 3 〜 4 回振った結果の平均値は、例えばたまたま「6」が連続して出れば 5 〜 6 になり、本来の期待値から大きな誤差を持ったデータになってしいます。

このように、大きな誤差を含む可能性が高い、精度の低い勝率データ を元にして、深い読みを行うミニマックス法（最大・最小の計算）を行っても、そこから導き出される 最善手も大きな誤差を含む可能性が高い、精度の低いものになってしまうことは避けられません。

さらに致命的な問題となるのが、1 局面あたりの プレイアウトの回数が 1 未満（0.7 回） に突入する深さが 5 の場合です。これは全体で 15,120 種類ある局面のうち、約 3 分の 1 にあたる「5,120 局面」では、1 度もプレイアウトが行われない という異常事態を意味しています。当然ですが、1 度もプレイアウトが行われていない局面の勝率は「完全に不明」 です。しかし、4 手目の勝率（最小値・最大値）を計算するためには、これらの「勝率不明な局面」を無理やり無視して進めるか、適当な数値（例えば 0.5 勝など）をでっちあげて計算するしかありません。判断材料となるデータがこのように、勝率が不明な穴ぼこだらけ（スカスカ）の状態で計算された勝率は、ただの「運まかせなもの」であり、最善手の精度は致命的なまでに暴落してしまいます。

深さを増やした原始モンテカルロ法の問題点のまとめ

以上の検証から、原始モンテカルロ法の深さを単純に増やすというアプローチには、以下の「トレードオフ（利点と欠点）」があることがわかりました。

利点：ミニマックス法の先読みの深さ（上限）を高めることができ、理論上はより先を見据えた大局的な手が打てるようになる
欠点：深さを広げた瞬間に 1 局面あたりのプレイアウト回数が激減し、計算される勝率の精度が著しく低下する。さらに一定以上深くすると、1 度もプレイアウトが行われない未踏の局面が大量に発生し、アルゴリズムが崩壊（最大値・最小値を計算できない局面が大量に発生する）する

このことから、最善手の精度を高めようとして深く読めば読むほど、割り当てられるプレイアウトの回数が減少し、得られる最善手の精度が致命的に悪化する というジレンマが、深さを単純に増やすというアプローチの致命的な弱点であることがわかりました。

今回の記事のまとめ

今回の記事では、原始モンテカルロ法の読みの深さを単純に広げるというアプローチについて説明し、そこには「組み合わせの爆発によって、勝率や最善手の精度が崩壊する」という致命的な欠点があることを示しました。

「深く読もうとすると勝率の精度が致命的に悪化し、勝率の精度を高くしようとすると 1 手先しか読めない」というジレンマを解決するために考案された画期的なアルゴリズムがモンテカルロ木探索（Monte Carlo Tree Search（MCTS））です。

次回の記事で詳しく説明しますが、モンテカルロ木探索の考え方は「探索の選択と集中」というもので、平たく言えば 重要な局面に対してプレイアウトを多く割り当てる という「えこひいき」を行います。具体的には、すべての未来の局面を平等に調べるのをやめ、「勝敗を分ける重要な局面」や「筋の良さそうな強い手」だけをえり好みして、重点的にプレイアウトの回数を注ぎ込みます。その結果、モンテカルロ木探索のアルゴリズムは、限られた制限時間の中でも「勝率の精度を高く保ったまま」、「読みの深い探索を行う」ことを両立させることに成功しました。

次回の記事からは、モンテカルロ木探索の具体的な考え方と手法について詳しく解説する予定です。

参考までに Wikipedia のモンテカルロ木探索のリンクを下記に紹介します。予習を行いたい方は是非参考にしてみて下さい。

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

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

次回の記事

近日公開予定です。

プレイアウトによって求められるのは、状態価値そのものではなく、状態価値の推定値である点に注意して下さい。大数の法則により、プレイアウトの回数が多くなればなるほど推定値の精度が高くなり、勝率（推定値）が限りなく状態価値（本当の勝率）に近づくことになります ↩
$s'$ は状態 $s$ で行動 $a$ を選択した場合に遷移する次の状態 $s' = f(s, a)$ を表します ↩
正確には、前者は「1 手進んだ局面の状態価値の推定値」、後者は「現在の局面の行動価値の推定値」となります。 ↩
前回の記事のノートで説明したように、最善手が複数存在する場合は、それらを合わせた選択確率の合計が 1（100%）になるように設定します ↩
この修正を行う前に、決着がついた状態へ遷移した際に得られた即時報酬と同じ値のことです ↩
Monte-Carlo Go Developmentsという囲碁の AI に関する論文内で「depth 2 enhancement（深さ 2 への拡張）」という説明でこのアルゴリズムが紹介されていますが、このアルゴリズムに具体的な名称は与えられていませんでした。おそらくこのアルゴリズムがこの後で解説するように「実用性が低すぎて誰も使わなかった」ために、名前すら付けられなかったのではないかと筆者は推測しています ↩
この記法に従うと、従来の原始モンテカルロ法は「深さ 1 の原始モンテカルロ法」となります ↩
Monte-Carlo Go Developmentsによると、原始モンテカルロ法の深さを 1 から 2 に増やした結果、囲碁の AI の勝率が逆に悪化したことが実際に報告されています ↩
一般的なゲームが終盤になればなるほど局面の形勢がはっきりするという性質から、局面が終盤に近付くほど計算する評価値の精度が高くなることが期待されます ↩
深さの上限を増やすことでミニマックス法の計算時間が指数関数的に増えるため、深さの上限を無限に増やすことはできません ↩
深さを 5 までとした理由は、〇× ゲームでは決着がつくまでに最低でも 5 手が必要となるからです。6 手目以降についてはそれ以前に決着がつく可能性があるため単純な計算式でその数を求めることはできません。なお、手数ごとの正確な局面の数については以前の記事で具体的な値を求めたのでそちらを参照して下さい ↩
同一局面を別の局面として区別した場合です。ただし、同一局面を同じ局面として数えた場合でも、手数を増やすと局面の種類が指数的に増えることに変わりはありません ↩
「原則として」と表記した理由は、例えば囲碁の場合は、囲碁のルールによって空いていても置くことができないマスや、相手の石を取ることで合法手の数が増える場合があるからです ↩
詳細はこちらの Wikipedia のリンク先を参照して下さい ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

Pythonで〇×ゲームのAIを一から作成する その244 原始モンテカルロ法の単純な拡張とその問題点