モンテカルロ法:MonteCarloAIPlayer

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

MonteCarloAIPlayer01

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

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

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

アルゴリズム

今、●(黒) の番であり、A~I の9通りの手を選べるとします。

montecarloaiplayer02

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

montecarloaiplayer03

角を取れました。●(黒) の優勢になった感がありますが、この後ゲームがどう進展するかはまだ分かりません。●(黒) の勝ちに繋がれば選択が正しかったことになり、そうでなければ他の手を選ぶべきだったのかもしれません。

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

montecarloaiplayer04

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

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

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

montecarloaiplayer05a

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

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

montecarloaiplayer06

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

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

解説

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

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

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

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

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

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

更なる改善に向けて

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

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

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

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

スポンサーリンク
reversi_main 336*280
reversi_main 336*280

シェアする

フォローする