メインコンテンツまでスキップ

モンテカルロ木探索

モンテカルロ木探索とは​

原始モンテカルロ法では完全にランダムに手を選択していた。そのため、自分にとって良い手も相手にとって良い手も等しい確率で選択されるため、勝率をあげることができなかった。 この問題を改善したものがモンテカルロ木探索である。モンテカルロ木探索では、評価関数に基づいて探索する手を選択し、その後はランダムで手を選択する。これにより、強い手はより探索が行われ、弱い手はあまり探索を行わないようになり、より良い手を選択できる様になる。

アルゴリズム​

モンテカルロ木探索の評価関数としてよく用いられるのがUCT(Upper Confidence Bound for Trees)と呼ばれる評価関数で、探索された各ノードの価値と探索回数の組み合わせに基づいて、ノードの選好度を計算する関数である。

UCT(n)=Q(n)N(n)+Cln⁡N(p)N(n)Q(n):ノード n の合計報酬（例: 勝利の回数）N(n):ノード n が訪れられた回数N(p):全試行回数C:調整パラメータで、探索と活用のバランスを調整する \begin{align*} UCT(n) &= \frac{Q(n)}{N(n)} + C \sqrt{\frac{\ln{N(p)}}{N(n)}} \\ Q(n) &\text{:ノード $n$ の合計報酬（例: 勝利の回数）} \\ N(n) &\text{:ノード $n$ が訪れられた回数} \\ N(p) &\text{:全試行回数} \\ C &\text{:調整パラメータで、探索と活用のバランスを調整する} \\ \end{align*}

++記号で分けると左側は勝率を表し、勝利することが多い場合はこちらの値が大きくなる。右側は試行回数で決める値になっており、試行回数が多いほど小さく、少ないほど大きな値を取るようになる。勝率が高いかあまり探索されていないノードがより優先的に選択される評価関数となっている。また、Cは慣習的に2\sqrt{2}とすることが多い。

以下の盤面を考える。次に白が置ける場所は6箇所ある。

モンテカルロ木探索

一番初めは訪れた回数(N(n)N_{(n)})が0なので評価値を最大にする。ここでは最大値を10910^9とする。

番号訪れた回数勝利数UCT値
1◯\textcircled{\scriptsize 1}0010910^9
2◯\textcircled{\scriptsize 2}0010910^9
3◯\textcircled{\scriptsize 3}0010910^9
4◯\textcircled{\scriptsize 4}0010910^9
5◯\textcircled{\scriptsize 5}0010910^9
6◯\textcircled{\scriptsize 6}0010910^9

この中で一番大きいUCT値を持つのは1◯\textcircled{\scriptsize 1}なので、1番の手を選択する。その後ゲームが終了するまでお互いにランダムな手を選択してゲームを終了させる。

モンテカルロ木探索2

今回はゲーム終了までシミュレーションすると計算時間がかかるので20手打ち合い、その時点での勝敗を記録する。

白を置いた手番での自分のコマの数が多い場合は勝利とみなし、Q(n)Q_{(n)}に加算する。今回の場合は1◯\textcircled{\scriptsize 1}を選択した後に白が勝利したとすると、木のUCT値は以下の様に変化する。

番号訪れた回数勝利数UCT値
1◯\textcircled{\scriptsize 1}111/1+2×ln⁡11=11/1 + \sqrt{2} \times \sqrt{\frac{\ln{1}}{1}} = 1
2◯\textcircled{\scriptsize 2}0010910^9
3◯\textcircled{\scriptsize 3}0010910^9
4◯\textcircled{\scriptsize 4}0010910^9
5◯\textcircled{\scriptsize 5}0010910^9
6◯\textcircled{\scriptsize 6}0010910^9

この流れを1回として繰り返していく。閾値を設定し、閾値を超えた回数探索した木から子ノードの拡張を行っていく。今回は閾値を10回とし、上記の選択+シミュレーションを繰り返していくと閾値を超える手が登場する。

番号訪れた回数勝利数UCT値
1◯\textcircled{\scriptsize 1}1099/10+2×ln⁡4210≈1.76469/10 + \sqrt{2} \times \sqrt{\frac{\ln{42}}{10}} \thickapprox 1.7646
2◯\textcircled{\scriptsize 2}411/4+2×ln⁡424≈1.61701/4 + \sqrt{2} \times \sqrt{\frac{\ln{42}}{4}} \thickapprox 1.6170
3◯\textcircled{\scriptsize 3}511/5+2×ln⁡425≈1.42271/5 + \sqrt{2} \times \sqrt{\frac{\ln{42}}{5}} \thickapprox 1.4227
4◯\textcircled{\scriptsize 4}966/9+2×ln⁡429≈1.57806/9 + \sqrt{2} \times \sqrt{\frac{\ln{42}}{9}} \thickapprox 1.5780
5◯\textcircled{\scriptsize 5}744/7+2×ln⁡427≈1.60484/7 + \sqrt{2} \times \sqrt{\frac{\ln{42}}{7}} \thickapprox 1.6048
6◯\textcircled{\scriptsize 6}744/7+2×ln⁡427≈1.60484/7 + \sqrt{2} \times \sqrt{\frac{\ln{42}}{7}} \thickapprox 1.6048

1◯\textcircled{\scriptsize 1}が10回を超えたので木を展開する。展開すると次のような木を構成する。木を展開すると次の局面の開始が変わるので、評価する際の勝ち, 負けの判断が反転することになる。

1番目の番号2番目の番号訪れた回数勝利数UCT値
1◯\textcircled{\scriptsize 1}10910910^9
1◯\textcircled{\scriptsize 1}1◯\textcircled{\scriptsize 1}0010910^9
1◯\textcircled{\scriptsize 1}2◯\textcircled{\scriptsize 2}0010910^9
1◯\textcircled{\scriptsize 1}3◯\textcircled{\scriptsize 3}0010910^9
1◯\textcircled{\scriptsize 1}4◯\textcircled{\scriptsize 4}0010910^9
1◯\textcircled{\scriptsize 1}5◯\textcircled{\scriptsize 5}0010910^9
2◯\textcircled{\scriptsize 2}411/4+2×ln⁡424≈1.61701/4 + \sqrt{2} \times \sqrt{\frac{\ln{42}}{4}} \thickapprox 1.6170
3◯\textcircled{\scriptsize 3}511/5+2×ln⁡425≈1.42271/5 + \sqrt{2} \times \sqrt{\frac{\ln{42}}{5}} \thickapprox 1.4227
4◯\textcircled{\scriptsize 4}966/9+2×ln⁡429≈1.57806/9 + \sqrt{2} \times \sqrt{\frac{\ln{42}}{9}} \thickapprox 1.5780
5◯\textcircled{\scriptsize 5}744/7+2×ln⁡427≈1.60484/7 + \sqrt{2} \times \sqrt{\frac{\ln{42}}{7}} \thickapprox 1.6048
6◯\textcircled{\scriptsize 6}744/7+2×ln⁡427≈1.60484/7 + \sqrt{2} \times \sqrt{\frac{\ln{42}}{7}} \thickapprox 1.6048

モンテカルロ木探索3

1番目の1◯\textcircled{\scriptsize 1}のUCT値は展開した2番目の番号の中の最大の値を採用する。そのため1番目の1◯\textcircled{\scriptsize 1}のUCT値は10910^9となる。そのため、5回分は1◯\textcircled{\scriptsize 1} - 1◯\textcircled{\scriptsize 1} ∼\sim 5◯\textcircled{\scriptsize 5} が選択される。

1番目の番号2番目の番号訪れた回数勝利数UCT値
1◯\textcircled{\scriptsize 1}15113.7749 (1◯\textcircled{\scriptsize 1}-2◯\textcircled{\scriptsize 2})
1◯\textcircled{\scriptsize 1}1◯\textcircled{\scriptsize 1}100/1+2×ln⁡471≈2.77490/1 + \sqrt{2} \times \sqrt{\frac{\ln{47}}{1}} \thickapprox 2.7749
1◯\textcircled{\scriptsize 1}2◯\textcircled{\scriptsize 2}111/1+2×ln⁡471≈3.77491/1 + \sqrt{2} \times \sqrt{\frac{\ln{47}}{1}} \thickapprox 3.7749
1◯\textcircled{\scriptsize 1}3◯\textcircled{\scriptsize 3}111/1+2×ln⁡471≈3.77491/1 + \sqrt{2} \times \sqrt{\frac{\ln{47}}{1}} \thickapprox 3.7749
1◯\textcircled{\scriptsize 1}4◯\textcircled{\scriptsize 4}100/1+2×ln⁡471≈2.77490/1 + \sqrt{2} \times \sqrt{\frac{\ln{47}}{1}} \thickapprox 2.7749
1◯\textcircled{\scriptsize 1}5◯\textcircled{\scriptsize 5}100/1+2×ln⁡471≈2.77490/1 + \sqrt{2} \times \sqrt{\frac{\ln{47}}{1}} \thickapprox 2.7749
2◯\textcircled{\scriptsize 2}411/4+2×ln⁡474≈1.63741/4 + \sqrt{2} \times \sqrt{\frac{\ln{47}}{4}} \thickapprox 1.6374
3◯\textcircled{\scriptsize 3}511/5+2×ln⁡475≈1.44091/5 + \sqrt{2} \times \sqrt{\frac{\ln{47}}{5}} \thickapprox 1.4409
4◯\textcircled{\scriptsize 4}966/9+2×ln⁡479≈1.59166/9 + \sqrt{2} \times \sqrt{\frac{\ln{47}}{9}} \thickapprox 1.5916
5◯\textcircled{\scriptsize 5}744/7+2×ln⁡477≈1.62024/7 + \sqrt{2} \times \sqrt{\frac{\ln{47}}{7}} \thickapprox 1.6202
6◯\textcircled{\scriptsize 6}744/7+2×ln⁡477≈1.62024/7 + \sqrt{2} \times \sqrt{\frac{\ln{47}}{7}} \thickapprox 1.6202

このように閾値を超えた木は展開させ、木を深くしていく。これにより、有効な手の調査回数を増加させ、不利な手の調査回数を下げることができる。 この様にシミュレーション, バックプロパゲーション, 拡張, 選択の4つステップが存在し、これを繰り返し行っていく。

  • 選択 (Selection): 現在の木構造を使用して、各ノードに対して適切な評価値を計算し、最も有望な手を選択する。
  • 拡張 (Expansion): 選択したノードに子ノードを生成し、新しい手を追加する。これにより、未知の領域を探索する機会が増える。
  • シミュレーション (Simulation): 新しく追加された子ノードや既存のノードに対して、ランダムな手を選択してゲームをシミュレートする。
  • バックプロパゲーション (Backpropagation): シミュレーションの結果を使用して、選択されたノードの評価値（勝率など）を更新する。これは、親ノードからルートノードまで逆向きに行う。(今回の例では勝利数・訪れた回数を変化させている)

探索を終了する条件は様々であり、一定回数探索が行われた場合に終了する場合や一定時間が経過したら終了とする等存在する。 探索を終了した後に、最終的に自分が選択する手は深さ1にあるノードの中で一番訪れた回数が多いもの=一番探索が行われた=一番有利だろう手を選択する。

ランダム 選択とモンテカルロ木探索(深さ20, 最大探索時間100ms, 最大探索回数200回, 閾値20, 2\sqrt{2}の調整パラメータ)で 100 回の対戦結果は以下のとなった

アルゴリズム勝利数
モンテカルロ木探索94
ランダム5

でランダム選択に勝率94%であったが、探索時間と回数を

ランダム 選択とモンテカルロ木探索(深さ20, 最大探索増やすと時間1000ms, 最大探索回数2000回, 閾値20, 2\sqrt{2}の調整パラメータ)で 100 回の対戦結果は

アルゴリズム勝利数
モンテカルロ木探索100
ランダム0

でランダム選択に勝率100%を記録した。

原始モンテカルロと同じ条件でMiniMax 法(深さ 2 まで)とモンテカルロ木探索(深さ20, 最大探索時間100ms, 最大探索回数200回, 閾値20, 2\sqrt{2}の調整パラメータ)で 100 回の対戦結果は以下のとなった

アルゴリズム勝利数
モンテカルロ木探索32
MiniMax67

となり、原始モンテカルロ法の時よりも勝率が上昇していることがわかる。

原始モンテカルロ(深さ20, 探索回数200回)とモンテカルロ木探索(深さ20, 最大探索時間100ms, 最大探索回数200回, 閾値20, 2\sqrt{2}の調整パラメータ)で 100 回の対戦結果は以下のとなった

アルゴリズム勝利数
モンテカルロ木探索63
原始モンテカルロ34

コード​

monte_carlo_tree_search_action​

反復深化を導入し、一定時間が経過した場合は探索を停止し、時間内で一番良い手を選択する様にしている。

monte_carlo_tree_search_action.py
from lib.evaluation import *
from .action import Action
from lib.othello import Othello, GameState
import sys
from pathlib import Path
import random
import time
import math
sys.path.append(str(Path(__file__).parent.parent.parent))


class Node:
    # モンテカルロ木を構築するためのClass
    def __init__(self, othello: Othello, _id: int, action: tuple[int, int] | None = None, parent=None):
        # この木の行動結果
        self.othello = othello
        # この木の行動
        self.action = action
        # この木で行動したPlayer
        self.id = _id
        # 親ノード
        self.parent = parent
        # 子ノード
        self.children = []
        # この木を選択した回数
        self.visits = 0
        # この木の価値 (勝利: 1, 引き分け: 0.5, 負け: 0)
        self.value = 0

    def build_tree(self):
        # 木に子ノードを展開する
        # 木にはNode.idが行動した後の盤面が記録されている
        for action in self.othello.legal_actions(self.id ^ 1):
            next_othello = self.othello.copy_board()
            next_othello.put(self.id ^ 1, action)
            # 取れるアクション子ノードを作成
            child = Node(next_othello, self.id ^ 1, action, self)
            self.children.append(child)


class MonteCarloTreeSearchAction(Action):

    def __init__(self, id: int, threshold: int = 10, max_time: float = 10000, exploration_weight: float = 1.41421356237, max_count: int = 300, depth: int = -1) -> None:
        super().__init__(id)
        # 計算する最大時間 (反復深化)
        self.max_time = max_time
        # ハイパーパラメータ c
        # (理論的には)√2が良いとされている
        self.exploration_weight = exploration_weight
        # 探索する深さ
        self.max_depth = depth
        # 木を展開する閾値
        self.threshold = threshold
        # 最大試行回数
        self.max_count = max_count

    def action(self, othello: Othello):
        # 何もできない場合は何もせずに次へ
        if len(othello.legal_actions(self.id)) == 0:
            return None
        # 根を作成
        # 根は相手が盤面を選択して終了しているのでplayer idを変更する
        root = Node(othello, self.id ^ 1, None, None)
        # 初めの子ノードを展開
        root.build_tree()

        end_time = time.time() + self.max_time
        count = 0
        while time.time() < end_time and count < self.max_count:
            node = self.select(root, count)
            result = self.simulate(node.othello.copy_board(), node.id)
            self.back_propagate(node, result)
            if node.visits > self.threshold:
                node.build_tree()
            count += 1
        best_child = self.best_child(root)
        return best_child.action

    def select(self, node: Node, cum_time: int):
        # 子が存在する場合は子ノードのなかで最大のNodeを選定する
        while len(node.children) > 0:
            node = self.best_uct(node, cum_time)
        return node

    def best_uct(self, node: Node, cum_time: int):
        # UCT(Upper Confidence Bound for Trees)による行動選択を行う
        def uct_value(child):
            if child.visits == 0:
                return float('inf')
            # UCT
            # c * sqrt(ln(N) / n) + v / n
            # c : ペナルティ項目
            # N : 累計試行回数
            # n : このNodeの試行回数
            # v : 価値
            return (child.value / child.visits) + self.exploration_weight * (math.sqrt(math.log(cum_time) / child.visits))

        return max(node.children, key=uct_value)

    def simulate(self, othello: Othello, _id: int):
        play_id = _id ^ 1
        depth = 0
        while not othello.is_done() and depth <= self.max_depth:
            actions = othello.legal_actions(play_id)
            if len(actions) == 0:
                play_id ^= 1
                continue
            action = random.choice(actions)
            othello.put(play_id, action)
            play_id ^= 1
            depth += 1

        result = othello.get_count()
        if result[0] < result[1]:
            return 0 if self.id == 0 else 1
        elif result[0] > result[1]:
            return 1 if self.id == 0 else 0
        return 0.5

    def back_propagate(self, node, result):
        while node is not None:
            node.visits += 1
            node.value += result if node.action is not None else 0  # 盤面が存在するものだけ更新
            node = node.parent

    def best_child(self, node: Node) -> Node:
        return max(node.children, key=lambda child: child.visits)

変更​

player​
player.py
class Player():
    def __init__(
        self,
        _id: int,
        board: Othello,
        strategy: str,
        depth=2,
        evaluation: str = "mass_count",
        max_time: int = 1,
        max_count=100,
        threshold: int = 20,
        exploration_weight: float = 1.41421356237
    ) -> None:
        self.id = _id
        self.othello = board
        # 次の手を選択する手法を返る
        match strategy:
            case "random":
                self.strategy = RandomAction(_id)
            case "minimax":
                self.strategy = MiniMaxAction(_id, depth, evaluation)
            case "alpha_beta":
                self.strategy = AlphaBetaAction(_id, depth, evaluation)
            case "iterative_deepening_alpha_beta":
                self.strategy = IterativeDeepeningAlphaBetaAction(
                    _id, depth, evaluation, max_time)
            case "primitive_monte_carlo":
                self.strategy = PrimitiveMonteCarloAction(
                    _id, max_count, max_time, depth)
            case "monte_carlo_tree_search":
                self.strategy = MonteCarloTreeSearchAction(
                    _id, threshold, max_time, exploration_weight, max_count, depth)
            case _:
                self.strategy = RandomAction(_id)
c++だけ​

makefile

# コンパイラとコンパイラオプション
CXX = g++
CXXFLAGS =

OUT_PATH = ./out

# ターゲット: 依存ファイル
othello: $(OUT_PATH)/main.o $(OUT_PATH)/othello.o $(OUT_PATH)/evaluation.o $(OUT_PATH)/action.o $(OUT_PATH)/random_action.o $(OUT_PATH)/mini_max_action.o $(OUT_PATH)/alpha_beta_action.o $(OUT_PATH)/iterative_deepening_alpha_beta_action.o $(OUT_PATH)/primitive_monte_carlo_action.o $(OUT_PATH)/monte_carlo_tree_search_action.o $(OUT_PATH)/player.o
 $(CXX) $(CXXFLAGS) $^ -o othello

# ソースファイルからオブジェクトファイルを生成
$(OUT_PATH)/othello.o: lib/othello.cpp
 $(CXX) $(CXXFLAGS) -c $< -o $@

$(OUT_PATH)/evaluation.o: lib/evaluation.cpp
 $(CXX) $(CXXFLAGS) -c $< -o $@

$(OUT_PATH)/action.o: lib/action/action.cpp
 $(CXX) $(CXXFLAGS) -c $< -o $@

$(OUT_PATH)/random_action.o: lib/action/random_action.cpp
 $(CXX) $(CXXFLAGS) -c $< -o $@

$(OUT_PATH)/mini_max_action.o: lib/action/mini_max_action.cpp
 $(CXX) $(CXXFLAGS) -c $< -o $@

$(OUT_PATH)/alpha_beta_action.o: lib/action/alpha_beta_action.cpp
 $(CXX) $(CXXFLAGS) -c $< -o $@

$(OUT_PATH)/iterative_deepening_alpha_beta_action.o: lib/action/iterative_deepening_alpha_beta_action.cpp
 $(CXX) $(CXXFLAGS) -c $< -o $@

$(OUT_PATH)/primitive_monte_carlo_action.o: lib/action/primitive_monte_carlo_action.cpp
 $(CXX) $(CXXFLAGS) -c $< -o $@

$(OUT_PATH)/monte_carlo_tree_search_action.o: lib/action/monte_carlo_tree_search_action.cpp
 $(CXX) $(CXXFLAGS) -c $< -o $@

$(OUT_PATH)/player.o: lib/player.cpp
 $(CXX) $(CXXFLAGS) -c $< -o $@

$(OUT_PATH)/main.o: main.cpp $(OUT_PATH)
 $(CXX) $(CXXFLAGS) -c $< -o $@

# OUT_PATHディレクトリが存在しない場合に作成する
$(OUT_PATH):
 mkdir -p $(OUT_PATH)


.PHONY: clean

clean:
 rm -f $(OUT_PATH)/*.o

run:
 ./othello

g++:
 g++ main.cpp lib/othello.cpp lib/evaluation.cpp lib/action/action.cpp lib/action/random_action.cpp lib/action/mini_max_action.cpp lib/action/alpha_beta_action.cpp lib/action/iterative_deepening_alpha_beta_action.cpp lib/action/primitive_monte_carlo_action.cpp lib/action/monte_carlo_tree_search_action.cpp lib/player.cpp -o ./othello

action.hpp

enum class Strategy
{
    RANDOM,
    MINIMAX,
    ALPHABETA,
    ITERATIVE_DEEPENING_ALPHA_BETA,
    PRIMITIVE_MONTE_CARLO,
    MONTE_CARLO_TREE_SEARCH,
};