アルファ・ドッグの利器:モンテ・カルロアルゴリズム,読み終わったらわかる! (附属コード例) - 转載

アルファ・ドッグの道具:モンテ・カルロのアルゴリズム 読み終わったらわかる!

3月9日-15日に,ゴルフ界で大きな出来事があった. 5ラウンドの人間と機械の戦いがソウルで行われた. この試合の結果,人類は敗れ,世界ゴッホ選手のリー・シシュティンはGoogle社のAIプログラムAlphaGoに1対4で敗れた. では,AlphaGoとは何か? 勝利の鍵はどこにあるのか? ここでは,Monte Carlo Algorithmについて説明します.

• AlphaGoとモンテカーロアルゴリズム

新華社によると,AlphaGoプログラムは,米国Google社下属のDeepMindチームが開発した人間対ロボットゴッホーのプログラムで,中国のチェスファンは"アルファ・クソ"と口説いている.

前回の記事では,Googleが開発している機械学習のニューラルネットワークアルゴリズムについて言及しました. AlphaGoは同様の製品です.

中国自動化協会副会長,事務局長王飞跃は,プログラマはゴーチェーの知識を必要とせず,ゴーチェーの基本的なルールを理解する必要があると述べた.AlphaGoの背後には,優れたコンピュータ科学者のグループがあり,正確に言えば,機械学習の専門家である.科学者は神経ネットワークアルゴリズムを使用して,チェス専門家による試合記録をコンピュータに入力し,コンピュータが自分自身と競争し,その過程で絶えず学習する.ある意味では,AlphaGoのチェスは開発者が教えていないが,才能が自習している.

では,AlphaGoが自己学習して才能を持つための鍵はどこにあるのでしょうか? それはモンテカーロアルゴリズムです.

モンテカーロアルゴリズムは?モンテカーロアルゴリズムの説明は, 1000個のリンゴがバスケットの中にあり,目を閉じて一番大きいものを選ぶたびに,選択の制限はありません.それで,目を閉じてランダムに1つ選び,次に最初に比較して,大きなものを残し,またランダムに1つ選び,前回と比較して,再び大きなものを残すことができます.ループは繰り返されます.

つまり,モンテカーロアルゴリズムは,サンプル数が多くなるほど,最適な解決策を見つけるというものです. しかし,それは必ずしも最適であることを保証するものではありません. 10,000個のリンゴがあれば,おそらくもっと大きいものを見つけるでしょう.

グラビアのメディアは,この2つのアルゴリズムを比較すると, 俗説では,もし1つの鍵が1000個あるとすれば,1個しか正しくない.したがって,ランダムに1つの鍵を試すたびに1個ずつ変更する. 試し回数が多くなるほど,最も優れた機会が広がります. しかし,開くまで,間違った鍵は役に立たない.

だからラスベガスのアルゴリズムは可能な限り最良の解決策ですが,必ずしも見つけられないのです. 1000の鍵のうち,鍵を開ける鍵は1つも見つからないと仮定します.

AlphaGoのモンテカーロアルゴリズムゴルフの難しさは,人工知能にとって特に大きい. ゴルフの転落方法があまりにも多く,コンピュータが識別するのが難しい. 王飞跃:まずは,ゴーチェーの可能性はあまりにも多い.また,ゴーチェーの各ステップの可能性は非常に多く,プレイヤーは開始時に19×19=361種類の落とし子を選択する.また,1回 150ラウンドのゴーチェーの可能性は,10170種類まで.そして,規則は非常に微妙で,落とし子選択は,ある程度は経験によって形成された直感に依存する.また,ゴーチェーの落とし子では,コンピュータが当時の落とし子の強みと弱さを区別することは困難である.したがって,ゴーチェーの挑戦は人工知能のアポロ計画と呼ばれています.

AlphaGoはモンテカーロアルゴリズムだけのものではなく,モンテカーロアルゴリズムのアップグレードである.

AlphaGoはモンテカーロツリー検索アルゴリズムと2つの深層神経ネットワークと協力してチェスを完成させた.リッチストーンとの戦いの前に,Googleはまず,ヒト対の近3000万歩で,人間のプロチェスターがどのように落胆するかを予測することを学ぶために,AlphaGoの神経ネットワークを訓練した.さらに,AlphaGoが自分自身とチェスをプレイして,大規模な新しいチェスを生み出した.Googleのエンジニアは,AlphaGoが毎日百万歩を試みると主張した.

機械の役割は,協働して,より有望なステップを選び,明らかな欠陥を捨て,計算をコンピュータが実行できる範囲で制御することである.これは本質的に人間の棋手と同じである.

中国科学院自動化研究所の研究者イイヤンは,の伝統的なチェスソフトは,一般的に深青コンピュータを含む暴力的な検索を使用し,すべての可能な結果 (それぞれの結果は木の果実) に対して検索樹を構築し,必要に応じて検索を行います.この方法は,チェスやジャンプチェスなどの点で実現可能であるが,ゴーチェスの場合には実現できません.ゴーチェスの横断各19行に落下が非常に多くあり,コンピュータがこの果実を構成できないので,ゴーチェスの各19行に落下が非常に多くなります.AlphaGoは,非常に賢い方法を採用し,この問題を解決しました.その深い学習方法が検索樹の複雑さを低下させ,検索スペースを効果的に低下させました.例えば,戦略的な検索ネットワークは,人間のコンピュータが落下した場所の位置を指示するよりも,コンピュータがネットワークの位置を予測するよりも,次の検索で勝者の位置を決定する可能性があります.

ダンガッチはさらに説明する.深層神経ネットワークの最も基本的なユニットは,私たちの脳のような神経細胞であり,多くの層が人間の脳のような神経ネットワークのように接続されている.AlphaGoの二つの神経ネットワークは,戦略ネットワークと評価ネットワークである.

戦略ネットワークは,主に落としの戦略を生成するために用いられる.チェスの過程で,自分の落としの仕方を考えるのではなく,人間の熟練したプレーヤーの落とし方を考える.つまり,入力したチェスの現在の状態に基づいて,人間の次の落としの仕方を予測し,人間の考えに最も合致するいくつかの実行可能な落とし方を提案する.

しかし,戦略ネットワークは,自分のステップが良いのか悪いのか分からない.それは,このステップが人間のステップと同じかどうかを知っている.

値ネットワークは,各実行可能な条件のために,円盤全体の状況を評価し,勝利率を出す.これらの値は,モンテカーロのツリー検索アルゴリズムにフィードバックされ,上記のプロセスを繰り返して勝利率を推論する最も高い道を推論する.モンテカーロのツリー検索アルゴリズムは,戦術ネットワークが勝利率が高い場合にのみ推論を続けることを決定し,特定のルートを放棄し,ブラックに導かないようにする.

AlphaGoは,この2つのツールを利用し,現在の状況と将来の状況を判断する人間のチェスプレーヤーと同じように,各ステップの優劣を判断する.モンテカーロツリー検索アルゴリズムを使用して,例えば20ステップの未来を分析すると,どのステップで勝つ可能性が高いかを判断できる.

しかし,Mont Carlo アルゴリズムが AlphaGo の核心の一つであることは間違いない.

2つの小さな実験 モンテカーロアルゴリズムの2つの小さな実験を見てみましょう.

• 1.计算圆周率pi。

原則:まず,正方形を描き,その内側を円を描き,次にこの正方形内のランダムな描画点を,円の中に位置する点を約Pに設定すると,P=円面/正方形面である. 変数P= (π)Rこの2つの条件は,

ステップ: 1.円の中心を原点に置き,半径をRで円にする.最初の四角形の1/4円面積はPiである.RR/4 2. この1/4円の外接正方形を,座標が ((0,0) ((0,R) ((R,0) ((R,R) とすると,この正方形の面積は R である.R 任意の点 ((X,Y) を取ると0<=X<=Rで0<=Y<=Rになります. 式 X を使ってX+YYRが1/4円内にあるかどうかを判断する. 5. すべての点 (すなわち実験回数) の個数を N とすると,1/4 円内の点 (ステップ 4 に満たす点) の個数を M とすると,

これは,P=M/N,つまり,Pi=4*N/Mです.画像1

M_C ((10000) を実行すると,結果が3.1424になります.

• 2.蒙特卡洛模拟求函数极值，可避免陷入局部极值

# [-2,2] の範囲でランダムに数を生成し,対応する y を求め,その内の最大が [-2,2] の極大値であると考えられる値を見つけます.画像2

1000回模擬した結果,最大値は185.12292832389875 (非常正確) でした.

面白いですね! (Python言語) プログラミングは,手書きでできます. 微信公众号より転送