【機械学習】モンテカルロ法(Monte Carlo method)について。
モンテカルロ法(Monte Carlo method)とは、シュミレーションや数値計算を乱数を用いて行う手法のことです。
中性子が物質中を動き回る様子を探るために、ジョン・フォン・ノイマンという人により考案されました。
また、モンテカルロ法という名前は、カジノの都市国家であるモナコ公国の4つの地区の一つであるモンテ・カルロから名づけられました。
Contents
ゲーム用モンテカルロ法のアルゴリズム
モンテカルロ法は、ほんとうにシンプルなアルゴリズムで実装することができます。原始的なゲーム用モンテカルロ法は、以下の手順になります。
- ある初手aについて、以降の手を全ての合法手からランダムに選び終局まで進める(シュミレーションやプレイアウトと呼ぶ)。
- 終局時の勝ち・負けをカウントする。これを\(N_a\)回繰り返し、勝ち数\(W_a\)をカウントする。
- 1、2を全ての初手について行い、勝率\(\frac{W_a}{N_a}\)が最大の手を実際に打つ。
「ランダムに手を選んでシュミレーションしていき、勝率の良かった手を選ぶ」ということです。
モンテカルロ法とコンピュータ囲碁
2000年代後半に、コンピュータ囲碁においてモンテカルロ法を適応し、活躍しました(5年間でアマチュア初段レベルから六段レベルにまでなった)。コンピュータ囲碁においてモンテカルロ法が活躍した原因としては、
- ランダムに手を選ぶため、評価関数が必要ない(囲碁では評価関数を作成するのが難しい)。
- 一見、人間の考え方とは全く異なるが、自然な手を打たれることが多い。
が挙げられます。
ただし、以下のような欠点もあります。
- 十分な回数のシュミレーションが必要であるため、リアルタイムゲームや終わるまで長いゲームが苦手。
- シュミレーションを無限回やっても最適性はなく、当然の一手がある局面でもランダムに手を選択し、間違った勝率推定を行う可能性がある。
モンテカルロ法の改良
単純にランダムにシュミレーションするのではなく、以下のような自然な拡張をしてモンテカルロ法の改良が行われています。
指し手を純粋なランダムではなく、ありそうな手を選びやすくする(行動評価関数を使う)。
収束しにくいゲームでは、適当な深さまでランダムに進めて、評価関数を呼び判定する(深さ限定モンテカルロ法)。
もう調べる価値がなさそうな手を調べない(全ての手を同じだけプレイアウトするのではなく、良さそうな手に偏って資源配分する)。
一見良さそうな手を重点的に調べる(progressive widening)。
MINMAX探索との融合により、希望的観測に基づく手を防ぐ。相手の少ない良い手をちゃんと発見して尊重する(モンテカルロ木探索:Monte Carlo Tree Search)。
参考ページリンク
関連記事
-
-
【Chainer】手書き数字認識をしてみた【Deep Learning】
Chainerを用いて、ニューラルネットワークを構築し、手書き数字認識を行ったときのメモです。
-
-
機械学習の手法のまとめ。
機械学習は、「与えられた入出力事例をモデル化する行為」のことで、ディープラーニングなどで注目を集めて
-
-
【PyTorch】GPUのメモリ不足でエラーになったときの対処方法。
PyTorch で深層学習していて、 GPUのメモリ不足でエラーが出てしまったので、対処方法のメモで
-
-
【Fashion-MNIST】ファッションアイテムのデータセットを使ってみた【TensorFlow】
今回は、機械学習用に公開されているデータセットの1つである「Fashion-MNIST」について紹介
-
-
【Weka】フリーの機械学習ソフトをインストールする方法。
Weka は、GUIで使えるフリーの機械学習ソフトです。 https://ja.wikiped
-
-
【機械学習・手法比較】決定木とナイーブベイズを比較してみた。
同じデータを使って、教師有り機械学習手法の 決定木(Decision Tree)とナイーブベイズ(N
-
-
【探索】縦型・横型・反復深化法の探索手法の比較。
探索とは、チェスや将棋や囲碁などのゲームをコンピュータがプレイするときに、どの手を指すかを決定するの
-
-
【PyTorch】畳込みニューラルネットワークを構築する方法【CNN】
今回は、PyTorch を使って畳込みニューラルネットワーク(CNN)を構築する方法について紹介しま
-
-
【TensorFlow】GPUを認識しない時の対処方法【Python】
TensorFlow で GPU を認識させようとしたときにハマってしまったので、その対処方法のメモ
-
-
【探索】ダイクストラ法・最良優先探索・Aアルゴリズムの比較。
縦型探索や横型探索では、機械的に順序を付け、最小ステップでゴールを目指します。 つまり、