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

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

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

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

Contents

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

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

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

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

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

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

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

が挙げられます。

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

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

モンテカルロ法の改良

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

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

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

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

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

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

参考ページリンク

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

関連記事

【機械学習】パーセプトロン(Perceptron)について。

パーセプトロンは、教師あり学習の中でも、入出力モデルベース(eager learning:働き者の学

記事を読む

【Weka】CSVファイルを読み込んで決定木を実行。

フリーの機械学習ソフト Weka を使って、CSVファイルを読み込んで決定木(Decision Tr

記事を読む

【転移学習】学習済みVGG16 による転移学習を行う方法【PyTorch】

今回は、PyTorch を使って、学習済みのモデル VGG16 を用いて転移学習をしてみました。

記事を読む

【機械学習】決定木(decision tree)について。

教師あり学習の一つである決定木(desicion tree)について勉強したことを書いていきます。

記事を読む

【深層学習】 TensorFlow と Keras をインストールする【Python】

今回は、Google Colaboratory 上で、深層学習(DeepLearning)フレームワ

記事を読む

【Weka】ARFF 形式から CSV 形式に簡単に変換する方法。

フリーのデータマイニングツールである WEKA では、ARFF 形式と CSV 形式のデータを読み込

記事を読む

【TensorFlow】GPUを認識しない時の対処方法【Python】

TensorFlow で GPU を認識させようとしたときにハマってしまったので、その対処方法のメモ

記事を読む

【Weka】アソシエーション・ルール(association rule)【機械学習】

フリーの機械学習ツール Weka でアソシエーション・ルール(association rule)を使

記事を読む

【Weka】欠損データを自動的に補完するフィルタを使ってみた。

機械学習で用いるデータについてです。データは完璧なことに越したことはないが、通常は、ある属性の値が入

記事を読む

機械学習の手法のまとめ。

機械学習は、「与えられた入出力事例をモデル化する行為」のことで、ディープラーニングなどで注目を集めて

記事を読む

Message

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

【Cubase】イヤホンから音がでないときの対処方法。

Cubase でイヤホンから音がでなくなったときの対処方法のメモです。

【Cubase】特定のトラックを無効にする方法。

今回は、Cubaseで特定のトラックのみを無効にする方法について紹介し

【転移学習】学習済みVGG16 による転移学習を行う方法【PyTorch】

今回は、PyTorch を使って、学習済みのモデル VGG16 を用い

【PyTorch】畳込みニューラルネットワークを構築する方法【CNN】

今回は、PyTorch を使って畳込みニューラルネットワーク(CNN)

【PyTorch】ニューラルネットワークを構築する方法【NN】

今回は、PyTorch を使って、ニューラルネットワーク(NN)を構築

→もっと見る

PAGE TOP ↑