プランB - モンテカルロ法

モンテカルロ法
http://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%B3%E3%83%86%E3%82%AB%E3%83%...

『モンテカルロ法 (モンテカルロほう、Monte Carlo method, MC) とはシミュレーションや数値計算を乱数を用いて行なう手法の総称。元々は、中性子が物質中を動き回る様子を探るためにジョン・フォン・ノイマンにより考案された手法。カジノの賭博国家モナコ公国の4つの地区(カルティ)の一つであるモンテ・カルロから名づけられた。ランダム法とも呼ばれる。台湾中国など漢字圏では賭博手法と呼ばれる。』

極言すれば、将棋のAI検索はいかに「組合せ爆発」を抑えるかにかかっています。

組合せ爆発
http://ja.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E3%81%9B%E7%88%86%E7%99%...

『組合せ爆発(くみあわせばくはつ、英: Combinatorial explosion)は、数学において、組合せ的効果によって関数の値が急激に増大することを意味する。』

...その為に様々なテクが使用されます。

⇒ アルファ・ベータ (後ろ向き枝刈り)
⇒ トランスポジションテーブル (評価値を覚えておき再出現の局面は検索しなくてよい)
⇒ Null Move ヒューリスティクス (「一回休み」で検索・評価)
⇒ 前向き向き枝刈り
⇒ 並列検索

...で、無明が今回採用するのが「モンテカルロ法を使用した評価値の補正」となります。

なぜこんなみょうちくりんな物を引っ張ってくるかと言うと、

① (少なくとも今年は)誰も使用していないようですし...ネタ扱いですね

② 学習は要らない

③ プログラム部分は単純明快

④ モンテカルロ法は我が大学生当時(専攻は離散数学)多用していた手法なので

検索の実際はこんな感じになります。

① アルファ・ベータ使用で一定深度まで検索...その時点での評価値を計算。

② そこから◎手ランダムに手を進め、その時点での評価値を計算...これを数万~数十万回繰り返し、その平均を求める。

③ 最終評価値は ① + α x (②-①) とする。

基本の考え方は以下の通りです...

ある程度の深度まで読み評価値を計算したとします。この評価値が安定した信頼できる数値ならば、この局面から数手双方がランダムに駒を動かしても大して評価値は変動しないハズです。もしこの手が評価値以上の悪手・好手なら評価値にブレが出ます。この手法の肝は一定深度まで検索した評価値にさらにその未来の予測を加味して精度を上げよう...といった企みです。

投稿者: 紫外線 投稿日時: 日, 03/14/2010 - 19:01 categories [ ]

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。

正統(?)なモンテカルロ法

...の場合、現在の局面からランダムに駒を動かして(これを何万・何千万回繰り返す)比較的ましな結果に到る手を選びます。

我の手法はMinMax法とモンテカルロ法のハイブリッドとなります...制限時間内(一手20秒程度)ではおのずと読める深さに限りがでます。それを補足するために検索木の端でランダム(おおざっぱ)に検索することにより「この先は良さそう・悪そう」といった観測を評価値に加味する...と言う事ですね。

モンテカルロ法

...は基本的にランダム(乱数)を利用して数値計算を行うテクです。

(有名な例)

Q.琵琶湖の面積の近似値を「湖そのものを測らずに」求めよ。

http://maps.google.com/maps?q=%E7%90%B5%E7%90%B6%E6%B9%96

A.

① 琵琶湖の地図をプリントする。

② 琵琶湖を適当な長方形で囲み、縮尺から長方形の面積を求める。(湖そのものを測っていないのでOK)

③ ②で囲った長方形内にランダムに「点」を打ちます。この数は多ければ多いほど良い。

④ 琵琶湖の面積は (長方形の面積) x (湖内の点の数) ÷ (点の総数) により近似される。

湖内に点が打たれる確率は湖の面積に比例するので点の打つ数を増やすほどに

((湖内の点の数) ÷ (点の総数)) と ((湖の面積) ÷ (長方形の面積)) は近似します。

よって、

  (長方形の面積) x ((湖内の点の数) ÷ (点の総数))
≒  (長方形の面積) x ((湖の面積) ÷ (長方形の面積))
≒  (湖の面積)

...となります。

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。