不完全情報ゲーム例として大貧民のアルゴリズムについて調べた

今回は不完全情報ゲームについて調べる。不完全情報ゲームは各プレイヤーが相手の手札などの知らない情報が存在するゲームのことで、MTGは当然これに含まれる。不完全情報ゲームの基本的なAIの動作に関しては情報処理学会誌に以下のような記述がある。

　ゲームの状態がわからないとモンテカルロ木探索などの探索的手法は適用できない。そこで可能なじょうたいからランダムに状態をサンプリングし、完全情報ゲームと同様にモンテカルロ木探索を実行することが行われている。これをモンテカルロサンプリングという。[情報処理学会誌より]

モンテカルロ木探索

　まず、見えないハンドをランダムに割り当てる。これに対して、何度もランダムにゲームが終わるまでプレイしてみて各プレイの勝率を調べる。また別のハンドを割り当てて同じことを行う。これを繰り返して勝率の高いプレイを選択するというのがモンテカルロ木探索である。囲碁で初めに使用された手法であるが、ランダムにプレイしてみるタイプは無駄な探索が多くとても弱いらしい。囲碁なんて適当に打ったら端っことかにも石を置くだろうし当然といえば当然であるが。そこで、もっともらしい手の比率を上げてランダムにプレイするという手法がとられている。結局このもっともらしさとは何かを調べるのが大変なのであろう。

参考：http://homepage1.nifty.com/ta_ito/fit2008/muramatsu-fit.pdf

　さらに、情報処理学会誌に書かれている内容に、ε-Greedy法というものあるが、これは初手はランダムでプレイして手が進むにつれてもっともらしい手を中心に打つようになるというものである。この手法は尤もらしさの評価により強く依存するようになっている。