AlphaGoを1から — 探索と学習の結婚

囲碁が長く「解けない」とされた理由から始め、方策ネットワーク・価値ネットワーク・モンテカルロ木探索・自己対戦が互いの弱点をどう埋め合うかを式とコードで解きほぐす。最後に、この設計がLLMの推論時計算にどう受け継がれたかを整理する。

Mastering the game of Go with deep neural networks and tree search (Silver et al.

なぜ囲碁だけが最後まで残ったのか

1997年、チェスの世界王者がコンピュータに敗れました。それから20年近く、囲碁だけが残ります。「あと10年はかかる」というのが2015年頃までの相場観でした。チェスを解いた探索の技術は、そのまま持ち込んでも動かなかったのです。

理由は2つあり、どちらも「量」ではなく「質」の問題です。

1つ目は分かれ道の多さ。碁盤は19×19の361交点で、対局を通した平均でもおよそ250通りの合法手があり、対局はおよそ150手続きます。チェスは1手あたりおよそ35通り、80手程度ですから、桁が違う。分かれ道が250本ある迷路を、150個目の分岐まで見通せと言われているようなものです。

差の効き方は掛け算で見えます。3手先を読むだけで $250^3 \approx 1560$ 万通り。10手先の $250^{10}$ は、宇宙年齢を秒に直しても足りません。19路盤の合法な盤面の総数は2016年に厳密に数え上げられていて、およそ $2.08 \times 10^{170}$ 通り——観測可能な宇宙の原子数（$10^{80}$ 程度と見積もられる）の2乗より多い。しかも1手読むごとに250倍になる木は、計算機を100万倍速くしても2手か3手しか深く読めません。「速いマシンを買えばいい」で済む話ではないのです。

2つ目の壁: 「今どっちが勝っているか」が言えない

チェスには荒っぽくても強力な物差しがあります。駒の点数です。クイーンは9点、ルークは5点……と足し引きすれば途中の局面でもだいたいの優劣が分かる。だから探索を途中で打ち切っても、そこそこ正しい評価が返ります。

囲碁にはそれがない。石はすべて同じ石で点数の差がなく、強さは石の「形」と「関係」だけで決まります。チェスの「クイーンを取られた」は誰が見ても悪い。囲碁の「この石は死んでいる」は、10手先まで読んでようやく確定することがある。高段者は一目見て「黒がやや良い」と言えますが、その判断を数式に書き下した人はいませんでした。

つまり囲碁は、幅が広すぎて全部は読めないうえに、途中で打ち切っても評価できない。探索という道具が、入口と出口の両方から封じられていたわけです。だから2000年代の囲碁プログラムは評価関数を諦め、「そこからランダムに最後まで打ってみて勝率を数える」という荒技に頼っていました。

探索と学習は、もともと別の道具だった

ここで2つの道具を並べます。探索はその場で先を読むこと。ルールさえ与えれば動き、答えも正確です。ただし指数関数的に高価。学習は過去の経験から関数を作ること。一瞬で答えが出ます。ただし訓練データの外では平気で間違えるし、盤面を「見た」だけで細い読み筋までは追えません。

強い探索は遅く、速い直感は浅い。長いあいだ囲碁AIはこの二択のどちらかに賭けていました。AlphaGoの発明は、新しい部品を作ったことではなく、2つを互いの弱点にちょうど当てはめたことです。

• 学習した方策が、250本の分かれ道から有望な数本を指す → 木の幅が刈られる
• 学習した価値が、終局まで読まずに勝ち負けを返す → 木の深さが刈られる
• 刈られて現実的な大きさになった木を、探索が丁寧に読む

刈るのはニューラルネット、読むのは探索。どちらか一方では届かなかった場所に、組み合わせで届きました。

方策ネットワーク: 幅を刈る

方策（policy）ネットワークは盤面 $s$ を入力し、各交点に打つ確率 $p(a\mid s)$ を返します。初代AlphaGoはこれを人間の棋譜の教師あり学習で作りました。「この局面で人間はどこに打ったか」を当てる分類問題で、論文が報告する的中率は57.0%です。

大事なのは57%は「強さ」ではないこと。役割は勝つことではなく、250本の候補を有望な十数本に絞ることです。AlphaGoは精度を捨てて速度を取った高速方策（線形モデル、的中率24.2%）も併せ持ち、末端から終局まで大急ぎで打ち切る用に使いました。

価値ネットワーク: 深さを刈る

価値（value）ネットワークは盤面 $s$ から1つの数 $v(s) \in [-1, 1]$ を返します。$+1$ が手番側の勝ち、$-1$ が負け。囲碁になかった評価関数を、学習で作ったわけです。

罠は訓練データにありました。1局の全局面を使うと局面同士が似すぎていて、ネットは「この対局は黒が勝った」を丸暗記します。そこで自己対戦3000万局から1局につき1局面だけ取り出しました。量ではなく、データ同士の独立性を買ったのです。

MCTS が2つを縫い合わせる

方策と価値を受け取って手を決めるのがモンテカルロ木探索（MCTS）です。1手を選ぶあいだに、次の4つを数百〜数千回繰り返します。

1. 選択: 根から葉まで、下の式に従って枝をたどる
2. 展開: 葉で子を作り、方策ネットに $p(a\mid s)$ を出させる
3. 評価: その葉の良し悪しを見積もる
4. 逆伝播: 見積もりを根まで戻し、通った枝の統計を更新する

選択の式がこの手法の心臓です。

要するに、「打ってみて良かった手」と「まだ試していないが方策が推す手」を足して、大きいほうを選ぶだけです。$Q(s,a)$ はその枝の探索の平均評価（実績）、$P(s,a)$ は方策が与えた事前確率（勘）、$N(s,a)$ は選んだ回数、$c_{\mathrm{puct}}$ は勘をどれだけ信じるかのつまみ。

第2項は $N(s,a)$ が分母にいるので選ぶたびに小さくなります。最初は勘に従って広がり、回数を重ねると実績 $Q$ が主導権を握る。「試す」と「活かす」の綱引きが1本の式に畳まれています（モンテカルロ法と同じ血筋です）。

初代はさらに、3番目の評価を加重平均 $V(s_L) = (1-\lambda)\, v_\theta(s_L) + \lambda \, z_L$ にしました。つまり、価値ネットの見積もりと、高速方策で終局まで打ち切った実際の勝敗を混ぜる。論文は $\lambda = 0.5$ の半々が最も強かったと報告しています。学習した勘と、雑でも最後まで読んだ実測は、混ぜたほうが良かったわけです。

自己対戦: 探索の結果を、自分の直感として飲み込む

翌年のAlphaGo Zeroは、出発点だった人間の棋譜を捨てます。ネットワークは1つになり、同じ胴体から方策 $\mathbf{p}$ と価値 $v$ の2つの頭が生えました。

鍵はMCTSは方策改善オペレータであるという見方です。素の $\mathbf{p}$ より、それを勘として1600回探索した結果のほうが良い手を指す。ならば探索結果を教師にして、「次からは探索なしでこう指せ」と教え込めばいい。ラベルは訪問回数から作ります。

言い換えると、たくさん読まれた手ほど高い確率を割り当てるだけ。$\tau$ は温度で、$\tau = 1$ なら訪問回数の比のまま、$\tau \to 0$ なら最多訪問の1手に全部集まります。

学習の目的関数は3つの足し算です。

$$\ell = (z - v)^2 - \boldsymbol{\pi}^\top \log \mathbf{p} + c\lVert\theta\rVert^2$$

つまり、勝敗 $z$ を価値の頭に当てさせ、探索が作った $\boldsymbol{\pi}$ を方策の頭に真似させ、重みが暴れないよう罰を足す。

これで輪が閉じます。ネットが強くなる → 同じ探索回数でより良い手が出る → 教師ラベルが良くなる。外部データなしに強くなるのは、探索が毎回わずかな上乗せを作り、学習がそれを固定するからです。

もう1つ欠かせないのが根ノードへのディリクレ雑音 $P(s,a) = (1-\varepsilon)\, p_a + \varepsilon\, \eta_a$。これがないと自己対戦は今よいと思う手ばかり打ち、頭打ちになります。この設計にチェスと将棋のルールを差し替えたのがAlphaZero、ルールすら与えないのがMuZeroです。

コードで書く PUCT-MCTS

import numpy as np

def puct_select(node, c=1.5):
    total = np.sqrt(node.N.sum())            # 親の総訪問回数の平方根
    u = c * node.P * total / (1 + node.N)    # 勘（未訪問ほど大きい）
    return int(np.argmax(node.Q + u))        # 実績 + 勘

def simulate(node, net):
    if node.is_terminal():
        return -node.result()                # 手番が入れ替わるので符号反転
    if node.children is None:                # 展開: ここで初めてネットを呼ぶ
        node.P, v = net(node.state)          # 方策と価値を同時に得る
        node.children = node.expand()
        return -v
    a = puct_select(node)
    v = simulate(node.children[a], net)      # 再帰で葉まで潜る
    node.W[a] += v; node.N[a] += 1           # 逆伝播
    node.Q[a] = node.W[a] / node.N[a]
    return -v

符号を毎回反転させているのが唯一の癖です。ある局面の $+0.8$（自分が良い）は、1手前の相手にとって $-0.8$。忘れると探索は自分と相手の得を取り違えたまま、自信満々に間違えます。

LLMの推論に何が受け継がれたか

AlphaGoは2016年3月にトップ棋士へ4勝1敗、2017年5月には当時の世界第一人者に3戦全勝しました。象徴は第2局の37手目——人間がそこに打つ確率を1万分の1ほどと見積もっていたと報じられる一手です。

設計自体は今も言語モデルの中で生きています。推論時に計算を足すと賢くなる（推論時スケーリング）、価値関数＝途中経過の採点者（プロセス報酬モデル）、探索結果の蒸留。

ただし一番大事な前提だけが移植できていません。囲碁には完璧な審判がいて、$z$ に嘘が混じらない。文章の「良さ」にそれはなく、採点者自身が学習された近似です。すると探索は、正しさではなく採点者の穴を見つけにいきます（LLMエージェントの基礎）。

現場ではこう使う

誰がいつ使うか。 この形がそのまま効くのは、①手が有限で列挙でき、②終端で正しいスコアが機械的に決まる問題です。ゲームAI、組合せ最適化（配送計画・回路配置）、「テストが通ったか」で自動採点できるコード生成やツール操作エージェント。

触るパラメータ。 num_simulations（1手あたりの探索回数。強さと計算時間を交換する最大のつまみ）、c_puct、temperature（$\tau$。自己対戦は高く、本番は0近く）、dirichlet_epsilon、virtual_loss（並列探索で全スレッドが同じ枝に殺到するのを防ぐ）、resign_threshold。実装はDeepMindの mctx（JAX）や OpenSpiel、囲碁なら KataGo / Leela Zero が読めます。

落とし穴。

• 符号の反転漏れ。手番ごとに反転しないと、探索は自滅手を最善と信じます。「1手詰みを詰ませるか」が最短のテスト。
• $c_{\mathrm{puct}}$ は $Q$ の尺度に依存。$Q$ が $[-1,1]$ か $[0,1]$ かで同じ値の意味が2倍ずれます。
• 推論時に探索雑音を残す。ディリクレ雑音と $\tau=1$ は学習用の仕掛け。切り忘れると本番が弱くなり、原因がバグに見えません。
• 採点関数を最適化対象にした瞬間、探索はそれを壊しにいく。報酬が近似モデルなら、強い探索ほど早く穴に届きます。

まとめ

• 囲碁の壁は「幅が広い」と「途中を評価できない」の2つで、探索だけでは越えられなかった
• 方策ネットが幅を刈り、価値ネットが深さを刈り、MCTSが刈られた木を読む
• 自己対戦は、探索の上乗せを学習が固定する輪
• LLMへ移ったのは推論時計算・価値による枝刈り・探索結果の蒸留。移せていないのは完璧な審判