TIM Labs

2015年12月アーカイブ

モンテカルロ木探索では、プレイアウトするノードを選ぶ工夫をしていた。
なので、ここでは、プレイアウトするノードを選ぶ工夫を一切止めるとどうなるか試してみよう。

つまり、どの葉ノードも同じプレイアウト回数にするとどうなるだろうか。
ルートノードから指定レベルだけ木を展開し、その末端の全ての葉ノードについて、同じ回数だけプレイアウトしてみよう。
つまり、次図のようなことを試してみよう。

lab-calc15-1.png


そのために、親ノードと、木を展開する高さ(level)を与えると、子ノードの中で一番成功率の高いノードを親のメンバー変数bestにセットするようにした。

もちろん、このメソッドは、再帰的に呼ばれるようになっている。この、再帰的に行えるということは非常に有利な点である。 モンテカルロ木探索では、それまでの成功率が複雑に影響していたのだが、この単細胞モンテカルロ木探索(これは勝手に命名したものである。正式の言い方があるかも知れない)では、つねに一定回数のプレイアウトしかしないので、ノードの成功率や試行回数などを記録しておく必要もなければ、プレイアウトが終わったノードは除去してもかまわない、とてもメモリにやさしい方法である。

では、プログラムの修正部分を示す。

まず、この単細胞モンテカルロ木探索の核となる再帰的に調べるメソッドを示す。

	// 現在の盤面から指定レベル下の葉ノードで、指定回数playoutする
	void	simpletree( Node parent, int level ) {
		Stock	stock = new Stock();

		if( level == 0 ) {	// 指定回数のプレイアウトを行い、成功率を設定し、終了
			double	successsum = 0.0;
			for( int i=0; i<PLAYOUTCOUNT; ++i ) {
				successsum += simpleplayout();
				stock.restore();
			}
			parent.success = successsum / PLAYOUTCOUNT;
			return;
		}

		ArrayList<Move> list = getAllTefudas();
		boolean	istefuda = list.size()>0;
		if( list.size()==0 )
			list = getAllMoves();

		if( list.size()==0 ) {
			parent.success = restcount==0 ? 1.0 : 0.0;
			return;
		}
		parent.moves = list.size()==0 ? null : list;

		double	sumsuccess = 0.0;
		double	maxsuccess = -1;
		Node	bestnode = null;
		for( Move mv : list ) {
			Node nd = new Node( parent, mv );
			mv.exec();
			simpletree( nd, level-1 );
			if( istefuda ) {
				sumsuccess += nd.success;
			} else {
				if( nd.success > maxsuccess ) {
					maxsuccess = nd.success;
					bestnode = nd;
				}
			}
			stock.restore();
		}
		if( istefuda ) {
			parent.success = sumsuccess/list.size();
		} else {
			parent.success = maxsuccess;
			parent.best = bestnode;
		}
	}

そして、1ゲームを行うメソッドonegameから呼び出す。

	int	onegame() {
		initialize();

		int	step = 0;
		currentsuccess = 0.0;

		for(;;) {
			if( tefudatop == 0 )
				opentefuda();

			Node	root = new Node();
			simpletree( root, DEPTH );
			if( root.moves.size() == 0 )
				break;

			Node	nd = root.best;
			currentsuccess = nd.success;
			nd.move.exec();
			++step;
		}

		return	restcount;
	}

モンテカルロ木探索に比べると非常に単純になるのだが、これでも高い成功率が得られるのであろうか?

レベル	幅	成功率
4	20	60/100	0.600
5	20	72/100	0.720
6	20	83/100	0.830
7	20	82/100	0.820
7	50	90/100	0.900
8	2	82/100	0.820
8	20	46/52	0.885
9	3	43/50	0.860
9	5	92/100	0.920

この結果から分かることは、

  • 木の高さを増やす
  • 幅(葉ノードでのプレイアウト回数)を増やす
の2点である。いずれも増加させると、計算時間が掛かるようになる。幅の方は単に正比例する程度であるが、高さを増やすと、計算時間は指数関数的に増加してしまう。
結論として、単細胞モンテカルロ木探索でも、どうやら成功率90%くらいは達成することが分かったが、モンテカルロ木探索に比較して、やや成功率が落ちている。
単細胞モンテカルロ木探索の最大のメリットは、とにかくメモリを食わないことである。性能は、モンテカルロ木探索よりやや劣るが、予想以上の結果が出た。
ということは、このような不完全情報ゲームに対してモンテカルロ木探索を行った場合、不完全な部分がかなり支配的ならば、単細胞モンテカルロ木探索でも良いかも知れない。

さらに

ひとり遊び「計算」には、さらに難易度を上げた遊び方がある。

  • コンピュータ:最初に台札を全然出さない。
  • 超人:台札の山を3つにする。

コンピュータはやや難しくなる程度だが、超人は一気に難しくなる。
ここで紹介したモンテカルロ木探索でも、それらについて、ある程度の成功率を出すことができたが、技術的に特別なことは何もしていないので省略する。


おわりに

とらんぷの一人遊び「計算」について、できるだけ安直に成功率の高い方法を検討しようということで、モンテカルロ木探索を行い、さらに単細胞モンテカルロ木探索なるものまで試した。
面倒でも良いから、もっと高い成功率を得たいと思った人は、あれこれ試してい欲しい。頑張れば99%以上の成功率が得られることは、第2回(9月16日公開)に書いていたので、それを参考にさらに研究を進めることも可能と思われる。
この連載は、コンピュータ囲碁の世界で有名になったモンテカルロ木探索を、別の世界でも効果があるのかどうかを試すことであった。結論は、まずまずの成果だった。めでたし、めでたしということで、連載を終了とする。

まず最初に、プレイアウト回数を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な方法があれば素晴らしいことである。

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

「体系的に学ぶ 安全なWebアプリケーションの作り方」について

体系的に学ぶ 安全なWebアプリケーションの作り方」(通称徳丸本)はWebアプリケーションの脆弱性や攻撃技法とその対策についての定番中の定番と言える書籍です。

「体系的に学ぶ 安全なWebアプリケーションの作り方」表紙

書籍には付録としてVMWareのディスクイメージを収録したCD-ROMが付属し、仮想環境で脆弱性を試すことができます。

また、電子版ではディスクイメージのダウンロードURLが記載されています。

Webアプリケーション開発にMacを使っていて、VMWareではなくVirtualBoxやVagrantを使っている人も多いのではないでしょうか?

ここではOS XでVagrantを使って通称徳丸本の仮想環境を動かす方法を解説します。

このアーカイブについて

このページには、2015年12月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2015年11月です。

次のアーカイブは2016年1月です。

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