TIM Labs

2015年11月アーカイブ

前回、プレイアウト回数を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万回プレイアウトという条件で実験しておこう。
そして、次回は、一般的でないことにも挑戦してみようと思う。

さて、モンテカルロ木探索が紹介されている情報を探すと、UCTアルゴリズムが紹介されている。 より正確に言うと、UCB(Upper Confidence Bound)によって比較するものである。

詳しくは、いくつかリンク先を紹介しておくので、詳細は自分で調べよう。

computer-igo-matsubara.jpg
  1. 「モンテカルロ木探索 並列化、囲碁、マリオAI 」美添一樹
    ちらっと勉強するだけなら、これで十分かな。
  2. これで書ける「コンピュータ囲碁講習会」 動画(電通大・イベント), 資料ページ
    2015年の夏に電気通信大学で行われた講習会。ビデオ、資料、ソースコード一式揃ってあるので、必見。
  3. 「コンピュータ囲碁 モンテカルロ法の理論と実践」松原仁編
    これが一番まとまっているかな。

さて、成功率だけで評価していたのだが、これはうまく行かなかったのだ。
それで、成功率だけでなく、プレイアウト回数が妥当かどうかも含めた評価値を用意する方法が必要だ。

プレイアウト回数が少ないと、たとえば1回だけだとすると、その1回で失敗していると評価値が非常に悪い。でも、実際にはとても成功率が高いのだが、偶然プレイアウトに失敗しているかも知れない。たった1回の失敗で、そのノードが低く評価され、二度とプレイアウトされないのはとてもまずいことだ。
それで、プレイアウト回数が少ないほど評価値が上がり、プレイアウトする確率が高まるべきである。

で、一気に、UCB値なるものの式を示す。要するに、専門書でちょっと勉強してきた。

lab-calc10-2.png

あるノードに対して、札移動を行ってできる全子ノードを考えるわけだが、プレイアウト数が少ないほど評価値を高めるには、プレイアウト数を分子に入れるのは直ぐ考えつくだろう。
単純に、 総プレイアウト数/プレイアウト数 とすると、総プレイアウト数が増加したときの効果が出過ぎるので、理工学ではとてもよくやる手である対数を利用する。
そして、この割合の平方根をとって、適当な係数を掛けたものを成功率に加えてUCB値としている。

定数が0だと今まで通り、成功率だけの評価になる。
定数を増やしていくと、成功率よりも既存のプレイアウトの分布を意識するようになる。
実際には定数を適当な値、たとえば0.5あたりに設定して実行すると良いらしい。

なお、この数式のもっと詳しい意味については、論文もいろいろ発表されているので、自分で調べよう。

これに基づき、特定のノードに対するUCBを計算するメソッドを用意した。
といっても、数式そのまんまなので、何の説明も不要だろう。

	double	getUCB() {					// UCB1
		return	success + UCBCONSTANT * Math.sqrt(2.0*Math.log(parent.playcount)/playcount);
	}

前回と同じ void playouttree( Node node ) の中を以下のように書き換え、UCB値の最大になるノードを見つけるようにした。

			if( node.childmovetype ) {		
				// UCB式に従って枝を選択し、playoutを進める
				double	maxucb = -1;
				for( Node nd : node.childrenpre ) {
					if( nd==null )
						continue;
					double ucb = nd.getUCB();
					if( maxucb < ucb ) {
						maxucb = ucb;
						selectednode = nd;
					}
				}
			} else {

同様に、 void makeMoveBranch( Node parent ) の中も変更した。
移動に対する子ノードを用意するメソッドだが、最初に全子ノードについて1度ずつプレイアウトしており、それでも不足の場合に、さらにプレイアウトを増やすとき、どのノードについてプレイアウトするかについて、UCB値を使っている。

		for( ; i<+i ) {
			stock.restore();
			if( list.size()>0 ) {		// 子供がいる場合は、子供のどれかでplayout
				Node maxnd = null;
				double	maxucb = -1.0;
				for( Node nd : parent.children ) {
					double ucb = nd.getUCB();
					if( ucb > maxucb ) {
						maxucb = ucb;
						maxnd = nd;
					}
				}
				maxnd.move.exec();
				double sr = simpleplayout();
				maxnd.addSuccess( sr );
			} else {			// 子供がいない場合は、自身でplayout
				double sr = simpleplayout();
				parent.addSuccess( sr );
			}
		}

UCBへの変更は、たったこれだけで済む。

ということで、早速実行してみよう。
条件は、プレイアウト回数=1000, UCB定数=0.5, 閾値(ノードに対する最大プレイアウト数)=5にて実行してみた。
失敗することも多いのだが、次のように成功することもある。

	Game end, rest=0	1/1  1.00000 
Hand:     _ : 
Table:  K  K  K  K 
[1]  
[2]  
[3]  
[4]  

ということで、 プレイアウト回数=1000, UCB定数=0.5, 閾値=5, ゲーム数=100 で実行してみた。つまり、100回プレイしてみた。

	Game end, rest=16	18/100  0.18000 
Hand:     _ : 
Table:  J(Q)  K  8(J)  7(J) 
[1]  TK7Q95JT2K 
[2]  JA 
[3]  K6 
[4]  A4 
----- FINISHED -----

100回で18回成功した。まあ、走らせる度に成功率は違うのだが、だいたい20%前後である。

とりあえず、ほぼ成功率が0.0%が、UCBを計算に使うことで一気に上昇した。
いままで、ほとんど成功しなかったものが、ある程度成功するようになったので、劇的な進歩である。
まだ何もパラメータを調整していないので、次回以降、そのあたりを調整することで、成功率の上昇に挑戦してみよう。

前回、次図のようになった。

     Game end, rest=32       0/1  0.00000 
Hand:     _ : 
Table:  8(9)  6(8)  9(Q)  J(2) 
[1]  Q9TTKKA5J85JKQ829QA7KA254TJT6937 
[2]  
[3]  
[4]  

札が屑札[1]に延々と重なるが、他の屑札 の山にはさっぱり重ならないことが分かった。

なぜ、こうなってしまうのだろうか。


まず、プレイアウトだけれど、まだ始まったばかりの状態では、成功率は0に限りなく近い。まあ、常に0が出ると仮定しても問題ないくらいだ。

手札をいずれかの屑札の上に重ねるとき、屑札[1]〜屑札[4]のいずれかの山への移動を行うわけだが、プログラムでは[1]から順番に調べるようになっている。
そして、[1]〜[4]のなかで、そのノード(札移動とノードは対応する)の今までの成功率を調べ、成功率が一番高いノードを選び、そのノードに対する盤面の状態からプレイアウトして、成功/失敗をシミュレーションするのであった。

さて、成功率だが、プレイアウトすると、ほぼ確実に、99.99%の率で成功率0.0となるのだった。
また、まだ一度もプレイアウトしていないノードの成功率は0.0 としているので、選ぼうとしている現ノードの直下のノードの成功率はどれも0.0 の筈なのだ。

全て同じ0.0 の成功率のノードの中から比較して一番成功率の高いノードを選択しているのだが、これが結局いつも最初のノードを選ぶことになっているのだ。

lab-calc10-1.png

さて、こうなる部分のソースコードを見てみよう。とくに、カードを移動する場合に、どの移動を選択するかの部分に注目してみよう。
void playouttree( Node node )の中の以下の部分が該当する。

			if( node.childmovetype ) {
				double	max = -1;
				for( Node nd : node.children ) {
					if( nd==null )
						continue;
					if( max < nd.success ) {
						max = nd.success;
						selectednode = nd;
					}
				}
			} else {

条件判断が、if( max < nd.success ) となっているので、最も大きい最初のノードが選ばれる。
これを、次のように変えてみた。

			if( node.childmovetype ) {
				double	max = -1;
				for( Node nd : node.children ) {
					if( nd==null )
						continue;
					if( max <= nd.success ) {	//  比較に=を含めた
						max = nd.success;
						selectednode = nd;
					}
				}
			} else {

不等号に=を加えたのだが、同様の比較が成功率を再帰的に書き換える場所にもあるが、全く同様なので説明を省略する。

さて、これで、結果はどうなるだろうか?
最終結果が次:

         Game end, rest=23       0/1  0.00000
Hand:     _ : 
Table:  3(4)  Q(A)  8(J)  K 
[1]  
[2]  
[3]  
[4]  9TKKJ6T9A8K7A744JJ575Q3

今度は、最後の[4]がゴミ札だらけになったので、想定通りである。
一応、最初のあたりも載せておく。

Hand:     K : 9QJT56789TJQKA23456789TJQKA23456789TJQKA2345678

---- game ----  step  1  success= 0.00000
Hand:     T : 9QJT56789TJQKA234567898JQKA23456789TJQKA234567
Table:  A(2)  2(4)  3(6)  4(8) 
[1]  K
[2]  
[3]  
[4]  

---- game ----  step  2  success= 0.00663
Hand:     3 : 9QJT56789TJQKA234567898JQKA23456789TJQKA27456
Table:  A(2)  2(4)  3(6)  4(8) 
[1]  K
[2]  T
[3]  
[4]  

---- game ----  step  3  success= 0.00000
Hand:     8 : 9QJT56789TJQKA234567698JQKA23456789TJQKA2745
Table:  A(2)  2(4)  3(6)  4(8) 
[1]  K
[2]  T
[3]  3
[4]  

---- game ----  step  4  success= 0.00000
Hand:     Q : 9QJT56789TJ5KA234567698JQKA23456789TJQKA274
Table:  A(2)  2(4)  3(6)  8(Q) 
[1]  K
[2]  T
[3]  3
[4]  

最初は色々な山にバラバラに積まれていくようだが、あるところから最後に固まってしまうみたいだ。
これも、たぶん、どの屑札の山を選んでも成功率が0になり、比較に等号が入ったので、最後が選ばれるようになった結果であろう。

さて、両極端な例が確認できたのであるが、成功率を大いに考慮し、成功率が高いノードでさらにプレイアウトするのはもちんなのだが、成功率が低いとか、まだ一度もプレイアウトされていないノードなども考慮したノード選択をすべきであろう。

というところまで分かったが、実際にはどうすれば良いのだろうか?
何かうまい方法は考案されていないのだろうか?

さて、ひと通り完結するまで、あと少しであるので、完成させ、ちょっと走らせて様子を見てみよう。

実際に新しいノードを付け加える処理を以下に示す。

	// 手札をめくってでた札(数)に対する、新しいノードを1つだけ作る。
	Node	makeOpenBranch( Node parent, Move mv ) {
		int 	i = mv.fudanum;
		Node	nd = parent.children[i];
		if( nd==null ) {
			nd = parent.children[i] = new Node( parent, mv );
			++parent.childcnt;
		}
		
		return	nd;
	}

やってきることは、親と子ノードの関係を調整しているだけであるので、細かい説明は省略する。


もう1つ出てくるのが、Nodeクラスのメンバーメソッド addSuccess( double sr ) である。

		void	addSuccess( double sr ) {
			++playcount;
			successsum += sr;
			success = successsum / playcount;
			recountSuccess();
		}

これは、プレイアウトした結果得られた成功率(1.0または0.0)を木に反映させる。

注目しているノードに関しての処理だけでは不十分で、木を上にたどりながら、プレイアウト回数および成功率を木のルートに至るまで書き換えていかなければならない。
そのために、recountSuccess()を用意した。


成功率の書き換えを次で行っている。

		// 成功率を再帰的に書き換える
		void  recountSuccess() {

			for( Node pr=this; pr!=null; pr=pr.parent) {
				if( pr.childcnt == 0 )
					continue;
				pr.playcount = 0;
				for( Node nd : pr.children )
					if( nd != null )
						pr.playcount += nd.playcount;
				
				if( pr.childmovetype ) {		// 成功率最大を選ぶ
					double	max = -1;
					for( int i=0; i<pr.children.length; ++i ) {
						Node	ch = pr.children[i];
						if( ch==null)
							continue;
						if( ch.success > max ) {
							pr.success = max = ch.success;
						}
					}
					pr.success = max;
				} else {		// 手札をめくる場合	// 成功率は平均となる
					double	ave = 0.0;
					for( Node ch : pr.children ) {
						if( ch==null )
							continue;
						ave += ch.success * ch.playcount / pr.playcount;
					}
					pr.success = ave;
				}
			}
		}

最初のforループを周回する度に、木を1段ずつ上がっていく。

最初のところで、プレイアウト総数の計算を行っている。

次に成功率を求めているのだが、札を移動する場合と、手札をめくる場合に場合分けされている。
札移動の場合には、子のノードの中から、一番高い成功率を親ノードの成功率としている。
手札オープンの場合には、どの手を選ぶかの選択権はなく、神の指示に従うしかないので、子ノード全体の成功率の平均を求めて、親ノードの成功率としている。


さて、これで一応必要なものは準備できたので、実行してみよう。

プレイアウト数を1000回、閾値を5で実行してみた。

       Game end, rest=32       0/1  0.00000
Hand:     _ : 
Table:  8(9)  6(8)  9(Q)  J(2) 
[1]  Q9TTKKA5J85JKQ829QA7KA254TJT6937
[2]  
[3]  
[4]  

なぜか[1]の屑札の山だけにたくさんあって、他の屑札の山には何もない。
なぜ?

最初の方も見てみよう。

Hand:     Q : K9JT56789TJQKA23456789TJQKA23456789TJQKA2345678

---- game ----  step  1  success= 0.00000
Hand:     9 : K9JT56789TJQKA23456788TJQKA23456789TJQKA234567
Table:  A(2)  2(4)  3(6)  4(8) 
[1]  Q
[2]  
[3]  
[4]  

---- game ----  step  2  success= 0.00059
Hand:     4 : K9JT56789TJQKA23456788TJQKA23756789TJQKA23456
Table:  A(2)  2(4)  3(6)  4(8) 
[1]  Q9
[2]  
[3]  
[4]  

---- game ----  step  3  success= 0.00059
Hand:     T : K9JT56789TJQKA234567886JQKA23756789TJQKA2345
Table:  A(2)  4(6)  3(6)  4(8) 
[1]  Q9
[2]  
[3]  
[4]  

---- game ----  step  4  success= 0.00053
Hand:     T : K9JT56789TJQKA234567886JQKA237567895JQKA234
Table:  A(2)  4(6)  3(6)  4(8) 
[1]  Q9T
[2]  
[3]  
[4]  

最初から、ずっと屑札[1]にしか札が積まれていない。
最後の台札の状態

Table:  8(9)  6(8)  9(Q)  J(2) 

を見ると、少しは台札に重ねられているが、手札屑札移動は、手札→屑札[1] に限定されているようだ。

なぜ?
これでは絶対に成功しない。
何か間違えたかな。
...ということで、この原因を次回までに考えよう。

今回は、前回後述するといったことを中心に説明していく。


まず、あるノードでプレイアウトしようとしたとき、閾値を超えててしまって、下位ノードを展開する場合を説明する。 このメソッドは、playouttree(Node node)の最初の方で呼ばれる。

	// 移動に対応する枝分かれを作る
	// 指定したノードを親として、子ノードを作り、子全体でparentで指定された以上のプレイアウトを行う。
	void	makeMoveBranch( Node parent ) {
		Stock stock = new Stock();

		int tomakecount = parent.playcount + 1;		// 作るべき子全体のプレイアウト数
		ArrayList list = getAllMoves();
		
		int i;
		parent.childmovetype = true;
		parent.children = new Node[list.size()];
		parent.childcnt = 0;
		for( i=0; i<list.size(); ++i ) {
			Move mv = list.get(i);
			mv.exec();
			Node nd = new Node( parent, mv );		// 子ノードを作る
			parent.children[i] = nd;
			if( mv.typ==MoveType.手札屑札||mv.typ==MoveType.手札台札) {
				makeOpenBranch( nd );
			}
			if( nd.childcnt == 0 ) {
				double sr = simpleplayout();	// プレイアウトし成功率を求める
				nd.addSuccess( sr );
			}
			stock.restore();
		}

		if( list.size()==0 ) {	// 子が作れない場合、親で1回プレイアウトして終わり
			double sr = simpleplayout();		// プレイアウトし成功率を求める
			parent.addSuccess( sr );
		}
		
		parent.childcnt = list.size();

		for( ; i<tomakecount; ++i ) {
			stock.restore();
			if( list.size()>0 ) {		// 子供がいる場合は、子供のどれかでplayout
				Node maxnd = null;
				double	max = -1.0;
				for( Node nd : parent.children ) {
					if( nd.success > max ) {
						max = nd.success;
						maxnd = nd;
					}
				}
				maxnd.move.exec();
				double sr = simpleplayout();
				maxnd.addSuccess( sr );
			} else {			// 子供がいない場合は、自身でplayout
				double sr = simpleplayout();
				parent.addSuccess( sr );
			}
		}
	}

最初の stock は、現在の盤面の保存用であり、プレイアウトした後に元の盤面に戻すためである。

次に、子のノード全体でのプレイアウト総数を、現在のノード(=parent)のプレイアウト数より1だけ多くする。


そして、札移動の全てのMoveオブジェクトを getAllMoves()で取得し、listとする。

forループで、listの全Moveオブジェクトに対してノードを生成する。ノードを作ったら、親ノードにの下に入れる。

もし、Moveが手札を移動するもの(手札台札、手札屑札)の場合には、すぐ次に手札をめくることになるので、そのために makeOpenBranch()を呼び出す。なお、makeOpenBranch()は、呼ばれて手札をめくるノードが1つだけ作られる。
makeOpenBranch()の説明は後述する。


Moveが手札移動だった場合、その下の手札をめくるノードが1つ作られ、プレイアウトも行われるようになっている。 そのため、nd.childcntは1になっているため、次のifは実行されない。

次のifは、Moveの移動が手札移動でなかった場合、つまり、屑札台札移動だった場合に行われる。
この場合、そのノードに対して単純なプレイアウトを行い、成功率を求める。
親、先祖について、成功率を計算し必要なら書き換える。

forループの最後で、最初にセーブしておいた盤面を利用して、元に戻している。これで、ループを回るとき、毎回このメソッドに飛んできた時の盤面状態になっている。

forループが終わったとき、listの各Moveオブジェクトに対して1回ずつプレイアウトしたことになっている。
万一、listが空だったとき、とりあえず親においてプレイアウトしている。

最後に、もう一度forループが出てくるが、これはparent以下でのプレイアウト総数が、まだ所定個数に足りないとき、parentの子ノードのどれかをランダムに選んで、プレイアウトを行う。これを、所定の回数になるまで繰り返す。

なお、このやり方だと、最初のforループだけで、プレイアウト回数が所定の回数を超える場合もありうるのだが、まあ気にしないことにしている。どうせどんどん木が展開されていくので、そのようなものは無視しうる誤差のはず。


手札をめくるのに相当するメソッドが2つ用意されている。

まず、手札移動した直後に、手札をオープンするのに相当する枝づくりをするのだが、その場合を示す。

	// 手札をオープンすることに対応する枝分かれを作る
	// 手札移動のノードを作ったら、直ぐに手札をオープンする下位ノードをすぐに作る。
	void	makeOpenBranch( Node parent ) {
		if( tefudalen==0 )
			return;
		
		parent.childmovetype = false;
		parent.children = new Node[MAXNUM+1];
		parent.childcnt = 0;
		
		int  r = rnd.nextInt(tefudalen);
		int  t = tefuda[r];
		Move mv = new Move(t);
		Node nd = makeOpenBranch( parent, new Move(t) );
		
		mv.exec();
		double sc = simpleplayout();				// プレイアウトを行う
		nd.addSuccess( sc );
	}

まず、既に手札がなかったら何もしない。(手札が無いのだから、何もできない)

手札がある場合には、まず、parentノードの下に、最大13個の手札オープンに関するMoveをぶら下げられるように要素数 MAXNUM+1、つまりサイズ14の配列を用意する。この配列に手札を、オープンしたときの札の数を添字にして配列参照すれば子ノードが分かるような仕掛けにしている。

その後で、実際の手札の数rが決まったところで、それに対するMoveをつくり、ノードを実際に付け加える処理を引数だけ違う同名のメソッドにやらせている。

あとは、mv.exec()で盤面を1手進めて、その後単純プレイアウトを行い、成功率の処理を行っている。


もう1つ説明すべきメソッドがあるのだが、連休なので、ここで休止しよう。

このアーカイブについて

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

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

次のアーカイブは2015年12月です。

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