【AlphaZeroを理解する】モンテカルロ法編

概要

囲碁、将棋、チェスなどのボードゲームにおいてルール以外のドメイン知識を利用せずに対戦用AIとしてのState-of-the-art（SOTA）を達成したAlphaZeroを細かく分解しながら理解していこうというシリーズです。今回はAlphaZeroの根底にあるモンテカルロ木探索のさらに基礎となるモンテカルロ法についてまとめていきます。

モンテカルロ法

AlphaZeroの候補手探索のベースになっているのがモンテカルロ木探索で、モンテカルロ木探索が依拠しているのがモンテカルロ法というアルゴリズムです。

モンテカルロ法はシミュレーションや数値計算などを行う際に乱数を用いる手法の総称です。

代表的な例として円周率の近似があります。 辺の長さが1の正方形内にランダムに点を打っていき、正方形内にある半径1の四分円の中に入った点の数を集計します。

四分円の面積は

四分円内にある点の数(n_in) / 正方形内にある点総数(n)

で近似できるので、円周率も

という形で近似できます。 上記のシミュレーションをPythonで実装して視覚化してみると下図のようになります。

▶︎Pythonコード

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

# ランダムな点を生成する回数
n = 1000

# 四分円の内側にある点と外側にある点を格納するリスト
inside = []
outside = []

for i in range(n):
    x = random.random()
    y = random.random()
    # 点が四分円の内側にあるかチェック
    if x**2 + y**2 <= 1:
        inside.append((x, y))
    else:
        outside.append((x, y))

# 点をプロット
inside_x, inside_y = zip(*inside)
outside_x, outside_y = zip(*outside)
plt.scatter(inside_x, inside_y, color='b', label='Inside')
plt.scatter(outside_x, outside_y, color='r', label='Outside')
# 四分円の内側にある点と外側にある点の数と円周率の近似値を表示
plt.title('n = ' + str(n) + ', in = ' + str(len(inside)) + ', out = ' + str(len(outside)) + ', pi = ' + str(4 * len(inside) / n))

# 四分円を描く
theta = np.linspace(0, np.pi/2, 100)
plt.plot(np.cos(theta), np.sin(theta), color='k')
# 1辺の長さが1の正方形を描く
plt.plot([0, 1, 1, 0, 0], [0, 0, 1, 1, 0], color='k')

# グラフの設定
plt.legend()
plt.grid(True)
plt.gca().set_aspect('equal', adjustable='box')
plt.show()

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

円周率は3.172と近似されており概ね正しい値に収束していることがわかります。

このように乱数を用いたサンプリングを数千、数万回と繰り返していくことでシミュレーションや数値計算の解が一定の値に収束していき、サンプリング数が十分な大きさになると近似解が得られます。これがモンテカルロ法の基本的な考え方になります。

次回の記事ではこのモンテカルロ法をゲーム木探索に適用したモンテカルロ木探索についてまとめます。