第2章: AlphaGo: 探索と学習の出会い

モンテカルロ木探索、2つのニューラルネットワーク、そして世界チャンピオンを席から立たせた一手

📖 Reading Time: 20-25 minutes 📊 Difficulty: Beginner 💻 Code Examples: 0 📝 Exercises: 0

ビデオ講義

このビデオは以下のテキストと同じ内容をカバーしています。お好みの学習形式をお選びください。

🌐 JP | 🇬🇧 EN | Last sync: 2026-08-19

機械学習道場 > AlphaGoからAlphaFoldへ > 第2章

第1章は、独立した2つの理由によって囲碁が不可能に見える状態で終わりました。木は探索するには広すぎ、そして葉は判定できない。どちらか一方の壁だけでも深刻でしたが、その2つが揃って、40年の努力に対してこのゲームを守り抜いてきたのです。

本章は、その両方の壁がどのようにして同時に崩れたのかを扱います。そして解の形は、始める前に述べておく価値があります。それは本シリーズの残りが従うテンプレートだからです。

学習された直観が「そこを見よ」と告げる場所を探索せよ。そして学習された判断が「そこで何が見つかるか」を告げたら、探索をやめよ。

機構を順番に構築していきます。まず モンテカルロ木探索（MCTS） をゼロから——その4つのステップ、それを操舵する数式、そしてなぜ開始するのに評価関数を必要としないのか。次にAlphaGoが加えた2つのニューラルネットワークと、それらが正確にどこに差し込まれるのか。それから対局の話、コンピュータのゲームプレイ史上で最も議論された2つの手を含めて。そして最後に、あなたが走らせられる完全なMCTS——思考時間を与えるにつれてランダムな打ち方から本質的に完璧な打ち方へと変わっていくもの——を示します。

強化学習の機構をきちんと展開してほしい読者——価値関数、方策勾配、一般形での探索と活用のトレードオフ——は、本シリーズと並行して 強化学習入門 シリーズを読んでください。ここではそれらの考え方を 使い、あちらではそれらが 構築 されます。

2.1 モンテカルロ木探索をゼロから

古典的なミニマックス法は木を 一様に 成長させます。すべての枝が、その価値にかかわらず同じ深さまで探索されます。だからこそ分岐因子250で死ぬのです。MCTSは一様性を完全に放棄します。ゲームが面白いところでは深く、それ以外のあらゆる場所では浅い 木を成長させ、しかもどちらであるかを自分自身の蓄積した統計から決めます。

このアルゴリズムはメモリ上に木を1つ保持します。各ノードは局面と2つの数値——訪問回数 \(N\) と累積された 総価値 \(W\) ——を保持します。アルゴリズムの1回の反復——1回の シミュレーション ——は、根から葉へ歩き、対局を打ち切り、戻り道で数値を更新します。それがすべてです。時間切れになるまでこれを繰り返します。

各シミュレーションは4つのステップからなります。

ステップ1 — 選択（Selection）。 根から始めます。現在のノードのすべての子がすでに作られている限り、そのうちの1つを選んで降りていきます。この選択はランダムでも貪欲でもありません。2.2節のUCBの規則を使い、最も良く見える手をたどることと、あまり試されていない手を確認することのバランスを取ります。まだ未探索の手が残っているノード、あるいは終局に達するまで降り続けます。

ステップ2 — 展開（Expansion）。 そのノードで、一度も試されていない手を1つ取り、それが導く子局面を作成して木に追加します。したがって木は 1シミュレーションあたりちょうど1ノード ずつ成長します。これがメモリを制御下に置き、成長を一様ではなく適応的にしているのです。

ステップ3 — シミュレーション（ロールアウト）。 新しいノードから、安価な方策を使って対局を終局まで打ちます。最も素朴な版では、その方策は 一様ランダム です。結果——勝ち、負け、引き分け——を記録します。これが第1章のモンテカルロ評価器であり、古典的なプログラムなら代わりに手作りの評価関数を呼んでいた場所です。

ステップ4 — バックアップ（Backup）。 いま降りてきた経路を、新しいノードから根まで逆にたどります。その経路上のすべてのノードで \(N\) を1増やし、結果を \(W\) に加えます。アルゴリズムがそもそも機能するかどうかを決める細部が1つあります。結果は そのノードへ入る手を選んだプレイヤーの視点から 記録されなければなりません。黒の勝ちは、黒が選んだノードでは勝ちであり、白が選んだノードでは負けです。これを逆にすると、探索は自信満々に最悪の手を見つけ出します。

最後のシミュレーションが終わると、プログラムは根から手を打ちます。注目すべきことに、選ばれる手はたいてい 最も訪問された 子であって、最も得点の高い子ではありません。3回の訪問での高い平均はノイズです。訪問回数が多いということは、精査のもとで選択規則が繰り返しそこへ戻ったということです。訪問回数のほうが頑健な統計量であり、2.7節のコードもそれを使います。

📚 エニータイム性

MCTSには、アルファベータ探索にはない特徴があり、それは実務においてどんな個別の技術的細部よりも重要です。

いつでも止めてよく、その時点での最良の答えを返してくれる。 10回のシミュレーションの後では下手に打ち、1万回の後では上手に打ち、1000万回の後ではさらに上手に打ちます。無効な中間状態はなく、数値が意味をもつために完了させねばならない深さもなく、木が整合的になるために終わらせねばならない反復もありません。各シミュレーションは、推定値に対する完結した自己充足的な改善なのです。

これは エニータイム性（anytime property） と呼ばれ、挙げるに値する帰結が3つあります。

2.2 UCB: 探索はどこを見るかをどう決めるのか

選択はこのアルゴリズムの心臓であり、多腕バンディット問題でおなじみのジレンマに直面します。現在最も良く見える手を 活用（exploit） するのか、それとも推定がまだ不確かな手を 探索（explore） するのか?

純粋な活用は罠です。最強の手が、たまたま運悪く最初の2回のランダムプレイアウトで負けたとしましょう。貪欲な探索者はそれを永久に見捨て、しかもその誤りは回復不能です。誤りを正すはずの証拠を二度と集めないからです。純粋な探索も同じくらい無用です。250手にシミュレーションを均等にばらまくのは、機能しえないと先に確認した一様探索そのものです。

上側信頼限界（Upper Confidence Bound, UCB） の規則がこれを解決します。ノード \(s\) において、その子 \(a\) のうち、次を最大化するものを選びます。

\[ \mathrm{UCB}(s,a) \;=\; \underbrace{\frac{W(s,a)}{N(s,a)}}{\text{exploitation}} \;+\; \underbrace{c\,\sqrt{\frac{\ln N(s)}{N(s,a)}}} \]}

ここで \(N(s,a)\) は子 \(a\) を通ったシミュレーションの回数、\(W(s,a)\) はその総価値、\(N(s)\) は親への訪問回数、そして \(c\) はバランスを制御する定数です。

2つの項を別々に読みましょう。

第1項はその手の経験的な勝率 \(W/N\) です。探索がその手についてこれまでに学んだことのすべてであり、それ以上ではありません。

第2項は無知の度合いの尺度です。 \(N(s,a)\) が小さいとき（この手は兄弟に比べて探索不足である）に大きくなり、また親が訪問を蓄積するにつれて——ゆっくりとですが——大きくなります（ノード全体がより熱心に研究されているので、未検証の兄弟はもう一度見られる価値がある）。名前はその由来から来ています。2つの項の和は、その手の真の価値に対する楽観的な上界であり、それによって選択することが 「不確実性に直面したときの楽観主義」 という原理を実装しているのです。

📚 なぜ平方根と対数なのか

探索項の形は恣意的ではなく、2つの部分は異なる仕事をしています。

\(1/\sqrt{N(s,a)}\) という因子は 統計的な誤差棒 の形です。\(N\) 個の標本の平均の不確かさは \(1/\sqrt{N}\) のように縮むので、このボーナスは定数倍を除いて、勝率のまわりの信頼区間の幅そのものです。4回サンプルされた手は、16回サンプルされた手の2倍のボーナスを担います。

\(\sqrt{\ln N(s)}\) という因子は、ボーナスを親の訪問回数とともに増加させますが、対数的にしか ——きわめてゆっくりとしか——増加させません。これが保証を成立させます。ボーナスは決して増加を止めないので、どの手も恒久的に見捨てられることはなく、すべての子はいずれ再訪されます。しかしその増加があまりに遅いので、探索は圧倒的多数の労力を良い手に費やし続けます。その帰結として、悪い手に浪費されるシミュレーションの割合は \(\ln N\) のようにしか増えないのに対し、総シミュレーション数は \(N\) のように増えるのです。

定数 \(c\) はバランスを直接に設定します。小さな \(c\) は早く決め打ちして見落としうる探索を、大きな \(c\) はいつまでも自分を疑い続ける探索を作ります。よくある既定値は \(c = \sqrt{2}\) であり、2.7節のコードもそれを使っています。いろいろ試してみる価値があります。

決定的な性質 は、そしてこの仕組み全体が手作りの評価器を上回る理由は、シミュレーションが蓄積するにつれて何が起きるかにあります。初期には推定値はランダムプレイアウトから来ており、貧弱です。しかし十分深く降りたシミュレーションはすべて、ランダムな当て推量を実際の対局結果に置き換えて木を上へ伝播させ、選択規則はシミュレーションを重要な変化へ押し込み続けます。評価器が自分自身を改善するのです。 人間は囲碁の知識を1つも書き込んでいません。知識はその場で、ルールと計算から製造されます。

2.3 MCTSがなお弱かったところ

モンテカルロ木探索は、コンピュータ囲碁をか弱いレベルから強いアマチュアのレベルへ引き上げました。それ単独でプロの棋力には達せず、その2つの限界がまさにAlphaGoが加えたものを指し示しています。

ロールアウトが愚かすぎる。 一様ランダムな打ち方は、どんな囲碁棋士も見覚えのない対局を生み出します。価値が精確な手順に依存する局面——死活の戦い、際どい攻め合い——では、ランダムな継続が答えを決めているまさにその構造を破壊してしまい、統計は自信をもって誤った数値へ収束します。ロールアウトをわずかにランダムでなくする手書きの「高速方策」は助けになりましたが、それはモンテカルロが排除するはずだった手作り知識の問題を、ちょうど再導入することでもありました。

分岐因子はどのノードでも依然として250である。 MCTSは不均等に探索しますが、これは大きな改善であるものの、ある手が悪いと判断する前に、それを展開して少なくとも1回はサンプルしなければなりません。どのノードにも250の合法手がある以上、あらゆるシミュレーション予算の大きな割合が、明らかにひどい手がひどいと発見するために費やされます。

この2つの弱点を必要事項として述べ直せば、AlphaGoの設計はおのずと書き下されます。

これらは2つの異なる学習された関数であり、AlphaGoはそれぞれに1つずつ訓練しました。

2.4 2つのネットワーク: 探索を絞り、葉を判定する

AlphaGoは、2016年にNature誌で発表された 論文で記述されたシステムであり、MCTSに2つの深層ニューラルネットワークを加えました。どちらも盤面の表現を入力に取ります。答える問いが違います。

方策ネットワーク: 何を考慮すべきか?

方策ネットワーク（policy network） は局面を取り、合法手上の確率分布 を出力します。各手がどれくらい打たれそうかという推定です。これは事実上 もっともらしさ のモデルであり、2段階で構築されました。

第1段階: 人間から学ぶ。 ネットワークはまず、強い人間棋士による対局の大規模なコレクションから取った局面に対して、人間が実際に選んだ手を目標として、教師あり学習で訓練されました。これは通常の分類です。盤面を入力し、手を予測する。こうして得られるのは、囲碁の直観 と呼べるものを備えたネットワークです——局面を見て、強い棋士が考慮するであろうひと握りの手を即座に提案する能力です。ここで何が起きたのかに注目してください。数十年にわたって手によるコード化に抵抗した知識——厚み、形、勢力——は、まったく書き下されませんでした。それは例から 暗黙のうちに吸収された のです。専門家の手を予測できるようにする内部特徴として、なんであれ機能したものとして。

第2段階: 自己対局で改善する。 人間を模倣するよう訓練されたネットワークは、人間の模倣が上限になります。そして模倣は目的ではありません——勝つことが目的です。そこで方策ネットワークの複製が 強化学習 によって改善されました。ネットワークは自分自身の過去のバージョンと対局し、勝った対局の手はより打たれやすく、負けた対局の手はより打たれにくくされたのです。これは 方策勾配 の考え方であり、強化学習シリーズ できちんと展開されています。決定的な転換は訓練信号にあります。「ここで人間なら何を打っただろうか?」から「実際に何が勝つのか?」へ。

MCTSへの差し込まれ方: 方策ネットワークの確率は 選択 ステップにバイアスをかけ、それがもっともらしいと考える手へシミュレーションを操舵する事前分布を加えます。ネットワークが無視できるほどの確率しか与えない手は、形式的には禁じられていませんが、めったに訪問されません。実効的な分岐因子は250から、探索が実際に扱える水準へ崩れ落ちます——しかも どの手も 恒久的に排除されることなく。UCBの探索項が下でなお働いているからです。

価値ネットワーク: この局面はどれくらい良いのか?

価値ネットワーク（value network） は局面を取り、1つの数値——そこから 手番のプレイヤーが勝つ確率 の推定——を出力します。これこそ誰も手で書けなかった静的評価関数であり、やはり書くことによってではなく、きわめて多数の自己対局の結果から学習することによって得られました。

MCTSへの差し込まれ方: これは ロールアウト のステップを置き換える、あるいは補強します。200手のランダムな手を打って誰が勝ったかを観察する代わりに、探索は価値ネットワークに直接尋ねます。AlphaGoはロールアウトを完全に捨てはしませんでした。2つの推定を組み合わせたのであり、両方を残すのには良い理由があります。両者は異なる仕方で失敗するのです。価値ネットワークは訓練データに似ていない局面について自信満々に誤りうる一方、ロールアウトはある意味で不偏ですがきわめてノイジーで、精確な手順に対して盲目です。相関しない 失敗モードをもつ2つの不完全な推定器は、どちらか一方だけよりも強いのです。

📚 分業を、1つの表で

方策ネットワーク 価値ネットワーク
答える問い どの手が考慮する価値があるか? ここでは誰が勝っているか?
出力 合法手上の分布 1つの数値: 勝率
訓練データ 人間の専門家の手、次に自己対局 自己対局の結果
MCTS内での役割 選択 にバイアス——木を絞る ロールアウト を置換／補強——葉を評価する
どちらの壁を攻めるか 分岐因子（幅） 欠けた評価関数（深さ）

最後の行が本章全体の要点です。第1章は 2つの 独立した壁を特定し、そしてこれは それぞれに1つずつネットワークを向けた システムであり、それらを、すでに計算量を強さへ変換するのが得意だった探索が結び合わせています。どちらのネットワークも単独では囲碁を打ちません。方策ネットワークだけなら、計算の裏づけのないもっともらしく見える手を打つでしょう。価値ネットワークだけなら、手を考慮する方法すらありません。探索だけでは、すでに見たとおり、離陸すらできません。組み合わせこそが達成なのです。 そして直観と探索が互いを強化し合う点は精確に述べる価値があります。ネットワークは探索を、深くなれるほど効率的にします。そして探索は、変化を実際に打ち切ることでネットワークの誤りを正します。

2.5 対局

3年間に3つの対局が、このシステムを「興味深い研究」から、一般の人々の大半が実際に目撃した瞬間へと押し上げました。

ファン・フイ、2015年。 AlphaGoはヨーロッパ王者ファン・フイと対局し、5-0 で勝ちました。プログラムがプロ棋士に、全盤面の互先で勝ったのはこれが初めてであり、Nature論文と同時に発表されました。囲碁界の反応は抑制されたものでした——ヨーロッパのプロの棋力はゲームの頂点からはかなり下であり、多くの強豪棋士は最上位との差がなお数年は保たれると予想していたのです。

イ・セドル、2016年。 AlphaGoは同世代最強の棋士の1人であるイ・セドルと五番勝負を戦い、4-1 で勝ちました。この対局からの2つの手が、いまなお議論されています。

1つ目は 第2局の第37手 です。AlphaGoは五線への肩ツキを打ちました——囲碁を学ぶ者が早い段階で習う定跡的な常識に反する手であり、解説者たちは当初それを間違いかバグだと考えました。どちらでもありませんでした。局面が進むにつれてその石の勢力は決定的であることが判明し、いまではこの手は、コンピュータの奇癖ではなく囲碁理論への真に創造的な貢献として広く見なされています。この対局に文化的な重みを与えたのはこの瞬間でした。人間より速く計算する機械ではなく、人間なら思いつかなかったことを打ち、しかも 正しかった 機械なのです。

2つ目は 第4局の第78手、イ・セドルが打った手です——AlphaGoの陣形の真ん中への割り込みであり、プログラムは明らかにそれを重く見ていませんでした。AlphaGoのその後の打ち回しは崩れ、イ・セドルがその局を制しました。このマッチにおいて、そのバージョンのシステムに対して誰かが勝った唯一の1局です。両方の手がこの物語に属しており、2つ目を省くと教訓を取り違えます。AlphaGoは無謬ではありませんでした。学習された判断が薄い領域をゲームの中に持っており、世界最高水準の人間が、途方もない重圧の下でその1つを見つけ出したのです。

柯潔、2017年。 その後のバージョンのシステムが、当時の世界ランキング1位だった柯潔と対局し、勝ちました。その対局のすぐ後、プログラムは 競技から引退 しました。その時点で、人間の対戦相手ともっと打つことで確立できることはあまり残っておらず、研究はすでに第3章が取り上げる問いへ移っていたのです。訓練から人間の対局を完全に取り除いたら何が起きるのか、という問いへ。

📚 対局を誠実に読む

3つの留保を述べます。これは誇張を招く物語だからです。

「囲碁で超人的」は狭い主張である。 それが意味するのは、このゲームにおいて、このルールで、この持ち時間の下で、このシステムがこれらの棋士に勝った、ということです。システムが囲碁を理解していたとか、手を説明できたとか、少し違うルールの変種を打てたとか、他に何かができたとか、そういうことは一切意味しません。

第37手は訓練についての証拠であって、意識についての証拠ではない。 AlphaGoが人間なら考慮しない手を打てた理由は、その方策が模倣だけでなく自己対局によって形作られていたからです。人間の手を模倣するためだけに訓練されたネットワークは、構成上、人間が打たない手を生み出しにくい。目的が 専門家の手に一致すること ではなく 勝つこと になった途端、到達可能な戦略の空間は人間の分布を超えて広がりました。これがここでの「創造性」に対する精確で機械的な説明であり、神秘的な説明よりも有用です。

第78手はカバレッジについての証拠である。 学習された評価器は、訓練が訪れた局面空間の領域では信頼でき、その外では信頼できません。イ・セドルは、AlphaGoの経験において薄かった局面のタイプを見つけました。この失敗モード——訓練分布の外で、自信満々に、流暢に、そして誤る——は囲碁に固有のものではありません。第5章へ持ち越すべき最も重要な留保がこれです。そこでは同じアーキテクチャがタンパク質に向けられ、「この入力は訓練データに似ているか?」という問いが、現実の帰結を伴う科学的な問いになるのです。

2.6 なぜこれが囲碁を超えて重要だったのか

囲碁の部分を取り除くと、一般的なテンプレートが残ります。それが、構造生物学で終わるシリーズの冒頭に本章が属する理由です。

学習された直観が提案し、探索が処分する。 ニューラルネットワークは、扱いようもなく大きな選択肢の空間を、もっともらしいものの短いリストに変えます。次に探索の手続きがそのリストをきちんと吟味し、そして——決定的なことに——その結果はネットワークを 却下できます。ネットワークは速いが時に誤り、探索は遅いが実際のルールに根ざしています。それぞれが相手の失敗モードを覆うのです。

3つの教訓がボードゲームを超えて一般化します。

残る問いは、本シリーズの後半を可能にするものです。AlphaGoは出発点として人間の対局を必要としました。もしこの手法全体が専門家である人間の判断の大規模なコーパスに依存するのなら、その射程はそうしたコーパスをもつひと握りのドメインに限られます。本当にそうなのでしょうか? 第3章がそれに答え、その答えこそが、ゲームプレイの成果を科学の道具へと変えるものです。

2.7 ハンズオン: 80行の完全なMCTS

MCTSについて語るより、走らせるほうがずっと説得力があります。以下は三目並べ（tic-tac-toe）のための完全な実装です——4つのステップすべて、2.2節に書いたとおりのUCBの規則、そしてランダムなロールアウト。ニューラルネットワークもいかなる評価関数もありません。 このプログラムに含まれる囲碁的な知識は、ゲームのルールだけです。

実験の内容: いくつかのシミュレーション予算のもとで、探索を一様ランダムに打つ相手と対局させ、棋力が本当に計算量に追随するかを見ます。シミュレーション0回の行は、両者が同じランダム方策であり、「探索なし」がどう見えるかのベースラインとして含めています。

import math

import numpy as np

# ---------------------------------------------------------------
# 完全なモンテカルロ木探索、およそ80行。
# ゲーム: 三目並べ。ニューラルネットワークも手作りの評価関数も
# 使わない——知識の源は「ランダムなプレイアウト」だけである。
# ---------------------------------------------------------------
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)]


def winner(board):
    """そのプレイヤーが3つ並べていれば1か2を、そうでなければ0を返す。"""
    for i, j, k in LINES:
        if board[i] != 0 and board[i] == board[j] == board[k]:
            return board[i]
    return 0


def legal(board):
    return [i for i in range(9) if board[i] == 0]


def apply_move(board, move, player):
    nb = list(board)
    nb[move] = player
    return tuple(nb)


class Node:
    """探索木の中の1局面。

    `player` はここでの手番の側。`W` はこのノードへ「入る手を打った」側、
    すなわち親での手番の側の視点から結果を累積する。この約束事こそが、
    親におけるUCBの比較を同じ土俵の比較にしているものである。
    """

    def __init__(self, board, player, parent=None, move=None):
        self.board, self.player = board, player
        self.parent, self.move = parent, move
        self.children = []
        self.result = winner(board)
        self.terminal = self.result != 0 or not legal(board)
        self.untried = [] if self.terminal else legal(board)
        self.N, self.W = 0, 0.0

    def ucb(self, c):
        """上側信頼限界（UCB）: 活用 + 探索。"""
        return self.W / self.N + c * math.sqrt(math.log(self.parent.N) / self.N)


def reward(win, mover):
    """終局した対局を `mover` の視点から採点する。"""
    if win == 0:
        return 0.5
    return 1.0 if win == mover else 0.0


def mcts_move(board, player, n_sims, rng, c=math.sqrt(2)):
    root = Node(board, player)
    for _ in range(n_sims):
        node = root

        # --- 1. 選択: ノードが完全に展開されている限りUCBで降りる
        while not node.terminal and not node.untried:
            node = max(node.children, key=lambda ch: ch.ucb(c))

        # --- 2. 展開: 未探索の子を1つ追加する
        if not node.terminal:
            mv = node.untried.pop(rng.integers(len(node.untried)))
            child = Node(apply_move(node.board, mv, node.player),
                         3 - node.player, parent=node, move=mv)
            node.children.append(child)
            node = child

        # --- 3. シミュレーション: 残りの対局をランダムに打つ
        b, p = node.board, node.player
        win = winner(b)
        while win == 0 and 0 in b:
            mv = legal(b)[rng.integers(len(legal(b)))]
            b = apply_move(b, mv, p)
            win, p = winner(b), 3 - p

        # --- 4. バックアップ: いま辿った経路を上へ結果を押し上げる
        while node is not None:
            node.N += 1
            if node.parent is not None:
                node.W += reward(win, node.parent.player)
            node = node.parent

    # 最も得点の高い手ではなく、最も訪問された手を打つ:
    # 訪問回数のほうが頑健な統計量である。
    return max(root.children, key=lambda ch: ch.N).move


def random_move(board, player, rng):
    mv = legal(board)
    return mv[rng.integers(len(mv))]


def play_game(n_sims, rng):
    """MCTS（プレイヤー1、先手）対 一様ランダムな相手。"""
    board, player = (0,) * 9, 1
    while True:
        w = winner(board)
        if w or not legal(board):
            return w
        if player == 1:
            mv = random_move(board, player, rng) if n_sims == 0 \
                else mcts_move(board, player, n_sims, rng)
        else:
            mv = random_move(board, player, rng)
        board, player = apply_move(board, mv, player), 3 - player


# --- 実験: 探索を増やすと本当に棋力が上がるのか? ---
N_GAMES = 200
rng = np.random.default_rng(0)

print(f"MCTS (X, first) vs random (O) -- {N_GAMES} games per setting")
print(f"{'simulations/move':>18} {'win':>8} {'draw':>8} {'loss':>8}")
print("-" * 46)
for n_sims in [0, 10, 100, 1000]:
    results = np.array([play_game(n_sims, rng) for _ in range(N_GAMES)])
    win = np.mean(results == 1) * 100
    draw = np.mean(results == 0) * 100
    loss = np.mean(results == 2) * 100
    label = "0 (pure random)" if n_sims == 0 else str(n_sims)
    print(f"{label:>18} {win:7.1f}% {draw:7.1f}% {loss:7.1f}%")

出力:

MCTS (X, first) vs random (O) -- 200 games per setting
  simulations/move      win     draw     loss
----------------------------------------------
   0 (pure random)    58.5%    12.5%    29.0%
                10    87.5%     5.5%     7.0%
               100    97.5%     2.5%     0.0%
              1000    98.0%     2.0%     0.0%

結果の読み方。 重要度の低いものから順に4つ挙げます。

試してみるべきことが3つあり、それぞれが具体的な何かを教えてくれます。

🎯 演習問題

  1. 符号の約束事。 2.1節は、バックアップのステップが各ノードへ 入る手を打った プレイヤーの視点から結果を記録しなければならないと警告しています。コードの中でこれを実装している行を見つけてください。そのうえで、node.parent.player を node.player に変えたらプログラムがどう打つようになるかを言葉で予測し、なぜそれが単にランダムに打つより悪いのかを説明してください。

  2. UCBの式を読む。 あるノードが100回訪問されています。子Aは50回の訪問で \(W/N = 0.6\)、子Bは4回の訪問で \(W/N = 0.8\) です。\(c = \sqrt{2}\) として、両方のUCBスコアを手で計算し、どちらが選ばれるかを述べてください。次に、Bの勝率を固定したまま、Aが代わりに選ばれるようになるにはBへの追加訪問が何回必要かを求めてください。

  3. どの壁に、どのネットワーク。 以下のそれぞれについて、幅の問題と評価の問題のどちらに対処するものかを述べ、AlphaGoの2つのネットワークのどちら（あるいはどちらでもないか）がその役割を担うかを述べてください。(a) アルファベータ枝刈り、(b) UCBの探索項、(c) ランダムなロールアウト、(d) 方策ネットワークの手の確率、(e) 価値ネットワークの勝率推定。

  4. 模倣か目的関数か。 人間の対局だけ で訓練された方策ネットワークが、第37手のような手を生み出す見込みがきわめて低い理由を訓練信号の観点から説明し、自己対局の訓練がそうした手を到達可能にする理由を説明してください。次に、自己対局が導入する一方で模倣学習にはないリスクを1つ述べてください。

  5. 第78手を診断する。 イ・セドルの第4局の割り込みは、AlphaGoが誤って評価していた局面のタイプを露呈させました。学習された評価器を配備する 前に 測定できて、そうした盲点について警告を与えてくれる具体的な事柄を2つ述べてください。それぞれの測定が何を検出でき、何を検出できないのかを明確に述べてください。

まとめ

モンテカルロ木探索 は、ゲームが面白いところでは深く、それ以外では浅い木を、1シミュレーションあたり1ノードずつ、4つのステップを通して成長させます。既存の木を降りる 選択、新しい子を1つ加える 展開、終局までロールアウトする シミュレーション、そして辿った経路に沿って結果を戻す バックアップ ——結果は各ノードへ入る手を打ったプレイヤーの視点から記録されます。MCTSは エニータイム性 をもちます。いつ中断しても、その時点の最良の答えが有効であり、したがって計算量は閾値なしに滑らかに強さへ変換されます。

選択は UCBの規則 \(W/N + c\sqrt{\ln N(s) / N(s,a)}\) を使います。第1項は経験的な勝率、第2項は統計的な誤差棒の形をした無知の尺度です。\(1/\sqrt{N(s,a)}\) の因子がサンプル不足の手を魅力的にし、\(\ln N(s)\) の増加が、どの手も恒久的には見捨てられないことを保証しつつ、浪費されるシミュレーションの割合を小さく保ちます。決定的なのは、シミュレーションが蓄積するにつれて 評価器が自分自身を改善する ことです——開始に人間の知識は要りません。

MCTS単独では強いアマチュア囲碁で頭打ちになりました。理由は2つ。ランダムなロールアウトが多くの局面を決める精確な手順を破壊すること、そして各ノードにはなお約250の手があり、却下される前にそれぞれをサンプルしなければならないことです。2016年にNature誌で発表されたAlphaGoは、それぞれの問題に1つずつネットワークを加えました。 方策ネットワーク ——まず人間の専門家の手で訓練され、次に自己対局の方策勾配で改善——は、もっともらしい手の分布を出力して 選択 にバイアスをかけ、何も禁じることなく実効的な分岐因子を崩壊させます。価値ネットワーク ——自己対局の結果で訓練——は勝率を出力して ロールアウト を置換／補強し、数十年の手作業のコード化が生み出せなかった静的評価関数を供給します。2つはロールアウトを置き換えるのではなく組み合わされました。異なる仕方で失敗する推定器は、一緒のほうが強いからです。

結果はすぐに続きました。2015年のファン・フイ戦（5-0）、互先で破られた最初のプロ。2016年のイ・セドル戦（4-1）、常識に反しながら正しかった肩ツキである 第2局の第37手、そしてイ・セドルが盲点へ割り込んでこのマッチでAlphaGoに勝った唯一の1局を生んだ 第4局の第78手 で記憶されています。そして 2017年の柯潔戦、その後システムは競技から引退しました。誠実に読めば、第37手は訓練目的についての証拠——自己対局が方策を人間の分布から解き放つ——であり、第78手はカバレッジについての証拠——訓練経験の外で学習された評価器が示す、自信満々で誤る失敗——です。

一般化するテンプレートは 学習された直観が提案し、探索が処分する です。速いネットワークが扱いようもない空間を短いリストに絞り、接地された探索がそれを検査し、却下することもできます。私たちの三目並べの実装は、その探索の半分だけを、学習をまったく使わずに実証しました——負けはシミュレーション0回での29.0%から、10回で7.0%へ、そして 100回で0.0% へ落ち、残る2%の引き分けはアルゴリズムではなくゲーム自身の天井でした。

依存関係が1つ残っており、それがこのすべてが科学に届くかどうかを決めます。AlphaGoは、人間の専門家の対局の大規模なコーパスから直観を学びました。次章はそのコーパスを完全に取り除き、ルールだけから出発したシステムが自力で何を発見するのかを検討し、ゲームそのものを取り上げたときにこの手法に何が残るのかを問います。

← 第1章: ゲームという試金石 第3章: Zeroとその先: 人間なしで学ぶ →

免責事項

シリーズトップへ戻る 次の章へ →