TIM Labs

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

| コメント(0) | トラックバック(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] に限定されているようだ。

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

トラックバック(0)

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

コメントする

このブログ記事について

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

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

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

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