週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

前回モンテカルロ法の論文の紹介をしましたが....どうも読みにくいですね。数式を分析するよりも実用を紹介したほうがわかりやすいのでしょうか。実用例の論文をあまり探していませんが。特定の例にはあまり興味がないです。

閑話休題。

Kearnsらの示したモンテカルロ法は、計算時間がゲームの状態数に依存しません。 しかし、計算時間そのものがまだかなり大きく、単純に実装しただけでは現実的な計算量にならない(らしい)です。

適用するゲームを限定すれば、いろいろと改善策は作れます。山下さんのページにもありますが、明らかにだめな手をランダム候補からはずすだけで性能はよくなります。

そして本題です。id:ajitakへの解説の意味をこめて。

Kocsisらはもっと汎用的に、モンテカルロサンプリングの性能を向上させる手法を提案しました。 それは、モンテカルロ法で「ランダムに手段を選ぶ」際に、一様なランダムではなく、特に調べる必要のある有利な手段だけを優先的に調べるよう、確率を偏らせることでした。

Kocsisらの手法におけるモンテカルロ法は、Kearnsらの論文のものとはちょっと違います。 探索開始の際の状態から、たとえば10手先までランダムに手段を選んでシミュレーションします。この選んだ手段と、その結果の状態の成績を記録します。 この「10手先までランダムに予測する」を何度も繰り返して、最も成績のよいものを最適手段として最終的に選びます。 たぶん、Kearnsらの提案手法と比較して、性能は大して変わらないのではないかと思います。(後で調べます。)

Kocsisらの改良点はここからです。 「10手先までランダムに予測する」を何度も繰り返すと、たとえば1--3手目などでは、以前のシミュレーションと同じ途中状態になることがよくあります。 このとき、その次にとれる手段のうちいくつかについては、以前のシミュレーションの得点がわかるわけです。この情報を根拠に、以前成績がよかった手段がより多く選ばれるように確率を偏らせます。

ゲーム木の探索で知りたいのは、「各プレーヤーが最適の判断をすると仮定したときに、この局面での最適の手段は何か」です。 そのため、先の局面で最適と思われる手段については、より詳しく調べる、というのが合理的ですね。

さて、ここでひとつ問題があります。 モンテカルロシミュレーションは全探査していないので、計算途中で成績がよくなっていても、それは偶然かもしれません。 ある手段をとったときに成績がよいと評価されても、それは実はその後の局面をシミュレートする際に相手がひどく悪い手段を選択したため偶然成績がよく見えるだけであり、全探査した際にはぜんぜんよい成績でないかもしれません。 このような当てにならない途中の成績を手がかりにして乱数を偏らせるようなKocsisらの手法は、本当に安定なのでしょうか。モンテカルロ法の初期の結果にその後のシミュレーションが引きずられて、時々ひどく失敗したりすることはないのでしょうか。

実はこの辺もちゃんと調べてあります。詳しくは次回。

スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/156-dbd0db92
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。