TIM Labs

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

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

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


まず、あるノードでプレイアウトしようとしたとき、閾値を超えててしまって、下位ノードを展開する場合を説明する。 このメソッドは、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つ説明すべきメソッドがあるのだが、連休なので、ここで休止しよう。

トラックバック(0)

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

コメントする

このブログ記事について

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

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

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

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