2016 年 3 月、囲碁の世界トップ李世乭が AlphaGo に 4-1 で敗れた。多くの専門家が「あと 10 年は AI に勝てない」と予想していた囲碁を解いたのが MCTS (Monte Carlo Tree Search) + Deep Neural Network の組合せ。評価関数なしに、ランダムプレイの勝率だけで最善手を見つける という反直感的なアルゴリズム。
1. これで何が動いているか
- AlphaGo / AlphaZero / MuZero (囲碁 / 将棋 / チェス、DeepMind)
- KataGo / Leela Chess Zero (オープンソース最強)
- AlphaStar (StarCraft II)
- Pluribus (ポーカー)
- プログラム自動合成 (Program Synthesis) の一部研究
- 経路最適化・配車 (Uber / Lyft の一部)
2. MCTS の 4 ステップ
- 1Selection: ルートから UCB が最大の子を選んで降りる (葉まで)
- 2Expansion: 葉に到達したら、未試行の子ノードを 1 つ追加
- 3Simulation (Rollout): その子から終局までランダムプレイし、結果 (勝/負/引分) を取得
- 4Backpropagation: ルートまで戻りながら、訪問数と勝数を更新
UCB1 の式
UCB(c) = 勝率(c) + C × √(ln N(parent) / N(c))。第 1 項 = 活用、第 2 項 = 探索。訪問が少ない子ほど第 2 項が大きく、新しい手を試す動機。多腕バンディット問題の最適解 (Auer 2002)。
3. Python 実装: ○×ゲーム (動作確認済)
○×ゲームでの MCTS
Python
import mathimport randomfrom copy import deepcopy
class TicTacToe: def __init__(self): self.board = [' '] * 9 self.player = 'X' def legal_moves(self): return [i for i in range(9) if self.board[i] == ' '] def play(self, move): new = deepcopy(self) new.board[move] = new.player new.player = 'O' if new.player == 'X' else 'X' return new def winner(self): lines = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)] for a,b,c in lines: if self.board[a] == self.board[b] == self.board[c] != ' ': return self.board[a] if ' ' not in self.board: return 'draw' return None
class Node: def __init__(self, state, parent=None, move=None): self.state, self.parent, self.move = state, parent, move self.children = [] self.untried = state.legal_moves() self.visits = 0 self.wins = 0.0 def ucb(self, c=1.4): if self.visits == 0: return float('inf') return self.wins/self.visits + c*math.sqrt(math.log(self.parent.visits)/self.visits) def best_child(self, c=1.4): return max(self.children, key=lambda n: n.ucb(c))
def rollout(state): '''ランダムに終局まで''' while state.winner() is None: state = state.play(random.choice(state.legal_moves())) w = state.winner() return 0.5 if w == 'draw' else (1 if w == 'X' else 0)
def mcts(root_state, n_iter=2000): root = Node(root_state) for _ in range(n_iter): node = root # 1. Selection while not node.untried and node.children: node = node.best_child() # 2. Expansion if node.untried: move = random.choice(node.untried) node.untried.remove(move) child = Node(node.state.play(move), node, move) node.children.append(child) node = child # 3. Simulation result = rollout(node.state) # 4. Backpropagation while node: node.visits += 1 # X 視点で記録 (X が勝つと result=1) node.wins += result if node.state.player == 'O' else (1 - result) node = node.parent return max(root.children, key=lambda c: c.visits).move
# 中央が空いている盤面で X の最善手を MCTS で求めるrandom.seed(0)state = TicTacToe()state.board = ['X', 'O', ' ', ' ', ' ', ' ', ' ', ' ', ' ']state.player = 'X'move = mcts(state, n_iter=2000)print(f'2000 回シミュレーションでの推奨手: {move} (中央 4 が定石)')4. UCB の探索 vs 活用バランス
| C (探索係数) | 挙動 | 適用 |
|---|---|---|
| 0 | 完全活用 (greedy) | 局所最適に陥る |
| 1.4 (≈√2) | 理論的最適 | 標準 |
| 3.0+ | 探索強化 | 未知ゲームの初期 |
| 可変 | 段階的に減らす | 強化学習統合 |
5. AlphaZero への発展
- Policy Network: 子ノード選択を rollout でなく NN で評価
- Value Network: rollout の代わりに NN が「この局面はどちらが優勢か」を即評価
- 自己対戦: NN が MCTS と対戦してデータを生成、それで NN を再訓練を繰返す
- 結果: 人間の棋譜なしで、囲碁・将棋・チェス全てで世界最強級
6. メリットとデメリット
- メリット: 評価関数の設計が不要 (rollout が代替)
- メリット: 並列化が容易 (各 simulation が独立)
- メリット: Anytime アルゴリズム (時間が増えるほど良くなる)
- デメリット: 状態空間が極端に大きいと収束しない
- デメリット: ランダムプレイが意味のないゲームでは苦手 (Reinforcement Learning と統合)
7. 次の話
EP.15 では Self-Attention (Transformer) を扱います。ChatGPT / Claude / Gemini を支える 並列化可能な系列モデルの中核 ── 「Attention is All You Need」 (2017) を Python で実装。
この記事の感想を教えてください
あなたの 1 クリックで、本当にこの記事は更新されます。「もっと詳しく」「続編希望」が一定数集まった記事は、 ふくふくが 実際に内容を拡充したり続編記事を公開 します。 送信したリアクションはお使いのブラウザに記録され、再カウントされません。