【機械学習】モンテカルロ法（Monte Carlo method）について。

モンテカルロ法（Monte Carlo method）とは、シュミレーションや数値計算を乱数を用いて行う手法のことです。

中性子が物質中を動き回る様子を探るために、ジョン・フォン・ノイマンという人により考案されました。

また、モンテカルロ法という名前は、カジノの都市国家であるモナコ公国の４つの地区の一つであるモンテ・カルロから名づけられました。

ゲーム用モンテカルロ法のアルゴリズム

モンテカルロ法は、ほんとうにシンプルなアルゴリズムで実装することができます。原始的なゲーム用モンテカルロ法は、以下の手順になります。

1. ある初手aについて、以降の手を全ての合法手からランダムに選び終局まで進める（シュミレーションやプレイアウトと呼ぶ）。
2. 終局時の勝ち・負けをカウントする。これを\(N_a\)回繰り返し、勝ち数\(W_a\)をカウントする。
3. １、２を全ての初手について行い、勝率\(\frac{W_a}{N_a}\)が最大の手を実際に打つ。

「ランダムに手を選んでシュミレーションしていき、勝率の良かった手を選ぶ」ということです。

モンテカルロ法とコンピュータ囲碁

２０００年代後半に、コンピュータ囲碁においてモンテカルロ法を適応し、活躍しました（５年間でアマチュア初段レベルから六段レベルにまでなった）。コンピュータ囲碁においてモンテカルロ法が活躍した原因としては、

• ランダムに手を選ぶため、評価関数が必要ない（囲碁では評価関数を作成するのが難しい）。
• 一見、人間の考え方とは全く異なるが、自然な手を打たれることが多い。

が挙げられます。

ただし、以下のような欠点もあります。

• 十分な回数のシュミレーションが必要であるため、リアルタイムゲームや終わるまで長いゲームが苦手。
• シュミレーションを無限回やっても最適性はなく、当然の一手がある局面でもランダムに手を選択し、間違った勝率推定を行う可能性がある。

モンテカルロ法の改良

単純にランダムにシュミレーションするのではなく、以下のような自然な拡張をしてモンテカルロ法の改良が行われています。

指し手を純粋なランダムではなく、ありそうな手を選びやすくする（行動評価関数を使う）。

収束しにくいゲームでは、適当な深さまでランダムに進めて、評価関数を呼び判定する（深さ限定モンテカルロ法）。

もう調べる価値がなさそうな手を調べない（全ての手を同じだけプレイアウトするのではなく、良さそうな手に偏って資源配分する）。

一見良さそうな手を重点的に調べる（progressive widening）。

MINMAX探索との融合により、希望的観測に基づく手を防ぐ。相手の少ない良い手をちゃんと発見して尊重する（モンテカルロ木探索：Monte Carlo Tree Search）。

参考ページリンク

http://www.yss-aya.com/monte.html