TIM Labs

モンテカルロ木探索で一人不完全情報ゲーム「計算」を賢くする[14]

| コメント(0) | トラックバック(0)

まず最初に、プレイアウト回数を100万回にした場合の結果を示す。

	プレイアウト回数=100万、UCB定数=0.5, 閾値=5 で 94/100

プレイアウト回数を増やすと、成功率が着々と上昇し、90%を超えることができた。
といっても、たった100回しかゲームが行われていないので、甚だ精度が心もとない。本当なら1万ゲームくらいやり成功率を求めるべきなのだが、時間がかかるのでやめた。
それでも、100万回やれば成功率は9割を超えると言えるだろう。


さて、今回は、いままでのパラメータとは違う種類のパラメータをでっちあげ、有効性を調べてみよう。
プレイアウトが終わったときの2つの場合を示すので、この差について考えてみよう。

Hand:     _ : 
Table:  K  K  7(T)  K 
[1]  
[2]  
[3]  
[4]  TK

Hand:     _ : 
Table:  6(7)  9(J)  2(5)  7(J) 
[1]  JJAJ65K
[2]  AJ7T8
[3]  4TKK795T8
[4]  2K9Q

現状では、プレイアウトの結果の成功率の値は、1.0(成功) と0.0(失敗)しかない。 この事について考えてみる。

上の2つの場合、屑札として残ったカード枚数は、2枚と25枚である。一方は、成功まであと一歩の状態であるが、もう一方はどうにもならない大失敗である。この差をなんとかしようというのが今回のテーマである。
プレイアウトが終わったとき、屑札の山に1枚でも少ないほうが成功に近いと考えてみよう。

残り枚数1はありえない。理由の説明は省略するの、考えて欲しい。

それで、残り枚数に応じて成功率が変わるグラフを作ってみた。左側は従来のもので、右側が今回考えたものである。

lab-calc13-1.png

残り枚数が2枚、10枚、20枚となった場合、これら3つの状態の成功率をどれも0.0にするのではなく、それぞれ0.2, 0.05, 0.02 とかにできないであろうか。
それで、右グラフのような結果を出すメソッドを用意した。引数として、残り枚数を与えると、それに応じた妥当な成功率を返してくる。

グラフ中の縦軸のbは、残り枚数が2枚の時の成功率で、プログラム中ではBADMAXとなっている。

	// 残り札数から成功率を見積もる
	double	resttoSuccessRate( int r ) {
		if( r <= 1 )
			return	1.0;
		int failnum = (int)(MAXCOUNT*0.5);
		if( r > failnum )
			return	0.0;
		double sc = (1.0-(double)(r-2)/failnum);
		sc = BADMAX * sc * sc;
		return	sc;
	}

計算は相当いい加減にしているが、右図のような傾向があれば良い。もっと頑張りたい人は、自分で工夫して、素晴らしい結果になったら、ぜひ教えて欲しい。

このメソッドを simpleplayoutの最後で呼び出すようにすれば、修正はおしまいである。

	double	simpleplayout() {

		for(;;) {
			opentefuda();		//	手札をめくる

			ArrayList<Move>	list  = getAllMoves();		// 札の移動を考える
			if( list.size() == 0 )
				break;
	
			Move	mv = selectRandomly(list);
			mv.exec();
		}

		//	return	restcount==0 ? 1.0 : 0.0;
		return	resttoSuccessRate(restcount);
	}

では、この残り枚数を考慮した成功率に変更した場合の効果について調べてみよう。

条件:プレイアウト回数=10000, UCB定数=0.5, 閾値=5, ゲーム数=100

BADMAX	成功率/100
	0.00		56
	0.01		57
	0.02		57
	0.03		55
	0.04		55
	0.05		60
	0.06		57
	0.07		58
	0.08		59
	0.09		60
	0.1		53
	0.2		54
	0.5		51

この表を見ると、BADMAXが0.05〜0.09あたりがやや成功率が高くなる傾向がみられる。
といっても、100回程度の試行では誤差の方が大きい。

さて、モンテカルロ木探索はどうだったであろうか。
UCBにより、急に成功率が上昇したのであるが、成功率を非常に高くしようとすると、かなり大変である。
UCBの有無は成功率に著しい差が出るが、その他のパラメータの影響はさほどでもない。
パラメータをごちゃごちゃイジるよりも、プレイアウト回数を増やす方が確実に成功率が上がる。
しかし、このアルゴリズムにも根本的な欠陥がある。それは、序盤がとても下手なことである。中盤以降は極めて正確に最適に近い手、成功する手を選択しているようであるが、序盤は判断するに十分な統計的データが得られないので、良い手を打てないでいる。

これの対策をしようとすると、しっかり機械学習させるとか、屑札の山のカードの連鎖具合をしっかり調べるなどを行わなければいけなくなり、モンテカルロ木探索でお手軽に賢くするという趣旨から外れてしまうので、そのあたりまでは深入りしない。 もし、そのあたりで良い結果が出たら、連絡して欲しい。うまくやれば、99%以上の成功率が出ることがわかっているのだが、なんかスマートな、lazyな方法があれば素晴らしいことである。

さて、これで終わろうかと思ったが、次回は、ここまで説明してきたモンテカルロ木探索とは違う単純な方法で高い成功率を出すことにチャレンジしてみようと思う。
そんな方法は果たしてあるのだろうか?

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/484

コメントする

このブログ記事について

このページは、fujiが2015年12月 7日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「「体系的に学ぶ 安全なWebアプリケーションの作り方」の仮想環境をVagrantで動かす」です。

次のブログ記事は「モンテカルロ木探索で一人不完全情報ゲーム「計算」を賢くする[15]」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。