モンテカルロ法:MonteCarloAIPlayer

MonteCarloAIPlayer は、モンテカルロ・シミュレーションにより最善手を選ぶプレーヤーです。

MonteCarloAIPlayer01

モンテカルロ・シミュレーションとは?

なにやら難しい専門用語のように聞こえますが、超ざっくり言えば、「ランダムに何度も何度もやってみて傾向を探る」という手法の総称です。
(^^; より厳密な定義をお求めのかたは他のサイトを当たってください…)

リバーシにおけるモンテカルロ・シミュレーション適用の考え方は非常に単純であり、誰でも理解できるものです。
以下、具体的に見ていきましょう。

アルゴリズム

今、●(黒) の番であり、a~f の6通りの手を選べるとします。

ここで、仮に A の手を選んだとしましょう。

危険な手ですね。○(白) に左上の角を取られてしまうためあまり良い手ではないように見えますが、この後ゲームがどう進展するかはまだ分かりません。●(黒) の勝ちに繋がれば選択が正しかったことになりますし、そうでなければ他の手を選ぶべきだったということになります。

では、この後の進展をどう予測すればよいでしょうか?
試しに、n+1手目以降の手をランダムに選んで、ゲーム終了まで進めてみましょう。

●(黒)、○(白) 双方の手をランダムに選んでゲーム終了まで進めると、当然ながら、●(黒) の勝ちか ○(白) の勝ちか引き分けかのいずれかに行き着きます。
今回は ○(白) の勝ちになりました。

手をランダムに選んでゲーム終了まで進めることを、ここでは「プレイアウト」と呼ぶことにしましょう。

それでは、プレイアウトを何度も何度も繰り返すとどうなるでしょうか? やがて、勝ち負けの傾向が見えてくるはずです。

a の手を選び、その後のゲームをランダムに進めた場合、どうやら ○(白) の勝つ確率が高いようです。

これを、a~f それぞれについて行ってみます。

b を選んだときが、●(黒) にとって最も良い成績になりました。

このように、プレイアウトの結果に基づきどの手が最も有利かを判断するのがモンテカルロ法(原始モンテカルロ法と呼ばれることもあります)のアルゴリズムです。この場合は b の手が最も有利であると判断し選択します。

解説

モンテカルロ法は、深さ優先探索と幅優先探索の欠点を補ったものと言えます。

深さ優先探索はゲーム終了時点まで手を読み進めるため、勝敗を確実に予測できる一方で、予測に非常に多くの時間を要するため、ゲーム終盤にならないと使い物にならないことが欠点でした。

幅優先探索は数手先の手を満遍なく予測する一方で、ゲーム途中のリバーシ盤の状態の有利不利を見極める必要があり、その評価関数の精度を上げることが難しいという弱点がありました。

モンテカルロ法は、数手先(ここで紹介した例では1手先)の全ての手を予測するとともに、プレイアウトによる手の評価はゲーム終了時点の勝ち負けの成績に基づくものです。
大した処理量を必要としないため、ゲームの序盤から利用することができます。

見方を変えると、モンテカルロ法は「プレイアウトによる勝敗率」を評価関数として採用した幅優先探索であるとも言えます。

かなり荒っぽい大雑把なアルゴリズムに感じるかもしれませんが、本サイトで紹介している5種類のAIプレーヤーの中では最も良い成績を上げる、強いプレーヤーに仕上がっています。

更なる改善に向けて

原始モンテカルロ法にも弱点はあり、それを克服しより強化されたアルゴリズムが考案されています。

次のサイト(PDFファイル)は囲碁を題材としたものですが、原始モンテカルロ法を改善したアルゴリズムが分かり易く解説されています。
興味のある方は、ぜひご自身で実装に挑戦してみてください。

外部サイト:[PDF]モンテカルロ木探索の理論と実践

本ページの内容で分かりにくい点がありましたら、こちらまでご意見お寄せください。

タイトルとURLをコピーしました