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


2015年 10月 26日

先日、情報処理学会から、「コンピュータ将棋プロジェクトの終了宣言」が出された。将棋プログラムの能力がプロ棋士の能力を超えたと統計的に判断でき、当初の目的を終えたので、プロを超すのを目指すよりも、今までの研究で得られた技術を他へ活かして行くということだ。

さて、ここで紹介しているモンテカルロ木探索は囲碁で使われているアルゴリズムなのだが、囲碁はまだまだプロには及ばない。でも、アマの有段者並にはなっており、これからはプロ棋士に勝つという点では、囲碁に注目が集まってくると思われる。

私も囲碁をやるのだが、最近の囲碁ソフトは強くなって勝てなくなった。ハンデなしで初めはリードしていても、1局ミスなしで打ち切るのは難しい。

さて、前回の続きを行う。

モンテカルロ木探索は、木を再帰的に探索するので、再帰呼出しになっている。これは、一般の木に対する処理を行う場合と基本的には何ら変わらない。
木あるいは部分木に対して、再帰的にモンテカルロ木探索を行うとはどいういうことが考えていこう。

前回最後に示したメソッド playouttree( Node node ) を以下に示す。

// 指定されたノードに対して、モンテカルロ木のプレイアウトを1回再帰的に行う。
void	playouttree( Node node ) {

		// 札の移動
		if( node.childcnt==0 ) {		// 子がいない
			if( node.playcount+1>=EXPANDCOUNT ) {	// 展開
				makeMoveBranch( node );
			} else {
				double sc = simpleplayout();		// 単純プレイアウト
				node.addSuccess(sc);
			}
		} else {
			Node selectednode = null;			// 最良ノード
			
			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 {					// 手札オープンの場合
				int  r = rnd.nextInt(tefudalen);
				int  t = tefuda[r];
				selectednode = node.children[t];
				if( selectednode==null )
					selectednode = makeOpenBranch( node, new Move(t) );
			}
			
			selectednode.move.exec();		// 選んだ枝に対する札の移動を行う
			
			playouttree(selectednode);
		}
	}

このメソッドが、このモンテカルロ木探索の中核であり、これを理解してしまえば、後は枝葉と思って構わない。

木(部分木)は、その根のノードで指定できる。この根ノードを引数とするplayouttreeメソッドを用意した。

最初に行っているのは、子ノードがない場合の処理である。
ノードが持てるプレイアウトの最大数(閾値)が EXPANDCOUNTに入っているので、閾値を超えた場合には makeMoveBranch()により子ノードを作る。詳細は後述。

まだプレイアウトの閾値に達していない場合には、プレイアウトを行い、成功か失敗を1か0で得る。
そして、その結果をノードに反映するのだが、今のnodeだけではなく、親ノードを次々とたどって、親のノードが持っている成功率も書き換える必要がある。
これをnode.addSuccess(sc)で行っているのだが、これも後述し、肝心な部分を先に説明する。

else 以下のブロックは、子ノードが存在し、いずれかの子ノードを選択する場合である。
最終的に選択される最良ノードのための変数を selectednode とし、最初null を入れている。
子ノードは、札移動と手札オープンの2種類のいずれかに別れる。

まず、札移動の場合、子ノードの中から、一番成功率の高いノードを selectednodeとしている。

手札オープンの場合、乱数を使って手札のうちの1枚を選び、札の数を求める。
札の数に対する子ノードが既にあれば、それを selectednodeとし、もしまだその数に対する子ノードが存在しなければ、子ノードを作成し、生成された子ノードをselectednodeとする。

これで、札移動の場合でも、手札オープンの場合でも、子ノードが選択できた。
盤面の札移動または手札オープンを実際に行うのが、selectednode.move.exec()である。

それで、最後に、選んだノードに対して再帰的に playouttree()を呼び出している。

次に、このメソッドを利用して、現在の盤面から、次の一手を選ぶメソッドを示す。このとき、引数にプレイアウト回数を与える。1手プレイする度に、このメソッドを呼び出し、指定した回数だけプレイアウトを行っている。

// 現在の盤面から 指定回数playout し、打つ手を選択する
	Move	playouttree( int playoutcount ) {		
		if( tefudatop == 0 ) {
			if( tefudalen>0 ) {	// 手札をオープンする 
				int  r = rnd.nextInt(tefudalen);
				int  t = tefuda[r];
				Move mv = new Move(t);
				return	mv;
			}
		}
		
		// 次の手がないなら、手札をめくる。
		ArrayList<move> list = getAllMoves();		
		if( list.size()==0 ) {		// 打つ手がない
			return	null;
		} if( list.size()==1 ) {		// 打つ手は1手のみ
			Move mv = list.get(0);
			return	mv;
		}

		Node root = new Node();
		Stock	stock = new Stock();
		while( root.playcount &lt; playoutcount ) {
			playouttree(root);	// 再帰的にモンテカルロ木ツリーを1回プレイアウトする
			stock.restore();
		}

		// 一番プレイアウトされた手を選ぶ
		int		maxcount = -1;
		Node	maxnd = null;
		if( root.childcnt &gt; 0 ) {
			for( Node nd : root.children ) {
				if( nd == null )
					continue;
				if( nd.playcount &gt; maxcount ) {
					maxcount = nd.playcount;
					maxnd = nd;
				}
			}
		}
		
		currentsuccess = root.success;
		
		stock.restore();

		if( maxnd == null )
			return	null;

		return	maxnd.move;
	}

本メソッドは、どう札を動かしたら良いかを求めている。

最初は、手札のトップが表になっていないとき、手札を1枚めくるというMoveを作って、それをreturnする。

次に、getAllMoves()で、次に打つことができる手の全リストを求め、手が無いときはnullを返し、次の手が1つしかない場合にはその1つだけだった手を返し、そうでない、つまり複数の可能性がある場合だけ次の手をどれにするか調べている。

whileのところで、playoutcount だけループしている。ここで、ルートノードに対するプレイアウトを延々と行って、モンテカルロ木がループするに従って成長していく。

次の一手を選択するのに、ルートの直下のノードの中で、一番成功率の高いのを選ぶと思うだろうが、モンテカルロ木選択では、そうはしない。もっとも多い回数プレイアウトされたノードを選ぶ。

ノードが決まれば、そのノードにMoveが付属しているので、それを返す。
Currentsuccessは、ゲーム進行中に成功率がどのように変化するかを表示(print)させるために用意しているだけで、プログラムの動きには関係ない。

以上の2つのplayouttreeにより、ゲームが実行できる。
原始モンテカルロ計算にあったonegame() において、単なるモンテカルロをモンテカルロ木探索に置き換えるだけである。なお、playoutcount は、プログラム起動時に値が決まるものとする。

int	onegame() {
		initialize();
		
		for(;;) {
			opentefuda();
			
			// Move mv = primalMonteCarlo();
			Move mv = playouttree(playoutcount);

			if( mv==null )
				break;
			mv.exec();
		}
		
		return	restcount;
	}

以上で、モンテカルロ木探索の基本部分が終了である。
先を急いだので、説明を略した部分があるので、次回はそのあたりの説明を行う。