モンテカルロ木探索
From Wikipedia, the free encyclopedia
モンテカルロ法
他のアプローチでは解決不可能または困難な決定問題を、ランダム性を使用するモンテカルロ法で解決する試みは、1940年代に始まった。ブルース・アブラムソンは、1987年の博士論文で、通常の静的評価関数ではなく、ミニマックス法をランダムなゲームプレイアウトに基づく期待結果モデルと組み合わせた[1]。アブラムソンは、期待結果モデルは「正確・高精度で簡単に推定でき、効率的に計算でき、ドメインに依存しないことが示された」と述べた[1]。アブラムソンは、三目並べ、リバーシ、チェスの機械生成の評価関数を詳細に実験した[1]。
この方法は、1989年に、W・エルテル・シューマンとC・ズットナーによって、定理の自動証明の分野に適用され、幅優先探索、深さ優先探索、反復深化などの探索アルゴリズムにおいて、指数関数的な探索時間を改善することが発見された[2][3][4]。
1992年、B・ブルークマンは、コンピュータ囲碁のプログラムに初めてそれを採用した[5]。チャンら[6]は、マルコフ決定プロセスモデルのアダプティブマルチステージサンプリング（AMS）アルゴリズムで「適応型」サンプリングを選択して、「再帰的ロールアウトとバックトラック」のアイデアを提案した。AMSは、サンプリング/シミュレーション（モンテカルロ）ツリーの構築におけるUCBベースの探査と開発のアイデアを探求した最初の試みであり、UCT（上位信頼性ツリー）のメインシードだった[7]。
モンテカルロ木検索
2006年、これらの研究に触発されて[8]、レミ・クーロンは、ゲームツリー検索へモンテカルロ法を適用させ、「Monte Carlo tree search（モンテカルロ木検索）」と命名した[9]。L・コチシュとCs・セーペスヴァーリはUCT（ツリーに適用される上限信頼限界）アルゴリズム[10]を開発した。S・ゲーリーらは、彼らのプログラムMoGoにUCTを実装した[11]。2008年にMoGoは9路盤の囲碁でアマチュア有段者の域に到達し、Fuegoは9路盤でアマチュアの強豪プレーヤーに勝ち始めた[12]。
2012年1月、モンテカルロ木探索を導入したZenは、19路盤のアマチュア二段のプレーヤーとの番勝負に3対1で勝利した[13] 。また、クーロンが開発に携わっているCrazy Stoneも2014年の第2回電聖戦で依田紀基九段に19路盤の4子局の置き碁（ハンデ戦）で勝利するなど、着実に進歩していった[14]。それでもなおトップ棋士に勝てるようになるには10年以上かかると考えられていたが[15]、2016年1月、Google DeepMind社は開発を進めていたAlphaGoについて公表した。AlphaGoは2015年10月に樊麾二段に19路盤でハンディキャップなしに勝利しており、初めてプロ棋士に互先で勝利したコンピュータ碁プログラムになっていた[16][17][18]。2016年3月、AlphaGoは国際棋戦優勝多数の李世乭九段を相手に5番勝負を行い、4勝1敗で勝利した（詳細はAlphaGo対李世乭を参照）[19]。AlphaGoは、以前の囲碁プログラムを大幅に改善しただけでなく、機械学習は、ポリシー（移動選択）と値に人工ニューラルネットワーク（ディープラーニング手法）を使用したモンテカルロ木検索を使用したため、以前のプログラムをはるかに上回る効率が得られた[20]。
MCTSアルゴリズムは、他のボードゲーム（例えば、ヘックス[21] 、ハバナ[22]、アマゾンズ[23]、アリマア[24]）、リアルタイムビデオゲーム（例えばパックマン[25][26]、Fable Legends[27]）、不完全情報ゲーム（スカート[28]、 ポーカー[29]、マジック:ザ・ギャザリング[30]、カタンの開拓者たち[31]）などに応用された。
AlphaGo登場以降はディープラーニングを利用したプログラムが主流となったが、モンテカルロ木探索を利用したプログラムの開発も一部で行われている[32]。
_-_Updated_2017-11-19.svg)
