0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ysgeso

Pythonで〇×ゲームのAIを一から作成する　その246　多腕バンディット問題への抽象化と処理の高速化

0
Last updated at Posted at 2026-09-20

目次と前回の記事

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

前回の記事のおさらいと今回の記事の内容

前回の記事では、「真の勝率が高い有望な手ほど、プレイアウトを多く割り当てなければならない」というモンテカルロ木探索の「えこひいき」の方針が数学的に合理的であることを証明しました。

一方で、現実の強化学習では、まったく未知の状態から学習を始めるため、どの合法手がどれくらい強いのかということは事前にはわかりません。そのため、実力が分からないのに、実力が高い合法手をえこひいきしなければならないという困難な課題に直面します。

この課題をクリアするために、モンテカルロ木探索は下記の 「探索」と「活用」を並行して行う というアプローチをとります。

  • 探索（Exploration）：未知の局面の「本当の実力（真の勝率）」を正しく推測するために、いろんな合法手を幅広く試すこと
  • 活用（Exploitation）：これまでに行った探索から「この手が強そうだ」と分かった有望な合法手に、プレイアウトを多く割り当てる（えこひいきする）こと

今回の記事の内容

前回の記事で説明したように、モンテカルロ木探索には、大きく分けて「プレイアウトをどう割り当てるか」と「どうやって読みの深さを広げるか」という 2 つのテーマがあります。今回の記事では前回の記事に引き続き、後者の「深さを広げる問題」はいったん脇に置き、原始モンテカルロ法と同じく、「1 手先（深さ 1）の局面だけに、限られたプレイアウトの総数をどう分配するか」という問題に絞って考えていきます。

以後は、この問題を「1 手先の分配問題」と短く表記することにします。

今回の記事では、「1 手先の分配問題」における「探索」と「活用」のトレードオフについて説明する前準備として、この問題と完全に同じテーマを扱う、より簡潔な「多腕バンディット」問題について説明します。

「1 手先の分配問題」を「多腕バンディット問題」に置き換えることで、ゲームの複雑なルールを無視して、「どの確率の選択肢に、回数をどう分配するか」という問題の本質だけに集中して考えられるようになります。その結果、プログラムによるシミュレーションの計算を大幅に高速化できるという利点も得られます。

なお、今回の記事でも、前回の記事から引き続き、「勝率」と「真の勝率」という用語を多用します。これらの用語については前回の記事を参照して下さい。

多腕バンディット問題への置き換え

以前の記事では、原始モンテカルロ法のアルゴリズムの性能を確認するために、実際に何回も 〇× ゲームの対戦を行うというプログラムによるシミュレーションを行いました。

今後の記事で紹介する「1 手先の分配問題」に対する「探索と活用のトレードオフを行うアルゴリズム」の性能を確認する際も、同様にプログラムによるシミュレーションを行います。しかし、「1 手先の分配問題」を愚直にシミュレートしようとすると、プログラムの処理速度を大きく引き下げる原因となる ボトルネック （処理を遅くしている最大の原因）にぶつかります。

それは、『ゲームが終了するまで「ランダムに着手を選ぶ」、「盤面を更新する」、「勝敗判定を行う」という複雑な処理を何回も繰り返す』という、プレイアウトの処理 です。

そこで、この重いプレイアウトの処理を、数学的にまったく同じ結果が得られる、より軽い処理に置き換える ことを考えることにします。

プレイアウトで行われる処理の置き換え

〇× ゲームでは、1 回のプレイアウトによって計算される値は「〇 の勝利 = 1」、「引き分け = 0.5」、「〇 の敗北 = 0」という、3 種類の値ですが、ここでは話をシンプルにするために、引き分けが存在しないルールであるものとして説明を行います（引き分けが存在する場合については、すぐ下のノートで補足します）。

引き分けが存在しない場合は、1 回のプレイアウトによって計算される値は「〇 の 勝利 = 1」と「〇 の敗北 = 0」という 2 種類です。そして、プレイアウトを何度も繰り返したときに「得られる値の期待値（平均値）」は、無限回のプレイアウトを行ったときの勝率の理論値である 「真の勝率」に完全に一致 します。

このことから、ある局面の「真の勝率」さえわかっていれば、わざわざ時間をかけてゲームを最後まで遊ぶ（プレイアウトを行う）必要がなくなります。その代わりに、プログラムで次のような 一瞬で終わる計算を行うだけで、1 回のプレイアウトとまったく同じ効果（シミュレーションのデータ）を得る ことができます。

  • 0 以上 1 未満の「一様乱数」1を 1 つ発生させる
  • その乱数の値が「真の勝率」未満であれば計算結果を 1 とし、そうでなければ 0 とする

引き分けが存在する本来のルールを再現する場合は、以下のように発生した乱数の範囲を 3 つに分割します。

  • 0 以上 1 未満の一様乱数を 1 つ発生させる
  • 乱数が「〇 が勝利する確率」未満であれば、計算結果を 1 とする
  • 乱数が「〇 が勝利する確率」以上、かつ「〇 が勝利する確率 + 引き分けになる確率」未満であれば、計算結果を 0.5 とする
  • それ以外（どちらの範囲にも入らなかった場合）の場合は、計算結果を 0 とする

例えば、ある局面で「〇 が勝利する確率が 0.3（30 %）」、「引き分けになる確率が 0.2（20 %）」となる場合は、プログラムの判定は以下の表のようになります。

意味 乱数の値の範囲 計算する値 発生する確率
〇 の勝利 0 以上 0.3 未満 1 30 %
引き分け 0.3 以上 0.5 未満 0.5 20 %
〇 の敗北 0.5 以上 1 未満 0 50 %

多腕バンディット問題への置き換え

このような、「乱数を発生させ、その値が特定の値以下の場合に 1 が得られる」という現象は、くじびきやスロットマシンなどの「特定の確率で景品が当たる」ギャンブルと同じ性質を持ちます。例えば、1 回のプレイアウトをスロットマシンで例えると下記のようになります。

「真の勝率」と同じ確率でコインが 1 枚当たるスロットマシンのレバーを引く。

この例えでは、「1 回のプレイアウトの結果」と「スロットマシンのレバーを 1 回引いて得られるコインの枚数」が下記の表のように 1 対 1 に完全に対応します。

1 回のプレイアウトの結果 スロットマシンのレバーを 1 回引いた結果
0 （〇 の敗北） コインを 0 枚得る（ハズレ）
1 （〇 の勝利） コインを 1 枚得る（当たり）

また、この例えを用いることで、「1 手先の分配問題」を、下記の強化学習の入門用の題材として非常に有名な「多腕バンディット問題（multi-armed bandit problem）」に完全に置き換えることができます。

  • スロットマシンが複数台存在する
  • 各スロットマシンは、レバーを引くと特定の確率でコインが 1 枚当たる
  • 各スロットマシンのコインが当たる確率はあらかじめ決められており、後から変化することはない
  • スロットマシンのレバーを引ける総回数があらかじめ決められている場合に、どのようにレバーを引けば（= スロットマシンを選択）、得られるコインの総数を最大化できるか

「1 手先の分配問題」の目的は「真の勝率が高い有望な手ほど、プレイアウトを多く割り当てる（えこひいきする）」ことでした。これは多腕バンディット問題における「一番当たりやすいスロットマシンを見つけて、得られるコインの総数を最大化する」という目的にそのまま置き換えることができます。その詳しい理由についてはこの後で説明します。

つまり、「1 手先の分配問題」を「どのスロットマシンを何回引くか？」という問題に置き換えるということです。

下記は「1 手先の分配問題」と「多腕バンディット問題」の対応表です。

1 手先の分配問題 多腕バンディット問題
現在の局面の合法手の数 スロットマシンの数
合法手を着手した 1 手目の局面 個々のスロットマシン
1 手目の局面の「真の勝率」 対応するスロットマシンでコインが当たる確率
合法手を選択してプレイアウトを行う スロットマシンを選択してレバーを引く
1 回のプレイアウトを行った結果 レバーを 1 回引いて得られたコインの枚数

引き分けが存在する場合は、スロットマシンの設定が下記のように変わるだけで、多腕バンディット問題の本質は変わりません。

レバーを引くと「〇 が勝利する確率」で コインが 1 枚、「引き分けになる確率」でコインが 0.5 枚当たる。

多腕バンディット問題の名前の由来はギャンプルにあります。

スロットマシンなどのギャンブルは、一般的に胴元（ギャンブルの運営側）が儲かるようになっています。スロットマシンも例外ではなく、長い目で見ればコインを入れてレバーを引くと徐々にコインが奪われて、客が損をすることになります。このことからスロットマシンのレバーを「腕（arm）」に見立て、皮肉を込めて「片腕の強盗（bandit）」と呼ぶようになりました。

この「片腕の強盗」で例えられたスロットマシンを同時に複数相手にすることが多腕（multi-armed）バンディット問題」の由来です。

なお、現実のスロットマシンでは、揃った絵柄によってさまざまな種類の賞金が得られますが、多腕バンディット問題では問題をシンプルにするために、レバーを引いた時に得られるコインを 1 枚（当たり）か 0 枚（ハズレ）に限定するのが一般的です。

ただし、〇× ゲームのように「引き分け」を導入して 0.5 枚のコインが得られるように問題を拡張して、問題の本質は変わりません。

参考までに下記に Wikipedia の多腕バンディット問題のリンクを示します。

強化学習としての多腕バンディット問題

ここからは、この多腕バンディット問題が強化学習のルール（数理モデル）としてどのように定義されるかについて説明します。強化学習の用語や記号については以前の記事と以前の記事を参照して下さい。

行動空間

多腕バンディット問題における 行動 は、スロットマシンを選択してレバーを引く というものです。従って、スロットマシンの数を $n$ とすると、エージェントが取れる行動の集まり（選択肢のリスト）を表す行動空間 $\mathcal{A}$ は下記のように定義されます。なお、$a$ の添え字 $(1, 2, \dots, n)$ はどのスロットマシンのレバーを引くかを表す番号であり、エピソードのステップ数とは異なる意味を持つ点に注意して下さい。

$$\mathcal{A} = {a_1, a_2, \dots, a_n}$$

状態空間

これまでの記事で説明した 〇× ゲームを題材とする強化学習では、「それぞれの局面」を別々の状態として考えてきました。そのため、合法手を着手するという 行動を行うと 局面が変化し、別の状態へ移り変わる（遷移する） という性質がありました。

一方、多腕バンディット問題では 「すべてのスロットマシンをひっくるめて一つの状態と考える」 点が大きく異なります。

個々のスロットマシンを別々の状態に分けない理由は、どのスロットマシンのレバーを引いてもそれぞれのスロットマシンの「コインが出る確率」が一切変化しないからです。つまり、いくら行動を起こしても、エージェントを取り巻く状況（環境）がまったく変化しない ためです。

そのため、状態の集まりを表す状態空間 $\mathcal{S}$ は、下記のようにたった 1 つの状態 $s$ だけを持つ集合として定義されます2。

$$\mathcal{S} = {s}$$

「1 手先の分配問題」では、現在の局面からプレイアウトを始めると、局面（状態）が次々と変化していき、最終的な勝敗結果を元に報酬が得られます。しかし、その次のプレイアウトを行う際は、再び「現在の局面」という全く同じスタート地点に戻って行動を選択する ことになります。

つまり、「1 手先の分配問題」の内部にはたくさんの状態が存在しているものの、エージェント（AI）が意思決定を行う状態は常に「現在の局面」という 1 つだけ であるため、「状態が1つだけ」である多腕バンディット問題とまったく同じ構造として扱うことができます。

状態遷移関数

行動を行っても状態は一切変化しないため、状態がどう移り変わるかを表す状態遷移関数 $f$ は下記のようになります3。

$$\text{行動空間 } \mathcal{A} \text{ に属するすべての行動 } a \text{ に対して、}f(s, a) = s$$

報酬関数

これまでの記事で扱ってきた強化学習の題材では、特定の状態で特定の行動をとると、常に同じ即時報酬が得られるという「決定論的」なものでした。そのため、状態 $s$ で行動 $a$ を選択した場合に得られる即時報酬を表す報酬関数を $r(s, a)$ というシンプルな関数で表すことができました。

一方、多腕バンディット問題ではスロットマシンのレバーを引いた時に得られる即時報酬（コイン）の数は、確率によってその都度変化する「確率的」なものです。そのため、多腕バンディット問題の報酬関数は「確率質量関数」を使って表します。

各スロットマシンでコインが 1 枚当たる確率（probability）を $p_i$4 と表記すると、報酬関数は下記のようになります。なお、報酬関数を表す確率の記号は、以前の記事に倣って報酬（reward）の頭文字である「R」を添字に付けて $P_{R}$ と表記しました。

式 意味
$P_R(1 \mid a_i) = p_i$ $i$ 番のスロットマシン（行動 $a_{i}$）を選択した際に、コインが 1 枚得られる確率
$P_R(0 \mid a_i) = 1 - p_i$ $i$ 番のスロットマシン（行動 $a_{i}$）を選択した際に、コインが得られない確率

エピソードの初期状態と終了条件

多腕バンディット問題では、状態は $s$ の一つしか存在せず、行動しても一切変化しません。そのため、エピソードのスタート地点となる 初期状態は常に $s$ です。

また、多腕バンディット問題は、「あらかじめ決められた回数だけレバーを引く」というルールであるため、その 指定された回数だけ行動を行うことがエピソードの終了条件 になります。以後は、このレバーを引ける総回数を $m$ と表記することにします

目的関数

「1 手先の分配問題」の目的は、「真の勝率が高い有望な手ほど、プレイアウトを多く割り当てる（えこひいきする）」というものでした。「多腕バンディット問題」ではこの「真の勝率」が「スロットマシンでコインが当たる確率」に対応します。

従って、「1 手先の分配問題」の目的を「バンディット問題」の設定に置き換えて説明すると「コインが当たる確率が高いスロットマシンほど、多くの回数のレバーを引く」ということになります。

当然ですが、コインが当たる確率が高いスロットマシンを多く選べば選ぶほど、全体で得られるコインの総数が多くなることが期待できます。つまり、「1 手先の分配問題」の目的は、バンディット問題の本来の目的である「得られるコインの総数を最大化する」に完全に一致します。

得られたコインの総数は、エピソードを通じて手に入れた即時報酬の合計である「累積報酬」そのものです。このことから、多腕バンディット問題の目的関数は、まさに「累積報酬の期待値（平均してどれくらいコインが稼げるか）」であることがわかります。

上記をまとめると、多腕バンディット問題とは「スロットマシンのレバーを合計 $m$ 回引くという条件のもとで、得られる累積報酬の期待値が最大となるような、スロットマシンの回数の割り当て方を求める」という最適化問題であることがわかります。

以後は、「1 手先の分配問題」を「バンディット問題」に置き換えて説明を行います。

多腕バンディット問題の専門書などでは、目的関数として一般的に「リグレット（後悔）」と呼ばれる関数が用いられ、「リグレットを最小化する問題」として定式化されます。

リグレットの具体的な仕組みについては今後の記事で詳しく説明しますが、「リグレットを最小化すること」と、今回説明した「累積報酬の期待値を最大化すること」は数学的にまったく同じ意味を持ちます。本記事では、リグレットよりも「得られるコインの期待値を最大にする」と言ったほうが直感的に分かりやすいと考えたため、目的関数を「累積報酬の期待値」として説明を進めることにしました。

多腕バンディット問題の特徴

ここまで説明してきた状態遷移関数と報酬関数は、いずれも現在の状態のみに依存するというマルコフ性を持ちます。従って、多腕バンディット問題はマルコフ決定過程です。

多腕バンディット問題が、一般的な強化学習と大きく異なる最大のポイントは、「状態がたった 1 つしかないマルコフ決定過程」 であることです。

通常の強化学習では、「今の行動が未来の状態を複雑に変えてしまう」ため、先々の展開まで計算しなければならず、これが難易度を跳ね上げる要因になっていました。しかしバンディット問題では、そのような複雑な「状態遷移」の先読みを一切考える必要がありません。未来の心配をせず、純粋に「目の前の選択肢の確率」だけに集中できるため、問題設定がシンプルで扱いやすく、強化学習の入門用の題材として世界中でよく取り上げられます。

また、問題が極めてシンプルなため、この後に行うシミュレーション用のプログラムを簡単に作成でき、かつその計算を非常に高速に実行できるという大きなメリットもあります。

スロットマシンの標準偏差（参考）

この節の内容は前回の記事の補足です。

前回の記事では説明を簡単にするために、すべての 1 手目の局面の標準偏差を 1 と仮定して計算を行いましたが、実際のゲームやスロットマシンでは、標準偏差がぴったり 1 になることはありません。

ここでは、スロットマシンの標準偏差（= 1 手目の局面の本来の標準偏差）が具体的にどのような値になるかについて説明します。

多腕バンディット問題では、それぞれのスロットマシンが特定の確率で「コインを 1 枚出す（当たり = 1）」か「出さない（ハズレ = 0）」のどちらかの振る舞いをします。このように 結果が 2 択になる確率分布を、統計学では「ベルヌーイ分布」 と呼びます。参考までに下記に Wikipedia のベルヌーイ分布のリンクを示します。

コインが当たる確率を $p$、得られたコインの枚数を表す確率変数を $X$ とすると、この分布の期待値、分散、標準偏差は下記の式で求めることができます。

  • 確率質量関数（確率のリスト）：
    $$
    \begin{aligned}
    & P(X=0) = 1 - p \\
    & P(X=1) = p
    \end{aligned}
    $$

  • 期待値（平均値）：
    $$E[X] = 0 \times P(X=0) + 1 \times P(X=1) = p$$

  • 分散（ばらつきの指標）5：
    $$\begin{aligned}
    V[X] & = E[X^2] - E[X]^2 \\
    & = 0^2 \times P(X^2=0^2) + 1^2 \times P(X^2 = 1^2) - p^2 \\
    & = 0^2 \times P(X=0) + 1^2 \times P(X = 1) - p^2 \\
    & = p-p^2
    \end{aligned}
    $$

  • 標準偏差（ブレの幅）：
    $$SD[X] = \sqrt{V[X]} = \sqrt{p-p^2}$$

ここで、上記で求めた分散 $p - p^2$ の平方完成を計算すると下記のようになります。

$$p - p^2 = -(p-0.5)^2 + 0.25$$

この式から分散はコインが当たる確率が $p = 0.5$ の時に最大値 0.25 を取る、下記のグラフで表される上に凸な放物線（左右対称な山形）であることがわかります。

また、このグラフから分散は、確率 $p$ が絶対に当たらない0 または 100 % 当たる 1 に近づくほど小さくなり、完全に 0 または 1 になった時に最小値 0 を取ることがわかります。

参考までに上記の分散のグラフを描画するプログラムを下記に示します。

import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib

X = np.linspace(0, 1, 100)
Y = X - X * X
plt.plot(X, Y)
plt.xlabel("p")
plt.ylabel("V[X]")
plt.show()

分散のルート（平方根）である標準偏差 $SD[X] = \sqrt{p-p^2}$ も全く同じ傾向を示します。下図のグラフのように、$p=0.5$ の時に最大値 $\sqrt{0.25} = 0.5$ を取り、0 または 1 のときに最小値 0 を取ります。

標準偏差のグラフを描画するプログラムは以下の通りです。

Y = np.sqrt(X - X * X)
plt.plot(X, Y)
plt.xlabel("p")
plt.ylabel("SD[X]")
plt.show()

スロットマシンの標準偏差の性質をまとめると下記のようになります。

  • スロットマシンの標準偏差（ブレ幅）は、コインが当たる確率 $p$ よって決まる
  • 確率 $p$ が 0.5 のときに、最大値の 0.5 になる
  • 確率 $p$ が 0 または 1 に近づくほど小さくなり、完全に 0 または 1 の時に最小値である 0 となる

コインが当たる確率が 1（100 % 当たる）または 0（100 % はずれる）の場合は、レバーを引く前から結果が完全に予測できるため、平均からのブレ（不確実性）が 0 になるのは直観的にも納得がいくはずです。逆に確率が 0.5 の時が一番どちらが出るかがわからなくなるため、数学的にも標準偏差が最大になります。

「1 手先の分配問題」で引き分けが存在する場合を「多腕バンディット問題」に置き換えると、スロットマシンから得られるコインの枚数の種類が「1 枚（勝ち）」、「0.5 枚（引き分け）」、「0 枚（負け）」の 3 種類になります。

この場合の期待値や標準偏差は、コインが $x$ 枚得られる確率を表す $P(X=x)$ を用いた下記の式から計算する必要があります。

$$E[X] = 0 \times P(X=0) + 0.5 \times P(X=0.5) + 1 \times P(X=1)$$

$$E[X^2] = 0^2 \times P(X^2=0^2) + 0.5^2 \times P(X^2=0.5^2) + 1^2 \times P(X^2=1^2)$$

$$SD[X] = \sqrt{V[X]} = \sqrt{E[X^2] - E[X]^2}$$

2 択（勝ちと負けだけ）の時とは異なり、引き分けがある場合は「期待値」だけから標準偏差を一意に決めることはできません。

たとえば、100 % の確率で常に引き分けに相当する「0.5 枚」を出すスロットマシンがあるとします。このスロットマシンの期待値（平均値）は 0.5 ですが、毎回絶対に 0.5 枚しか出ず、結果に一切の「ばらつき」がないため、標準偏差を計算すると 0 になります。このように、同じ期待値が 0.5 であっても、五分五分で 1 枚か 0 枚が出るスロットマシンの標準偏差（0.5）とは全く異なる性質を持つことになります。

多腕バンディット問題を扱うクラスの定義

多腕バンディット問題のシミュレーションを行うために、多腕バンデッド問題（multi-armed bandit problem）を扱う MAB というクラスを定義 することにします。

クラスの設計

多腕バンディット問題では、それぞれ異なる「当たり確率」を持つ複数のスロットマシンを扱う必要があります。

そこで、それぞれのスロットマシンでコインが当たる確率を list で表現し、MAB クラスの p という属性に代入することにします。また、スロットマシンの台数を p から計算して num という属性に代入することにします。

さらに、スロットマシンのレバーを引くという一連の処理は、スロットマシンで「遊ぶ（play）」とぃう意味を込めて play という名前のメソッドとして実装することにします。

属性（データ）の一覧

下記は、MAB クラスが持つ属性の一覧です。

属性名 意味
num スロットマシンの台数（int 型のデータ）
p それぞれのスロットマシンのコインが当たる確率を格納した list

メソッドの一覧

下記は、MAB クラスに実装するメソッドの一覧です。

__init__ メソッド（初期化）

  • 処理：MAB クラスからインスタンス（オブジェクト）を作るときに自動で呼び出され、スロットマシンの設定を属性に記録する
  • 仮引数：
    • p：それぞれのスロットマシンのコインが当たる確率を表す list
  • 返り値：なし

play メソッド（レバーを引く）

  • 処理：指定された番号のスロットマシンのレバーを引き、確率に応じて得られたコインの枚数（1 または 0）を計算して返す
  • 仮引数：
    • arm：レバー（arm）を引くスロットマシンの番号（リストのインデックスに対応する 0 〜 num - 1 の整数）
  • 返り値：得られたコインの枚数（1 または 0）

MAB クラスの定義

下記は MAB クラスを定義するプログラムです。

  • 3 行目：スロットマシンの台数は、それぞれのスロットマシンの確率が代入された list の要素の数なので、組み込み関数 len を使うことで、台数を自動的に計算して num 属性に記録することができる
  • 7 行目：play メソッドでは、np.random.rand を呼び出して、0 以上 1 未満の一様乱数を発生させ、その値が arm 番のスロットマシンでコインが当たる確率 self.p[arm] 未満であるかを比較する。この比較の結果は bool 型の False（ハズレ） または True（当たり）になるが、組み込み関数 int を用いることで False が 0 に、 True が 1 に変換されるので、その値を返り値として返す
1  class MAB:
2      def __init__(self, p):
3          self.num = len(p)
4          self.p = p
5  
6      def play(self, arm):
7          return int(np.random.rand() < self.p[arm])
行番号のないプログラム 
class MAB:
    def __init__(self, p):
        self.num = len(p)
        self.p = p

    def play(self, arm):
        return int(np.random.rand() < self.p[arm])

np.random.rand の詳細については、下記のリンク先を参照して下さい。

MAB クラスの使用例

作成した MAB クラスが本当に正しく動作することを、実際にスロットマシンを作って確認することにします。

下記は、コインが当たる確率がそれぞれ 0.2（20 %）、0.5（50 %）、0.8（80 %）に設定された 3 つのスロットマシンを用意し、それぞれのレバーを 10 回ずつ引いて結果を表示するプログラムです。

p = [0.2, 0.5, 0.8]
mab = MAB(p = p)

for arm in range(3):
    print(f"コインの獲得確率が {p[arm]} のスロットマシン")
    for i in range(10):
        print(mab.play(arm))

実行結果（乱数を用いているため下記の結果は毎回変わります）

コインの獲得確率が 0.2 のスロットマシン
1
0
1
0
0
0
1
0
0
0
コインの獲得確率が 0.5 のスロットマシン
1
1
0
1
0
0
1
0
0
1
コインの獲得確率が 0.8 のスロットマシン
1
1
1
1
1
0
1
1
1
1

たった 10 回という少ない回数の実験ですが、それぞれのマシンの性格（確率）が下記のようにしっかりと結果に表れていることが確認できます。

  • 確率 0.2 の台：ほとんどがハズレの 0 で、たまに 1（当たり）が出る（上記の場合は 10 回中 3 回当たっている）
  • 確率 0.5 の台：1 と 0 半々で、バランスよく出ている（上記の場合は 10 回中 5 回当たっている）
  • 確率 0.8 の台：ほとんどが当たりの 1 で、たまに 0（ハズレ）が出る（上記の場合は 10 回中 9 回当たっている）

プレイアウトの処理との比較

次に、新しく作った MAB クラスによるシミュレーションが、〇× ゲームの 原始モンテカルロ法と同じ計算を、どれほど高速に実行できるか を実際に確認することにします。

比較実験として、まずは 〇× ゲームのルール通りにプレイアウトの処理を行う、従来の原始モンテカルロ法のシミュレーションを行います。実験の設定は以下の通りです。

  • ゲーム開始時の局面をスタート地点とする
  • それぞれの合法手（次の 1 手）を着手した局面に対して、それぞれ 10,000 回のプレイアウトを行い、その勝率を計算する

原始モンテカルロ法のシミュレーション

下記は、従来の Marubatsu クラスを利用して、実際に合計 90,000 回（9マス × 10,000回）のプレイアウトを行うプログラムです。なお、mb.playout() は、その局面からゲームが決着するまでランダムに打ち進めた最終結果を返します。

  • 4 行目：ゲーム開始時の局面を表す Marubatsu クラスのインスタンスを作成する
  • 5 行目：ゲーム開始時の局面の合法手を計算する
  • 6 行目：各局面でプレイアウトを行った際の勝利数を記録する変数を、デフォルト値を 0 とした defaultdict で初期化する
  • 7 行目：各局面に対して行うプレイアウトの回数を表す変数 pnum を 10,000 で初期化する
  • 9 ~ 17 行目：各合法手に対して 10,000 回のプレイアウトを行う繰り返し処理を行う
  • 10 ~ 16 行目：合法手を着手した局面に対して 10,000 回のプレイアウト行い、勝利した回数を wincount に記録する。なお、16 行目で引き分け（mb.DRAW）の場合に 0.5 を加算しているのは、引き分けを 0.5 勝として計算するためである
  • 17 行目：10 行目で行った合法手の着手を unmove メソッドで取り消してゲーム開始時の局面に戻す
  • 19、20 行目：それぞれの合法手に対する勝率を計算して表示する。なお、mb.board.move_to_xy(move) は move を (x, y) の座標に変換する処理である
 1  from marubatsu import Marubatsu
 2  from collections import defaultdict
 3  
 4  mb = Marubatsu()
 5  legal_moves = mb.calc_legal_moves()
 6  wincount = defaultdict(int)
 7  pnum = 10000
 8  
 9  for move in legal_moves:
10      mb.move(move)
11      for _ in range(pnum):
12          result = mb.playout()
13          if result == mb.CIRCLE:
14              wincount[move] += 1
15          elif result == mb.DRAW:
16              wincount[move] += 0.5
17      mb.unmove()
18  
19  for move in legal_moves:
20      print(f"{mb.board.move_to_xy(move)} win ratio = {wincount[move]/pnum:.3f}")
行番号のないプログラム 
from marubatsu import Marubatsu
from collections import defaultdict

mb = Marubatsu()
legal_moves = mb.calc_legal_moves()
wincount = defaultdict(int)
pnum = 10000

for move in legal_moves:
    mb.move(move)
    for _ in range(pnum):
        result = mb.playout()
        if result == mb.CIRCLE:
            wincount[move] += 1
        elif result == mb.DRAW:
            wincount[move] += 0.5
    mb.unmove()
    
for move in legal_moves:
    print(f"{mb.board.move_to_xy(move)} win ratio = {wincount[move]/pnum:.3f}")

実行結果

(0, 0) win ratio = 0.674
(0, 1) win ratio = 0.593
(0, 2) win ratio = 0.670
(1, 0) win ratio = 0.601
(1, 1) win ratio = 0.753
(1, 2) win ratio = 0.599
(2, 0) win ratio = 0.667
(2, 1) win ratio = 0.603
(2, 2) win ratio = 0.672

上記の実行結果（10,000 回の平均値）と、下図の以前の記事でのゲーム木解析によって求めておいた左端の一列の各局面の「真の勝率（累積報酬の期待値）」を見比べてみてください。数値がほぼ完全に一致していることがわかります。

従ってこの実行結果から、大数の法則によって「プレイアウトをたくさん繰り返せば理論上の期待値に近づ」く、という原始モンテカルロ法の正しさが改めて確認できました。

処理時間の計測

続いて、上記のプログラムから初期設定を行う 4、5 行目と、結果を表示する 19、20 行目のプログラムを除いた「純粋なプレイアウトのループ処理」の処理時間を下記のプログラムで計測します。なお、プレイアウトの回数が「1 万回」のままだと計測に時間がかかりすぎてしまうため、ここではプレイアウトの回数を 100 回に減らして計測を行いました。

%%timeit

pnum = 100
for move in legal_moves:
    mb.move(move)
    for _ in range(pnum):
        result = mb.playout()
        if result == mb.CIRCLE:
            wincount[move] += 1
        elif result == mb.DRAW:
            wincount[move] += 0.5
    mb.unmove()

実行結果

11.5 ms ± 512 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

実行結果から、筆者のパソコンではこの処理を約 11.5 ms（ミリ秒）で行うことができることが確認できました。

「11.5 ミリ秒なら一瞬で終わるのではないか」と思う人がいるかもしれませんが、これはプレイアウトの回数を「100 回」にまで極端に減らしたときの話です。もし本来の目的である「10,000回」のプレイアウトを行おうとすると、単純計算でこの 100 倍、つまり 約 1.15 秒以上 の待ち時間が発生することになります。

多腕バンディット問題のシミュレーション

次に、上記で行った原始モンテカルロ法とまったく同じ計算を、今回作成した MAB クラス（多腕バンディット問題）に置き換えて実行してみることにします。

シミュレーションの設定は以下の通りです。

  • スロットマシンの台数は、合法手の数と同じ 9 台とする
  • それぞれのスロットマシンでコインが当たる確率は、ゲーム木解析で求めたそれぞれの合法手の「真の勝率」と同じ値に設定する
  • それぞれのスロットマシンを 10,000 回ずつ選択し、1 回あたりに得られるコインの平均枚数（勝率のシミュレーション値）を計算する。

下記は上記のシミュレーションを行うプログラムです。3、4 行目の処理は先ほどと同じなので説明は省略します。

  • 1 行目：9 つのスロットマシンに、それぞれの合法手を着手した局面の真の勝率を設定した MAB クラスのインスタンスを作成する
  • 5 ~ 7 行目：9 つのスロットマシン（arm）に対して mab.play(arm) で 10,000 回ずつスロットマシンのレバーを引いて、その結果を wincount に加算する
  • 9、10 行目：それぞれのスロットマシンに対する勝率を計算して表示する
 1  mab = MAB(p=[0.671, 0.600, 0.671, 0.600, 0.750, 0.600, 0.671, 0.600, 0.671])
 2  
 3  wincount = defaultdict(int)
 4  pnum = 10000
 5  for arm in range(9):
 6      for _ in range(pnum):
 7          wincount[arm] += mab.play(arm)
 8  
 9  for arm in range(9):
10      print(f"{arm} win ratio = {wincount[arm]/pnum:.3f}")
行番号のないプログラム 
mab = MAB(p=[0.671, 0.600, 0.671, 0.600, 0.750, 0.600, 0.671, 0.600, 0.671])

wincount = defaultdict(int)
pnum = 10000
for arm in range(9):
    for _ in range(pnum):
        wincount[arm] += mab.play(arm)

for arm in range(9):
    print(f"{arm} win ratio = {wincount[arm]/pnum:.3f}")

実行結果

0 win ratio = 0.682
1 win ratio = 0.600
2 win ratio = 0.662
3 win ratio = 0.603
4 win ratio = 0.752
5 win ratio = 0.598
6 win ratio = 0.668
7 win ratio = 0.598
8 win ratio = 0.668

下記は先ほどの「原始モンテカルロ法での実験結果」です。上記の実行結果の先頭のスロットマシンの番号と下記の盤面の座標（マスの位置）が上から順番に順番に対応します。両者を見比べて、ほぼ同じ勝率のデータが得られていることが確認して下さい。

(0, 0) win ratio = 0.674
(0, 1) win ratio = 0.593
(0, 2) win ratio = 0.670
(1, 0) win ratio = 0.601
(1, 1) win ratio = 0.753
(1, 2) win ratio = 0.599
(2, 0) win ratio = 0.667
(2, 1) win ratio = 0.603
(2, 2) win ratio = 0.672

処理時間の計測

次に、多腕バンディット問題に置き換えたことで、どれくらい処理速度が上がったかを下記のプログラムで計測してみることにします。条件を揃えるため、こちらもレバーを引く回数 pnum を 100 回 に減らして計測を行うことにします。。

%%timeit

wincount = defaultdict(int)
pnum = 100
for arm in range(9):
    for _ in range(pnum):
        wincount[arm] += mab.play(arm)

実行結果

508 μs ± 10 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

実行結果から、筆者のパソコンではこの処理をたったの約 500 μs（マイクロ秒6）= 0.5 ms で行うことができることが確認できました。先ほどの愚直にプレイアウトを行った場合の処理時間は 11.5 ms でした。つまり、「1 手先の分配問題」を「多腕バンディット問題」に抽象化したことで、処理時間が約 23 倍も高速化 されたことになります。

また、本来の目的である「10,000回」のシミュレーションを行う場合でも、単純計算でこの 100 倍の 約 0.05 秒、つまり人間にとっては「完全に一瞬」で計算を終えることができます。

以上の実験から、〇× ゲームの複雑なルールを削ぎ落としてスロットマシンの問題（MAB）に置き換えるアプローチが、アルゴリズムの検証効率を 20 倍以上も劇的に跳ね上げる ことが実証できました。

上記の MAB クラスを用いたシミュレーションは引き分けを考慮していないため、厳密には実際のプレイアウトと 100 % 同一の確率分布を再現しているわけではありません。具体的には、先程の「スロットマシンの標準偏差（参考）」の節の最後で説明したように、標準偏差（ブレの度合い）に若干の違いがあります。

しかし、引き分け（0.5枚のコイン）を考慮するように MAB クラスを修正しても、「複雑なゲームの処理をスキップして乱数だけで判定する」という仕組みは変わらないため、処理時間が圧倒的に高速になるという大きな利点はそのまま維持されます。

今回の記事のまとめ

今回の記事では、モンテカルロ木探索の効率化を目指すために、下記の説明を行いました。

  • 問題の抽象化：「1 手先（深さ 1）の局面だけに、限られたプレイアウトの総数をどう分配するか」という課題を、「多腕バンディット問題」というシンプルな問題に完全に置き換えられることを説明した

  • 処理の高速化：複雑な処理（プレイアウト）を、スロットマシン（乱数）の処理に置き換えた結果、シミュレーションの計算速度を 20 倍以上高速化できることを実証した

次回の記事からは、実装した MAB クラスを利用して、「多腕バンディット問題」の一番の課題である「探索」と「活用」のトレードオフを賢く制御するアルゴリズム順番に紹介していくことにします。

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

MAB クラスは ap.py に保存することにします。

リンク 説明
marubatsu.ipynb 本記事で入力して実行した JupyterLab のファイル
ai_new.py 本記事で更新した ai_new.py

次回の記事

  1. 特定の範囲の数値が等確率で発生する乱数のことです ↩

  2. 状態が 1 つしか存在せず、他の状態と区別する必要がないため添字は省略しました ↩

  3. 全称記号 $\forall$ を用いると $\forall a \in \mathcal{A}, f(s, a) = s$ となります ↩

  4. 多腕バンディット問題ではプレイアウトは行わないため、この $p$ はプレイアウトの回数ではなく、コインが当たる確率（probability）を表します ↩

  5. 得られるコインの枚数を表す $X$ は $0$ か $1$ のどちらかの値しかとりません。そのため、$X=0$ の場合は $X^2=0^2$ となり、$X=1$ の場合は $X^2=1^2$ となります。したがって、$P(X^2=0) = P(X=0)$ および $P(X^2=1) = P(X=1)$ が成り立ちます ↩

  6. マイクロ秒は 1 秒の 100 万分の一、ミリ秒の 1,000 分の一です ↩

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?