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

Michael Kearns, Yishay Monsour, Andrew Y. Ng, `A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes', Machine Learning,49,193--208,(2002) [pdf]

まず、モンテカルロ法を利用したゲームのAIについての論文を紹介します。 私はこのあたりも詳しくないので、目的の論文を理解するまでに関連研究を複数読まなければいけませんでした。さらに、その前にark君にちょっと話を聞いて、以下二つの山下さんのページを教えてもらいました。

ゲームのAIではたとえば、ありうる状態を現在状態からすべて探索して、相手がどんなに頭がよくてもあまり負けない手を選びます。ここの「すべて探索」ができてしまえば、コンピュータの完全勝利です。先手必勝か後手必勝かもわかってしまいます。

しかしたいていのゲームは状態数が多いです。状態数が少ないのは○×三目並べみたいな簡単なゲームだけです。すべて探索をしていると日が暮れるどころか鬼が笑います。そのため、コンピュータは10手先とか20手先とかまで読んで、読んだ盤面についてどちらがどの程度有利かを適当に判定して済ませます。

モンテカルロ法は、そもそもすべて探索するのをあきらめます。 ゲームの状態数が非常/無限に大きい場合は、 計算量が状態数に依存するアルゴリズムは不利です。 Kearnsらは、適切な量のサンプリングと適切な深さの探索を行えば、 最適戦略に十分近い戦略を選ぶことができること、そして、 その計算量が状態数に依存しないことを示しました。

彼らの提案は、ゲーム木の幅と深さを両方制限しています。 幅の制限とは、たとえば取れる手段が毎回108式まであるときに、そのうち一定の個数をランダムに選んでます。 この上で先読みの深さも制限していて、結果的にゲーム木の部分木の上で探索をすることになります。

モンテカルロ法では全探査はしないので、この結果提案される手法が間違っている、すなわち全探査でわかる最適手法から外れることもあります。提案される手法によって得られる得点の期待値(提案される手法自体が確率的に変動するので、それを平均化した期待値)を、全探査による最適手法で得られる得点と比較して、差εが一定値より小さくなればよい、とします。Kearnsらはその状態になるまでの計算量を測っています。

計算量が状態数に依存しないなら何に依存するのかというと、εのほかに評価値の最大値、そして深読みの深さに関係するγです。εは当然入るはずで、これと同じ次元を持つ評価値に関係する値も入るのは納得できます。

ただγ、これは個人的に疑問が残ります。

γは次の式に現れます。sがゲームの状態、dが探索の深さ、aが状態sのとき取れる行動、Rsaがsの状態でaの行動をとったときの報酬をあらわし、V(s,d)が、状態sのときに探索の深さdだったときの、合計報酬の見積もりとすると、

V(s,d) = Maxa Rsa + γV(s',d+1)
みたいになります。s'はsの状態からaの行動をとったときの先の状態です。書いていてわかりにくい気がしますが。あと、この式ではdは意味ないように見えますが、dが一定の大きさになるとγVの項自体が消えます。あるいは全部消えてゼロになります。

このようにγ深読みしたときの評価値の重みになっているので、深読みの長さに直接かかわります。そのため、γに依存するというのは間接的にゲームの深さに依存するのではないかなと疑問に思います。

このγが入ってくる理由は、全探査法が一定の深さで打ち切ったりγのような項を入れていて、モンテカルロ法が全探査と性能を比較しているから、条件を同じにするために入れたとかでしょうか。よくわかりません。もっと簡単な話かもしれません。

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