TIM Labs

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

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

前回、プレイアウト回数を1000にすることで、そこそこ成功することが確認できた。

それで、まず、プレイアウト回数を変更することで、成功率がどのように変わるか、100ゲームのシミュレーションをしてみた。 UCB定数=0.5, 閾値5, ゲーム数100としている。

UCB定数=0.5, 閾値5, ゲーム数100としている。

プレイアウト回数 成功数/100
	1000		17
	2000		28
	5000		40
	10000		53
	15000		59
	20000		65
	30000		72
	40000		69
	50000		77
	100000		80
	200000		86

それぞれのプレイアウト回数にて、100回ゲームしているだけなので、かなり誤差を含むのだが、傾向ははっきり読み取れる。つまり、プレイアウト回数を増やすと、成功率は上がるようだ。プレイアウト回数が10000以下では着実に成功率が上昇するのだが、20000を超えるあたりからプレイアウト回数の上昇が成功率の上昇にすこししか効かなくなってくる。そして、プレイアウト回数が3万回を超えたあたりから、効果はとても僅かなものになっている。

プレイアウト回数を10万回以上にすると、成功率が80%を超えるようだ。この調子だと、100万回プレイアウトすると、成功率90%の可能性もありそうだ。でも、やめておく。プレイアウト回数の上昇は有効なことが分かったが、限界もあるようだ。とりあえず、プレイアウト回数を増やしてテストするのはこのあたりで止めておく。なにしろ、プレイアウト回数を増やすと計算時間がかかってやってられないのである。


前回、モンテカルロ木探索のキモであるUCBの計算式を示した。

lab-calc10-2.png

この中に定数があるのだが、いままではとりあえず0.5で試してきた。このUCB定数を変更すると「計算」の成功率がどのように変わるかをじっくり調べてみよう。時間節約のため、プレイアウト回数を10000回で行った。

	UCB定数		成功数/100
	0.0		0
	0.0000001	30
	0.000001	21
	0.00001		18
	0.0001		25
	0.001		31
	0.005		32
	0.01		39
	0.05		45
	0.1		54
	0.2		53
	0.5		52
	1.0		53
	10.0		51 

USB定数は、0.1を超えると、ほとんど変化しないようだ。
0.1を切るとどんどん成功率は下がるのだが、0.0001くらいまで下がると、20〜30%程度の成功率に落ち着いて、0.0にすると成功率も一気に0に落ちる。
これから、USB定数は0.1以上だと何でもよさそうに思える。それで、今後は0.5とすることにしよう。 USB定数の値は木の形や成功率(勝率)など、対象が変われば変わると思われるが、追求はこのあたりでお終いにしておこう。


もう1つのパラメータとして、閾値がある。つまり、葉ノード(末端ノード)に対して、最大何回のプレイアウトを行うかによっても成功率が変わるはずだ。

閾値 成功数/100 1 49 2 50 3 51 4 61 5 56 6 63 7 60 8 54 9 55 10 55 20 55

総試行数(ゲーム数)が100回と少ないのであるが、この表から閾値は4〜7あたりが良い感じである。
これは、プレイアウト回数が10000回で行っのだが、プレイアウト回数が増えると、それに伴って最適な閾値も徐々に増加してくるのではと思うが、あまり急激な変化はないようだ。
さて、閾値1というのは、葉のノード1つについてプレイアウト回数が1回ということである。つまり、10000回プレイアウトしているので、葉ノードが10000個になっているはずである。これは、木が実をたわわにつけるのではく、枝をどんどん伸ばし、先端の葉にたった1つの実をつけた状態である。そんな状態でも、成功率はたいして落ちないのは興味深い。


今回は、モンテカルロ木探索で調整される一般的なパラメータをいろいろいじって効果を見てみた。
それでわかったことは、とにかくプレイアウト回数を増やすのが良いということだ。
つまり、微妙な調整を頑張るよりも、マシンパワーに頼る方が良い結果が出るというよくある面白くない結果になってしまった。
ということで、次回までに、100万回プレイアウトという条件で実験しておこう。
そして、次回は、一般的でないことにも挑戦してみようと思う。

トラックバック(0)

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

コメントする

このブログ記事について

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

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

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

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