【機械学習】モンテカルロ法(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)。
参考ページリンク
関連記事
-
-
【PyTorch】GPUのメモリ不足でエラーになったときの対処方法。
PyTorch で深層学習していて、 GPUのメモリ不足でエラーが出てしまったので、対処方法のメモで
-
-
【機械学習】パーセプトロン(Perceptron)について。
パーセプトロンは、教師あり学習の中でも、入出力モデルベース(eager learning:働き者の学
-
-
【Weka】ARFF 形式から CSV 形式に簡単に変換する方法。
フリーのデータマイニングツールである WEKA では、ARFF 形式と CSV 形式のデータを読み込
-
-
【機械学習】 scikit-learn で不正解データを抽出する方法【Python】
Python の scikit-learn ライブラリを使って機械学習でテストデータを識別(2クラス
-
-
【画像認識】 Google画像検索結果を取得する方法 【google image download】
今回は、深層学習(DeepLearning)で画像認識をするための画像データの収集を、Google画
-
-
【探索】縦型・横型・反復深化法の探索手法の比較。
探索とは、チェスや将棋や囲碁などのゲームをコンピュータがプレイするときに、どの手を指すかを決定するの
-
-
【Weka】欠損データを自動的に補完するフィルタを使ってみた。
機械学習で用いるデータについてです。データは完璧なことに越したことはないが、通常は、ある属性の値が入
-
-
【PyTorch】ニューラルネットワークを構築する方法【NN】
今回は、PyTorch を使って、ニューラルネットワーク(NN)を構築したときのメモです。 フ
-
-
【PyTorch】畳込みニューラルネットワークを構築する方法【CNN】
今回は、PyTorch を使って畳込みニューラルネットワーク(CNN)を構築する方法について紹介しま
-
-
【機械学習】決定木(decision tree)について。
教師あり学習の一つである決定木(desicion tree)について勉強したことを書いていきます。