【機械学習】モンテカルロ法(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)。
参考ページリンク
関連記事
-
-
【転移学習】学習済みVGG16 による転移学習を行う方法【PyTorch】
今回は、PyTorch を使って、学習済みのモデル VGG16 を用いて転移学習をしてみました。
-
-
【機械学習・手法比較】決定木とナイーブベイズを比較してみた。
同じデータを使って、教師有り機械学習手法の 決定木(Decision Tree)とナイーブベイズ(N
-
-
【Weka】アソシエーション・ルール(association rule)【機械学習】
フリーの機械学習ツール Weka でアソシエーション・ルール(association rule)を使
-
-
【Weka】欠損データを自動的に補完するフィルタを使ってみた。
機械学習で用いるデータについてです。データは完璧なことに越したことはないが、通常は、ある属性の値が入
-
-
【深層学習】 TensorFlow と Keras をインストールする【Python】
今回は、Google Colaboratory 上で、深層学習(DeepLearning)フレームワ
-
-
機械学習の手法のまとめ。
機械学習は、「与えられた入出力事例をモデル化する行為」のことで、ディープラーニングなどで注目を集めて
-
-
【Weka】フリーの機械学習ソフトをインストールする方法。
Weka は、GUIで使えるフリーの機械学習ソフトです。 https://ja.wikiped
-
-
【Weka】CSVファイルを読み込んで決定木を実行。
フリーの機械学習ソフト Weka を使って、CSVファイルを読み込んで決定木(Decision Tr
-
-
【機械学習】決定木(decision tree)について。
教師あり学習の一つである決定木(desicion tree)について勉強したことを書いていきます。
-
-
【PyTorch】ニューラルネットワークを構築する方法【NN】
今回は、PyTorch を使って、ニューラルネットワーク(NN)を構築したときのメモです。 フ