モンテカルロ法による探索

この記事はデータ構造とアルゴリズム Advent Calendar 2019 22日目の記事です。

はじめに

エージェントが目的を達成するために、どのような行動を取ればよいか、状態空間を探索して「望ましい行動」を取れるような方策を獲得する問題で、近年、モンテカルロ法に基づく手法が活用されています。

この「方策」を獲得する観点から、モンテカルロ法による探索について記述します。

プレイアウト

前提として、シミュレーション環境または実験環境により、任意の状態を観測できるとします。初期の状態から、何か一つ行動を選び、その行動で得られた状態から、また次の行動を選ぶ問題を考えます。

このとき、囲碁や将棋などのゲームを含む複雑な問題では、行動によって起こり得る状態が広がりすぎて、探索が難しくなります。かりに強化学習で解くための「報酬」を定義しようとしても、ゲームの途中段階で適切な報酬を定義することは容易ではありません。

探索するための手法として、モンテカルロ法による「プレイアウト」があります。プレイアウトは、乱数を用いて最終状態まで進めるものです。自分や相手の行動を、擬似乱数で一様ランダムに選んで、勝ち負けなどの最終状態になるまで継続します。

もちろん、一回のプレイアウトで得られる結果は「でたらめ」ですが、何回も繰り返すことにより統計的な分布が得られます。プレイアウトで得られる分布を、次の行動を選ぶための方策に使うだけでも、簡単なゲームでは「それなりに」賢く行動します。

囲碁におけるプレイアウトは、現在は理研AIPの美添先生によるコンピュータ囲碁におけるモンテカルロ法～理論編～の「原始モンテカルロ囲碁」に説明があります。

なお、コンピュータ囲碁―モンテカルロ法の理論と実践―でも解説されていますが、原始モンテカルロ囲碁では「相手のミスを期待した手を選択することがある」ため、現在では性能向上のための対策を講じた「モンテカルロ木探索」が使用されています。

AlphaGoのrollout

前項では、簡単のためプレイアウトは一様ランダムとして説明しましたが、一様ランダム以外のランダムな方法も考えられ、ZeroではないAlphaGoの論文では「rollout」と呼称して使われています。

AlphaGoのしくみにも説明されていますが、800万の盤面で機械学習を行って得られた方策を確率分布として、擬似乱数で確率的に行動を選んで最終状態まで進めるのがrolloutです。例えば、3種類の行動を選べる状況で、方策が(0.7, 0.2, 0.1)のとき、rolloutでは70%、20%、10%の確率でランダムに行動を選びます。

このrolloutは、AlphaGo Zero以降では採用されていませんが、機械学習や深層学習で得られた方策を使ってランダムに行動を選ぶことは、問題を解くアプローチの一つとして有効ではないかと考えます。

なお、AlphaGoのrolloutで使用していた方策は、CNNを使った深層学習ではなく、盤面から計算できる約11万個の特徴量を入力とした線形回帰です。深層学習ではなく線形回帰とした理由は、rolloutを繰り返し高速に実行できるだけの速度が要求されていたからと思われます。

おわりに

AI-SCHOLARのMuZeroの衝撃。囲碁のルールを自ら学習しAlphaZeroを凌駕。では、Google DeepMind発表の最新手法「MuZero」が、わかりやすく解説されています。

MuZeroは、ルールを与えなくても方策を学習できることが特色ですが、知能を作りたい立場から少し離れた「特定の問題を解きたい」立場なら、ルールを与えてもかまわないのではないかと考えています。

今後、モンテカルロ木探索などのモンテカルロ法を活用したアプローチで、リーズナブルな計算資源でも現実の問題を解くことができる手法の発展を期待したく思います。