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%）も併せ持ち、末端から終局まで大急ぎで打ち切る用に使いました。

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