AlphaGo Zeroを指に

明日、人工知能は地球を奴隷化し、そのシステムの機能をサポートする面白いバッテリーとして人間を使い始めます。そして今日、私たちはポップコーンを買いだめして、それがどこから始まるのかを見ます。



2017年10月19日に、DeepmindチームはNatureに記事を公開しました 。その要旨は、新しいAlphaGo Zeroモデルが以前のバージョンのネットワークを無効にするだけでなく、トレーニングプロセスへの人間の参加を必要としないことです。 当然、この声明はAIコミュニティで爆発する爆弾の効果を生み出し、誰もがすぐに興味を持ち、そのような成功を達成することができました。



パブリックドメインの資料に基づいて、Simon sim0nsaysは素晴らしいストリームを記録しました。





そして、一度見るよりも二度読むほうが簡単だと思う人のために、私はこれをすべて手紙で説明しようと思います。



closedcircles.comでの議論に基づいて、ストリームと記事が大幅に拡大しているため、議論されている問題の範囲と特定のナレーションの方法にすぐに注目したいと思います。



さあ、行きましょう。

どうしたの？

囲ancientは古代の（さまざまな推定によれば、2〜5000年前の）ボード戦略ゲームです。 垂直線で描かれたフィールドがあります。 2人のプレーヤーがいます。1人はバッグに白い石があり、もう1人は黒い石があります。 プレイヤーは交代で交代で石を置きます。 異なる色の石で4つの方向に囲まれた1つの色の石は、ボードから削除されます。











勝者は、ゲームの終了までに、より広い領域を「囲む」人です。 まだいくつかの微妙な点がありますが、基本はすべてです-彼の人生で初めて彼を見た人にとって、5分でルールを説明することはかなり可能です。

そして、なぜそれは難しいと考えられていますか？

さて、いくつかのボードゲームを比較してみましょう。



チェッカーから始めましょう。 チェッカーでは、プレーヤーは動きをするための約10のオプションを持っています。 1994年、世界ドラフトチャンピオンは 、アルバータ大学の研究者によって書かれたプログラムにbeatられました 。



次はチェスです。 チェスでは、プレーヤーは平均20回の有効な動きを選択し、ゲームごとに約50回その選択を行います。 1997年、IBMが作成したプログラムであるDeep Blueは、世界チェスチャンピオンのGarry Kasparovを破りました。



さあ行く 専門家は、19x19のフィールドでプレーします。これにより、石を置く場所に361のオプションが与えられます。 他の石に占領されている公然と失われた動きやポイントをカットしても、ゲームごとに平均50〜70回行う必要がある200を超えるオプションを選択できます。 状況は、石が互いに相互作用して構造を形成するという事実によって複雑になり、その結果、移動35に設定された石は115にのみ利益をもたらすことができます。 そして、ほとんどの場合、この動きが私たちを助けたのか妨げたのかを理解することは一般的に困難です。 しかし、2016年、AlphaGoプログラムは、スコア4：1の5回のゲームでリーセドルの世界最強（少なくとも最強の1人）を破りました。

なぜ勝つのにそんなに時間がかかったのですか？ たくさんのオプションがありますか？

大まかに言えば、はい。 また、チェッカー、チェス、およびゴーでは、アルゴリズムが機能する一般的な原則はまったく同じです。 これらのゲームはすべて、完全な情報を持つゲームのカテゴリに分類されます。つまり、可能なすべてのゲーム状態のツリーを構築できます。 したがって、私たちはそのようなツリーを構築するのはつまらないです。そして、枝に沿って進むだけで、勝利につながります。 微妙な点は、ツリーの場合、分岐係数が大きく印象的な深さがあるためにツリーが非常に大きくなり、適切な時間内にツリーを構築したり移動したりできないことです。 DeepMindのスタッフはこの問題を解決できました。

そして、彼らはどのように勝ちましたか？

ここからが楽しみです。



まず、GoGoアルゴリズムがAlphaGoの前にどのように機能したかについて説明しましょう。 それらのすべては、最も印象的な結果を示さず、平均的なアマチュアのレベルで成功し、すべてモンテカルロツリー検索-MCTSと呼ばれる方法に依存していました。 アイデアは何ですか（これを理解することが重要です）。



状態の木があります-動き。 この特定の状況から、このツリーの枝のいくつかに沿って、それが終わるまで歩いています。 ブランチが終了したら、新しいノード（ノード）を追加して、このツリーを徐々に完成させます。 そして、追加されたノードを評価して、ツリー自体を公開せずに、将来このブランチを歩くかどうかを決定します。



より詳細には、次のように機能します。











ステップ1、選択：位置のツリーがあり、移動するたびに、現在の位置に最適な子ノードを選択します。



ステップ2、拡張：ツリーの終わりに達したとしますが、これはゲームの終わりではありません。 新しい子ノードを作成して、そこに移動するだけです。



ステップ3、シミュレーション：さて、新しいノードが登場しました。実際、私たちが初めて見つけたゲームの状況です。 次に、それを評価する必要があります。つまり、私たちが良い状況にあったかどうかを理解する必要があります。 どうやってやるの？ 基本コンセプトでは、いわゆるロールアウトを使用します。現在の位置からゲーム（または多くのゲーム）をプレイし、勝ったか負けたかを確認します。 結果の結果とノードの推定値を考慮します。



4番目のステップ、バックプロパゲーション：新しいノードが良いか悪いかに応じて、ツリーを上ってすべての親ノードの重みを増減します。 一般原則を理解することは重要ですが、まだこの段階を詳細に検討する時間があります。



各ノードで、2つの値を保存します。現在のノードの値と、そのノードを実行した回数です。 そして、これらの4つのステップのサイクルを何度も繰り返します。

最初のステップで子ノードを選択するにはどうすればよいですか？

最も単純なバージョンでは、最高の信頼限界（UCB）を持つノードを使用します。











ここで、 vはノードの値、 nはこのノードにいた回数、 Nは親ノードにいた回数、 Cは単なる要因です。



それほど単純ではないバージョンでは、より正確な結果を得るために数式を複雑にしたり、ニューラルネットワークなど他のヒューリスティックを使用したりすることもできます。 このアプローチについても説明します。



少し広く見ると、古典的な多腕バンディット問題があります。 タスクは、利用可能な最良のオプションの使用と新しい機会の探索との最適なバランスを提供するようなノード選択機能を見つけることです。

なぜ機能するのですか？

MCTSを使用すると、決定ツリーが非対称に成長するため、関心のあるノードがより頻繁にアクセスされ、関心の低いノードがより頻繁にアクセスされなくなり、ツリー全体を公開せずに単一のノードを評価できるようになります。

これはAlphaGoと関係がありますか？

一般に、AlphaGoは同じ原則に基づいています。 主な違いは、第2段階で新しいノードを追加するときです。新しいノードを追加するときは、ロールアウトの代わりにニューラルネットワークを使用します。 どうやってやるの？



（前のバージョンのAlphaGoについて簡単に説明しますが、実際には十分な興味深いニュアンスがあります。詳細が必要な場合は、ビデオの冒頭のウェルカムをご覧ください。



まず、2つのネットワークをトレーニングします。各ネットワークは、ボードの状態を入力として受け取り、この状況で人がどのような動きをするかを示します。 なぜ2つ？ 1つは低速ですが、うまく機能し（正しい予測の57％、および追加の各パーセンテージは最終結果に非常に堅実なボーナスを与える）、2番目の精度ははるかに低くなりますが、高速です。



これらのネットワークは、低速でも高速でも、人間の動きでトレーニングします。簡単にgoサーバーにアクセスし、適切なレベルのプレイヤーを多数選び、トレーニングのためにパーシムとフィードを行います。



第二に、私たちは「人に」訓練されたこれらの2つのネットワークを利用し、彼らと一緒に遊んでそれらをポンピングし始めます。









そのようなもの。



第三に、ボードの現在の状態を入力として受け取り、それに応じて-1から1の数字を与えるバリューネットワークをトレーニングします。これは、ゲームのある時点でこの位置にある勝ちの確率です。



したがって、どこに行くか（ステップ2から）を示す1つの低速で正確な関数、あまり良くない（ステップ2から）が同じことを行う1つの高速関数、および3番目の関数ボードを見て、この状況で自分自身を見つけたら負けるか勝つかを言います（ステップ3から）。 これで、MCTSで再生し、最初のノードを使用して現在のノードからポップする必要があるノードを確認し、2番目のノードを使用して現在の位置からロールアウトを非常にすばやく刺激し、3番目のノードを使用してノードがどの程度良好かを直接評価します突っ込んだ。 最終的な値については、2番目と3番目のネットワークによって返される値は単純に加算されます。 その結果、分岐係数を大幅に削減し、ノードを評価するためにツリーを登ることはできません（そして、登った場合、迅速かつ迅速に）。

そして、それはニューラルネットワークなしのオプションよりもはるかに直接機能しますか？

はい、突然これで十分です。



2015年10月、AlphaGoはヨーロッパで3回優勝したFan Huiと対戦し、スコア5：0で彼を破りました。 イベントは、一方では大きなものです。なぜなら、コンピューターが初めて対等な立場でプロに勝ったからです。他方では、そうではありません。 （9つの可能性のうち）。 この試合でプレーしたAlphaGoのバージョンは、内部名AlphaGo Fanを受け取りました。



しかし、2016年3月、AlphaGoの新しいバージョンは、世界で最も優れたプレーヤーの1人であるリー・セドルと5ゲームをプレイし、スコア4：1で勝利します。 面白いのは、メディアでの試合の直後、リー・セドルはAIを失った最初のトッププレイヤーとして扱われ始めましたが、時間はその場所にすべてを置き、今日セドルはコンピューターを打ち負かす最後の人のままです（そしておそらく永遠に残るでしょう）。 しかし、私は自分自身に先んじています。 このバージョンのAlphaGoは、後にAlphaGo Leeと指定されました。









よくやった、リー、でもない。



その後、2016年の終わりから2017年の初めに、AlphaGo（AlphaGo Master）の次のバージョンは、世界ランキングの上位のプレイヤーとオンラインで60試合を行い、合計スコア60：0で勝ちます。 5月、AlphaGo MasterはKe Jieの世界ランキングのトップ1でプレーし、3-0でアウトパフォームしました。 実際、すべて、人間とコンピューターの対決は完了しています。









ELOレーティング。 GnuGo、Pachi、およびCrazyStoneは、ニューラルネットワークを使用せずに作成されたボットです。

しかし、彼らは皆を破ったのに、なぜ彼らは別のネットワークを必要としたのですか？

要するに-美しさのために。 コミュニティには、AlphaGoに関する3つの比較的大きな主張がありました。



1）トレーニングを開始するには、人々のゲームが使用されます。 人間の知能がなければ、人工知能は機能しません。

2）多くの設計された機能。 私はこの瞬間を改めて省略しましたが、ビデオとAlphaGo Leeに関する投稿では十分な注意が払われています。使用される両方のネットワークは、人々が発明したかなりの量の機能を受け取ります。 これらの機能は、それ自体では新しい情報を伝達せず、ボード上の石の位置に基づいて計算できますが、ネットワークがそれらなしでは対処できません。 たとえば、状態自体に加えて、次の移動を決定するネットワークは次を受け取ります。

• 1つまたは別の石が何回前にセットされたか。
• この石の周りにいくつのフリーポイントがあるか。
• 特定の地点に行くと、いくつの石を寄付しますか。
• この移動がまったく合法かどうか、つまりgoのルールで許可されているかどうか。
• この時点で置かれた石がいわゆる「階段」の建物に参加するかどうか。

など-合計48層の情報。 勝利の可能性を予測する「高速」ネットワークは、10万以上の準備されたパラメーターの入力に完全に戻ります。 モデルは、ゲーム自体をプレイするのではなく、多数のプロパティを備えた非常によく準備された環境で結果を表示することを学習し、そのことについて再度説明します。



3）すべてを開始するには健全なクラスターが必要です。



そしてほんの1か月前、Deepmindはアルゴリズムの新しいバージョンであるAlphaGo Zeroを導入しました。これらの問題はすべて排除されました。モデルは最初から学習し、それ自体で遊んで、ニューラルネットワークのランダムな重みを開始として使用します。 ボード上の石の位置のみを使用して決定を下します。 ハードウェア要件の点ではるかに簡単です。 楽しいボーナスで、彼女はAlphaGo Leeを100ゲームの対決で倒し、合計スコアは100：0です。

それで、これのために何をしなければなりませんでしたか？

2つの大きなこと。



まず、以前のバージョンのAlphaGoの2つのネットワークを1つに結合します。 少数の機能を備えたボードの状態を受け取り（少し後で説明します）、これらすべてをそのレイヤーで実行し、最後に出力の2つが2つの結果を出します：ポリシー出力は、各動きがどれほど可能性があるかを示す19x19配列を与えますこの位置から、そして値は1つの数字を与えます-再びこの位置からゲームに勝つ確率。



次に、RLアルゴリズム自体を変更します。 以前MCTSがゲーム中にのみ直接使用されていた場合、トレーニング中にすぐに使用されます。 どのように機能しますか？







状態ツリーの各ノードには、 N （このノードに沿って歩いた回数）、 V （このノードの値）、 Q （このノードのすべての子ノードの平均値）、 P （すべてのノードのうちこの移動が許可される確率）の4つの値が格納されますこれを選択します）。 ネットワークがそれ自体で再生する場合、各ターン中に次のシミュレーションを行います。

1. 現在のノードをルートとするツリーを取得します。
2. より多くのQ + Uがある娘ノードに移動します（ Uは新しい方法の検索を刺激する加算器です。トレーニングの開始時であり、将来は減少します）。
3. このような簡単な方法で、ツリーの最後に到達します。つまり、子がいない状態ですが、ゲームはまだ終わっていません。
4. この状態をニューラルネットワークの入力に送信し、それに応じてv （現在のノードの値）およびp （次の移動の確率）を受け取ります。
5. vをノードに書き込みます。
6. pおよびゼロN 、 V 、およびQに従ってPを持つ子ノードを作成します。
7. 次のように、シミュレーション中に選択された電流より上のすべてのノードを更新します。N：= N + 1; V：= V + v; Q：= V / N
8. サイクルを1〜7回1600回繰り返します。

実践では、このようなシミュレーションは基本的なニューラルネットワークよりもはるかに強力な予測を生成することを示しています。



そして、ネットワークが実際に行う移動は、次の2つの方法のいずれかで選択されます。



-これが実際のゲームである場合は、 Nを超える場所に移動します（そのようなメトリックが最も信頼できることが判明しました）。

-トレーニングだけの場合、分布Pi〜N ^（1 / T）から移動を選択します。ここで、 Tは研究と効率のバランスを制御するための温度です。



ポリシーと価値の両方が1つの共通ネットワークによって予測されるという事実により、これらすべてを非常に効率的に実行できます。 ある種のノードになって、このノードをネットワークに送信し、結果Vを取得し、すべてのPが子ノードの初期重みとして記憶され、すべて、ネットワークは何度もこのノードに使用されません行ったが、予測された結果がすでにかなり正確であることを考慮して、ロールアウトを開始しません。 美人

ポリシーと価値の両方を予測するネットワークをトレーニングする方法は？

全体がそのような損失を使用して訓練されています：









それは何ですか、バリモア？



数式は3つの部分で構成されています。



最初の部分では、ネットワークは結果を予測できる必要があります。つまり、 z （パーティの最終的な方法）はv （予測した値）と異なるべきではありません。



2番目の部分では、改善された確率をポリシーのラベルとして使用します。 教師あり学習の報酬のようなものです。ツリーを通過するときに得られる確率をできるだけ正確に予測したいのです。 クロスエントロピー損失に非常に似ています。



3番目の部分である式の最後のcは、単なる正則化機能です。











よりグローバルには、重みAを持つ「最適な」ネットワークがあります。 このネットワークAは、それ自体で25,000回プレイし（新しいノードを評価するために独自の重みを持つMCTSを使用）、各移動ごとに状態自体、Piの分布、およびゲームの終了方法（勝利の場合は+1、敗北の場合は-1）を保存します。 次に、最後の500,000ゲームの2048個のランダムな位置からバッチを準備し、1,000個のバッチをトレーニング用に割り当て、重みBの新しいネットワークを取得します。その後、ネットワークAはネットワークBで 400ゲームをプレイします。新しいノードを評価するとき、 Aは明らかにその重みを使用し、 Bは独自の重みを使用します。 ケースの55％以上でBが勝った場合、 Bが最高のネットワークになり、そうでない場合、チャンピオンは変わりません。 完了するまで繰り返します。

そして、あなたはまだ入り口で提供される機能について話すことを約束しました。

うん、そうだった。 したがって、入力フィールドは19x19であり、各ピクセルには17個のチャネルがあるため、19x19x17になります。 次は17層が必要です。



最初の1つは、あなたの石がこの時点にあるかどうか（1-スタンド、0-なし）、そして次の7つ-前の7つの動きのいずれかに彼がいたかどうかを示します。





次の8つのレイヤーは同じですが、相手の石用です。



最後の17番目のレイヤーには、黒をプレイするとユニットが詰まり、白をプレイするとゼロになります。 これが必要なのは、最終的な得点では、ホワイトが2位になったためにわずかなボーナスを得るためです。



実際のところ、ネットワークはボードの状態のみを実際に見ることができますが、どの色の石がプレイするかに関する情報と8つの動きの履歴があります。

建築はどうですか？

畳み込み層、次に40の残りの層、最後に2つの出力があります-バリューヘッドとポリシーヘッド。 私はこれについて詳しく説明したくはありません。誰にとって重要なのですか-彼は自分でそれを見るでしょうし、残りのすべての具体的な層はほとんど面白くありません。 要約すると、Leeバージョンと比較して、ネットワークが大きくなり、バッチ正規化が追加され、接続が残っています。 革新は非常に標準的で、非常に主流であり、ここには独立したロケット科学はありません。

そして、すべてこれがそうですか？

そして、このすべてがそのような結果につながりました。











3日間、AlphaGo Zeroは21-マスターのためにリーのバージョンを打つことを学び、それから宇宙に入ります。 40日間のトレーニングの後、彼女は100：0のスコアでリーバージョンを、89：11のスコアでマスターバージョンを破りました。 この観点から、MasterとZeroは同じトレーニングアルゴリズム、同じアーキテクチャを持ち、入力に供給される機能にすべての違いがあり、Zeroは人のゲームでトレーニングしないことに注意してください。 そして勝ちます。

つまり、すべて、コンピューターはよりスマートで、人類にはチャンスがありませんか？

外出中-はい、私たちは公式にperにいるようです。 一般的に、いいえ。 Goには、現在の教育方法に不可欠ないくつかの機能があります。

• 理想的でシンプルなシミュレーターが存在する、常に正確に定義された環境。 事故や外部からの介入はありません。
• Goは完全な情報を備えたゲームです。 前の段落と少し似ていますが、それでもなお、発生することはすべてわかっています。

これらのフレームワークによって厳しく制限された環境では、人間をはるかに超える有効性を持つシステムを構築することを学びました。 フレームワークを少し超える必要があり、すべてがより複雑になります。 Andrej Karpathyの投稿で詳細を読むことができます。

そして、次の砦は何ですか？

ゲームで-StarcraftとDotA。 双方向では、アクティブな作業が進行中ですが、これまでのところ、同等の規模の突破口はありません。 待っています。

うわー 少しわかりやすいようです。 トピックで他に何を見ることができますか？

まず、この投稿の冒頭にあるビデオをご覧ください。これはクールで、スキップした多くの質問をカバーしています。

次に、 AlphaGo Leeに関するSemyonの投稿を読んでください。

第三に、closedcircles.comの#dataチャンネルにアクセスしてください。ここですべてを積極的に議論しています。

第4に、AGZについて今言ったことがすべて1つの写真に収められています。

さあ

この投稿は、元の論文の最後の段落で終わります。



人類は、数千年にわたってプレイされた何百万ものゲームから囲Goの知識を蓄積し、それらをまとめてパターン、ことわざ、本に蒸留しました。 Tabula rasaを始めた数日間のスペースで、AlphaGo ZeroはこのGoの知識の多くを再発見することができました。また、最も古いゲームへの新しい洞察を提供する斬新な戦略もありました。



考えてみてください。



この場所にスクロールする忍耐を持っていたすべての人に感謝します。 sim0nsaysのユーザーにコンテンツとコメントに感謝し、校正に協力してくれたburiyに感謝します。